2005/09/06 by Ahmed Belal, Belal, Ahmed, Amr Elmasry +1
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Genomics and Phylogenetic Studies #Information Theory (cs.IT)
paper · pdf · doi:10.48550/arxiv.cs/0509015
openalex publication_date 2005/09/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A new method for constructing minimum-redundancy binary prefix codes is\ndescribed. Our method does not explicitly build a Huffman tree; instead it uses\na property of optimal prefix codes to compute the codeword lengths\ncorresponding to the input weights. Let n be the number of weights and k be\nthe number of distinct codeword lengths as produced by the algorithm for the\noptimum codes. The running time of our algorithm is O(k \⋅ n). Following\nour previous work in citebe, no algorithm can possibly construct optimal\nprefix codes in o(k \⋅ n) time. When the given weights are presorted our\nalgorithm performs O(9k \⋅ \log2kn) comparisons.\n