Universal Coding of Zipf Distributions
Abstract
Background. One of the best known results in information theory says that a data sequence x _1, x _2,..., x _ n produced by independent random draws from a fixed distribution P over a discrete domain can be compressed into a binary sequence, or code whose expected length is at most nH ( P )+1 bits, where H ( P ) = − ∑ _ i P _ i log P _ i is the entropy of P . It is also known that this compression is near optimal as nH ( P ) is the smallest achievable expected number of code bits.
Cite
Text
Freund et al. "Universal Coding of Zipf Distributions." Annual Conference on Computational Learning Theory, 2003. doi:10.1007/978-3-540-45167-9_57Markdown
[Freund et al. "Universal Coding of Zipf Distributions." Annual Conference on Computational Learning Theory, 2003.](https://mlanthology.org/colt/2003/freund2003colt-universal/) doi:10.1007/978-3-540-45167-9_57BibTeX
@inproceedings{freund2003colt-universal,
title = {{Universal Coding of Zipf Distributions}},
author = {Freund, Yoav and Orlitsky, Alon and Santhanam, Prasad and Zhang, Junan},
booktitle = {Annual Conference on Computational Learning Theory},
year = {2003},
pages = {736-737},
doi = {10.1007/978-3-540-45167-9_57},
url = {https://mlanthology.org/colt/2003/freund2003colt-universal/}
}