IT2010-20 定常エルゴード情報源に対する極小禁止語長の概収束(フレッシュマンセッション,一般)

概要

論文の詳細を見る
与えられた入力系列に対して,その系列に現れない極小の長さの系列を極小禁止語と呼び,その集まりを反辞書と呼ぶ.反辞書を用いた符号化手法である反辞書符号化法は,ブロックソートを用いた高性能な符号化法と同等以上の性能を持つことが知られており,また,ユニフィラーな有限状態情報源に対する漸近的最良性も示されている.一方,反辞書符号化法の性能解析に必要となる極小禁止語の長さについては,定常エルゴード情報源Xに対して評価が行なわれている.従来研究では,Xに対する極小禁止語の長さをM(n,X)とし,H(X)をXのエントロピーレートとおくと,n→∞のとき,log_2n/M(n,X)がE(X)に確率収束することが示されている.しかしながら,従来研究の結果は,確率収束によるものであるため,漸近的評価としては弱い形である問題点があった。そこで本稿では,漸近的評価を従来結果である確率収束に比べて強い形である概収束で成り立つことを示す。すなわち,X上の系列田に対して,Pr{lim_n→_∞log_2n/M(n,x)=H(X)}=1が成り立つことを示す.また,得られた結果を用いて,X上のすべての系列に出現しない系列の集まりとX上のある系列xから構築される反辞書A(x)の関係について考察し,A(x)からxを求めるアルゴリズムについて述べる.
2010-07-15

IT2010-20 定常エルゴード情報源に対する極小禁止語長の概収束(フレッシュマンセッション,一般)

スポンサーリンク

概要

著者

関連論文

スポンサーリンク