A fast algorithm for optimal length-limited Huffman codes

Abstract

An O ( nL )-time algorithm is introduced for constructing an optimal Huffman code for a weighted alphabet of size n , where each code string must have length no greater than L . The algorithm uses O ( n ) space.