A fast algorithm for constructing nearly optimal prefix codes. (3rd November 2015)

• Record Type: Journal Article
• Authors: Osorio, Roberto R.; González, Patricia
• Is Part Of: Software, practice & experience. Volume 46:Number 10(2016)
• Page Start: 1299
• Page End: 1316
• Publication Date: 2015-11-03
• Subjects: data compression -- prefix‐codes -- Huffman algorithm; Computer software -- Periodicals; Computer programming -- Periodicals; Computer programs -- Periodicals; 005.3
• DOI: 10.1002/spe.2375
• Languages: English
• ISSNs: 0038-0644

Abstract

Summary: Huffman algorithm allows for constructing optimal prefix‐codes with O ( n · l o g n ) complexity. As the number of symbols n grows, so does the complexity of building the code‐words. In this paper, a new algorithm and implementation are proposed that achieve nearly optimal coding without sorting the probabilities or building a tree of codes. The complexity is proportional to the maximum code length, making the algorithm especially attractive for large alphabets. The focus is put on achieving almost optimal coding with a fast implementation, suitable for real‐time compression of large volumes of data. A practical case example about checkpoint files compression is presented, providing encouraging results. Copyright © 2015 John Wiley & Sons, Ltd.