遷移先関数を拡張した効率的なパターン照合機械の設計と実装

摘要

コンピュータにおいて，複数パターンの照合は文字列照合だけでなく，アンチウイルスなどのソフrnトウェアにも用いられ，メモリ消費量が小さく，高速に照合するアルゴリズムが求められる．AC法は登録パrnターン集合からACマシンと呼ばれる一種の有限オートマトンを構築し，対象データを線形時間で照合する手法rnとして有名である．本論文では，ダブル配列を用いたACマシンの遷移先関数を拡張することで照合速度を高rn速化する方法を提案し，その実硯方法について述べる．また，提案手法の応用例として，アンチウイルスソフrnトClamAntiVirusに提案マシンを実装する．実験の結果，提案マシンは他手法に対し約39～81%の時間で対象rnデータを照合した．