Algorithmic counting of nonequivalent compact Huffman codes
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2019
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909351730479104 |
|---|---|
| author | Elsholtz, Christian Heuberger, Clemens Krenn, Daniel |
| author_facet | Elsholtz, Christian Heuberger, Clemens Krenn, Daniel |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1901_11343 |
| institution | arXiv |
| publishDate | 2019 |
| record_format | arxiv |
| spellingShingle | Algorithmic counting of nonequivalent compact Huffman codes Elsholtz, Christian Heuberger, Clemens Krenn, Daniel Combinatorics Computational Complexity Discrete Mathematics Symbolic Computation 05A15, 05C05, 05C30, 11D68, 68P30 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. |
| title | Algorithmic counting of nonequivalent compact Huffman codes |
| topic | Combinatorics Computational Complexity Discrete Mathematics Symbolic Computation 05A15, 05C05, 05C30, 11D68, 68P30 |
| url | https://arxiv.org/abs/1901.11343 |