2012/04/26 by Jérémy Barbay, Barbay, Jérémy
Computer Science · #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning and Algorithms #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1204.5801
openalex publication_date 2012/04/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We describe an algorithm computing an optimal prefix free code from N unsorted positive integer weights in time linear in the number of machine words holding those weights. This algorithm takes advantage of common non-algebraic instructions, and of specific results on optimal prefix free codes. This result improves over the state of the art complexities of O(N\lg N) in the algebraic decision tree model and O(N\lg\lg N) in the RAM model for the computation of Huffman's codes, a landmark in compression and coding since 1952.