Sublinear algorithms for approximating string compressibility
From MaRDI portal
Publication:2392931
DOI10.1007/s00453-012-9618-6zbMath1270.68109arXiv0706.1084MaRDI 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
68W05: Nonnumerical algorithms
68P30: Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)
Related Items
Substring complexities on run-length compressed strings, Near-optimal search time in \(\delta \)-optimal space, On stricter reachable repetitiveness measures, Internal shortest absent word queries in constant time and linear 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
