二元情報源に対する畳語分解を用いたデータ圧縮法

摘要

LZ78符号で用いられる増分分解は増分分解木を用いて実現できるが，横尾は増分分解木とCBT符号と組み合わせることにより，二元データ系列を効率よく圧縮できることを示している．しかし，増分分解木は，木の更新時に葉の対が1つしか増加しないため，分解木の成長が遅くデータ系列の特徴を反映した分解木ができるまでに時間がかかるという欠点がある．他方，二元系列の複雑度を定義するために，我々は増分分解とT-符号で使用されるT-分解の中間の特性を持つ畳語分解を提案し，畳語分解木の成長が増分分解木より速く，またT-分解木のように速く成長しすぎることもないことを示した．そこで，本稿では，畳語分解木を用いた二元系列に対するユニバーサルなデータ圧縮符号を提案する．そして，二元定常エルゴード情報源に対して，提案符号がある条件の下でユニバーサルにエントロピーレートを漸近的に達成できることを証明する．また，コーパスを用いて，提案符号が横尾符号よりよい圧縮率を達成できることを示す．