| 講演名 | 2009-03-10 長さ制限のある極小禁止語を用いた動的な反辞書データ圧縮法(情報通信基礎サブソサイエティ合同研究会) 太田 隆博, 森田 啓義, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 反辞書は,入力系列に現れない極小系列(極小禁止語)の集まりのことで,これを算術符号の確率モデルとして用いたデータ圧縮法が提案されている.この静的手法では,復号側に送る反辞書コストの削減のために,長さ制限のある極小禁止語の集まりを反辞書として利用し,よい圧縮率を与えることが知られている.しかしながら,反辞書コストを抑えるために,2値アルファベットしか扱えない問題点がある.本稿では,圧縮率の改善を目的として,多値アルファベットを扱える動的な反辞書データ圧縮法を改良し,長さ制限のある極小禁止語の集まりを用いた線形計算量で動作する動的手法を提案する.計算機実験の結果,無記憶およびマルコフ情報源に対してエントロピーレートに近い圧縮率が得られた.また,Calgary corpusのファイルに対しても,従来手法より圧縮率が改善し,平均圧縮率でbzip2と同じ圧縮率が得られた. |
| 抄録(英) | An antidictionary is the set of all minimal strings, called Minimal Forbidden Words (MFWs), which never appear in an input string, and adaptive arithmetic codings using a statistical model based on antidictionaries have been proposed. In this article, we propose an algorithm using a set of restricted length of MFWs instead of the antidictionary. The proposed algorithm works with on-line manner in linear time. Experimental results show that the proposed algorithm gives better compression ratios on Calgary corpus than traditional algorithms and the same compression ratio on average as a popular compression application bzip2 does. |
| キーワード(和) | 反辞書 / 極小禁止語 / データ圧縮 / 接尾辞木 / 線形計算量 |
| キーワード(英) | Antidictionary / Minimal Forbidden Word / Data Compression / Suffix Tree / Linear Complexity |
| 資料番号 | IT2008-99,ISEC2008-157,WBS2008-112 |
| 発行日 |
| 研究会情報 | |
| 研究会 | WBS |
|---|---|
| 開催期間 | 2009/3/2(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Wideband System(WBS) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 長さ制限のある極小禁止語を用いた動的な反辞書データ圧縮法(情報通信基礎サブソサイエティ合同研究会) |
| サブタイトル（和） | |
| タイトル（英） | Adaptive Antidictionary Data Compression Using a Set of Restricted Length of Minimal Forbidden Words |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 反辞書 / Antidictionary |
| キーワード(2)（和/英） | 極小禁止語 / Minimal Forbidden Word |
| キーワード(3)（和/英） | データ圧縮 / Data Compression |
| キーワード(4)（和/英） | 接尾辞木 / Suffix Tree |
| キーワード(5)（和/英） | 線形計算量 / Linear Complexity |
| 第 1 著者 氏名（和/英） | 太田 隆博 / Takahiro OTA |
| 第 1 著者 所属（和/英） | 長野県工科短期大学校電子技術科 Department of Electronic Engineering, Nagano Prefectural Institute of Technology |
| 第 2 著者 氏名（和/英） | 森田 啓義 / Hiroyoshi MORITA |
| 第 2 著者 所属（和/英） | 電気通信大学大学院情報システム学研究科 Graduate School of Information Systems, University of Electro-Communications |
| 発表年月日 | 2009-03-10 |
| 資料番号 | IT2008-99,ISEC2008-157,WBS2008-112 |
| 巻番号（vol） | vol.108 |
| 号番号（no） | 474 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |