Large alphabets and incompressibility

DOI10.1016/j.ipl.2006.04.008zbMath1185.68367arXivcs/0506056MaRDI QIDQ845735

Travis Gagie

Publication date: 29 January 2010

Published in: Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

relative entropy; data compression; Markov processes; Kolmogorov complexity; analysis of algorithms; normal numbers; de Bruijn sequences; Shannon's entropy; threshold phenomena; birthday paradox; empirical entropy; self-information

Mathematics Subject Classification ID

68Q45: Formal languages and automata

68Q30: Algorithmic information theory (Kolmogorov complexity, etc.)

Related Items

Unnamed Item, Practical Wavelet Tree Construction, Fast Label Extraction in the CDAWG, Compressed Multiple Pattern Matching, Fast Compressed Self-Indexes with Deterministic Linear-Time Construction, On compressing and indexing repetitive sequences, Bounds from a card trick, LZ77 computation based on the run-length encoded BWT, Universal compressed text indexing, Fast compressed self-indexes with deterministic linear-time construction, Lempel-Ziv-like parsing in small space, Stronger Lempel-Ziv based compressed text indexing, On the Value of Multiple Read/Write Streams for Data Compression

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A Mathematical Theory of Communication
• A guided tour of Chernoff bounds
• Compressing probability distributions
• Compressed representations of sequences and full-text indexes
• An analysis of the Burrows—Wheeler transform
• Self-adjusting binary search trees
• Sorting and Searching in Multisets
• The Construction of Decimals Normal in the Scale of Ten
• On the Length of Programs for Computing Finite Binary Sequences
• A formal theory of inductive inference. Part I
• On Information and Sufficiency
• Note on normal numbers
• An example of a computable absolutely normal number