複数パターンの文字列照合におけるマッチングマシンの動的構成法

概要

論文の詳細を見る
複数パターンの文字列照合とは, テキストと呼ばれる比較的長い一つの文字列の中にパターンと呼ばれる複数個の文字列のうちのどれかが文学部分列として含まれるか否かを判定し, 含まれていればテキスト上の位置を見つける問題である. 代表的なアルゴリズムとして知られるAho-Corasick法[1] (以下AC法と略記する)は, 与えられたパターンからマッチングマシンと呼ばれるオートマトンを構成し, それを用いて照合する方法である. またAC法を動的なパターン集合に対処できるようにするために, マッチングマシンを局所的に更新する動的構成法も既に提案されている[2]. 最近, パターンが一つの場合の効率の良いアルゴリズムとして知られるBoyer-Moore法[3]に, 決定性オートマトンの概念を導入して複数パターンヘ拡張したアルゴリズムFAST法[4]〜[6], MBM法[7]等が提案され, AC法より高速で実用的なアルゴリズムであることが示された. 本論文では, MBM法を動的なパターン集合に対処できるようにするために, マッチングマシンを動的に構成するアルゴリズムを提案する. 10個から1500個のパターン集合に対する実験により, パターンを一つ追加する場合でマッチングマシンの構成時間が約2.7倍〜78.2倍, 削除する場合で約2.3倍〜30.3倍高速になることが確認された. また, テキストとの照合時間も含めると, AC法の動的構成法よりも高速であることが確認された.
社団法人電子情報通信学会の論文
1997-08-25

複数パターンの文字列照合におけるマッチングマシンの動的構成法

スポンサーリンク

概要

著者

関連論文

スポンサーリンク