| タイトル | 文法規則に基づくユニバーサル符号化アルゴリズムに関する研究 |
|---|---|
| 著者 | 西村信哉 |
| 年度 | 2005 |
| 形式 | 卒業論文 |
| 分野 | 情報源符号化 |
| 掲載雑誌名 | 早稲田大学卒業論文 |
| 掲載号・ページ | |
| 掲載年 | 2005 |
| 掲載月 | |
| アブスト （日本語） |
近年，情報通信技術の発展に伴い，扱われる情報の量が増大している．そのためデータ圧縮の技術がますます重要となってきている．本研究では圧縮された情報を誤り無く復号する，無歪圧縮を取り扱う．無歪圧縮は，情報源系列を符号語と呼ばれる系列に一対一に変換することで実行される．符号語の長さを符号長と呼び，その限界がエントロピーで表されることが知られている．情報源系列の確率分布が既知の場合はこの限界を達成できる符号化法として算術符号やハフマン符号などがある．しかし，実用において系列の確率分布が既知であることはまれである．このような確率分布が未知の状況において，漸近的にこの限界を達成する符号化法をユニバーサル符号と呼ぶ．このとき，冗長度（平均の符号長とエントロピーの差）と符号化計算量が評価基準となる．ユニバーサル符号の具体的な符号化法に逐次MPM法[1]，[2] やベイズ符号[3] などがある．逐次MPM 法は情報源系列から文法規則を生成して符号化するアルゴリズムで計算量が線形となる[1]，[2]．ただし，漸近的に冗長度は0 に近づくが有限時点での性能は良くない．一方，ベイズ符号は有限時点において冗長度がベイズ基準の下で最適となる符号化法である．しかし，系列の長さに従って計算量が大きく増大する．文法規則とは，情報源系列を生成する変換の規則である．文法に基づく符号化法の様子を図1 に示す．本研究では，まず情報源としてマルコフ情報源を仮定したときのそれぞれの符号化法の冗長度・計算量を比較し，特徴・利点を明確にする．そして逐次MPM法を改良して計算量がベイズ符号ほど大きくならずに冗長度がベイズ最適に近づく符号化法を提案する． |
| アブスト （英語） |
|
| 備考 （日本語） |
本論（研究室内のみアクセス可能） 発表資料（研究室内のみアクセス可能） |
| 備考 （英語） |
|
| 論文原稿 | |
| 発表資料 |
