Xref: utzoo comp.databases:10359 comp.compression:679 Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!swrinde!cs.utexas.edu!uunet!ns-mx!pyrite.cs.uiowa.edu From: jones@pyrite.cs.uiowa.edu (Douglas W. Jones,201H MLH,3193350740,3193382879) Newsgroups: comp.databases,comp.compression Subject: Re: In Search Of a key compression algorithm! (redirected) Message-ID: <6301@ns-mx.uiowa.edu> Date: 2 Jun 91 19:15:32 GMT References: Sender: news@ns-mx.uiowa.edu Followup-To: comp.databases Distribution: comp Lines: 19 > From: jerryw@tove.cs.umd.edu (Jerry Wieber) > Organization: U of Maryland, Dept. of Computer Science, Coll. Pk., MD 20742 > > I am looking for an algorithm that can compress keys without destroying > lexigraphic ordering. I'm at home and can't check my references, but the compression technique that you might want is called the Garcia Wachs (or something like that) algorithm. I have a reprint of a paper by Jeff Kingston that discusses this algorithm. In sum, the idea is to use a prefix code, as with Huffman Codes, but to balance the encoding tree without reordering the leaves. This can be done with compression efficiency that is no worse than one bit per character worse than the efficiency of a Huffman code (which is no worse than one bit per character worse than the source entropy under the source model used for compression). Doug Jones jones@cs.uiowa.edu