The Burrows-Wheeler Transform (BWT) is an algorithm that rearranges the characters of a string into runs of similar characters. It is primarily used as a preprocessing step in data compression algorithms. The BWT is particularly effective when combined with other compression schemes, such as Move-To-Front encoding, Huffman coding, or arithmetic coding. ### Key Concepts 1. **Input**: The BWT takes a string of characters (often terminated with a unique end symbol) as input.
Articles by others on the same topic
The Burrows-Wheeler transform appends a unique smallest terminator to a string, sorts its cyclic rotations in lexicographic order, and records the last column. It is reversible because the first and last columns contain the same characters and the last-to-first mapping preserves the occurrence order of each character. The resulting letter arrangement supports both compression and backward search.[ref]
Opportunistic Data Structures with Applications by Paolo Ferragina and others. §2, Background: sorted cyclic shifts and inversion