An optimal algorithm for the construction of optimal prefix codes with given fringe

The codeword lengths of a maximal prefix code with minimum length among those with a given number of codewords differ by at most one. This paper studies the length of the optimal maximal prefix code with a given number N of codewords and the additional constraint that the difference of the lengths of the longest and shortest codeword must be equal to a given parameter Δ. An optimal algorithm is given that, for all N and Δ, constructs an (N,Δ)-MPC of minimum length. Then a lower bound is given for the length of the optimal (N,Δ)-MPC for Δ⩽N/2