Grammar-based codes: a new class of universal lossless source codes
From MaRDI portal
DOI10.1109/18.841160zbMATH Open1001.94019OpenAlexW2130956967WikidataQ29037105 ScholiaQ29037105MaRDI QIDQ4503585FDOQ4503585
Authors: Enhui Yang, John C. 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
Recommendations
- Structured grammar-based codes for universal lossless data compression.
- The Universality of Grammar-Based Codes for Sources With Countably Infinite Alphabets
- Grammar-Based Lossless Universal Refinement Source Coding
- Efficient universal lossless data compression algorithms based on a greedy sequential grammar transform-part two: with context models
- Efficient universal lossless data compression algorithms based on a greedy sequential grammar transform. I. Without context models
entropyChomsky hierarchycontext-free grammarsKolmogorov complexitylossless codingredundancy boundsuniversal codegrammar-based code
Measures of information, entropy (94A17) Source coding (94A29) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Grammars and rewriting systems (68Q42)
Cited In (71)
- GraCT: a grammar-based compressed index for trajectory data
- Grammar-Based Tree Compression
- Finger search in grammar-compressed strings
- Uniquely decodable \(n\)-gram embeddings
- Quasi-distinct parsing and optimal compression methods
- Novel results on the number of runs of the Burrows-Wheeler-transform
- Application of Kolmogorov complexity and universal codes to identity testing and nonparametric testing of serial independence for time series
- Block trees
- Variable-length coding of two-sided asymptotically mean stationary measures
- Constructing small tree grammars and small circuits for formulas
- The smallest grammar problem as constituents choice and minimal grammar parsing
- Grammar compressed sequences with rank/select support
- Time-universal data compression
- Compaction of Church numerals
- Searching for smallest grammars on large sequences and application to DNA
- Tracing compressed curves in triangulated surfaces
- Collage system: A unifying framework for compressed pattern matching.
- On bounded redundancy of universal codes
- Structured grammar-based codes for universal lossless data compression.
- Grammar-based compression and its use in symbolic music analysis
- Efficient universal lossless data compression algorithms based on a greedy sequential grammar transform-part two: with context models
- Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
- Linear-time text compression by longest-first substitution
- Universal coding and prediction on ergodic random points
- In-place update of suffix array while recoding words
- An LMS-based grammar self-index with local consistency properties
- Grammar index by induced suffix sorting
- On stricter reachable repetitiveness measures
- On the complexity of the smallest grammar problem over fixed alphabets
- XML compression techniques: A survey and comparison
- Approximability of minimum AND-circuits
- Random access to grammar-compressed strings and trees
- Textual data compression in computational biology: algorithmic techniques
- A fully linear-time approximation algorithm for grammar-based compression
- Grammar-compressed indexes with logarithmic search time
- Title not available (Why is that?)
- Using static suffix array in dynamic application: case of text compression by longest first substitution
- Compressibility of Finite Languages by Grammars
- Self-indexed Text Compression Using Straight-Line Programs
- Optimal rank and select queries on dictionary-compressed text
- Efficient universal lossless data compression algorithms based on a greedy sequential grammar transform. I. Without context models
- Universal codes as a basis for nonparametric testing of serial independence for time series
- A bisection algorithm for grammar-based compression of ordered trees
- Faster repetition-aware compressed suffix trees based on block trees
- Asymptotically most powerful tests for random number generators
- Excess entropy in natural language: present state and perspectives
- A fast and efficient nearly-optimal adaptive Fano coding scheme
- Using ideas of Kolmogorov complexity for studying biological texts
- Substring complexities on run-length compressed strings
- Quasi-distinct Parsing and Optimal Compression Methods
- Inductive synthesis of cover-grammars with the help of ant colony optimization
- A RUN-TIME EFFICIENT IMPLEMENTATION OF COMPRESSED PATTERN MATCHING AUTOMATA
- Sensitivity of string compressors and repetitiveness measures
- Title not available (Why is that?)
- Universal codes as a basis for time series testing
- On the compressibility of finite languages and formal proofs
- Universal compressed text indexing
- Syntactic methods for ECG signal diagnosis and QRS complexes recognition
- Faster repetition-aware compressed suffix trees based on block trees
- Efficient construction of the BWT for repetitive text using string compression
- Universal lossless data compression with side information by using a conditional MPM grammar transform
- Grammar-Based Lossless Universal Refinement Source Coding
- Performance Analysis of Grammar-Based Codes Revisited
- The Universality of Grammar-Based Codes for Sources With Countably Infinite Alphabets
- A FULLY COMPRESSED PATTERN MATCHING ALGORITHM FOR SIMPLE COLLAGE SYSTEMS
- Approximation ratios of \textsf{RePair}, \textsf{LongestMatch} and \textsf{Greedy} on unary strings
- Rpair: rescaling RePair with Rsync
- A Run-Time Efficient Implementation of Compressed Pattern Matching Automata
- A simple grammar-based index for finding approximately longest common substrings
- Computing all-vs-all MEMs in grammar-compressed text
- Space-efficient conversions from SLPs
This page was built for publication: Grammar-based codes: a new class of universal lossless source codes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4503585)
