Haskell/Burrows–Wheeler transform
Aus Franky
Version vom 22. Januar 2014, 19:00 Uhr von Franky (Diskussion | Beiträge)
Do you understand a compression algorithm like zip?[1] Either way, I recommend you to look into the we:Burrows–Wheeler transform at wikipedia. Coding the BWT in Haskell is quite easy.
-- Burrows-Wheeler. import List (sort,elemIndex) import Maybe (fromJust) transform :: (Ord x) => [x] -> ([x],Int) transform x = let n = length x line i = take n $ drop i $ x++x matrix = sort [line i | i<-[0..(n-1)]] in (map last matrix,fromJust $ elemIndex x matrix) reTransform :: (Ord x) => ([x],Int) -> [x] reTransform (x,n) = let tp = zip x [0..] len = length x sx = sort tp p :: [Int] -- permutation, index i is moved to p !! i p = map snd sx --f z = map ( z !! ) p f = flip map p . (!!) -- another point-free exercise solved. in map (x !!) [ l !! n | l<-take len $ iterate f p] --map (x !!) [ l !! n | l<-iterate f p] -- wrong!
The transformation is quite self-explanatory if you understand BWT. These four lines are neither efficient in terms of memory nor speed.
The back-transformation is a little bit harder, but the without p :: [Int]] line and the two comments it is just 6 lines. When I take the time to explain the BWT in my words, the code becomes clear.
- ↑ Surely, 'ziv' is not the name of a compression algorithm.