Definition: Rearrange a string so repeated substrings lead to repeated characters in the rearranged string, which is easier to compress. Knowing which character was last in the original string, the original can be reconstructed from the rearranged string.
Also known as BWT.
Aggregate child (... is a part of or used in me.)
Wikipedia entry for Burrows-Wheeler transform.
Michael Burrows and David J. Wheeler, A Block-sorting Lossless Data Compression Algorithm, Research Report SRC-124, Digital Equipment Corporation, Palo Alto, California, May 1994.
This transform is algorithm C in the paper.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 14 August 2008.
HTML page formatted Tue Dec 6 16:16:32 2011.
Cite this as:
Paul E. Black, "Burrows-Wheeler transform", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 14 August 2008. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/burrowsWheelerTransform.html