Large alphabets and incompressibility
From MaRDI portal
Publication:845735
DOI10.1016/j.ipl.2006.04.008zbMath1185.68367arXivcs/0506056MaRDI QIDQ845735
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
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
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