OpenBWT-2.0.0 development

[smjohn1]

Hi, I am new to this forum and a novice to compression in general. But I need a BWT related compression tool, and was pointed to OpenBWT-2.0.0 package.

My questions:

1) Any new developments in this package since 2010? What is the relation between DivSufSort and OpenBWT 2.0? Is DivSufSort a superset of OpenBWT 2.0?

2) In the OpenBWT 2.0, there is a directory called sst. What is sst? I guess the source codes contained there are for post processing methods after BWT. Are there any simple example codes to use these methods? And also are there published experimental results of using these methods, such as compression ratio, memory use and processing time using these methods together with RLE and entropy coder?

Many thanks for any help.

[xezz]

1) The relation is nothing. It's based on Induced Suffix Sorting.
2) sst is second stage transform. v1.3 has example codes.

[Shelwien]

1) divsufsort was updated more recently: https://github.com/y-256/libdivsufsort
I guess divsufsort is a normal library, while openbwt is more of a development/benchmark kit.

2) SST is "second stage transform", like MTF. There's also sst_test.c for their comparison.
Most of these methods are not actually used anywhere.

3) You can also look at
https://github.com/michaelmaniscalco/msufsort
https://github.com/IlyaGrebnov/libbsc

[smjohn1]

Thank you so much for the info

[Christoph Diegelmann]

I made some improvements on libdivsufsort a while ago which speeds up the second stage:

https://github.com/akamiru/libdivsufsort

[smjohn1]

Thx, will try out.

I made some improvements on libdivsufsort a while ago which speeds up the second stage:

https://github.com/akamiru/libdivsufsort

[smjohn1]

Any technical writings to explain how to use these SSTs used as examples in OpenBWT-1.5 ?

1) divsufsort was updated more recently: https://github.com/y-256/libdivsufsort
I guess divsufsort is a normal library, while openbwt is more of a development/benchmark kit.

2) SST is "second stage transform", like MTF. There's also sst_test.c for their comparison.
Most of these methods are not actually used anywhere.

3) You can also look at
https://github.com/michaelmaniscalco/msufsort
https://github.com/IlyaGrebnov/libbsc

[Shelwien]

https://en.wikipedia.org/wiki/Bzip2#...ront_transform

Simply apply to BWT output.

[michael maniscalco]

To expand upon Eugene's answer, 'second stage tranforms' are post BWT transforms intended to make the data more compressible after the BWT. That is, they are used like this:
BWT -> SST -> entropy coder. However, these secondary transforms are generally not as strong as direct encoding of the BWT itself and most modern BWT compressors avoid using any secondary transform.

Some people use a pre-BWT transform as well to reduce the long matches encountered during the BWT but this is completely unnecessary as modern suffix array algorithms no longer have problems with long substring matches. These 'pre-BWT' transforms are usually LZP and are intended not to compress the pre-BWT data but to encode any really long substring matches.

Examples of excellent modern compressors which encode the BWT directly:

BCM - encodes the BWT data directly using context mixing (Muravyov)
BWTMix - another context mixing BWT coder (Shelwein)
M99 - encodes the actions needed to sort the symbols of the BWT using bit packing (Maniscalco)
M03 - encodes the BWT data based on the contexts of the pre-BWT data (Maniscalco)

Examples of modern BWT compressors using post BWT transform:

BSC - uses QLFC (Grebnov)
- probably several other's that aren't coming to mind at the moment)

The key take away is that you don't really need post BWT transforms to effectively and efficiently encode the BWT.

- Michael

[smjohn1]

thanks for the info.

Anyone tried BWT (with or without SST) + ANS/FSE as FSE is a good and fast entropy encoder?

[hexagone]

thanks for the info.

Anyone tried BWT (with or without SST) + ANS/FSE as FSE is a good and fast entropy encoder?

Take a look here: https://github.com/flanglet/kanzi

Compression happens in 2 steps: transform, then entropy and you can specify both. For instance you can select BWT for stage 1 and ANS0 for stage 2. Or you can specify a level the pre-defines stage 1 and stage 2. EG. level=2 uses BWT, RANK (as SST), Zero RunLength, then ANS0.

The help option contains the list of implemented transforms and entropy coders.

[smjohn1]

Thanks!

Take a look here: https://github.com/flanglet/kanzi

Compression happens in 2 steps: transform, then entropy and you can specify both. For instance you can select BWT for stage 1 and ANS0 for stage 2. Or you can specify a level the pre-defines stage 1 and stage 2. EG. level=2 uses BWT, RANK (as SST), Zero RunLength, then ANS0.

The help option contains the list of implemented transforms and entropy coders.