Quasi-distinct parsing and optimal compression methods

DOI10.1016/J.TCS.2011.11.022MaRDI QIDQ417983zbMATHOpenAlexFDO

Authors Amihood Amir, Yonatan Aumann, Avivit Levy, Yuri Roshko

Publication date 14 May 2012

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2011.11.022

zbMATH Keywords

arithmetic progressionsparsingoptimal compression

Mathematics Subject Classification ID

Shift register sequences and sequences over finite alphabets in information and communication theory (94A55) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Other types of codes (94B60)

Recommendations

• Quasi-distinct Parsing and Optimal Compression Methods
• A worst-case analysis of the LZ2 compression algorithm
• Compression of Low Entropy Strings with Lempel--Ziv Algorithms
• scientific article; zbMATH DE number 1305530
• A note on the Ziv - Lempel model for compressing individual sequences (Corresp.)

Cites work

• scientific article; zbMATH DE number 107482 (Why is no real title available?)
• A universal algorithm for sequential data compression
• An analysis of the Burrows-Wheeler transform
• Coding theorems for individual sequences
• Compression of individual sequences via variable-rate coding
• Grammar-based codes: a new class of universal lossless source codes
• On the Complexity of Finite Sequences
• Some asymptotic properties of the entropy of a stationary ergodic data source with applications to data compression
• The Universal LZ77 Compression Algorithm Is Essentially Optimal for Individual Finite-Length $N$-Blocks
• The practical efficiency of convolutions in pattern matching algorithms

Cited in

(3)

• On arithmetically progressed suffix arrays and related Burrows-Wheeler transforms
• On parsing optimality for dictionary-based text compression -- the \texttt{Zip} case
• Quasi-distinct Parsing and Optimal Compression Methods

This page was built for publication: Quasi-distinct parsing and optimal compression methods

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q417983)