Large Alphabets and Incompressibility
arXiv:cs/0506056 · doi:10.1016/j.ipl.2006.04.008
Abstract
We briefly survey some concepts related to empirical entropy -- normal numbers, de Bruijn sequences and Markov processes -- and investigate how well it approximates Kolmogorov complexity. Our results suggest th-order empirical entropy stops being a reasonable complexity metric for almost all strings of length over alphabets of size about when surpasses .
Cited by in corpus (9)
- At the Roots of Dictionary Compression: String Attractors
- Universal Compressed Text Indexing
- Resolution of the Burrows-Wheeler Transform Conjecture
- Indexing Highly Repetitive String Collections
- Representing the suffix tree with the CDAWG
- Computing LZ77 in Run-Compressed Space
- Bounds from a Card Trick
- On Empirical Entropy
- New Algorithms and Lower Bounds for Sequential-Access Data Compression