| 講演名 | 2003/7/15 単語単位情報源に対するLZ78符号の圧縮性能(一般,フレッシュマン,招待講演 : フレッシュマンセッション) 吉田 幸二, 石田 崇, 平澤 茂一, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 代表的なユニバーサル符号であるZiv-Lempel(LZ)符号は,理論面だけでなく実用面からもより圧縮効果を高める修正アルゴリズムが数多く提案され,ユニバーサル性の証明や冗長度について議論されている.一方近年,実データに近い情報源を表現するモデルとして,言語アルファベット情報源や単語単位情報源が提案され,そのエントロピーレートが解析されている.また,LZ78符号は単語単位の定常エルゴード情報源に対して漸近最良であることがすでに示されている.単語単位の情報源に対するLZ78符号化として,(i)単語単位で増分分解を行う(ii)シンボル単位で増分分解を行うという2通りを考えることができる.これら2通りの方法でLZ78符号化を行う場合にどの程度の差が生じてくるのかという性能解析は興味深いテーマである.そこで,本稿では上記2通りのLZ78符号に基づく符号化法の平均冗長度について,その上界を求め,LZ78符号の有効性について考察を行う.その結果,(i)(ii)の2通りの方法ともその上界がO(1/log n)を達成することを示す.ここでnは入力系列長である. |
| 抄録(英) | The Ziv-Lempel(LZ)codes which are typical universal codes have been proposed modifing algorithms from not only theoretical but practical use. Recently, a word-valued source has been by proposed as a new class of source models, and its entropy rate is analyzed. The LZ78 codes for the word-valued source can be applied with two kinds of methods (i) inclemental parsing for each word (ii) inclemental parsing for each symbol. The performance compression of the LZ78 codes between these two kinds of methods is an interesting theme. In this paper, we show that the upper bound of average redundancy achieves O(1/log n) and consider about validity of LZ78 codes. |
| キーワード(和) | 情報源符号化 / 言語アルファベット情報源 / 冗長度 / LZ符号 |
| キーワード(英) | source coding / word-valued source / redundancy / LZ codes |
| 資料番号 | IT2003-14(2003-07) |
| 発行日 |
| 研究会情報 | |
| 研究会 | IT |
|---|---|
| 開催期間 | 2003/7/15(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Information Theory (IT) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 単語単位情報源に対するLZ78符号の圧縮性能(一般,フレッシュマン,招待講演 : フレッシュマンセッション) |
| サブタイトル（和） | |
| タイトル（英） | Performance of compression with the LZ78 codes for word-valued source |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 情報源符号化 / source coding |
| キーワード(2)（和/英） | 言語アルファベット情報源 / word-valued source |
| キーワード(3)（和/英） | 冗長度 / redundancy |
| キーワード(4)（和/英） | LZ符号 / LZ codes |
| 第 1 著者 氏名（和/英） | 吉田 幸二 / Kouji YOSHIDA |
| 第 1 著者 所属（和/英） | 早稲田大学理工学部 School of Science and Engineering, Waseda University |
| 第 2 著者 氏名（和/英） | 石田 崇 / Takashi ISHIDA |
| 第 2 著者 所属（和/英） | 早稲田大学理工学部 School of Science and Engineering, Waseda University |
| 第 3 著者 氏名（和/英） | 平澤 茂一 / Shigeich HIRASAWA |
| 第 3 著者 所属（和/英） | 早稲田大学理工学部 School of Science and Engineering, Waseda University |
| 発表年月日 | 2003/7/15 |
| 資料番号 | IT2003-14(2003-07) |
| 巻番号（vol） | vol.103 |
| 号番号（no） | 214 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |