Example
A coin collector has
-
four € coins of numismatic values , , and
respectively,
-
three € coins of numismatic values , and
respectively,
-
five € coins of numismatic values , , , and
respectively,
and wants to collect euros.
First, € coins are grouped two by two to form two packages of
€ with respective numismatic values and , dropping the
coin of numismatic value .
Then, these two packages are merged with the € coins and sorted.
Coins and packages of € are grouped, which produces two
€ packages of respective numismatic values and ,
disregarding the package of numismatic value .
Going on, these two packages are merged with the € coins and
sorted.
Finally, coins and packages of € are processed, which
gives three packages of respective numismatic values , and .
The picture illustrates the whole process.
The first two packages give the solution: euros composed of two
€ coins of numismatic values each; three € coins of
numismatic values , and ; and two € coins of numismatic
values and for a total numismatic value of .
|
Problem 100: Length-Limited Huffman Coding
|
|
Given the frequencies of alphabet letters, the Huffman algorithm builds an
optimal prefix code to encode the letters in such a way that encodings are as
short as possible.
In the general case there is no constraint on the length
of the codewords.
But sometimes one may want to bound the codeword length.
Building a code satisfying such a constraint is the subject of this problem.
The coin collector's problem is an example of where the constraint is used.
Collectors have coins with two independent properties: denominations
(currency values) and numismatic values (collector values).
Their goal is to
collect a sum while minimising the total numismatic value.
Let denominations be integer powers of : with .
Coins are organised as follows: there is a list for each denomination in
which coins are sorted in increasing order of their numismatic values.
The method consists in grouping adjacent coins two by two in the list of
smaller denominations, dropping the last coin if their number is odd.
The numismatic value of a package is the sum of numismatic values of the two
coins.
Newly formed packages are associated with the coins of the next
smallest denomination (sorted in increasing numismatic value).
The process is repeated until the list of coins of denomination
is processed.
Design an algorithm that computes for a list of frequencies an optimal
length-limited Huffman code in which no codeword is longer than and that
runs in time .
Reduce the problem to the binary coin collector's problem.
Algorithm PackageMerge implements the strategy described in the example
for a set of
coins with denominations between and .
Package groups two by two consecutive items of and
Merge merges two sorted lists.
Eventually, the first items of the list PackageMerge have the
lowest numismatic values and are selected to form the solution.
PackageMerge
1 for to do
2 list of coins of with denomination
3 sorted by increasing numismatic value
4 for downto do
7 return
\STATE \mbox{list of coins of } \mbox{ with denomination }
Both Package and Merge run in linear time according
to .
Thus, provided that the lists of coins are already sorted, the
algorithm PackageMerge runs in time and space .
References
J. Katajainen, A. Moffat, and A. Turpin. A fast and space-economical
algorithm for length-limited coding. In J. Staples, P. Eades, N. Katoh,
and A. Moffat, editors, Algorithms and Computation, 6th International
Symposium, ISAAC '95, Cairns, Australia, December 4-6, 1995,
Proceedings, volume 1004 of Lecture Notes in Computer Science, pages
12-21. Springer, 1995.
L. L. Larmore and D. S. Hirschberg. A fast algorithm for optimal lengthlimited
Huffman codes. J. ACM, 37(3):464-473, 1990.
B. Schieber. Computing a minimum weight-link path in graphs with the
concave Monge property. J. Algorithms, 29(2):204-222, 1998.
