Asymptotical Optimality of Two Variations of Lempel-Ziv Codes for Sources with Countably Infinite Alphabet

Tomohiko UYEMATSU; Fumio KANAYA

doi:10.1093/ietfec/e89-a.10.2459

Asymptotical Optimality of Two Variations of Lempel-Ziv Codes for Sources with Countably Infinite Alphabet

Tomohiko UYEMATSU, Fumio KANAYA

Full Text Views

0

Share
Cite this

Summary :

This paper considers the universal coding problem for stationary ergodic sources with countably infinite alphabets. We propose modified versions of LZ77 and LZ78 codes for sources with countably infinite alphabets. Then, we show that for any source µ with E_µ[log X₁]<∞, both codes are asymptotically optimum, i.e. the code length per input symbol approaches its entropy rate with probability one. Further, we show that we can modify LZ77 and LZ78 codes so that both are asymptotically optimal for a family of ergodic sources satisfying Kieffer's condition.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E89-A No.10 pp.2459-2465

Publication Date: 2006/10/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1093/ietfec/e89-a.10.2459

Type of Manuscript: Special Section PAPER (Special Section on Information Theory and Its Applications)

Category: Source Coding

Cite this

Copy

Tomohiko UYEMATSU, Fumio KANAYA, "Asymptotical Optimality of Two Variations of Lempel-Ziv Codes for Sources with Countably Infinite Alphabet" in IEICE TRANSACTIONS on Fundamentals, vol. E89-A, no. 10, pp. 2459-2465, October 2006, doi: 10.1093/ietfec/e89-a.10.2459.
Abstract: This paper considers the universal coding problem for stationary ergodic sources with countably infinite alphabets. We propose modified versions of LZ77 and LZ78 codes for sources with countably infinite alphabets. Then, we show that for any source µ with E_µ[log X₁]<∞, both codes are asymptotically optimum, i.e. the code length per input symbol approaches its entropy rate with probability one. Further, we show that we can modify LZ77 and LZ78 codes so that both are asymptotically optimal for a family of ergodic sources satisfying Kieffer's condition.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e89-a.10.2459/_p

Copy

@ARTICLE{e89-a_10_2459,
author={Tomohiko UYEMATSU, Fumio KANAYA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Asymptotical Optimality of Two Variations of Lempel-Ziv Codes for Sources with Countably Infinite Alphabet},
year={2006},
volume={E89-A},
number={10},
pages={2459-2465},
abstract={This paper considers the universal coding problem for stationary ergodic sources with countably infinite alphabets. We propose modified versions of LZ77 and LZ78 codes for sources with countably infinite alphabets. Then, we show that for any source µ with E_µ[log X₁]<∞, both codes are asymptotically optimum, i.e. the code length per input symbol approaches its entropy rate with probability one. Further, we show that we can modify LZ77 and LZ78 codes so that both are asymptotically optimal for a family of ergodic sources satisfying Kieffer's condition.},
keywords={},
doi={10.1093/ietfec/e89-a.10.2459},
ISSN={1745-1337},
month={October},}

Copy

TY - JOUR
TI - Asymptotical Optimality of Two Variations of Lempel-Ziv Codes for Sources with Countably Infinite Alphabet
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2459
EP - 2465
AU - Tomohiko UYEMATSU
AU - Fumio KANAYA
PY - 2006
DO - 10.1093/ietfec/e89-a.10.2459
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E89-A
IS - 10
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - October 2006
AB - This paper considers the universal coding problem for stationary ergodic sources with countably infinite alphabets. We propose modified versions of LZ77 and LZ78 codes for sources with countably infinite alphabets. Then, we show that for any source µ with E_µ[log X₁]<∞, both codes are asymptotically optimum, i.e. the code length per input symbol approaches its entropy rate with probability one. Further, we show that we can modify LZ77 and LZ78 codes so that both are asymptotically optimal for a family of ergodic sources satisfying Kieffer's condition.
ER -