2016/05/21 by Antonio Fariña, Travis Gagie, Fariña, Antonio +9
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 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1605.06615
openalex publication_date 2016/05/21 · openalex created_date 2022/08/14 · openalex updated_date 2026/08/01
For many kinds of prefix-free codes there are efficient and compact alternatives to the traditional tree-based representation. Since these put the codes into canonical form, however, they can only be used when we can choose the order in which codewords are assigned to symbols. In this paper we first show how, given a probability distribution over an alphabet of σ symbols, we can store an optimal alphabetic prefix-free code in \Ohσlog L bits such that we can encode and decode any codeword of length ℓ in \Ohmin (ℓ, log L) time, where L is the maximum codeword length. With \Oh2Lε further bits, for any constant ε>0, we can encode and decode \Ohlog ℓ time. We then show how to store a nearly optimal alphabetic prefix-free code in \(o (σ)\) bits such that we can encode and decode in constant time. We also consider a kind of optimal prefix-free code introduced recently where the codewords' lengths are non-decreasing if arranged in lexicographic order of their reverses. We reduce their storage space to \Ohσlog L while maintaining encoding and decoding times in \Ohℓ. We also show how, with \Oh2εL further bits, we can encode and decode in constant time. All of our results hold in the word-RAM model.