可変長-固定長符号としてのLempel-Ziv増分分解法の研究

点击翻译按钮获取中文摘要

近年,データ圧縮技術への期待が高まっている.通信需要以外にも,大量に蓄積しつつあるデータを記録媒体に長期にわたって効率的に記憶するにはデータ圧縮が不可欠であり,特に後者の目的には,算法が究極的な圧縮性能を持つよう設計しなければならず,長い視野に立った基礎研究が重要である.著者は,こうした視点に立って,実際と理論両面から,データ圧縮法に関する諸問題に取り組んできた.今回の研究の対象としたのは,誤りなしデータ圧縮法に分類されるLempel-Ziv増分分解法(以下LZ法と略)である.この分解法は,既に標準的なファイル圧縮法として普及しているとはいえ,圧縮限界からのずれを示す冗長度などの重要な性質には十分理解されていないところがあるうえ,アルゴリズム的にも改善すべき点がある.冗長度を知るには,ファイルに情報源確率モデルを仮定し,圧縮率を理論的に評価することが必要である.筆者は以前,無記憶情報源に対する圧縮率の厳密式を発見し,それを評価する方法を提案した.しかし,無記憶の仮定は情報源モデルとしては現実的でなく,これをマルコフ過程に拡張することが望まれる.ところが,LZ符号は非定常かつ自己組織的な符号であり,無記憶の場合すらその厳密解析は困難であった.著者はまずLZ増分分解列の期待長がなす奇妙な再帰関係に着目し,この解法を行なうという方法をとった.半無限列上に4つの基本的な作用素を定義し,その性質を利用してこの再帰関係を解くという別道を発見し,極めて形式的にLZ自己組織木の深さの統計量を,求める方法を見い出した.それによって,ユニフィラマルコフ過程に適合した状態依存型LZ増分分解法の厳密な圧縮率を求める閉式を見い出した.この結果は,その漸近解析とあわせて,IEEE情報理論国際シンポジウムで発表を予定しているが,同時に論文としても公表するつもりである.