A fast algorithm for constructing nearly optimal prefix codes. (3rd November 2015) - Osorio, Roberto R.; González, Patricia
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.