著者

蔵満 琢麻 松浦 寛生 望月久稔

出版者

情報処理学会

雑誌

情報処理学会論文誌データベース(TOD) (ISSN:18827799)

巻号頁・発行日

vol.1, no.2, pp.1-14, 2008-09-30

---

パターン照合は文書処理やアンチウイルスなどのソフトウエアに用いられ,メモリ消費量が小さく,照合速度が高速なアルゴリズムが求められる.AC 法は複数パターンの照合に有効な手法で,AC マシンと呼ばれる一種の有限オートマトンを登録パターン集合から構築し,対象データを線形時間で照合する手法である.本論文では,ダブル配列を用いて遷移先関数を拡張した AC マシンを提案し,他手法との比較実験によりその有効性を示す.また提案マシンの応用例として,アンチウイルスソフト ClamAntiVirus に提案マシンを実装する.実験の結果,提案マシンは他手法よりも小さい記憶領域でデータ構造を実現し,対象データを高速に照合した.また,提案マシンを実装した ClamAntiVirus は,システムの稼働時間を 72%,照合時に必要な記憶領域を 70% にできることを示した.Pattern matching is used for word processing and software such as antivirus. It is important to high-speed response and compact memory. Aho-Corasick algorithm is an efficient multiple pattern matching algorithm. In this paper, we present a multiple pattern matching machine with a double-array structure. It has the transition function extended. And also, we implement the proposal machine to ClamAntiVirus as an applied example. Our experiments show that the operation time decreased to 72% and required storage area decreased to 70%.