BWT Compression Comparison

In this test we compare Burrows-Wheeler based compressors. We especially try to compare such compressors that do not use preprocessing.

Definition

We define BWT compressor to be a program that applies BWT transformation before compression. When decompressing the program applies inverse BWT transformation after decompressing the data.

We define BWT compressor without preprocessing to be such that it does not apply any kind of transformation to the data before the context sorting phase of Burrows-Wheeler transform.

Programs

This is a special test. We include unrated compressors that do not qualify for the main benchmark and run compressors with only a single configuration for maximum compression. We do not assign ratings and no size for decoder program is considered. For some unrated compressors we do not list times nor other info at all (for technical reasons). We do not even verify correct decompression for some programs (where n/a is marked for d.time). Authors are welcome to contact me if they find their compressors are missing or tested incorrectly.

We have no decisive evidence whether a program uses preprocessing or not without the source code. Hence we must use undisclosed arbitrary qualifying methods to choose the set of programs for this test.

Brief comments about the programs which are considered for the test.

The following open source programs are not using preprocessing: bbb, bwtzip, chile, ABC, bwc, Dark, BWTmix. Because we do not wish to discard all other compressors, we include them anyway with hopes that they do not use heavy preprocessing for the test files. We discard RINGS and SBC since they do not fit well to the concept of BWT without preprocessing. We would have reasons to discard other compressors such as YBS, Blizzard, IMP, ZZIP, but we hope their preprocessing is rather inefficient for our test files and we include them anyway. This results arbitrary comparison, but this we knew from the start.

The programs are set up with maximum memory setting that works in the test machine. Dark reports out of memory using 125 MB block, therefore a smaller blocksize was used. For BMA the following switches are used in addition to the ones listed in the tables: '-rv- -pe- -t- -d- -l- -z- -tx-'. We run BMA with -sif0 because otherwise the program attempts to choose the best compression method that may lead of confusing results especially with the transformation test.

Memory Requirements

Most programs use 5 to 10n blocksize memory. bbb 0 and BWMonstr 0.02 work with less than 5n memory. bbb uses 1.25n blocksize memory, but requires 4n space for temporary files. BWMonstr uses less than 0.6n blocksize memory. The table beside gives an estimated memory requirements for each compressor compressing enwik9.

Test files

We will use special test files for this test: enwik9 for a large test file. A smaller 5 000 000 byte sample of enwik9 to attempt get as many programs as possible to compress the file using a single block. We also add book1 and obj2 (from the Calgary Corpus). Finally a random file DejaVuSans.ttf from Application1.

• enwik9
• enwik5m
• book1
• obj2
• ttf
• Transformation test

enwik9

enwik5m

book1

obj2

ttf

Transformation Test

Finally we try to get indicators of possible preprocessing and compressor behavior by applying various transformations to the data before compression. The table below lists compressed sizes for book1 with various transformations added. We use red color if a transformation causes the size to grow compared to the book1 result without transformation and green color if the transformation improves compression.

1. book1
2. book1 (reverse)
3. book1 (x[i]=255-x[i])
4. book1 (x[i]=0x55^x[i])
5. book1 (x[i]=x[i]*31 mod 256)
6. book1 (reorder)
7. book1 (DC 0.98b -n -s -d -e)

The results indicate that no compressor use heavy preprocessing for the original data. GCA 0.9k, bcm 0.09, BWTmix 1 and Blizzard 0.24 do not benefit from DC preprocessing, which is designed to help BWT compression. This may suggest that these programs may have preprocessing. BWTmix does not, but the program has a case insensitive model, which boosts the performance for text data. ZZIP uses preprocessing, but DC preprocessing works much better for it. This may be the case with some other compressors like BA.

The arguments used for each program are the same as in other tests.