2021/09/07 by Travis Gagie, Gagie, Travis
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 #Genomic variations and chromosomal abnormalities #Information Theory (cs.IT)
paper · pdf · doi:10.48550/arxiv.2109.02997
openalex publication_date 2021/09/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04
We give the first algorithm for adaptive alphabetic prefix-free coding that is worst-case optimal in terms of time and compression when σ∈ o ( \fracn1 / 2log n ), where σ is the size of the alphabet and n is the length of the input.