Lempel-Ziv符号と情報理論

摘要

情報源の統計的性質をあらかじめ知ることなく符号化#12539;復号化が行え，かつ入力列が長くなるにつれて，平均符号長が情報源のエントロピーレートに漸近する符号をユニバーサル符号という．本論文では，代表的なユニバーサル符号として，ZivとLempelによって提案された増分分解に基づくLempel-Ziv（LZ78）符号を取り上げる．まず，LZ78符号の漸近的最良性と平均冗長度について詳細に述べた後，LZ78符号が情報源の符号化のみならず情報理論における各種問題に対する最適解を具体的なアルゴリズムとともに与えることを示し，ユニバーサル符号の情報理論における重要性を明らかにする．