@moaaz said in The Huffman algorithm finds for?:

Optimal

If optimal is measured by average code word length, Huffman’s algorithm gives optimal codes, and the redundancy can be measured as the difference between the average code word length and Shannon’s entropy. If the objective function is replaced by an exponentially weighted average, then a simple modification of Huffman’s algorithm gives optimal codes. The redundancy can now be measured as the difference between this new average and Renyi’s generalization of Shannon’s entropy. By decreasing some of the codeword lengths in a Shannon code, the upper bound on the redundancy given in the standard proof of the noiseless source coding theorem is improved. The lower bound is improved by randomizing between codeword lengths, allowing linear programming techniques to be used on an integer programming problem. These bounds are shown to be asymptotically equal, providing a new proof of Kricevski’s results on the redundancy of Huffman codes. These results are generalized to the Renyi case and are related to Gallager’s bound on the redundancy of Huffman codes.