Academic
Publications
A Fast and Space - Economical Algorithm for Length - Limited Coding

A Fast and Space - Economical Algorithm for Length - Limited Coding,10.1007/BFb0015404,Jyrki Katajainen,Alistair Moffat,Andrew Turpin

A Fast and Space - Economical Algorithm for Length - Limited Coding   (Citations: 16)
BibTex | RIS | RefWorks Download
The minimum-redundancy prefix code problem is to deter- mine a list of integer codeword lengths I = (li l i E {1... n}), given a list of n symbol weightsp = (pili C {1 .n}), such that ~'~ 2 -l' < 1, �9 " i=l -- n and ~i=1 lipi is minimised. An extension is the minimum-redundancy length-limited prefix code problem, in which the further constraint li < L is imposed, for all i C {1...n} and some integer L > (log 2 hi. The package-merge algorithm of Larmore and Hirschberg generates length- limited codes in O(nL) time using O(n) words of auxiliary space. Here we show how the size of the work space can be reduced to O(L2). This rep- resents a useful improvement, since for practical purposes L is O(log n).
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
Sort by: