Sublinear algorithms for approximating string compressibility
From MaRDI portal
Publication:2392931
DOI10.1007/s00453-012-9618-6zbMath1270.68109arXiv0706.1084OpenAlexW2173739051MaRDI QIDQ2392931
Publication date: 5 August 2013
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0706.1084
Nonnumerical algorithms (68W05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)
Related Items (5)
On stricter reachable repetitiveness measures ⋮ Internal shortest absent word queries in constant time and linear space ⋮ Substring complexities on run-length compressed strings ⋮ Near-optimal search time in \(\delta \)-optimal space, and vice versa ⋮ Near-optimal search time in \(\delta \)-optimal space
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On average sequence complexity
- On the combinatorics of finite words
- The space complexity of approximating the frequency moments
- Using literal and grammatical statistics for authorship attribution
- On the maximum number of distinct factors of a binary string
- Generalized substring compression
- Universal Entropy Estimation Via Block Sorting
- Clustering by Compression
- The Similarity Metric
- Estimating Entropy on<tex>$m$</tex>Bins Given Fewer Than<tex>$m$</tex>Samples
- Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem
- Sublinear Algorithms for Approximating String Compressibility
- A universal algorithm for sequential data compression
- Compression of individual sequences via variable-rate coding
- Estimation of Entropy and Mutual Information
- The context-tree weighting method: basic properties
- Sampling algorithms
- Discrete Cosine Transform
- The Complexity of Approximating the Entropy
- Theory and Applications of Models of Computation
- Proof of a conjecture on word complexity
This page was built for publication: Sublinear algorithms for approximating string compressibility
