Haskell/Burrows–Wheeler transform: Unterschied zwischen den Versionen
Aus Franky
Franky (Diskussion | Beiträge) K (1 Version: Import des alten wiki) |
Franky (Diskussion | Beiträge) K (Change syntaxhighlighting to haskell) |
||
| Zeile 1: | Zeile 1: | ||
Do you understand a compression algorithm like zip?<ref>Surely, 'ziv' is not the name of a compression algorithm.</ref> Either way, I recommend you to look into the | Do you understand a compression algorithm like zip?<ref>Surely, 'ziv' is not the name of a compression algorithm.</ref> Either way, I recommend you to look into the | ||
[[we:Burrows–Wheeler transform]] at wikipedia. Coding the BWT in Haskell is quite easy. | [[we:Burrows–Wheeler transform]] at wikipedia. Coding the BWT in Haskell is quite easy. | ||
| − | < | + | <syntaxhighlight lang="haskell"> |
-- Burrows-Wheeler. | -- Burrows-Wheeler. | ||
| Zeile 25: | Zeile 25: | ||
map (x !!) [ l !! n | l<-take len $ iterate f p] | map (x !!) [ l !! n | l<-take len $ iterate f p] | ||
--map (x !!) [ l !! n | l<-iterate f p] -- wrong! | --map (x !!) [ l !! n | l<-iterate f p] -- wrong! | ||
| − | </ | + | </syntaxhighlight> |
The transformation is quite self-explanatory if you understand BWT. These four lines are neither efficient in terms of memory nor speed. | The transformation is quite self-explanatory if you understand BWT. These four lines are neither efficient in terms of memory nor speed. | ||
Aktuelle Version vom 22. Januar 2014, 19:00 Uhr
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.
