Sublinear algorithms for approximating string compressibility
From MaRDI portal
Publication:2392931
Abstract: We raise the question of approximating the compressibility of a string with respect to a fixed compression scheme, in sublinear time. We study this question in detail for two popular lossless compression schemes: run-length encoding (RLE) and Lempel-Ziv (LZ), and present sublinear algorithms for approximating compressibility with respect to both schemes. We also give several lower bounds that show that our algorithms for both schemes cannot be improved significantly. Our investigation of LZ yields results whose interest goes beyond the initial questions we set out to study. In particular, we prove combinatorial structural lemmas that relate the compressibility of a string with respect to Lempel-Ziv to the number of distinct short substrings contained in it. In addition, we show that approximating the compressibility with respect to LZ is related to approximating the support size of a distribution.
Recommendations
Cites work
- scientific article; zbMATH DE number 52869 (Why is no real title available?)
- scientific article; zbMATH DE number 107482 (Why is no real title available?)
- scientific article; zbMATH DE number 1336330 (Why is no real title available?)
- scientific article; zbMATH DE number 1010621 (Why is no real title available?)
- scientific article; zbMATH DE number 2089987 (Why is no real title available?)
- scientific article; zbMATH DE number 2119662 (Why is no real title available?)
- scientific article; zbMATH DE number 1421006 (Why is no real title available?)
- A universal algorithm for sequential data compression
- Approximating entropy from sublinear samples
- Clustering by Compression
- Compression of individual sequences via variable-rate coding
- Discrete Cosine Transform
- Estimating Entropy on<tex>$m$</tex>Bins Given Fewer Than<tex>$m$</tex>Samples
- Estimation of Entropy and Mutual Information
- Generalized substring compression
- On average sequence complexity
- On correlation polynomials and subword complexity
- On the combinatorics of finite words
- On the maximum number of distinct factors of a binary string
- Proof of a conjecture on word complexity
- Sampling algorithms: lower bounds and applications
- Strong lower bounds for approximating distribution support size and the distinct elements problem
- Sublinear Algorithms for Approximating String Compressibility
- Substring compression problems
- The Complexity of Approximating the Entropy
- The Similarity Metric
- The context-tree weighting method: basic properties
- The space complexity of approximating the frequency moments
- Theory and Applications of Models of Computation
- Universal Entropy Estimation Via Block Sorting
- Using literal and grammatical statistics for authorship attribution
Cited in
(18)- scientific article; zbMATH DE number 1490000 (Why is no real title available?)
- NC algorithms for finding a maximal set of paths with application to compressing strings
- Near-optimal search time in \(\delta \)-optimal space, and vice versa
- Upper bounds on distinct maximal (sub-)repetitions in compressed strings
- Compressed Dynamic Tries with Applications to LZ-Compression in Sublinear Time and Space
- On stricter reachable repetitiveness measures
- At the roots of dictionary compression: string attractors
- Near-optimal search time in \(\delta \)-optimal space
- Sublinear Algorithms for Approximating String Compressibility
- Internal shortest absent word queries in constant time and linear space
- Substring complexities on run-length compressed strings
- Sensitivity of string compressors and repetitiveness measures
- Adaptive learning of compressible strings
- Compressibility measures for two-dimensional data
- Frequency-constrained substring complexity
- Sublinear time Lempel-Ziv (LZ77) factorization
- Iterated straight-line programs
- CONCUR 2003 - Concurrency Theory
This page was built for publication: Sublinear algorithms for approximating string compressibility
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2392931)
