Dynamic Length-Restricted Coding
Travis Gagie · TSpace (University of Toronto) · 2003
Suppose that S is a string of length m drawn from an alphabet of n characters, d of which occur in S. Let P be the relative frequency distribution of characters in S. We present a new algorithm for dynamic coding that uses at most [lg n] + 1 bits to encode each character in S; fewer than (H(P) + 4.5)m + d lg n bits overall, where H is Shannon's entropy function; and O ((H ( P) + 1)m + d log2 n) time to encode and decode. This algorithm does not require P to be known before it encodes S. We extend recent results by Evans and Kirkpatrick for restructuring binary trees. In particular, we present a new algorithm for constructing node-oriented alphabetic minimax trees. We also describe how to efficiently implement an abstract data type that stores a dynamic list of non-negative integers and supports an operation to determine whether there exists a binary tree on nodes of those depths.