Burrows Wheeler Transform (BWT)

I am having difficulties in grasping the decode algorithm for the Burrows Wheeler transform (BWT.) I've done reading online and went through some sample code, but, they all seem to be using a 'primary index' to decode an encoded string.

My question is, how can we decode a BWT encoded string like 'rdacraaaabb' to its original 'abracadabra'.

Some sample开发者_高级运维 code would be wonderful.

You want to look at http://www.phpclasses.org/package/3559-PHP-Compress-and-decompress-data-using-BWT-and-MTF.html.

The inverse part is the easiest part of the algorithm: create cumulative histograms and retrieve values based on their rank.

You can find a complete block compressor/decompressor based on the BWT here: http://code.google.com/p/kanzi/source/browse/java/src/kanzi/transform/BWT.java