A fast and space-economical algorithm for length-limited coding

Abstract

The minimum-redundancy prefix code problem is to determine a list of integer codeword lengths l = [li | i ϵ {1… n}], given a list of n symbol weights p = [p; | i ϵ {1… n}], such that [formula presented] 2-li ≤ 1, and [formula presentd] lipi is minimised. An extension is the minimum-redundancy length-limited prefix code problem, in which the further constraint U < L is imposed, for all i 6 {1… n) and some integer L ≥ [log2a]. The package-merge algorithm of Larmore and Hirschberg generates length- limited codes in O(nL) time using O(nL) words of auxiliary space. Here we show how the size of the work space can be reduced to O(L2). This represents a useful improvement, since for practical purpos..