[mercury-users] Compression library

[Ralph Becket]

Hi Tyson,

hope you had a good day out in London before the 5000 mile
hike home.

> I just looked into it.  LZW is patented.

God, I just hate it when people do that.  [Ooops, the MS
police are on my case now...]

> Free software was once exempted by Unisys, but they decided to change
> their mind on this in 1996.  
> 
> The patent expires in 2003.  

While hunting around for info. on the patent status of LZW, I rediscovered
the Burrows Wheeler Transform, which is the maddest idea in the world.
Basically, you take the string you want to compress, compute all rotations
of it, sort them, and then take the final *column*, noting which line in
the sorted list contains the original string.  Now, the final column is
simply a permutation of the original string, but it compresses much better
because it consists of sequences of letters drawn from small subsets of the
alphabet (e.g. consider `the' - after the sort, there will be a lot of lines
starting with `he ...' and will therefore end with [tTsS] with a heavy bias
towards `t'.  This is ideal for compression.  The amazing thing is that one
can recover the original string from the final column by (a) sorting the
final column to get the first column and (b) working out the transposition
function from places in the first column to places in the last one and (c)
applying it starting with the row we identified at the start.  The
compression
ratios you get are just phenomenal - state of the art with relatively minor
effort.

Anyway, I'm just putting the finishing touches to an implementation of this
thing (basically BWT + Huffman) and I'll submit that, instead.

> http://www.cloanto.com/users/mcb/19950127giflzw.html

Makes you weep, doesn't it?!  How goes the lazy stuff?

Cheers,

Ralph
--------------------------------------------------------------------------
mercury-users mailing list
post:  mercury-users at cs.mu.oz.au
administrative address: owner-mercury-users at cs.mu.oz.au
unsubscribe: Address: mercury-users-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-users-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------