Burrows-Wheeler transforms

[compilerbitch]

I think that the BWT (Burrows-Wheeler transform), and particularly its inverse, are one of the coolest things I've ever seen. It's easy enough to see how someone could have thought of the forward transform, but the reverse transform is one of the most counter-intuitive ideas I've ever seen.

Go take a look: http://en.wikipedia.org/wiki/Burrows-Wheeler_transform

(As a sad aside, I was in the CL on the day that David Wheeler died -- I regret never having got to know him. I'm told by an old friend (ex-PhD student) of his that we'd have got on) 

Edit: The original paper is here, but is much less readable than the Wikipedia article.

Comments

[naranek.livejournal.com]

Aha - thanks for that! That's quite the clearest explanation of the inverse transform I've seen :-).

[caramel-betty.livejournal.com]

I learned from http://www.cl.cam.ac.uk/Teaching/2003/DSAlgs/dsa.pdf - pages 64 to 68. Page 65 is the decompression - tag all the characters, so you know what's what, sort them so that you get them in order but use the tagged order to sort out ties, using end of file as the earliest character. Then start with the . (end of file) in the sorted version. Write that down. Find out what's in the same place as the . in the unsorted version. Write that character down. Find it in the sorted version, and find out what's in the same place in the unsorted version. Write that down. Repeat until done (when you find the . in the unsorted version). Tada. You've just re-ordered the file. Backwards.

It's somehow sad that Wikipedia articles can be more comprehensible than lecture notes.

[borusa.livejournal.com]

Eee! That's fun! *works it out with a pen and paper* And very clever!

[the-local-echo.livejournal.com]

He was a nice guy.

[shevek.livejournal.com]

I remember this! It is incredibly cool.