Algorithmic counting of nonequivalent compact Huffman codes

Abstract: It is known that the following five counting problems lead to the same integer sequence~

f_{t} (n)

: the number of nonequivalent compact Huffman codes of length~

n

over an alphabet of

t

letters, the number of `nonequivalent' canonical rooted

t

-ary trees (level-greedy trees) with

n

~leaves, the number of `proper' words, the number of bounded degree sequences, and the number of ways of writing

1 = f r a c 1 t^{x_{1}} + d o t s + f r a c 1 t^{x_{n}}

with integers

0 l e q x_{1} l e q x_{2} l e q d o t s l e q x_{n}

. In this work, we show that one can compute this sequence for extbf{all}

n < N

with essentially one power series division. In total we need at most

N^{1 + v a r e p s i l o n}

additions and multiplications of integers of

c N

bits,

c < 1

, or

N^{2 + v a r e p s i l o n}

bit operations, respectively. This improves an earlier bound by Even and Lempel who needed

O (N^{3})

operations in the integer ring or

O (N^{4})

bit operations, respectively.

This page was built for publication: Algorithmic counting of nonequivalent compact Huffman codes