Basic BWT implementation pointer

[GerryB]

I'm looking for a basic implementation of the BWT and inverse. There are many implementations online (here's just one list) but I'm looking for a research friendly library. Most of the implementations are full compression implementations with encoders as well, but I'm looking for pure BWT mostly for experimenting with full text index searching and such.

Ideally I'd just love some C functions with an API sort of like:

size_t BWTransform(const unsigned char *inputData, size_t bytecount, unsigned char *output);

where the return value is a index to the first byte of output (as opposed to inserting a sentenel).
Similarly, I'd like a transform/untransform pair for a bitwise BWT.

I'm more interested in clear code than superfast performance, but to start with I'll be using it as a black box anyway.

I'd appreciate a recommendation of where to get such libraries, or which compressor would be most appropriate for me to dig into and try to isolate the BWT routines myself.
I've already started doing that using bzip2 but that's only a bytewise version, and I may be reinventing the wheel anyway.

Thanks!

[biject.bwts]

If you look at this site you can find the c lib of Yuta that has the BWT if you want the index. He also has the BWTS which is a BWT that does not use an index and is bijective. You can change a byte of ASCII to 8 bits of one and zero just pass that to the subroutines. Check out his OPENBWT library for these and several followers to use after the BWT.

[GerryB]

Thanks for the reference! I'll look at Yuta first.

The idea of computing a bitwise BWT by simply calling the bytewise routine with just bytes 0 and 1 never occurred to me... that's a great idea for simplicity. Thanks!

[Shelwien]

Simplest version, based on stdlib qsort:
http://ctxmodel.net/files/BWT.cpp

An upgrade of above, with custom qsort and inverse transform:
http://ctxmodel.net/files/mix_test/mix_test_v9.rar /BWT

And as to bitwise BWT, here's a dummy implementation: http://nishi.dreamhosters.com/u/binbwt_v0.rar
But unless you have some pure unaligned bitwise data (eg. 2-color bitmaps), it doesn't make any sense for compression.

[Bulat Ziganshin]

simplest implementation i have seen was in haskell and just one line or so

[Shelwien]

And it would be able to transform enwik8?

[Bulat Ziganshin]

yes, using about 10^17 bytes of memory

[Matt Mahoney]

http://mattmahoney.net/dc/dce.html#Section_55 has an introduction to BWT but you probably know most of this already. LibDivSufSort by Yuta Mori has a simple interface like what you are looking for.

[m^2]

Bulat, could you post it here? Sounds interesting.

[GerryB]

LibDivSufSort worked great, nearly exactly what I was looking for. But the other pointers (especially http://ctxmodel.net/, which has all kinds of other interesting support files too) are also great.

Thanks!

[Bulat Ziganshin]

import Control.Arrow
import Data.List
import Data.Function

main = interact (show.bwt.head.lines)

bwt = index >>> sortBy (compare 'on' snd) >>> map fst
index s = map (\n -> (n, drop n (s++s))) [0..length s-1]



ps: this is optimized version that needs only ~50*filesize memory to proceed