テキスト圧縮に基づく高速パターン照合アルゴリズムの研究

閲覧数: 3
ダウンロード数: 0
このエントリーをはてなブックマークに追加

テキスト圧縮に基づく高速パターン照合アルゴリズムの研究

フォーマット:
助成・補助金
Kyushu Univ. Production 九州大学成果文献
タイトル(他言語):
Studies on fast pattern matching algorithms based on text compressions
責任表示:
竹田 正幸(九州大学・大学院・システム情報科学研究科・助教授)
TAKEDA Masayuki(九州大学・大学院・システム情報科学研究科・助教授)
本文言語:
日本語
研究期間:
1997-1998
概要(最新報告):
従来,ファイル圧縮の目的は二次記憶領域の効率的利用にあった.したがって,現在広く使われている圧縮法は,圧縮率を第1の基準として選定されたものである.本研究では,この発想を大きく転換し,パターン照合の高速化を図るためにファイル圧縮を行うものと考える.本研究の目標は,以下の二つである. 目標1:展開後照合する方法と比べて,より高速に照合できること. 目標2:非圧縮テキストを照合する方法と比べて,より高速に照合できること. 2年間にわたる本プロジェクトにおいて,上記の二つの目標を達成し,以下の研究成果を得て,プロジェクトを成功裡に終了した. (1) UNIX標準の圧縮プログラムであるCompressで使用されているLZW圧縮法に関して,複数パターン照合アルゴリズムを開発した. (2) 上記(1)のアルゴリズムのより実用的な実現法として,Shift-And法に基づく方法を開発した. (3) 上記(1),(2)のアルゴリズムを実働化し,展開後照合する単純な方式と比べて2倍程度高速であることを示した。すなわち,目標1を達成した. (4) 同様に,二つのアルゴリズムが、非圧縮テキスト上のパターン照合と比べて高速であることを示した.すなわち,目標2を達成した。高速化の度合は,ほぼ圧縮率に等しい. (5) バイト対符号法,ハフマン符号,有限状態符号,否定辞書法などの圧縮法についても,パターン照合アルゴリズムを開発し,その評価を行った. 続きを見る
本文を見る

類似資料: