Characteristics of BWT

Compression

The achievable compression depends considerably on the size of the matrix. Presupposing a sufficient dimensioning, a compression can be achieved, that is clearly better than with conventional procedures, e.g. Deflate for ZIP or GZIP. With more complex procedures (PPM, LZMA) slightly better results may be obtained.

Encoding Speed

The processing speed of the encoder is dominated by the sort algorithm. With increasing block size this rises exponentially.

Decoding Speed

The sort procedure must be applied for decoding only to the simple string and not to the two-dimensional matrix. For that reason the decoding is clearly faster than the encoding.

Memory

The necessary main memory for the encoding is determined considerably by the block size. The storage requirement of BZIP2 is specified as the eightfold block size. There are different models to store the matrix, one variant represents each row by a pointer to the original data; i.e. each row of the matrix requires one pointer. Additionally memory for the sorting algorithm is required.

 <   ^   >