[kragen at canonical.org: Re: radix-sorting rational numbers with an efficient serialization of continued fractions]

[Kragen Javier Sitaker]

----- Forwarded message from Kragen Javier Sitaker <kragen at canonical.org> -----

Date: Tue, 18 Oct 2011 03:04:13 -0400
From: Kragen Javier Sitaker <kragen at canonical.org>
To: Darius Bacon <darius at wry.me>
Subject: Re: radix-sorting rational numbers with an efficient serialization
	of continued fractions
Message-ID: <20111018070413.GA12206 at canonical.org>
References: <20111017225537.GA1783 at canonical.org>
	<201110180002.p9I02Y5H003270 at wry.me>
	<20111018062120.GA9104 at canonical.org>
	<201110180658.p9I6wYgG005839 at wry.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Disposition: inline
In-Reply-To: <201110180658.p9I6wYgG005839 at wry.me>
User-Agent: Mutt/1.5.20 (2009-06-14)
Status: RO
Content-Length: 920
Lines: 21

On Mon, Oct 17, 2011 at 11:58:34PM -0700, Darius Bacon wrote:
> > I think the search engine I wrote in 2006
> > <http://lists.canonical.org/pipermail/kragen-hacks/2006-August/000432.html>
> > might benefit from using Golomb coding or something similar for its
> > pseudo-posting-lists.  It currently uses the "Altavista trick" to encode
> > integers in variable numbers of bytes, 7 bits per byte, with one bit per byte
> > used as a termination marker, but I suspect that it can probably use
> > substantially less space with Golomb coding.
> 
> Altavista trick? Does it really go back no further? (I thought it was
> in ASN.1 BER, but apparently that did something more complicated, as
> usual in that design.)

It could easily be much older, but I've seen it referred to as that and simply
as "variable byte encoding".

> > Do you mind if I forward your mail and this one to kragen-discuss?
> 
> Not at all. 

Thanks!

----- End forwarded message -----