圧縮データ上の高速パタン照合アルゴリズムを用いた知的全文検索システムの開発

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

圧縮データ上の高速パタン照合アルゴリズムを用いた知的全文検索システムの開発

フォーマット:
助成・補助金
Kyushu Univ. Production 九州大学成果文献
タイトル(他言語):
Development of Intelligent Full-text Search System using Efficient Pattern Matching Algorithms on Compressed Data
責任表示:
篠原 歩(九州大学・大学院・システム情報科学研究院・助教授)
SHINOHARA Ayumi(九州大学・大学院・システム情報科学研究院・助教授)
本文言語:
日本語
研究期間:
1998-2000
概要(最新報告):
圧縮データ上のパターン照合アルゴリズムの開発に関しては,理論的観点からのアプローチとして,辞書式データ圧縮法の統一的枠組み(Collage system)を開発し,その枠組みの上で,Knuth-Morris-Pratt型(KMP)とBoyer-Moore型(BM)の両方の照合アルゴリズムを開発することに成功した.KMPとBMは,通常のテキストに対する最も基本的な照合アルゴリズムである.これらをByte-Pair-Encoding(BPE)圧縮に適合させることで,実用上,最も高速な圧縮文字列照合アルゴリズムが得られることを実験的に確認した.さらに,このCollage Systemに対して,一般的な複数文字列照合アルゴリズムの開発にも成功した.この手法は,近似文字列照合を行う際にも有用であることも確認できた.この手法を,有望な圧縮プログラムSequiturに対して容易に適用でき,また実用上も有用であることが明らかになった.さらに,テキストのみならずパターンも圧縮された設定において,平衡直線的プログラムに対する圧縮文字列照合アルゴリズムの開発も行った.この平衡直線的プログラムは,圧縮率という観点からは一般の直線的プログラムよりも劣るが,しかしながら圧縮文字列照合の観点からはより有用であることがわかった.また,文字列の部分列を判定するための効率のよいデータ構造である部分列オートマトンを高速に構築するオンラインアルゴリズムの開発を行った.このアルゴリズムは,現在知られている中で最も高速であり,知識発見システムの実行速度を上げるためにも有用であることを確認した.一方,データベースからの知識発見に関しても,例から木の変換規則を学習するアルゴリズムや,大きなテキストデータベースから語の最適な結合規則を見つけるアルゴリズムを開発できた. 続きを見る
本文を見る

類似資料: