講演抄録/キーワード |
講演名 |
2008-09-11 14:30
文法推論に基づく無損失データ圧縮の改善 ○バユ ユディスティラ・岩沼宏冶・鍋島英知(山梨大) IT2008-22 |
抄録 |
(和) |
近年, 文法型データ圧縮方法に関する研究が盛んに行われている. Sequiturアルゴリズム[2]やMPM (Multilevel Pattern Matching) 符号[1]はその例である. 文法型データ圧縮はデータ系列に対し, 文脈自由文法を構成し符号化する. Sequiturアルゴリズムはデータ系列を逐次的に読み込み, Diagram (連続する2記号以上の並び)を単位として, 文法を生成する. 一方, MPM符号では全データ系列を読み込んだ後に文法を生成する. 本研究では, MPM符号をSequiturアルゴリズムの一部アイデアを用いて改良し, より圧縮率が優れた圧縮方法を提案する. 本手法は, Kieffer-Yang[1]が提案した元のMPM符号よりも, 平均して25%程度の圧縮率が改善されたMPM符号, Sequiturアルゴリズム, Gzipの3者と比較して平均圧縮率が最も高いことを実験的に確認した. |
(英) |
Recently, the research on grammatical-inference data compression method has been done actively, such as Sequitur algorithm [2] and MPM (Multilevel Pattern Matching) coding [1]. Grammatical-inference data compression forms a context-free grammar from a given sequence. Sequitur algorithm incrementally reads a sequence one by one and split up the sequence into a set of Diagram, i.e., consecutive two symbols. If Sequitur finds out two same Diagrams in the sequence, the Diagram is registered as a production rule. In MPM coding, after reading an entire sequence, a grammar is generated. In this paper, we propose a new algorithm where we improve MPM coding together with a partial idea of Sequitur algorithm and achieve the higher compression ratio than the original of MPM coding. |
キーワード |
(和) |
データ圧縮 / 文脈自由文法 / MPM符号 / ハフマン符号 / / / / |
(英) |
data compression / context-free grammar / MPM coding / Huffman coding / / / / |
文献情報 |
信学技報, vol. 108, no. 202, IT2008-22, pp. 13-18, 2008年9月. |
資料番号 |
IT2008-22 |
発行日 |
2008-09-04 (IT) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
IT2008-22 |
|