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

DOI10.1109/18.841160zbMath1001.94019OpenAlexW2130956967WikidataQ29037105 ScholiaQ29037105MaRDI QIDQ4503585

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

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Grammars and rewriting systems (68Q42) Measures of information, entropy (94A17) Source coding (94A29)

Related Items

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