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

DOI10.1016/S0304-3975(02)00777-6zbMath1051.68088MaRDI 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

68Q42: Grammars and rewriting systems

Related Items

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

Cites Work