CODEWITHSUNDEEP
algorithmdecodedecoderburrows-wheeler-transform
DeepHouse
DeepHouse

Reputation: 21

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.

Upvotes: 1

Views: 4772

Answers (2)

flanglet
flanglet

Reputation: 574

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

Upvotes: 0

Cybercartel
Cybercartel

Reputation: 12592

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

Upvotes: 1

Related Questions