Burrow wheeler implementation for large strings

Question

I have tried rotating a really large string in burrow wheelers cyclic string array.

But my input is about 200000 characters and when the input is this big i am unable to run the code as it runs out of heap space.

My prof said that the only way to implement it is Linear memory footprint. Which I have no clue what it means.

Can i Know what other ways to create a cyclic string which is memory efficient and use it without running out of memory

Answer 1

The trick to reducing memory usage is to create a circular suffix array, which can be done in time proportional to n lg n in the average case (and memory proportional to n) using a variant of quicksort which considers each character in the string individually (aka 3-way String quicksort; it's conceptually similar to a radix sort).

When even that takes too much memory, you need to restrict your burrows-wheeler transform to operate on blocks of fixed size (perform the encoding on X characters, then the next X characters, etc until you've encoded the whole string, reversing the process for decoding).