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

Tomohiko UYEMATSU  Fumio KANAYA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E89-A   No.10   pp.2459-2465
Publication Date: 2006/10/01
Online ISSN: 1745-1337
DOI: 10.1093/ietfec/e89-a.10.2459
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Information Theory and Its Applications)
Category: Source Coding
Keyword: 
countably infinite alphabet,  ergodic source,  incremental parsing,  Lempel-Ziv code,  string matching,  

Full Text: PDF>>
Buy this Article




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 X1]<∞, 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.