apfelmus wrote:
Note that the one usually adds an "end of string" character $ in the
Burrows-Wheeler transform for compression such that sorting rotated
strings becomes sorting suffices.
Yeah, I noticed that the output from by program can never actually be
reverted to its original form. ;-) Maybe it I alter the code to stick a
0-byte in there or something...
(Hmm, I wonder how Mr C++ managed it? Heh. If I could read C++, maybe
I'd know...)
Concerning the algorithm at hand, you can clearly avoid calculating
Raw.append over and over:
bwt :: Raw.ByteString -> Raw.ByteString
bwt xs = Raw.pack . map (Raw.last) . sort $ rotations
where
n = length xs
rotations = take n . map (take n) . tails $ xs `Raw.append` xs
assuming that take n is O(1).
...which is amusing because that's what the *first* implementation did. ;-)
I was trying to avoid O(n^2) RAM usage. :-}
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
