File BurrowsWheeler.h

↰ Parent directory (ADS/compression)

The transform of Burrows and Wheeler and the compressor built on it (chapter 14 of the notes).

Definition (ADS/compression/BurrowsWheeler.h)

Detailed Description

The rows of the matrix M’ are the rotations of s$, $ a sentinel smaller than every symbol, in sorted order; the transform bwt() is its last column L without the $, with the row r of the $. Since the rows that start with a string w are contiguous, the symbols that precede the occurrences of w are a substring of L, and on a text whose symbols depend on their contexts, as those of a language do, L is made of runs of few distinct symbols. The rows of M’ are the suffixes of s$ in order, so L[ i ] = s[ SA[ i ] - 1 ] (Theorem 14.6); the suffix array SA is that of the library [see File SuffixArray.h], built by the induced sorting SA-IS of Nong, Zhang and Chan in O( n ) time, with the suffix $ put first. The inverse transform inverseBwt() uses the LF-mapping: the k-th occurrence of c in L and the k-th in the first column F are the same symbol of s (Property 14.2), hence :math:` LF[ i ] = C[ L[ i ] ] + rank_{L[ i ]}( L , i ) `, with C[ c ] the number of the symbols smaller than c; from the row 0, which is $s and ends with s[ n - 1 ], each step of LF moves one symbol to the left in s, n steps in O( n ) time (Theorem 14.3), each a likely miss of the cache.

The transforms that follow (section 14.2): the move-to-front of Bentley, Sleator, Tarjan and Wei replaces each symbol with its place in a list of the alphabet and moves it to the front, so the runs of few symbols of L become runs of small integers, O( | :math:` Sigma | ) time per symbol here; its :math: gamma -code takes at most :math: 2 H_0 + 1 ` bits per symbol (Theorem 14.5). The run-length encoding replaces a run of :math:` ell ` symbols c with :math:` langle ell , c rangle . The bzip of section 14.3 chains them: the transform of each block, the move-to-front of L, then the run-length encoding RLE0 of the runs of 0 alone, the other integers grown by 1 and a run of m zeros written in the code of Wheeler, the binary digits of m + 1 after its leading 1 as the symbols 0 and 1, and at last an entropy code, here the canonical code of Huffman of the block with lengths up to 20 [see :ref:`file_ADS_compression_CanonicalHuffman.h], as in bzip2 (which writes the digits of the runs from the least significant and splits the block in groups coded by up to 6 tables). Coding L by contexts gives the entropy of order k for every k at once (the boosting of Ferragina, Giancarlo, Manzini and Sciortino, section 14.4), and Manzini bounds the chain of the transform, MTF, RLE and an arithmetic code by :math:` ( 5 + epsilon ) n H_k^*( s ) ` bits plus lower terms, :math:` H_k^* ` a variant of the entropy of order k [see File Entropy.h]. The transform is also an index [see File FMIndex.h].

The contracts [see File Contract.h]: the row r is that of a transform, each symbol of a move-to-front is in its alphabet of distinct symbols, a run is positive, the integers of RLE0 are at most 256, a block is positive; inverse( transform( x ) ) == x, an audit. The functions are defined in BurrowsWheeler.tpp.

  1. Ferragina, Pearls of Algorithm Engineering, Cambridge University Press, 2023, chapter 14

  1. Burrows, D. J. Wheeler, A block-sorting lossless data compression algorithm, Technical Report 124, Digital Systems Research Center, 1994

    1. Bentley, D. D. Sleator, R. E. Tarjan, V. K. Wei, A locally adaptive data compression scheme, Communications of the ACM 29(4), 320-330, 1986, doi:10.1145/5684.5688

  1. Manzini, An analysis of the Burrows-Wheeler transform, Journal of the ACM 48(3), 407-430, 2001, doi:10.1145/382780.382782

  1. Ferragina, R. Giancarlo, G. Manzini, M. Sciortino, Boosting textual compression in optimal linear time, Journal of the ACM 52(4), 688-713, 2005, doi:10.1145/1082036.1082043

  1. Nong, S. Zhang, W. H. Chan, Two efficient algorithms for linear time suffix array construction, IEEE Transactions on Computers 60(10), 1471-1484, 2011, doi:10.1109/TC.2010.188

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Classes

Functions