Burrows-Wheeler 变换（BWT）

We describe a block-sorting, lossless data compression algorithm, and our implementation of that algorithm. We compare the performance of our implementation with widely available data compressors running on the same hardware.

The algorithm works by applying a reversible transformation to a block of input text. The transformation does not itself compress the data, but reorders it to make it easy to compress with simple algorithms such as move-to-front coding.

Our algorithm achieves speed comparable to algorithms based on the techniques of Lempel and Ziv, but obtains compression close to the best statistical modelling techniques. The size of the input block must be large (a few kilobytes) to achieve good compression.

The most widely used data compression algorithms are based on the sequential data compressors of Lempel and Ziv [1, 2]. Statistical modelling techniques may produce superior compression [3], but are significantly slower.

In this paper, we present a technique that achieves compression within a percent or so of that achieved by statistical modelling techniques, but at speeds comparable to those of algorithms based on Lempel and Ziv's.

Our algorithm does not process its input sequentially, but instead processes a block of text as a single unit. The idea is to apply a reversible transformation to a block of text to form a new block that contains the same characters, but is easier to compress by simple compression algorithms. The transformation tends to group characters together so that the probability of finding a character close to another instance of the same character is increased substantially. Text of this kind can easily be compressed with fast locally-adaptive algorithms, such as move-to-front coding [4] in combination with Huffman or arithmetic coding.

Briefly, our algorithm transforms a string S of N characters by forming the N rotations (cyclic shifts) of S, sorting them lexicographically, and extracting the last character of each of the rotations. A string L is formed from these characters, where the ith character of L is the last character of the ith sorted rotation. In addition to L, the algorithm computes the index I of the original string S in the sorted list of rotations. Surprisingly, there is an efficient algorithm to compute the original string S given only L and I.

The sorting operation brings together rotations with the same initial characters. Since the initial characters of the rotations are adjacent to the final characters, consecutive characters in L are adjacent to similar strings in S. If the context of a character is a good predictor for the character, L will be easy to compress with a simple locally-adaptive compression algorithm.

This section describes two sub-algorithms. Algorithm C performs the reversible transformation that we apply to a block of text before compressing it, and Algorithm D performs the inverse operation. A later section suggests a method for compressing the transformed block of text.

In the description below, we treat strings as vectors whose elements are characters.

This algorithm takes as input a string S of N characters S[0]; …; S[N − 1] selected from an ordered alphabet X of characters. To illustrate the technique, we also give a running example, using the string S = 'abraca', N = 6, and the alphabet X = {'a','b','c','r'}.

C1. [sort rotations] Form a conceptual N × N matrix M whose elements are characters, and whose rows are the rotations (cyclic shifts) of S, sorted in lexicographical order. At least one of the rows of M contains the original string S. Let I be the index of the first such row, numbering from zero.

In our example, the index I = 1 and the matrix M is:
row 0: aabrac
row 1: abraca
row 2: acaabr
row 3: bracaa
row 4: caabra
row 5: racaab

C2. [find last characters of rotations] Let the string L be the last column of M, with characters L[0]; …; L[N − 1] (equal to M[0, N−1]; …; M[N−1, N−1]). The output of the transformation is the pair (L, I).

In our example, L = 'caraab' and I = 1 (from step C1).

We use the example and notation introduced in Algorithm C. Algorithm D uses the output (L, I) of Algorithm C to reconstruct its input, the string S of length N.

D1. [find first characters of rotations] This step calculates the first column F of the matrix M of Algorithm C. This is done by sorting the characters of L to form F. We observe that any column of the matrix M is a permutation of the original string S. Thus, L and F are both permutations of S, and therefore of one another. Furthermore, because the rows of M are sorted, and F is the first column of M, the characters in F are also sorted.

In our example, F = 'aaabcr'.

To assist our explanation, we describe this step in terms of the contents of the matrix M. The reader should remember that the complete matrix is not available to the decompressor; only the strings F, L, and the index I (from the input) are needed by this step.

