講演抄録/キーワード |
講演名 |
2009-03-10 10:15
長さ制限のある極小禁止語を用いた動的な反辞書データ圧縮法 ○太田隆博(長野県工科短大)・森田啓義(電通大) IT2008-99 ISEC2008-157 WBS2008-112 |
抄録 |
(和) |
反辞書は,入力系列に現れない極小系列(極小禁止語)の集まりのことで,
これを算術符号の確率モデルとして用いたデータ圧縮法が提案されている.
この静的手法では,復号側に送る反辞書コストの削減のために,長さ制限のある極小禁止語の集まりを反辞書として利用し,よい圧縮率を与えることが知られている.しかしながら,反辞書コストを抑えるために,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 / / / |
文献情報 |
信学技報, vol. 108, no. 472, IT2008-99, pp. 363-370, 2009年3月. |
資料番号 |
IT2008-99 |
発行日 |
2009-03-02 (IT, ISEC, WBS) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
IT2008-99 ISEC2008-157 WBS2008-112 |
研究会情報 |
研究会 |
WBS IT ISEC |
開催期間 |
2009-03-09 - 2009-03-10 |
開催地(和) |
公立はこだて未来大学(函館) |
開催地(英) |
Hakodate Mirai Univ. |
テーマ(和) |
一般:情報通信基礎サブソサイェティ合同研究会 |
テーマ(英) |
|
講演論文情報の詳細 |
申込み研究会 |
IT |
会議コード |
2009-03-WBS-IT-ISEC |
本文の言語 |
日本語 |
タイトル(和) |
長さ制限のある極小禁止語を用いた動的な反辞書データ圧縮法 |
サブタイトル(和) |
|
タイトル(英) |
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 |
キーワード(6)(和/英) |
/ |
キーワード(7)(和/英) |
/ |
キーワード(8)(和/英) |
/ |
第1著者 氏名(和/英/ヨミ) |
太田 隆博 / Takahiro Ota / オオタ タカヒロ |
第1著者 所属(和/英) |
長野県工科短期大学校 (略称: 長野県工科短大)
Nagano Prefectural Institute of Technology (略称: Nagano Prefectural Inst. of Tech.) |
第2著者 氏名(和/英/ヨミ) |
森田 啓義 / Hiroyoshi Morita / モリタ ヒロヨシ |
第2著者 所属(和/英) |
電気通信大学 (略称: 電通大)
University of Electro-Communications (略称: Univ. of Electro-Commu.) |
第3著者 氏名(和/英/ヨミ) |
/ / |
第3著者 所属(和/英) |
(略称: )
(略称: ) |
第4著者 氏名(和/英/ヨミ) |
/ / |
第4著者 所属(和/英) |
(略称: )
(略称: ) |
第5著者 氏名(和/英/ヨミ) |
/ / |
第5著者 所属(和/英) |
(略称: )
(略称: ) |
第6著者 氏名(和/英/ヨミ) |
/ / |
第6著者 所属(和/英) |
(略称: )
(略称: ) |
第7著者 氏名(和/英/ヨミ) |
/ / |
第7著者 所属(和/英) |
(略称: )
(略称: ) |
第8著者 氏名(和/英/ヨミ) |
/ / |
第8著者 所属(和/英) |
(略称: )
(略称: ) |
第9著者 氏名(和/英/ヨミ) |
/ / |
第9著者 所属(和/英) |
(略称: )
(略称: ) |
第10著者 氏名(和/英/ヨミ) |
/ / |
第10著者 所属(和/英) |
(略称: )
(略称: ) |
第11著者 氏名(和/英/ヨミ) |
/ / |
第11著者 所属(和/英) |
(略称: )
(略称: ) |
第12著者 氏名(和/英/ヨミ) |
/ / |
第12著者 所属(和/英) |
(略称: )
(略称: ) |
第13著者 氏名(和/英/ヨミ) |
/ / |
第13著者 所属(和/英) |
(略称: )
(略称: ) |
第14著者 氏名(和/英/ヨミ) |
/ / |
第14著者 所属(和/英) |
(略称: )
(略称: ) |
第15著者 氏名(和/英/ヨミ) |
/ / |
第15著者 所属(和/英) |
(略称: )
(略称: ) |
第16著者 氏名(和/英/ヨミ) |
/ / |
第16著者 所属(和/英) |
(略称: )
(略称: ) |
第17著者 氏名(和/英/ヨミ) |
/ / |
第17著者 所属(和/英) |
(略称: )
(略称: ) |
第18著者 氏名(和/英/ヨミ) |
/ / |
第18著者 所属(和/英) |
(略称: )
(略称: ) |
第19著者 氏名(和/英/ヨミ) |
/ / |
第19著者 所属(和/英) |
(略称: )
(略称: ) |
第20著者 氏名(和/英/ヨミ) |
/ / |
第20著者 所属(和/英) |
(略称: )
(略称: ) |
講演者 |
第1著者 |
発表日時 |
2009-03-10 10:15:00 |
発表時間 |
25分 |
申込先研究会 |
IT |
資料番号 |
IT2008-99, ISEC2008-157, WBS2008-112 |
巻番号(vol) |
vol.108 |
号番号(no) |
no.472(IT), no.473(ISEC), no.474(WBS) |
ページ範囲 |
pp.363-370 |
ページ数 |
8 |
発行日 |
2009-03-02 (IT, ISEC, WBS) |