BWT with compressed input data

[Shelwien]

http://ctxmodel.net/files/rcbwt_v0.rar
Contains two proof-of-concept implementations:
- "not working" uses a static o0 rangecoder for storing input data
in memory and compares encoded substrings without decoding.
It actually produces something very similar to BWT on output, but
regrettably the rangecoder doesn't _always_ preserve the lexicographic
order of strings, thus "not working".
- "working" uses a static o0 bit-aligned rangecoder, with ~485k
compressed size for book1.

http://ctxmodel.net/files/rcbwt_v1.rar
A new complete rewrite, with an order1 optimal ordered bitcode
(381.5k on book1) for input data storage.
Really produces a reversible BWT on output... for small enough files.
Also chunked processing is implemented, so memory usage except for
compressed input data is static.

Input file size            = 768771 (book1)
Memory usage:
 - o1 static bitcode model = 34473984
 - clustering statistics   = 4194304
 - BWT index table         = 65536
 - source data buffer      = 381510
 TOTAL                     = 39115334

Input file size            = 1000000 (enwik6)
Memory usage:
 - o1 static bitcode model = 34473984
 - clustering statistics   = 4194304
 - BWT index table         = 65536
 - source data buffer      = 529780
 TOTAL                     = 39263604

Unfortunately some "features" still have to be fixed:
- "static bitcode model" is too large (mainly due to decoding lookup table)
- Longer files (eg. enwik8) cause a 16bit code overflow
- The case with too many strings in a chunk is not handled yet (infinite loop)

Still, I think its interesting enough as it is.

[Shelwien]

Well, I couldn't stop ;)

http://ctxmodel.net/files/rcbwt_v2.rar
- Added frequency rounding to 14 bits (to avoid bitcode overflows)
- Chunk size is now dynamic

Input file size            = 100000000 (enwik8)
Memory usage:
 - o1 static bitcode model = 34736128
 - clustering statistics   = 4194304
 - BWT index table         = 5652984
 - source data buffer      = 53711205
 TOTAL                     = 98294621

Input file size            = 1000000000 (enwik9)
Memory usage:
 - o1 static bitcode model = 34736128
 - clustering statistics   = 4194304
 - BWT index table         = 68491184
 - source data buffer      = 538268254
 TOTAL                     = 645689870

And here, with enwik9, we finally have an example of BWT with 0.646N memory usage ;)
It still works though, and I don't think I have anything to verify that its correct.
Would later try to compress the output with o2rc and see what'd happen.

[toffer]

That is pretty impressive - Very good work!

What about transform speeds compared to non-precompressed input?

[Shelwien]

Well, I just tested on enwik8 and my dummy 5N BWT
(from http://ctxmodel.net/files/BWT_reorder_v2.rar)
took 89.766s, while rcBWT_v2 took 269.75s.
But its unoptimized and even does some unnecessary stuff
(like saving bitcoded and decoded data) and I'm going to
add multithreading too, so it might even become "faster"
than 5N one with 4 cores.