Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site water.UUCP
Path: utzoo!watmath!watnot!water!ylfink
From: ylfink@water.UUCP (ylfink)
Newsgroups: ont.events
Subject: UW Data Struc. Semi., Prof. Brown on "Design and Analysis of Dynamic Huffman Coding".
Message-ID: <152@water.UUCP>
Date: Wed, 8-Jan-86 15:07:24 EST
Article-I.D.: water.152
Posted: Wed Jan  8 15:07:24 1986
Date-Received: Wed, 8-Jan-86 23:30:48 EST
Expires: Fri, 10-Jan-86 00:00:00 EST
Organization: U of Waterloo, Ontario
Lines: 36


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.