Consider the rows of the matrix M that start with some given character ch. Algorithm C ensured that the rows of matrix M are sorted lexicographically, so the rows that start with ch are ordered lexicographically.

We define the matrix M' formed by rotating each row of M one character to the right, so for each i = 0,…, N−1, and each j = 0,…, N−1, M'[i,j] = M[i, (j−1) mod N].

In our example, M and M' are:
row 0: M = aabrac    M' = caabra
row 1: M = abraca    M' = aabrac
row 2: M = acaabr    M' = racaab
row 3: M = bracaa    M' = abraca
row 4: M = caabra    M' = acaabr
row 5: M = racaab    M' = bracaa

Like M, each row of M' is a rotation of S, and for each row of M there is a corresponding row in M'. We constructed M' from M so that the rows of M' are sorted lexicographically starting with their second character. So, if we consider only those rows in M' that start with a character ch, they must appear in lexicographical order relative to one another; they have been sorted lexicographically starting with their second characters, and their first characters are all the same and so do not affect the sort order. Therefore, for any given character ch, the rows in M that begin with ch appear in the same order as the rows in M' that begin with ch.

In our example, this is demonstrated by the rows that begin with 'a'. The rows 'aabrac', 'abraca', and 'acaabr' are rows 0, 1, 2 in M and correspond to rows 1, 3, 4 in M'.

Using F and L, the first columns of M and M' respectively, we calculate a vector T that indicates the correspondence between the rows of the two matrices, in the sense that for each j = 0,…, N−1, row j of M' corresponds to row T[j] of M.

If L[j] is the kth instance of ch in L, then T[j] = i where F[i] is the kth instance of ch in F. Note that T represents a one-to-one correspondence between elements of F and elements of L, and F[T[j]] = L[j].

In our example, T is: (4 0 5 1 2 3).

Now, for each i = 0,…, N−1, the characters L[i] and F[i] are the last and first characters of the row i of M. Since each row is a rotation of S, the character L[i] cyclically precedes the character F[i] in S. From the construction of T, we have F[T[j]] = L[j]. Substituting i = T[j], we have L[T[j]] cyclically precedes L[j] in S.

The index I is defined by Algorithm C such that row I of M is S. Thus, the last character of S is L[I]. We use the vector T to give the predecessors of each character: for each i = 0,…, N−1: S[N−1−i] = L[Tⁱ[I]], where T⁰[x] = x, and Tⁱ⁺¹[x] = T[Tⁱ[x]].

This yields S, the original input to the compressor.

In our example, S = 'abraca'.

We could have defined T so that the string S would be generated from front to back, rather than the other way around. The description above matches the pseudo-code given in Section 4.2.

The sequence Tⁱ[I] for i = 0,…, N−1 is not necessarily a permutation of the numbers 0,…, N−1. If the original string S is of the form Z^p for some substring Z and some p > 1, then the sequence Tⁱ[I] for i = 0,…, N−1 will also be of the form Z'^p for some subsequence Z'. That is, the repetitions in S will be generated by visiting the same elements of T repeatedly. For example, if S = 'cancan', Z = 'can' and p = 2, the sequence Tⁱ[I] for i = 0,…, N−1 will be [2, 4, 0, 2, 4, 0].

Algorithm C sorts the rotations of an input string S, and generates the string L consisting of the last character of each rotation.

To see why this might lead to effective compression, consider the effect on a single letter in a common word in a block of English text. We will use the example of the letter 't' in the word 'the', and assume an input string containing many instances of 'the'.

When the list of rotations of the input is sorted, all the rotations starting with 'he ' will sort together; a large proportion of them are likely to end in 't'. One region of the string L will therefore contain a disproportionately large number of 't' characters, intermingled with other characters that can precede 'he ' in English, such as space, 's', 'T', and 'S'.

