Application of Lempel-Ziv factorization to the approximation of grammar-based compression.

DOI10.1016/S0304-3975(02)00777-6zbMath1051.68088OpenAlexW1973608346MaRDI QIDQ1401326

Publication date: 17 August 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(02)00777-6

zbMATH Keywords

AVL-grammar AVL-tree LZ-compression Minimal grammar

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Related Items

Block graphs in practice ⋮ Comparison of LZ77-type parsings ⋮ Upper bounds on distinct maximal (sub-)repetitions in compressed strings ⋮ Speeding up HMM decoding and training by exploiting sequence repetitions ⋮ Closed Ziv-Lempel factorization of the \(m\)-bonacci words ⋮ A separation between RLSLPs and LZ77 ⋮ Access, Rank, and Select in Grammar-compressed Strings ⋮ Document listing on repetitive collections with guaranteed performance ⋮ Faster subsequence recognition in compressed strings ⋮ An LMS-based grammar self-index with local consistency properties ⋮ On the approximation ratio of LZ-end to LZ77 ⋮ Finding the smallest binarization of a CFG is NP-hard ⋮ Self-indexed Text Compression Using Straight-Line Programs ⋮ Approximation of smallest linear tree grammar ⋮ Prime normal form and equivalence of simple grammars ⋮ Constructing small tree grammars and small circuits for formulas ⋮ Fingerprints in compressed strings ⋮ Linear-time text compression by longest-first substitution ⋮ Grammar-compressed indexes with logarithmic search time ⋮ Longest previous overlapping factor array ⋮ Straight-line programs: a practical test (extended abstract) ⋮ On compressing and indexing repetitive sequences ⋮ LZRR: LZ77 parsing with right reference ⋮ Compact q-gram profiling of compressed strings ⋮ Binary jumbled pattern matching on trees and tree-like structures ⋮ A bisection algorithm for grammar-based compression of ordered trees ⋮ String search experimentation using massive data ⋮ Balancing run-length straight-line programs ⋮ Unified compression-based acceleration of edit-distance computation ⋮ Searching for smallest grammars on large sequences and application to DNA ⋮ Time-space trade-offs for Lempel-Ziv compressed indexing ⋮ Sensitivity of string compressors and repetitiveness measures ⋮ Random access in persistent strings and segment selection ⋮ A \textit{really} simple approximation of smallest grammar ⋮ On the compressibility of finite languages and formal proofs ⋮ Generalized substring compression ⋮ Unnamed Item ⋮ An efficient algorithm to test square-freeness of strings compressed by straight-line programs ⋮ Fast relative Lempel-Ziv self-index for similar sequences ⋮ Block trees ⋮ Universal compressed text indexing ⋮ Cadences in grammar-compressed strings ⋮ The smallest grammar problem as constituents choice and minimal grammar parsing ⋮ Algorithms for Indexing Highly Similar DNA Sequences ⋮ On Two LZ78-style Grammars: Compression Bounds and Compressed-Space Computation ⋮ A Self-index on Block Trees ⋮ Approximation of grammar-based compression via recompression ⋮ Tree compression using string grammars ⋮ Compressed subsequence matching and packed tree coloring ⋮ Functional programs as compressed data ⋮ The complexity of compressed membership problems for finite automata ⋮ Leaf languages and string compression ⋮ Unnamed Item ⋮ On z-factorization and c-factorization of standard episturmian words ⋮ Finite state complexity ⋮ LZ77 computation based on the run-length encoded BWT ⋮ On the complexity of the smallest grammar problem over fixed alphabets ⋮ Compressed range minimum queries ⋮ Tracing compressed curves in triangulated surfaces ⋮ On the Value of Multiple Read/Write Streams for Data Compression ⋮ On the size of overlapping Lempel-Ziv and Lyndon factorizations ⋮ Finger search in grammar-compressed strings ⋮ A Space-Optimal Grammar Compression. ⋮ Small-space LCE data structure with constant-time queries ⋮ Compressibility of Finite Languages by Grammars ⋮ Random Access to High-Order Entropy Compressed Text ⋮ Random Access to Grammar-Compressed Strings and Trees ⋮ Approximate pattern matching in LZ77-compressed texts ⋮ Compressed automata for dictionary matching ⋮ Balancing straight-line programs for strings and trees ⋮ Lyndon factorization of grammar compressed texts revisited ⋮ Finite state incompressible infinite sequences

Cites Work