To follow up my last post about the Burrows-Wheeler Transform, I decided to implement another simple algorithm which is often used after the BWT to help consolidate localized redundancy in the data before entropy encoding.
The idea behind the Move-to-Front algorithm is that we start with some known alphabet (like the list of ASCII characters), and encode our data elements as the index into that alphabet list of each element. The trick is that after each character is encoded, the alphabet list is modified by moving the element whose index we just looked up to the front of the alphabet.
Here are my implementations of encode and decode:
1 2 3 4 5 6 7 8 9 10
mapAccumL function is perfect for passing the state of the dictionary
list. Another point of interest to mention is the use of
minBound to let the
function be polymorphic over any type for which there is a defined order and
For example, we can do this:
*Main> mtf "SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES" >>= return . mtfDec :: Maybe String Just "SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES"
or we can decode to Word8 bytes, if we want to get back the ASCII character in that form, just by specifying a different return type:
*Main> :m + Data.Word *Main Data.Word> mtf "SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES" >>= return . mtfDec :: Maybe [Word8] Just [83,73,88,46,77,73,88,69,68,46,80,73,88,73,69,83,46,83,73,70,84,46,83,73,88,84,89,46,80,73,88,73,69,46,68,85,83,84,46,66,79,88,69,83]
Let me know your thoughts!