Co-sponsored by DIMACS and the IEEE Information Theory Society.
1.
Julia Abrahams, Rutgers University
Tutorial - Huffman Code Trees and Problem Variants:
Some Open Questions
Huffman code trees will be reviewed as the solution to the
minimum-average-codeword-length coding problem, and also as the
solution to the minimum-average-number-of-tests sequential
diagnosis or search problem. Variants of the underlying "word
problem" which impose costs or constraints on the paths through
the tree tend to arise in coding problems while costs or constraints
on the interior nodes of the tree tend to arise in testing problems,
although some variants are plausible problems of interest in both
contexts. Several examples of problem variants will be categorized
as instances of constrained Huffman problems or as examples of
Huffman problems with an imposed cost structure.
In order for a Huffman variant problem to be considered resolved,
we would like to have a parsimonious characterization of the set
of candidate trees, an entropy-type bound on the cost of the optimal
tree, and an efficient algorithm for the construction of the optimal
tree. Particular problems which are open in this sense include the
case that partial order constraints are imposed on the leaf nodes
of the tree, the case that the edges in the paths through the tree
occur according to a finite state cost model, and the case in which
costs are associated with setting up distinct tests. These three
examples will be presented in some detail as research challenges.
2.
Joy Thomas, IBM
Huffman Algebras
In this talk we define a class of two operator algebras for which the
Huffman algorithm is optimal, based on a rearrangement inequality by
Hardy, Littlewood and Polya. These algebras, called Huffman algebras,
include both real numbers and independent random variables. Many
examples of such algebras are given. For the case with random weights
of the leaves, we prove the optimality of the tree constructed by the
power of two rule, i.e., the Huffman algorithm assuming identical
weights, when the weights of the leaves are independent and
identically distributed. As a natural extension of our algebras, we
consider tree extensions, and derive an equivalent of entropy for some
of the algebras considered in the talk. Applications of these
algebras include not only the source coding problem, but also circuit
design and scheduling in parallel computers. (Joint work with C.S. Chang)
3.
Kingo Kobayashi, University of Electro Communications
Coding of Trees: From the Information-Theoretic Point of View
The tree structure has often played central roles in both computer
science and information theory. Various expressions for several
classes of trees have been devised in computer science. We can
compare these expressions by the efficiency of "coding" which is
an important concept of information theory. Here, from the coding
point of view, we give some results on the expression of trees.
4.
Lawrence L. Larmore, University of Nevada - Las Vegas
Optimal Trees and the Monge Property
In several cases, it is possible to reduce the problem of finding
an optimal tree to a seemingly unrelated problem in which the Monge
property applies. The first and simplest example is the reduction
of the Huffman coding problem to the concave least weight subsequence
problem. Although in this one simplest case no speedup is achieved,
it is nevertheless instructive. When the technique is extended to more
complex problems, there is typically a speedup of an order of magnitude.
5.
Rudolf Fleischer, Max-Planck Institut Saarbrucken
Self-Organizing Data Structures and Compression: A Survey
Self-organizing data structures like linear lists (with the Move-to-Front
rule, for example) or Splay Trees have been proposed to be used in
efficient implementations of encoders in compression algorithms. But
they can also be used directly to encode data yielding good compression
rates, in particular if used together with the Burrows-Wheeler transform.
In this talk, I will give a short survey on self-organizing lists and
Splay Trees, and how these data structures can be used for data
compression.
6.
Mike Fredman, Rutgers University
(with David M. Cohen, IDA)
Weighted Binary Trees for Concurrent Searching
A traditional cost measure for binary search trees is given by
weighted path length, which measures the expected cost of a single
random search. In this paper we investigate a generalization, the
k-cost, which is suitable for applications involving independent
parallel processors each utilizing a common search tree. The k-cost
is defined to be the expected value of the maximum length of the
search paths encountered during the course of k independently
performed random searches. For example, if k = 1, then the k-cost
represents the traditional weighted path length.
Our results include efficient algorithms for constructing binary
search trees having near optimal k-cost. An interesting feature
of one of our algorithms concerns the fact that it constructs a
search tree that simultaneously has near optimal k-cost for all k;
in fact, the structure of this tree is determined only by the order
permutation of the sequence of probability weights that are to be
assigned to the tree nodes. This stands in contrast to an example
which shows that a tree which is precisely optimal relative to
weighted path length (1-cost) can have k-cost which is exponentially
greater than the k-cost of the optimal tree.
7.
Bob Sedgewick, Princeton University
Is Quicksort Optimal?
This talk describes some relatively bold theoretical results
and some relatively new practical implementations that imply
tight relationships between the number of comparisons used by
a properly implemented Quicksort and the entropy of the set of
keys being sorted.
9.
Veronique Bruyere, University of Mons-Hainaut Le Pentagone
Tutorial - Codes: A Language Theoretic Approach
The topic of this tutorial is the theory of variable-length codes.
This theory was initiated by Schutzenberger in the fifties. It takes
its origin in the coding and information theory developed by Shannon.
In the first part of the tutorial, we survey the definitions and
basic results about codes, with an emphasis on the interconnections
with finite automata.
In the second part, we discuss some of the results recently obtained
in this direction together with some open problems, that might be
interesting for the information theory community and the algorithms
community. When the proofs are simple, we expose them in a way that
the audience has a flavor on the tools used in this domain.
9.
Dominique Perrin, Universite de Marne-la-Vallee
Bifix Codes
Bifix codes are codes which have the prefix property in both
directions. Many interesting -and not widely known - results hold
for this particular class of prefix codes introduced long ago by
Gilbert and Moore and by Schutzenberger. In this talk, I will present
several constructions allowing to embed a bifix code into a maximal
one. The results are due to Zhang and Shen (1995) and to Veronique
Bruyere and myself.
10.
Ian Munro, Waterloo
(with Venatesh Raman)
Succinct Tree Representations for Fast Navigation
We consider applications of large, mostly static, tree structures and
the implementation of abstract data types for the objects: binary tree,
rooted ordered tree and balanced parenthesis expression. We review a
number of representations, and present some new ones, that use an amount
of space within a lower order term of the information theoretic minimum
and support, in constant time, a rich set of navigational operations.
In the case of binary trees, for instance, we can move from a node to
its left or right child or to the parent in constant time while retaining
knowledge of the size of the subtree at which we are positioned.
11.
Erik D. Demaine, Waterloo
(with Ian Munro and Alex Lopez-Ortiz, University of New Brunswick)
Adaptive Computation of the Intersection of a Collection of Sets
This talk discusses the problem of computing the intersection of a
collection of sets, which is motived by the goal of efficiently
evaluating boolean queries in text retrieval systems. An optimal
adaptive algorithm is proposed to solve this problem. Information
theory is an important tool for analyzing this algorithm. In
particular, we study sets of comparisons that prove correctness of
an answer, and study optimal binary encodings of such proofs. The
lengths of these encodings form an information theoretic lower bound.
We present matching upper and lower bounds on the worst-case running
time with respect to the information theoretic lower bound.
12.
Stott Parker, UCLA
The Construction of Huffman Codes is a Submodular ('Convex')
Problem Over a Lattice of Binary Trees
We show that the space of all binary Huffman codes for a finite
alphabet defines a lattice, ordered by the imbalance of the code
trees. Representing code trees as path-length sequences, we show that
the imbalance ordering is closely related to a majorization ordering on
real-valued sequences that correspond to discrete probability density
functions. Furthermore, this tree imbalance is a partial ordering that
is consistent with the total orderings given by either the external
path length (sum of tree path lengths), or the entropy determined by
the tree structure. On the imbalance lattice, we show the weighted
path-length of a tree (the usual objective function for Huffman coding)
is a submodular function, as is the corresponding function on the
majorization lattice. Submodular functions are discrete analogues of
convex functions. These results give perspective on Huffman coding,
and suggest new approaches to coding as optimization over a lattice.
13.
Mihai Sipitca, Georgia Tech
(with David Gillman)
Lossless Encoding of DCT Coefficients for Video Compression
The last stage of many image or video coders is to losslessly encode
an orthogonal transformation of an image or a residual image,
after the transformed image has been quantized, or reduced in numerical
precision. Traditionally, image and video coders use a fixed table for
entropy coding the tokens that represent the quantized transform
coefficients. However, the characteristics of images are
highly non-stationary, i.e., different portions of images and different
images have different statistics which would require different entropy
coding tables for a more efficient encoding.
In our presentation, we will investigate the improvement obtained when
using multiple entropy tables instead of one. Issues addressed include:
1) choosing the variance as the characteristic of a block,
2) table compaction - keeping the memory requirements reasonable at a
minimum coding efficiency cost,
3) presenting the trade-off between memory requirements and the coding
efficiency improvement.
The results presented were obtained for resolutions between SIF
(similar to VHS) and CCIR-601 (broadcast TV). Future work is going to
target the low bit rate range.
14.
Sajal Das, U. North Texas
(with Amiya Bhattacharya)
Predictive Location Management Using Lossless Compression
A user in a cellular or PCS system, while enjoying the freedom to
be mobile, creates an uncertainty about the exact location of the
registered mobile terminal being carried. The system has to search
for the mobile against this uncertainty, to ensure a successful call
delivery within a time constarint. The collector network deployed is
usually organized in the form of a three-tier tree like hierarchy,
viz. with a mobile switching exchange at the root, a number of base
station controllers at the second tier, and several base stations as
leaves at the third tier. Each base station is dedicated to handle
the air-link within one cell.
On a call arrival, the search for the target mobile is inititaed by
the system by paging or polling the cells where the user can possibly
be found. Paging messages originate from mobile switching exchange and
when it reaches a base station, it is broadcast so that the target
mobile can respond if present. To limit the level of uncertainty, the
mobile can report its position from time to time. This mobile-initiated
reporting is called a location update or registration. Both paging and
update contribute to the location management cost, and the location
management problem aims at minimizing this total cost. Any more message
exchange than necessary would lead to wastage of valuable resources such
as wireless bandwidth and mobile equipment power, in effect increasing
the operational cost that the user has to bear.
In this paper, we propose a predictive location management technique
that makes use of path updates as opposed to the widely used position
updates. To enhance predictability, the mobility profile for each mobile
user must be built in the system database. For this, the path traced by
the user in the past needs to be made completely known to the system.
The cost minimization can come out of achieving this information exchange
in its information theoretic limit. The technique evolves out of the
mapping of the user's trail onto a string, as reducing the location
management cost translates to lossless compression of this string. The
compressibility of the fixed-to-variable length encoding of the acclaimed
Lempel-Ziv family of algorithms reduce the update cost, whereas their
built-in predictive power can be effectively used to reduce paging cost.
What we end up with is a family of adaptive on-line algorithms, which are
asymptotically optimal if the user mobility can be modeled as an ergodic
source. We discuss the underlying data structures used for building the
profile on the fly, and how good paging strategies can be designed based on
the profile. We take into consideration the limit on the memory available
on a mobile terminal for executing the proposed class of algorithms.
15.
Yuriy Reznik, RealNetworks
On Compact Level Partitioning of Digital Trees
A modification of digital tree structure is proposed that supports
non-uniform distribution of digits between levels (i.e. each
level may have nodes of different size). We call this distribution
of digits - level partitioning, and the resulting data structure -
LP-tree. We study general properties of LP-trees, and develop an
algorithm that for any given binary tree constructs an adequate
LP-tree that uses minimum amount of memory. We call the resulting
trees - compact LP-trees, and perform detailed analysis of their
properties. It turns out that, on average, the compact LP-tree uses
approximately 20.65% less memory than a binary tree, and even more
importantly, the average complexity of the successful search in
such a tree is O(1) (vs. O(log N) for the standard binary trie).
16.
Mamoru Hoshi, University of Electro Communications
Homophonic Coding by the Algorithm: Preliminary Considerations
We shall show that the idea of the successive refinement
of interval partitions, which plays the key role in the interval
algorithm for random number generation [Han and Hoshi], is directly
applicable also to the homophonic coding.
We propose an efficient and very simple algorithm for homophonic coding
which produces an i.i.d. sequence. The lower and upper bounds for the
expected length of the code generated by the algorithm are given.
In a special case, the expected length of the code generated by the
algorithm is bounded by H(X)/log M + 3, where H(X) is the entropy of a
source X. Homophonic coding with cost is also discussed.
17.
Andrej Brodnik, Lulea Technical University and IMFM,
and Svante Carlsson, Lulea Technical University
Sub-Linear Huffman Decoding: Some Theoretical and Practical Results
In the first part of our presentation we describe a succinct data
structure storing the Huffman encoding that permits sub-linear
decoding in the number of transmitted bits ([BroCar98]). The size of
the extra storage except for the storage of the symbols in the
alphabet for the new data structure is
O(l log N) bits,
where l is the longest Huffman code and N is the number of symbols in
the alphabet. Similar solution was independently presented by Moffat
and Turpin ([MofTur97]).
We use the presented data structure to describe two different decoding
algorithms -- one running in time O(l') and the other in O(log l'),
where l' is a number of distinct lengths of Huffman codes. We proceed
by showing that our algorithm decodes Huffman codes on average in time
O(log log N) for any probability distribution.
In the second part we present practical results obtained from the
implementation of the described algorithms. We show that with such an
efficient decoding algorithm, handling of the input stream of bits
(Huffman codes) becomes as expensive as the decoding itself.
To improve the latter we developed a more detail machine model which
better captures the memory hierarchy. The model was influenced by the
work on the external memory data structures (eg. [Arge96,ArgVit96]).
We conclude the presentation with some comments and open questions
related to the dynamic Huffman encoding ([Vitter87]).
The presented algorithms will be used in the fall release of the
``Phone Book of Slovenia'' ([PhBook]).
References
----------
[Arge96] L. Arge. Efficient External-Memory Data Structures and
Applications. PhD thesis, University of {\AA}rhus, 1996.
[ArgVit96] L. Arge and J.S. Vitter. Optimal dynamic interval
management in external memory. In 37\Th FOCS, 1996.
[BroCar98] A. Brodnik and S. Carlsson. Sub-linear Decoding of Huffman
Codes Almost In-Place IMFM, Technical Report IMFM-(1998)-PS-600.
(ftp://www.ijp.si/pub/preprints/ps/98/pp600.ps)
[MofTur97] A. Moffat and A. Turpin. On implementation of minimum
redundancy prefix codes. IEEE Transactions on Communications,
45(10):1200--1207, 1997.
[Vitter87] J.S. Vitter. Design and analysis of dynamic Huffman
codes. JACM, 34(4):825--845, October 1987.
[PhBook] Telekom Slovenije & ADACTA. Telefonski imenik Slovenije. URL:
http://tis.telekom.si.
Other Workshops
DIMACS Homepage