パタン照合アルゴリズムの効率化に関する研究

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

パタン照合アルゴリズムの効率化に関する研究

フォーマット:
助成・補助金
Kyushu Univ. Production 九州大学成果文献
タイトル(他言語):
Studies on String Pattern Matching Algorithms
責任表示:
有川 節夫(九大・理学部・教授)
Arikawa Setsuo(九大・理学部・教授)
本文言語:
日本語
研究期間:
1985-1986
概要(最新報告):
パタン照合アルゴリズムの効率化を実現し、それを実用的システムの中心的技法として応用するために、次下の点に重点を置いて研究を進めてきた。 1)パタン照合アルゴリズムの調査研究。 2)日本語テキスト用のパタン照合アルゴリズムの研究開発。 3)日本語テキスト用の複数文字列同時置き換え用のパタン照合アルゴリズムの研究開発。 4)汎用テキストデータベース管理システムSIGMAの改訂。 まず、1)については、Boyer-Moore型,Knuth-Morris-Pratt,Aho-Corasickの手法とその改良等に関して、詳細な調査を行い、1個のキーワードを対象としてアルゴリズムとしては最高速のBoyer-Moore法を大型計算機センターで開発したAIRシステムの新しい機能として実現した。2)については、コード系が複雑な日本語テキスト用に、複数キーワードが同時に扱えるAho-Corasick法を先に開発した文字列分割法の極く自然な一般化という形で、極めて高速な手法を確立した。3)については、既に研究代表者が研究開発していた手法を2)とほぼ同様な手法で一般化し、その効率的な実現法を研究した。4)については、昭和56年に研究開発し、大型計算機センターから一般公開しているSIGMAシステムを日本語テキストも扱えるように全面的に改訂した。これによりSIGMAの有用性が飛躍的に増大し、新しい応用面も拓けてきた。 上記の研究の他に、パタン照合問題に関連した、基礎的な研究成果も得た。論理プログラムにおけるパタン照合、すなわち単一化を拡張し、計算を伴う関数を扱えるようにし、その精緻な意味論を展開した。また、正則表現間の等式証明プログラムを開発し、単一化に関する問題点を明らかにした。 続きを見る
本文を見る

類似資料: