Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(2)
Prefix Code
Time Use
Related Publications
(3)
SpaceEfficient Construction of Optimal Prefix Codes
Practical Lengthlimited Coding for Large Alphabets
A fast algorithm for optimal lengthlimited Huffman codes
Subscribe
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
Edit
A Fast and Space  Economical Algorithm for Length  Limited Coding
(
Citations: 16
)
BibTex

RIS

RefWorks
Download
Jyrki Katajainen
,
Alistair Moffat
,
Andrew Turpin
The minimumredundancy
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 minimumredundancy lengthlimited
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 packagemerge 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).
Conference:
International Symposium on Algorithms and Computation  ISAAC
, pp. 1221, 1995
DOI:
10.1007/BFb0015404
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.
(
www.springerlink.com
)
(
www.springerlink.com
)
(
www.informatik.unitrier.de
)
Citation Context
(10)
...Following Katajainen et al. [
8
], we call the items which participate in code construction the active items...
...A more important tradeoff between time and space is the LazyPM algorithm of Katajainen et al. [
8
]...
Mike Liddell
,
et al.
Incremental Calculation of MinimumRedundancy LengthRestricted Codes
...These and other similar optimizations have been done in the past for the special case '(�) = �, lmin = 0, D =
2
[16]‐ [20], though we will not address or extend such improvements here...
Michael B. Baer
.
Dary BoundedLength Huffman Coding
...techniques of Moffat (with others) in [
30
]‐[34]...
Michael B. Baer
.
Source Coding for Quasiarithmetic Penalties
...These and other similar optimizati ons have been done in the past for the special case ϕ(δ) = δ, lmin = 0, D = 2 [
24
], [33], [36], [42], [43], though we do not address or extend such improvements here...
...Special cases (e.g., lmax ≈ logD n for ϕ(δ) = δ, lmin = 0, and D = 2) can be addressed using modifications of the PackageMerge approach [
24
], [33], [36], [42], [43]...
Michael B. Baer
.
Twenty (or so) Questions: $D$ary LengthBounded Prefix Coding
...Katajainen et al. [
14
] proposed a lazy implementation of this algorithm that runs in time and requires only additional space...
...It is worth mentioning that the quadratic additional space usage of the Lazy PackageMerge algorithm for the lengthrestricted code problem is also due to simultaneously maintaining one list of counters per level [
14
]...
Ruy Luiz Milidiú
,
et al.
Three spaceeconomical algorithms for calculating minimumredundancy p...
References
(9)
Path Length of Binary Search Trees
(
Citations: 22
)
T. C. Hu
,
K. C. Tan
Journal:
Siam Journal on Applied Mathematics  SIAMAM
, vol. 22, no. 2, 1972
A method for the construction of minimumredundancy codes
(
Citations: 1340
)
David A. Huffman
Journal:
Resonance
, vol. 11, no. 2, pp. 9199, 2006
A fast algorithm for optimal lengthlimited Huffman codes
(
Citations: 56
)
Lawrence L. Larmore
,
Daniel S. Hirschberg
Journal:
Journal of The ACM  JACM
, vol. 37, no. 3, pp. 464473, 1990
Constructing Huffman Trees in Parallel
(
Citations: 17
)
Lawrence L. Larmore
,
Teresa M. Przytycka
Journal:
Siam Journal on Computing  SIAMCOMP
, vol. 24, no. 6, pp. 11631169, 1995
InPlace Calculation of MinimumRedundancy Codes
(
Citations: 30
)
Alistair Moffat
,
Jyrki Katajainen
Conference:
Workshop on Algorithms and Data Structures  WADS
, pp. 393402, 1995
Sort by:
Citations
(16)
Incremental Calculation of MinimumRedundancy LengthRestricted Codes
Mike Liddell
,
Alistair Moffat
Journal:
IEEE Transactions on Communications  TCOM
, vol. 55, no. 3, pp. 427435, 2007
Dary BoundedLength Huffman Coding
Michael B. Baer
Journal:
Computing Research Repository  CORR
, vol. abs/cs/070, 2007
Source Coding for Quasiarithmetic Penalties
(
Citations: 7
)
Michael B. Baer
Journal:
IEEE Transactions on Information Theory  TIT
, vol. 52, no. 10, pp. 43804393, 2006
Twenty (or so) Questions: $D$ary LengthBounded Prefix Coding
Michael B. Baer
Journal:
Computing Research Repository  CORR
, vol. abs/cs/060, 2006
Source Coding for Quasiarithmetic Penalties
Michael B. Baer
Journal:
Computing Research Repository  CORR
, vol. abs/cs/050, 2005