Premium
Post BWT stages of the Burrows–Wheeler compression algorithm
Author(s) -
Abel Jürgen
Publication year - 2010
Publication title -
software: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.437
H-Index - 70
eISSN - 1097-024X
pISSN - 0038-0644
DOI - 10.1002/spe.982
Subject(s) - lossless compression , algorithm , computer science , data compression , entropy encoding , compression (physics) , context (archaeology) , permutation (music) , entropy (arrow of time) , alphabet , image compression , speech recognition , artificial intelligence , image (mathematics) , history , linguistics , image processing , art , materials science , physics , archaeology , quantum mechanics , composite material , philosophy , aesthetics
The lossless Burrows–Wheeler compression algorithm has received considerable attention over recent years for both its simplicity and effectiveness. It is based on a permutation of the input sequence—the Burrows–Wheeler transformation (BWT)—which groups symbols with a similar context close together. In the original version, this permutation was followed by a Move‐To‐Front transformation and a final entropy coding stage. Later versions used different algorithms, placed after the BWT, since the following stages have a significant influence on the compression rate. This paper describes different algorithms and improvements for these post BWT stages including a new context‐based approach. The results for compression rates are presented together with compression and decompression times on the Calgary corpus, the Canterbury corpus, the large Canterbury corpus and the Lukas 2D 16‐bit medical image corpus. Copyright © 2010 John Wiley & Sons, Ltd.