solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看10026次
Algorithmic counting of nonequivalent compact Huffman codes. (arXiv:1901.11343v1 [math.CO])
来源于:arXiv
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= \frac{1}{t^{x_1}}+ \dots + \frac{1}{t^{x_n}}$ with integers
$0 \leq x_1 \leq x_2 \leq \dots \leq x_n$. In this work, we show that one can
compute this sequence for \textbf{all} $n<N$ with essentially one power series
division. In total we need at most $N^{1+\varepsilon}$ additions and
multiplications of integers of $cN$ bits, $c<1$, or $N^{2+\varepsilon}$ 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. 查看全文>>