Grammar-based codes: a new class of universal lossless source codes
From MaRDI portal
Publication:4503585
DOI10.1109/18.841160zbMath1001.94019OpenAlexW2130956967WikidataQ29037105 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
entropyKolmogorov complexitycontext-free grammarsChomsky hierarchylossless codingredundancy boundsuniversal codegrammar-based code
Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Grammars and rewriting systems (68Q42) Measures of information, entropy (94A17) Source coding (94A29)
Related Items (57)
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 ⋮ Grammar-based compression and its use in symbolic music analysis ⋮ 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
This page was built for publication: Grammar-based codes: a new class of universal lossless source codes
