The Burrows-Wheeler Transform: Data Compression, Suffix Arrays, and Pattern Matching

摘要

David Wheeler and Mike Burrows introduced the Burrows-Wheeler Transform (BWT) as a practical method of data compression in 1994. The elegant simplicity of the BWT has captivated researchers for the past decade. The BWT is simple yet powerful. Other lossless compression techniques are a lot more cumbersome, making it difficult to assess their efficiency. Lossless compression is the preferred method of conserving space in text files. Audio and video files are typically compressed with lossy compression mechanisms since some content can be eliminated without noticeably compromising the quality of compressed data. The Burrows-Wheeler Transform presents an innovative approach to data compression. The transform is simply a permutation of the original data. This unique permutation makes it easier to process the data. Since the Burrows-Wheeler Transform is easily reversed, it lies at the basis of lossless compression techniques. The nature of the transform allows the transformed data to readily be compacted by a variety of compression techniques. Among them are run-length and move-to-front encoding.