Grammar-based codes: a new class of universal lossless source codes

DOI10.1109/18.841160zbMath1001.94019WikidataQ29037105 ScholiaQ29037105MaRDI QIDQ4503585

Enhui Yang, John Cronan Kieffer

Publication date: 7 September 2000

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/0de337c2d78c63a9b9da3b0c8d921abc8e2ad37c

zbMATH Keywords

entropy; Kolmogorov complexity; context-free grammars; Chomsky hierarchy; lossless coding; redundancy bounds; universal code; grammar-based code

Mathematics Subject Classification ID

68Q30: Algorithmic information theory (Kolmogorov complexity, etc.)

68Q42: Grammars and rewriting systems

94A17: Measures of information, entropy

94A29: Source coding

Related Items

Random Access to Grammar-Compressed Strings and Trees, Excess entropy in natural language: Present state and perspectives, Compressibility of Finite Languages by Grammars, A FULLY COMPRESSED PATTERN MATCHING ALGORITHM FOR SIMPLE COLLAGE SYSTEMS, Tracing compressed curves in triangulated surfaces, A bisection algorithm for grammar-based compression of ordered trees, Searching for smallest grammars on large sequences and application to DNA, Quasi-distinct parsing and optimal compression methods, Textual data compression in computational biology: algorithmic techniques, Using static suffix array in dynamic application: case of text compression by longest first substitution, On bounded redundancy of universal codes, Universal codes as a basis for time series testing, Variable-length coding of two-sided asymptotically mean stationary measures, XML compression techniques: A survey and comparison, Approximability of minimum AND-circuits, Application of Lempel-Ziv factorization to the approximation of grammar-based compression., Linear-time text compression by longest-first substitution, Inductive synthesis of cover-grammars with the help of ant colony optimization, On the compressibility of finite languages and formal proofs, Universal compressed text indexing, The smallest grammar problem as constituents choice and minimal grammar parsing, Collage system: A unifying framework for compressed pattern matching., Using ideas of Kolmogorov complexity for studying biological texts, Time-universal data compression, Compaction of Church numerals, GraCT: a grammar-based compressed index for trajectory data, Block trees, Finger search in grammar-compressed strings, Constructing small tree grammars and small circuits for formulas, Grammar compressed sequences with rank/select support, A fast and efficient nearly-optimal adaptive Fano coding scheme, Application of Kolmogorov complexity and universal codes to identity testing and nonparametric testing of serial independence for time series, Universal codes as a basis for nonparametric testing of serial independence for time series, A fully linear-time approximation algorithm for grammar-based compression, Grammar-compressed indexes with logarithmic search time, Self-indexed Text Compression Using Straight-Line Programs, Syntactic Methods for ECG Signal Diagnosis and QRS Complexes Recognition, A RUN-TIME EFFICIENT IMPLEMENTATION OF COMPRESSED PATTERN MATCHING AUTOMATA, Grammar-Based Tree Compression, A Run-Time Efficient Implementation of Compressed Pattern Matching Automata, Quasi-distinct Parsing and Optimal Compression Methods, IN-PLACE UPDATE OF SUFFIX ARRAY WHILE RECODING WORDS