Compression of Low Entropy Strings with Lempel--Ziv Algorithms

DOI10.1137/S0097539797331105MaRDI QIDQ4943851zbMATH OpenOpenAlexFDO

Authors S. R. Kosaraju, Giovanni Manzini

Publication date 19 March 2000

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539797331105

zbMATH Keywords

data compressionempirical entropyLempel-Ziv parsing

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On the bit-complexity of Lempel-Ziv compression
• A worst-case analysis of the LZ2 compression algorithm
• scientific article; zbMATH DE number 1263249
• On the bit-complexity of Lempel-Ziv compression
• Performance of LZ algorithms on individual sequences

Cited in

(37)

• A worst-case analysis of the LZ2 compression algorithm
• Range majorities and minorities in arrays
• Lempel-Ziv-like parsing in small space
• Lempel-Ziv compressed structures for document retrieval
• On the approximation ratio of Lempel-Ziv parsing
• Linked dynamic tries with applications to LZ-compression in sublinear time and space
• Stronger Lempel-Ziv based compressed text indexing
• Compressing table data with column dependency
• Sensitivity of string compressors and repetitiveness measures
• Compressing big data: when the rate of convergence to the entropy matters
• Random access to high-order entropy compressed text
• On the bit-complexity of Lempel-Ziv compression
• Space-Conscious Compression
• On compressing and indexing repetitive sequences
• A note on the Ziv - Lempel model for compressing individual sequences (Corresp.)
• Quasi-distinct parsing and optimal compression methods
• Dictionary-symbolwise flexible parsing
• Lempel-Ziv: a ``one-bit catastrophe but not a tragedy
• On the bit-complexity of Lempel-Ziv compression
• Performance of LZ algorithms on individual sequences
• A sensor-based framework for kinetic data compression
• Entropy lower bounds for dictionary compression
• Compressed Multiple Pattern Matching
• Compression and entropy
• Practical Wavelet Tree Construction
• At the roots of dictionary compression: string attractors
• Bicriteria data compression
• Computer Science Logic
• Space-efficient construction of Lempel-Ziv compressed text indexes
• Lempel-Ziv Dimension for Lempel-Ziv Compression
• A new class of string transformations for compressed text indexing
• On optimally partitioning a text to improve its compression
• Grammar-based compression and its use in symbolic music analysis
• Lempel-Ziv-78 compressed string dictionaries
• A normal sequence compressed by PPM* but not by Lempel-Ziv 78
• A simple storage scheme for strings achieving entropy bounds
• Indexing text using the Ziv--Lempel trie

This page was built for publication: Compression of Low Entropy Strings with Lempel--Ziv Algorithms

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