[Haskell-cafe] Re: Need for speed: the Burrows-Wheeler Transform

Andrew Coppin andrewcoppin at btinternet.com
Sat Jun 23 05:41:00 EDT 2007

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. :-}

More information about the Haskell-Cafe mailing list