Optimal prefix codes with fewer distinct codeword lengths are faster to construct

摘要

A new method for constructing minimum-redundancy binary prefix codes is described. Our method does not explicitly build a Huffman tree; instead it uses a property of optimal prefix codes to compute the codeword lengths corresponding to the input weights. Let n be the number of weights and k be the number of distinct codeword lengths as produced by the algorithm for the optimal code. The running time of our algorithm is O (k . n). Following our previous work, no algorithm can possibly construct optimal prefix codes in o(k . n) time. If the given weights are presorted, our algorithm performs O (9(k) . log(2k) n) comparisons. (C) 2019 Elsevier Inc. All rights reserved.