The same argument can be applied to all characters in all words, so any localized region of the string L is likely to contain a large number of a few distinct characters. The overall effect is that the probability that given character ch will occur at a given point in L is very high if ch occurs near that point in L, and is low otherwise.

This property is exactly the one needed for effective compression by a move-to-front coder [4], which encodes an instance of character ch by the count of distinct characters seen since the next previous occurrence of ch. When applied to the string L, the output of a move-to-front coder will be dominated by low numbers, which can be efficiently compressed by an entropy coder.

Algorithm M: Move-to-front coding

M1. [move-to-front coding] This step encodes each of the characters in L by applying the move-to-front technique to the individual characters. We define a vector of integers R[0]; …; R[N−1], which are the codes for the characters L[0]; …; L[N−1].

Initialize a list Y of characters to contain each character in the alphabet X exactly once. For each i = 0,…, N−1 in turn, set R[i] to the number of characters preceding character L[i] in the list Y, then move character L[i] to the front of Y.

Taking Y = ['a','b','c','r'] initially, and L = 'caraab', we compute the vector R: (2, 1, 3, 1, 0, 3).

M2. [encode] Apply Huffman or arithmetic coding to the elements of R, treating each element as a separate token to be coded.

Algorithm W: Move-to-front decoding

W1. [decode] Decode the coded stream OUT using the inverse of the coding scheme used in step M2. The result is a vector R of N integers.

W2. [inverse move-to-front coding] Initialize a list Y of characters to contain the characters of the alphabet X in the same order as in step M1. For each i = 0,…, N−1 in turn, set L[i] to be the character at position R[i] in list Y (numbering from 0), then move that character to the front of Y.

4.1 Compression

The most important factor in compression speed is the time taken to sort the rotations of the input block. A simple application of quicksort requires little additional space (one word per character), and works fairly well on most input data. However, its worst-case performance is poor.

A faster way to implement Algorithm C is to reduce the problem of sorting the rotations to the problem of sorting the suffixes of a related string.

4.2 Decompression

Steps D1 and D2 can be accomplished efficiently with only two passes over the data, and one pass over the alphabet, as shown in the pseudo-code below. ...

Compression can improve slightly if move-to-front is replaced by a scheme in which codes that have not been seen in a very long time are moved only part-way to the front. We have not exploited this in our implementations.

Although simple Huffman and arithmetic coders do well in step M2, a more complex coding scheme can do slightly better. This is because the probability of a certain value at a given point in the vector R depends to a certain extent on the immediately preceding value. In practice, the most important effect is that zeroes tend to occur in runs in R. We can take advantage of this effect by representing each run of zeroes by a code indicating the length of the run. A second set of Huffman codes can be used for values immediately following a run of zeroes, since the next value cannot be another run of zeroes.

In Table 1 we give the results of compressing the fourteen commonly used files of the Calgary Compression Corpus [7] with our algorithm. ... The CPU time measurements were made on a DECstation 5000/200, which has a MIPS R3000 processor clocked at 25MHz with a 64 kbyte cache.

In Table 2, we show the variation of compression effectiveness with input block size for two inputs. ... The table shows that compression improves with increasing block size, even when the block size is quite large.

Table 3 compares our implementation of Algorithm C with other compression programmes.

7. Conclusions

We have described a compression technique that works by applying a reversible transformation to a block of text to make redundancy in the input more accessible to simple coding schemes. Our algorithm is general-purpose, in that it does well on both text and non-text inputs. The transformation uses sorting to group characters together based on their contexts; this technique makes use of the context on only one side of each character.

To achieve good compression, input blocks of several thousand characters are needed. The effectiveness of the algorithm continues to improve with increasing block size at least up to blocks of several million characters.

Our algorithm achieves compression comparable with good statistical modellers, yet is closer in speed to coders based on the algorithms of Lempel and Ziv. Like Lempel and Ziv's algorithms, our algorithm decompresses faster than it compresses.