Premium
A fast algorithm for constructing nearly optimal prefix codes
Author(s) -
Osorio Roberto R.,
González Patricia
Publication year - 2016
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.2375
Subject(s) - huffman coding , prefix code , computer science , algorithm , prefix , sorting , coding (social sciences) , code (set theory) , fountain code , data compression , focus (optics) , time complexity , theoretical computer science , block code , linear code , mathematics , decoding methods , programming language , linguistics , philosophy , statistics , physics , set (abstract data type) , optics
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.