Burrows-Wheeler Transform Algorithm

The Burrows-Wheeler transform rearranges the characters of a string into runs of similar characters by forming every cyclic rotation of the string, sorting those rotations lexicographically, and taking the last column of the resulting sorted arrangement as the transformed output, a process that is reversible given the original string's position among the sorted rotations. Because the transform tends to group identical or similar characters together, the transformed output typically compresses far better with simple techniques such as run-length encoding than the original string does. Michael Burrows and David Wheeler described the transform in a 1994 technical report, and it underlies the bzip2 compression program and file-indexing structures such as the FM-index used in DNA sequence alignment tools.