Algorithmic counting of nonequivalent compact Huffman codes

Abstract

Abstract It is known that the following five counting problems lead to the same integer sequence $${f_t}({n})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>f</mml:mi> <mml:mi>t</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> : the number of nonequivalent compact Huffman codes of length n over an alphabet of t letters, the number of “nonequivalent” complete rooted t -ary trees (level-greedy trees) with n leaves, the number of “proper” words (in the sense of Even and Lempel), the number of bounded degree sequences (in the sense of Komlós, Moser, and Nemetz), and the number of ways of writing $$\begin{aligned} 1= \frac{1}{t^{x_1}}+ \dots + \frac{1}{t^{x_n}} \end{aligned}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mtable> <mml:mtr> <mml:mtd> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>=</mml:mo> <mml:mfrac> <mml:mn>1</mml:mn> <mml:msup> <mml:mi>t</mml:mi> <mml:msub> <mml:mi>x</mml:mi> <mml:mn>1</mml:mn> </mml:msub> </mml:msup> </mml:mfrac> <mml:mo>+</mml:mo> <mml:mo>⋯</mml:mo> <mml:mo>+</mml:mo> <mml:mfrac> <mml:mn>1</mml:mn> <mml:msup> <mml:mi>t</mml:mi> <mml:msub> <mml:mi>x</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:msup> </mml:mfrac> </mml:mrow> </mml:mtd> </mml:mtr> </mml:mtable> </mml:mrow> </mml:math> with integers $$0 \le x_1 \le x_2 \le \dots \le x_n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>0</mml:mn> <mml:mo>≤</mml:mo> <mml:msub> <mml:mi>x</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mo>≤</mml:mo> <mml:msub> <mml:mi>x</mml:mi> <mml:mn>2</mml:mn> </mml:msub> <mml:mo>≤</mml:mo> <mml:mo>⋯</mml:mo> <mml:mo>≤</mml:mo> <mml:msub> <mml:mi>x</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:mrow> </mml:math> . In this work, we show that one can compute this sequence for all $$n&lt;N$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>&lt;</mml:mo> <mml:mi>N</mml:mi> </mml:mrow> </mml:math> with essentially one power series division. In total we need at most $$N^{1+\varepsilon }$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>N</mml:mi> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>+</mml:mo> <mml:mi>ε</mml:mi> </mml:mrow> </mml:msup> </mml:math> additions and multiplications of integers of cN bits (for a positive constant $$c&lt;1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>c</mml:mi> <mml:mo>&lt;</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> depending on t only) or $$N^{2+\varepsilon }$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>N</mml:mi> <mml:mrow> <mml:mn>2</mml:mn> <mml:mo>+</mml:mo> <mml:mi>ε</mml:mi> </mml:mrow> </mml:msup> </mml:math> bit operations, respectively, for any $$\varepsilon &gt;0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ε</mml:mi> <mml:mo>&gt;</mml:mo> <mml:mn>0</mml:mn> </mml:mrow> </mml:math> . This improves an earlier bound by Even and Lempel who needed $${O}({{N^3}})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>N</mml:mi> <mml:mn>3</mml:mn> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> operations in the integer ring or $$O({N^4})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>N</mml:mi> <mml:mn>4</mml:mn> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> bit operations, respectively.

Locations

• arXiv (Cornell University) - View - PDF
• DataCite API - View
• Applicable Algebra in Engineering Communication and Computing - View - PDF