Large alphabets and incompressibility

DOI10.1016/J.IPL.2006.04.008zbMath1185.68367arXivcs/0506056OpenAlexW2150359208MaRDI 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 entropydata compressionMarkov processesKolmogorov complexityanalysis of algorithmsnormal numbersde Bruijn sequencesShannon's entropythreshold phenomenabirthday paradoxempirical entropyself-information

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Related Items (13)

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

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Large alphabets and incompressibility