| 講演名 | 2004-07-28 貪欲な文法変換に基づくデータ圧縮アルゴリズムの性能評価(フレッシュマンセッション)(フレッシュマン,一般) 小泉 直生, 古賀 弘樹, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | YangとKiefferにより提案された貪欲な文法変換に基づくユニバーサルデータ圧縮アルゴリズムは,定常エルゴード情報源に対して漸近最良性をもつことが証明されている.しかし,YangとKiefferのアルゴリズムを実際のファイルに適用した結果は,著者らが知る限り,容易にアクセスできる文献として公表されていない.本稿では,YangとKiefferにより提案されたデータ圧縮アルゴリズムを高速に動作するように実装し,実際の計算機ファイルに対して圧縮率の評価を行った結果を報告する.実際,圧縮率はgzipより勝ること,および,符号化に要する時間も現実的であることが示される.本稿ではまた,YangとKiefferのアルゴリズムを施す前に,Burrows-Wheeler変換により前処理をする場合の圧縮率についても調べる. |
| 抄録(英) | The universal data compression algorithm based on the greedy-grammar transform, which was proposed by Yang and Kieffer, is asymptotically optimal for stationary ergodic sources. However, the performance of the Yang-Kieffer algorithm for practical computer files is not open. In this paper we implement the Yang-Kieffer algorithm and evaluate its data compression performance for files in Calgary and Canterbury corpuses. We show that the Yarig-Kieffer algorithm performs better than gzip in compression ratio, and the time required for encoding is realistic. In addition we investigate the data compression performance of the Yang-Kieffer algorithm combined with the Burrows-Wheeler transform. |
| キーワード(和) | 文脈自由文法 / 貪欲な文法変換 / ユニバーサルデータ圧縮 |
| キーワード(英) | context-free grammar / greedy grammar transform / universal data compression |
| 資料番号 | IT2004-13 |
| 発行日 |
| 研究会情報 | |
| 研究会 | IT |
|---|---|
| 開催期間 | 2004/7/21(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Information Theory (IT) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 貪欲な文法変換に基づくデータ圧縮アルゴリズムの性能評価(フレッシュマンセッション)(フレッシュマン,一般) |
| サブタイトル（和） | |
| タイトル（英） | Performance Evaluation of Data Compression Algorithms Based on the Greedy Grammar Transform |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 文脈自由文法 / context-free grammar |
| キーワード(2)（和/英） | 貪欲な文法変換 / greedy grammar transform |
| キーワード(3)（和/英） | ユニバーサルデータ圧縮 / universal data compression |
| 第 1 著者 氏名（和/英） | 小泉 直生 / Naoki KOIZUMl |
| 第 1 著者 所属（和/英） | 筑波大学第三学部工学システム学類 College of Engineering Systems, University of Tsukuba |
| 第 2 著者 氏名（和/英） | 古賀 弘樹 / Hiroki KOGA |
| 第 2 著者 所属（和/英） | 筑波大学システム情報工学研究科知能機能システム専攻 Graduate School of Systems and Information Engineering, University of Tsukuba |
| 発表年月日 | 2004-07-28 |
| 資料番号 | IT2004-13 |
| 巻番号（vol） | vol.104 |
| 号番号（no） | 228 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |