ylfink@water.UUCP (ylfink) (01/08/86)
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
DATA STRUCTURING SEMINAR
- Thursday, January 9, 1986.
Dr. Jeffrey S. Vitter of Brown University will speak on
``Design and Analysis of Dynamic Huffman Coding''.
TIME: 3:30 PM
ROOM: MC 5158
ABSTRACT
We introduce an efficient new algorithm for dynamic
Huffman coding, called Algorithm V. It performs one-
pass coding and transmission in real-time, and uses at
most one more bit per letter than does the standard
two-pass Huffman algorithm; this is optimum in the
worst case among all one-pass schemes. We may analyze
the dynamic Huffman algorithm due to Faller, Gallager,
and Knuth. In each algorithm, both the sender and the
receiver maintain equivalent dynamically varying Huff-
man trees. The processing time required to encode and
decode a letter whose node in the dynamic Huffman tree
is currently on the lth level is O(l); hence, the pro-
- - -
cessing can be done in real time. Empirical tests show
that Algorithm V performs quite well in practice, often
better than the two-pass method. The proposed algo-
rithm is well-suited for file compression and online
encoding/decoding in data networks.