Computing the BWTS faster

[nburns]

I've been sitting on this for a little while, and talked about it with David Scott, and I figure now is as good a time as any to share.

This computes the BWTS using a new approach. Unlike the original implementation and the one in openbwt, it suffix sorts the input as a whole and then corrects the order to produce the BWTS. It's not clear to me whether it's fundamentally a better approach than merging, or if it's just simpler and benefits from the optimization that's gone into divsufsort. But it seems to get the BWTS quite a bit faster, and gets the same result as openbwt on all the data I've thrown at it.

Please let me know if you find a bug.

[nburns]

This now has a Google Code project: http://code.google.com/p/mk-bwts/

[Matt Mahoney]

I ran a quick test on the simple benchmark similar to http://encode.su/threads/1744-An-Ele...ll=1#post33777
All files produced output of identical size. I did not test the inverse BWTS to see if it was identical.

Of the 1 MB files, the slowest were l6002 and m6002, which are ascending lists of 16 bit integers in LSB first or MSB first format. These were 0.43 seconds. All others were under 0.27 sec. The file w8002 (2 copies of a 50 MB random string) took 52 sec. and 600 MB memory.

[nburns]

The steps that dominate the performance are, in descending order: the suffix sort, computing the inverse suffix array, permuting the text by the new order, and computing the new order. Computing the new order takes about 1-6% of the total time. I have an update that improves the performance of computing the order on some inputs, which I'll put on google code once it's fully tested. However, unless there's a dataset that triggers massively pathological behavior, the difference will be small.

The data that's allocated are the suffix array (4N), the inverse suffix array (4N), and the output array (N). The input is memory mapped for speed. I was originally computing and writing the output on the fly, but it turned out to be faster to generate it out of order and buffer it before writing. The SA gets freed before the output buffer is allocated, so the max allocated at a single time is 8N bytes.

Any significant improvement in speed/memory will have to come from doing something about the inverse suffix array, which will not be easy to get rid of.

[nburns]

I updated the google code repository with the sorting improvements. I tested it on ~20k files.