講演抄録/キーワード |
講演名 |
2010-07-22 15:35
定常エルゴード情報源に対する極小禁止語長の概収束 ○太田隆博(長野県工科短大)・森田啓義(電通大) IT2010-20 |
抄録 |
(和) |
与えられた入力系列に対して,その系列に現れない極小の長さの系列を極小禁止語と呼び,その集まりを反辞書と呼ぶ.反辞書を用いた符号化手法である反辞書符号化法は,ブロックソートを用いた高性能な符号化法と同等以上の性能を持つことが知られており,また,ユニフィラーな有限状態情報源に対する漸近的最良性も示されている.
一方,反辞書符号化法の性能解析に必要となる極小禁止語の長さについては,定常エルゴード情報源$\mathbf{X}$に対して評価が行なわれている.従来研究では,$\mathbf{X}$に対する極小禁止語の長さを$M(n, \mathbf{X})$と,$H(\mathbf{X})$を$\mathbf{X}$のエントロピーレートとおくと,$n \rightarrow \infty$のとき,$\log_2 n / M(n, \mathbf{X})$が$H(\mathbf{X})$に確率収束することが示されている.しかしながら,従来研究の結果は,確率収束によるものであるため,漸近的評価としては弱い形である問題点があった.
そこで本稿では,漸近的評価を従来結果である確率収束に比べて強い形である概収束で成り立つことを示す.すなわち,$\mathbf{X}$上の系列$\mb{x}$に対して,
$\Pr\{\lim_{n \rightarrow \infty} \log_2 n / M(n, \mb{x}) = H(\mathbf{X})\}=1$が成り立つことを示す.
また,得られた結果を用いて,$\mathbf{X}$上のすべての系列に出現しない系列の集まりと$\mathbf{X}$上のある系列$\mb{x}$から構築される反辞書$\mathcal{A}(\mb{x})$の関係について考察し,$\mathcal{A}(\mb{x})$から$\mb{x}$を求めるアルゴリズムについて述べる. |
(英) |
An antidictionary is in particular useful for data compression, and it consists of minimal forbidden words for a given string. For a string $\mb{x}$ of length $n$ under a stationary ergodic source $\mathbf{X}$ with entropy rate $H(\mathbf{X}) < \infty$, it has been proved that $\log_{2} n / M(n, \mathbf{X}) = H(\mathbf{X})$ in probability, as $n \rightarrow \infty$, where $M(n, \mathbf{X})$ is the average length of minimal forbidden words for $\mathbf{X}$.
In this paper, we prove that the almost sure convergence instead of the convergence in probability. In other words, it is proved that $\Pr\{\lim_{n \rightarrow \infty} \log_{2} n / M(n, \mb{x}) = H(\mathbf{X})\} = 1$. Moreover, we propose that an algorithm to reconstruct a string $\mb{x}$ from its antidictionary $\mathcal{A}(\mb{x})$. |
キーワード |
(和) |
極小禁止語 / 反辞書 / 反辞書符号化法 / データ圧縮 / 概収束 / / / |
(英) |
Minimal Forbidden Word / Antidictionary / Antidictionary Code / Data Compression / Almost Sure Convergence / / / |
文献情報 |
信学技報, vol. 110, no. 137, IT2010-20, pp. 51-56, 2010年7月. |
資料番号 |
IT2010-20 |
発行日 |
2010-07-15 (IT) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
IT2010-20 |