2011/07/14 by Keisuke Goto, Shirou Maruyama, Goto, Keisuke +9
Computer Science · Mathematics · #Algorithm #Algorithms and Data Compression #Artificial intelligence #Cellular Automata and Applications #Compression (physics) #Computer science #Data Structures and Algorithms (cs.DS) #Data compression #Decompression #Encoding (memory) #FOS: Computer and information sciences #Mathematics #Restructuring #String (physics) #cs.DS #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1107.2729
arxiv created 2011/07/14 · openalex publication_date 2011/07/14 · arxiv updated 2011/07/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the problem of \em restructuring compressed texts without explicit decompression. We present algorithms which allow conversions from compressed representations of a string T produced by any grammar-based compression algorithm, to representations produced by several specific compression algorithms including LZ77, LZ78, run length encoding, and some grammar based compression algorithms. These are the first algorithms that achieve running times polynomial in the size of the compressed input and output representations of T. Since most of the representations we consider can achieve exponential compression, our algorithms are theoretically faster in the worst case, than any algorithm which first decompresses the string for the conversion.