Sublinear algorithms for approximating string compressibility

DOI10.1007/s00453-012-9618-6zbMath1270.68109arXiv0706.1084OpenAlexW2173739051MaRDI QIDQ2392931

Yanyan Li

Publication date: 5 August 2013

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0706.1084

zbMATH Keywords

lossless compressionrun-length encodingLempel-Zivsublinear algorithms

Mathematics Subject Classification ID

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