文献

J-GLOBAL ID：200902253466364360   整理番号：09A0797632

ダブル配列を用いたAC法の効率的なパターン照合

Efficient Pattern Matching of Aho-Corasick Algorithm Using Double-Array

著者 (3件)： 蔵満琢麻 (大阪教大) ,  松浦寛生 (大阪教大) ,  望月久稔 (大阪教大)
資料名： 情報処理学会論文誌トランザクション(CD-ROM)  (情報処理学会論文誌 Computer Vision and Applications(CD-ROM))
巻： 2008  号： 1  ページ： VOL.1NO.2,1-14  発行年： 2008年11月15日 
JST資料番号： L7379A  ISSN： 1882-7772  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： パターン照合は文書処理やアンチウイルスなどのソフトウエアに用いられ,メモリ消費量が小さく,照合速度が高速なアルゴリズムが求められる。AC法は複数パターンの照合に有効な手法で,ACマシンと呼ばれる一種の有限オートマトンを登録パターン集合から構築し,対象データを線形時間で照合する手法である。本論文では,ダブル配列を用いて遷移先関数を拡張したACマシンを提案し,他手法との比較実験によりその有効性を示す。また提案マシンの応用例として,アンチウイルスソフトClamAntiVirusに提案マシンを実装する。実験の結果,提案マシンは他手法よりも小さい記憶領域でデータ構造を実現し,対象データを高速に照合した。また,提案マシンを実装したClamAntiVirusは,システムの稼働時間を72%,照合時に必要な記憶領域を70%にできることを示した。(著者抄録)

シソーラス用語： *パターンマッチング ,  *有限オートマトン ,  アルゴリズム ,  計算量 ,  配列 ,  コンピュータウイルス ,  *コンピュータセキュリティ ,  データ構造 ,  高速アルゴリズム ,  記憶容量 ,  *アンチウイルスソフトウェア ,  線形時間アルゴリズム
準シソーラス用語： *AC法 ,  タプル配列

分類 (3件)： 記号処理  (JE03000Q) ,  オートマトン理論  (JB04000O) ,  データ保護  (JD01020V)

引用文献 (14件)：

• Boyer, R. S. and Moore, J. S.: A Fast String Searching Algorithm, Comm. ACM, Vol.20, No.10, pp. 762-772(1977).
• Aho, A. V.: 文字列中のパターン照合のためのアルゴリズム, アルゴリズムと複雑さ, 丸善, chapter5, pp. 263-304(1994).
• Aho, A. V. and Corasick, M. J.: Efficient String Matching An Aid to Bibliographic Search, Comm. ACM, Vol.18, No.6, pp. 333-340(1975).
• 浦谷則好: 高速な複数文字列照合アルゴリズム: FAST, 情報処理学会論文誌, Vol.30, No.9, pp. 1119-1125(1989).
• 広瀬貞樹, 小栗伸幸, 吉澤寿夫, 山淵龍夫: 複数パターンの文字列照合におけるマッチングマシンの動的構成法, 電子情報通信学会論文誌, Vol. J80-DI, No.8, pp. 655-664(1997).

タイトルに関連する用語 (3件)： ダブル配列 ,  Ac ,  パターン照合