Premium
Improvements to Burrows–Wheeler compression algorithm
Author(s) -
Deorowicz Sebastian
Publication year - 2000
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/1097-024x(20001110)30:13<1465::aid-spe345>3.0.co;2-d
Subject(s) - lossless compression , computer science , compression ratio , algorithm , data compression , compression (physics) , class (philosophy) , data compression ratio , image compression , artificial intelligence , engineering , materials science , automotive engineering , composite material , internal combustion engine , image (mathematics) , image processing
In 1994 Burrows and Wheeler presented a new algorithm for lossless data compression. The compression ratio that can be achieved using their algorithm is comparable with the best known other algorithms, whilst its complexity is relatively small. In this paper we explain the internals of this algorithm and discuss its various modifications that have been presented so far. Then we propose new improvements for its effectiveness. They allow us to obtain a compression ratio equal to 2.271 bpc for the Calgary Corpus files, which is the best result in the class of Burrows–Wheeler transform based algorithms. Copyright © 2000 John Wiley & Sons, Ltd.