Grammar-based codes: a new class of universal lossless source codes
From MaRDI portal
Publication:4503585
DOI10.1109/18.841160zbMath1001.94019WikidataQ29037105 ScholiaQ29037105MaRDI QIDQ4503585
John Cronan Kieffer, Enhui Yang
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
entropy; Kolmogorov complexity; context-free grammars; Chomsky hierarchy; lossless coding; redundancy bounds; universal code; grammar-based code
68Q30: Algorithmic information theory (Kolmogorov complexity, etc.)
68Q42: Grammars and rewriting systems
94A17: Measures of information, entropy
94A29: Source coding
Related Items
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., Collage system: A unifying framework for compressed pattern matching., Using ideas of Kolmogorov complexity for studying biological texts, 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, Self-indexed Text Compression Using Straight-Line Programs, A RUN-TIME EFFICIENT IMPLEMENTATION OF COMPRESSED PATTERN MATCHING AUTOMATA, 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
