Programming, C++

[data compression]
RLE - run length encoding
MTF - move to front
BWT - burrows wheeler
Diatomic encoding
The static model

[bit io routines]
Bits & bytes
Bit io demo

'Burrows Wheeler Transform'

Consider the following string: "SINGING IN THE RAIN, JUST SINGING AND DANCING IN THE RAIN". Following standard BWT we get: "GDGG,EETNNNRRD NN HHNNNNNTT AGGCSSA IIIAAIIIIII NUS J". You can see the way that the new string has been encoded to force characters into runs of the same type, while retaining the actual count of original symbols. Look at the runs of 'I' and 'N'. The transform is done by sorting (alphabetically) all rotations of the text, then taking the last column as the encoded string. A single pointer or (primary index i.e. an integer value) is all that is needed to reverse the process. I have put all the global function type defs and vars at the top of the code. You will need to include the library's but the code should be pretty portable. I did not write the buffer rotation code, but I think I modified this from some free source code I found on the net.