ダブル配列を用いた AC 法の効率的なパターン照合
スポンサーリンク
概要
- 論文の詳細を見る
パターン照合は文書処理やアンチウイルスなどのソフトウエアに用いられ,メモリ消費量が小さく,照合速度が高速なアルゴリズムが求められる.AC 法は複数パターンの照合に有効な手法で,AC マシンと呼ばれる一種の有限オートマトンを登録パターン集合から構築し,対象データを線形時間で照合する手法である.本論文では,ダブル配列を用いて遷移先関数を拡張した AC マシンを提案し,他手法との比較実験によりその有効性を示す.また提案マシンの応用例として,アンチウイルスソフト ClamAntiVirus に提案マシンを実装する.実験の結果,提案マシンは他手法よりも小さい記憶領域でデータ構造を実現し,対象データを高速に照合した.また,提案マシンを実装した ClamAntiVirus は,システムの稼働時間を 72%,照合時に必要な記憶領域を 70% にできることを示した.
- 2008-09-30
著者
関連論文
- 遷移先関数を拡張した効率的なパターン照合機械の設計と実装(パターン照合・パターン発見,データ工学論文)
- ダブル配列の遷移拡張によるLR構文解析表の実現と解析速度の高速化
- ダブル配列により状態遷移を高速化したLR解析表の実現
- 6W-4 ダブル配列によるGLR解析表の設計(構文解析・生成・学習,学生セッション,人工知能と認知科学,情報処理学会創立50周年記念)
- 6R-6 ダブル配列上のシングル節点に着目した更新法の提案(データベース技術,学生セッション,データベースとメディア,情報処理学会創立50周年記念)
- D-002 ダブル配列による遷移表を用いたLR解析におけるshift・goto操作の高速化(データベース,一般論文)
- RD-001 ダブル配列の遷移集合管理による追加・削除処理の高速化(データベース,査読付き論文)
- ダブル配列により状態遷移を高速化したLR解析表の実現
- ダブル配列を用いたACマシンにおける遷移の分岐別管理による効率的な辞書構造の実現
- 教育実践という視点を核にした一般情報教育を体系的に学ぶWeb教材の開発とその評価
- ダブル配列により状態遷移を高速化したLR解析表の実現 (言語理解とコミュニケーション)
- ダブル配列を用いた AC 法の効率的なパターン照合
- D-032 複数パターンを高速に照合する遷移関数の実現(データベース,一般論文)
- D-029 ダブル配列における一方向分岐の遷移あたりに要する計算量の抑制(データベース,一般論文)
- D-028 遷移先節点集合の管理によるダブル配列の更新手法(データベース,一般論文)
- 4P-6 ClamAVのAC法をダブル配列により拡張したアンチウイルスエンジンの提案(アルゴリズムとその応用,学生セッション,ソフトウェア科学・工学)
- 4P-5 複数パターンマッチングマシンにおける遷移先決定関数の最適化(アルゴリズムとその応用,学生セッション,ソフトウェア科学・工学)
- D-017 パトリシアを多分木に拡張したデータ構造の構築方法(D分野:データベース)
- D-016 ダブル配列を用いたAC法の照合アルゴリズム(D分野:データベース)