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

'MTF'

Consider the numeric digits 12345678901234567890 (which reside in a text file) using an alphabet (0-9) and outputting a revised index for each byte read in. To start the Alphabet array is {0,1,2,3,4,5,6,7,8,9} First file byte read in is 1 which is at position 1 in the array, hence we output 1. We then alter the array to resemble {1,0,2,3,4,5,6,7,8,9} Next file byte read is 2 which is at position 2 in the array, hence we output 2. And so on, the array now resembles {2,1,0,3,4,5,6,7,8,9} When we reach the 0, it is at position 9, hence we output another 9. As we read in each byte after this, because they are always at position 9 we get the long string of 9's. I use these digits merely as an example as you could encode the repeated run using another technique. Using the MTF for the example above, we will encode these digits to 12345678999999999999. We do not need to store any alphabet as long as the decoder is aware of the length i.e. that we are using digits [0-9] for instance.

MTF - Numeric
     

MTF - Full Alphabet