A fast algorithm for constructing nearly optimal prefix codes

摘要

Huffman algorithm allows for constructing optimal prefix-codes with O(nlogn) complexity. As the number of symbols ngrows, 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 (c) 2015 John Wiley & Sons, Ltd.