2015/04/10 by Johannes Fischer, I Tomohiro, Fischer, Johannes +3
Computer Science · #Algorithms and Data Compression #Cellular Automata and Applications #Coding theory and cryptography #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1504.02605
openalex publication_date 2015/04/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For both the Lempel Ziv 77- and 78-factorization we propose algorithms generating the respective factorization using (1+ε) n \lg n + O(n) bits (for any positive constant ε≤ 1) working space (including the space for the output) for any text of size $n$ over an integer alphabet in O(n / ε2) time.