
The following pseudocode gives a simple but inefficient way to calculate the BWT and its inverse. It assumes that the input string function BWT (string s) create a table, rows are all possible rotations of s sort rows alphabetically return (last column of the table) function inverseBWT (string s) create empty table repeat length(s) times insert s as a column of table before first column of the table // first insert creates first column sort rows of the table alphabetically return (row that ends with the 'EOF' character) To understand why this creates moreeasilycompressible data, let's consider transforming a long English text frequently containing the word "the". Sorting the rotations of this text will often group rotations starting with "he " together, and the last character of that rotation (which is also the character before the "he ") will usually be "t", so the result of the transform would contain a number of "t" characters along with the perhaps lesscommon exceptions (such as if it contains "Brahe ") mixed in. So it can be seen that the success of this transform depends upon one value having a high probability of occurring before a sequence, so that in general it needs fairly long samples (a few kilobytes at least) of appropriate data (such as text). The remarkable thing about the BWT is not that it generates a more easily encoded output—an ordinary sort would do that—but that it is reversible, allowing the original document to be regenerated from the last column data. The inverse can be understood this way. Take the final table in the BWT algorithm, and erase all but the last column. Given only this information, you can easily reconstruct the first column. The last column tells you all the characters in the text, so just sort these characters to get the first column. Then, the first and last columns together give you all pairs of successive characters in the document, where pairs are taken cyclically so that the last and first character form a pair. Sorting the list of pairs gives the first and second columns. Continuing in this manner, you can reconstruct the entire list. Then, the row with the "end of file" character at the end is the original text. Reversing the example above is done like this:
[edit] OptimizationA number of optimizations can make these algorithms run more efficiently without changing the output. In BWT, there is no need to represent the table in either the encoder or decoder. In the encoder, each row of the table can be represented by a single pointer into the strings, and the sort performed using the indices. Some care must be taken to ensure that the sort does not exhibit bad worstcase behavior: Standard library sort functions are unlikely to be appropriate. In the decoder, there is also no need to store the table, and in fact no sort is needed at all. In time proportional to the alphabet size and string length, the decoded string may be generated one character at a time from right to left. A "character" in the algorithm can be a byte, or a bit, or any other convenient size. There is no need to have an actual 'EOF' character. Instead, a pointer can be used that remembers where in a string the 'EOF' would be if it existed. In this approach, the output of the BWT must include both the transformed string, and the final value of the pointer. That means the BWT does expand its input slightly. The inverse transform then shrinks it back down to the original size: it is given a string and a pointer, and returns just a string. A complete description of the algorithms can be found in Burrows and Wheeler's paper, or in a number of online sources. [edit] Bijective variantSince any rotation of the input string will lead to the same transformed string, the BWT cannot be inverted without adding an 'EOF' marker to the input or, augmenting the output with information, such as an index, that makes it possible to identify the input string from the class of all of its rotations. There is a bijective version of the transform, by which the transformed string uniquely identifies the original. In this version, every string has a unique inverse of the same length. The bijective transform is computed by first factoring the input into Lyndon words, and then sorting together all rotations of these words. The transformed string is then obtained by picking the last character of the strings in this sorted list. For example, applying the bijective transform gives: 
related documents 
Selection sort 
Naive Bayes classifier 
Affine transformation 
Minimum spanning tree 
Befunge 
Grover's algorithm 
Scientific notation 
Shell sort 
Curve 
Tree automaton 
Brute force attack 
Cyclic group 
Rootfinding algorithm 
Symmetric matrix 
Normal space 
Analytic function 
Tangent space 
Topological vector space 
MathML 
A* search algorithm 
Uniform convergence 
Universal quantification 
Free group 
Orthogonality 
Lexical analysis 
Burnside's problem 
Embedding 
Octonion 
Optimization (mathematics) 
Sufficiency (statistics) 