An efficient algorithm for constructing nearly optimal prefix codes
Kurt Mehlhorn · IEEE Transactions on Information Theory · 1980
A new algorithm is presented for constructing nearly optimal prefix codes in the case of unequal letter costs and unequal probabilities. A bound on the maximal deviation from the optimum is derived and numerical examples are given. The algorithm has running timeO(t \cdot n), wheretis the number of letters andnis the number of probabilities.