2013/03/21 by Angeline Rao, Ying Liu, Rao, Angeline +5
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Algorithms and Data Compression #Error Correcting Code Techniques #FOS: Computer and information sciences #Information Theory (cs.IT) #Machine Learning in Bioinformatics #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.1303.5134
17 pages, 6 figures, 1 table data
arxiv created 2013/03/21 · openalex publication_date 2013/03/21 · arxiv updated 2013/03/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Huffman coding is a widely used method for lossless data compression because it optimally stores data based on how often the characters occur in Huffman trees. An n-ary Huffman tree is a connected, cycle-lacking graph where each vertex can have either n "children" vertices connecting to it, or 0 children. Vertices with 0 children are called leaves. We let hn(q) represent the total number of n-ary Huffman trees with q leaves. In this paper, we use a recursive method to generate upper and lower bounds on hn(q) and get h2(q) ≈ (0.1418532)(1.7941471)q+(0.0612410)(1.2795491)q for n=2. This matches the best results achieved by Elsholtz, Heuberger, and Prodinger in August 2011. Our approach reveals patterns in Huffman trees that we used in our analysis of the Binary-Ternary (BT) trees we created. Our research opens a completely new door in data compression by extending the study of Huffman trees to BT trees. Our study of BT trees paves the way for designing data-specific trees, minimizing possible wasted storage space from Huffman coding. We prove a recursive formula for the number of BT trees with q leaves. Furthermore, we provide analysis and further proofs to reach numeric bounds. Our discoveries have broad applications in computer data compression. These results also improve graphical representations of protein sequences that facilitate in-depth genome analysis used in researching evolutionary patterns.