AHO-CORASICKアルゴリズムに基づいた多文字変換ストリングマッチング・アーキテクチャ

CHEN Chien-Chi; WANG Sheng-De

文献

J-GLOBAL ID：201302215035664336 整理番号：13A1870061

AHO-CORASICKアルゴリズムに基づいた多文字変換ストリングマッチング・アーキテクチャ

A MULTI-CHARACTER TRANSITION STRING MATCHING ARCHITECTURE BASED ON AHO-CORASICK ALGORITHM

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで {{ this.onShowJLink("http://jdream3.com/lp/jglobal/index.html?docNo=13A1870061&from=J-GLOBAL&jstjournalNo=F1199A") }}

著者 (2件)： ,
資料名：
巻： 8 号： 12 ページ： 8367-8386 発行年： 2012年12月
JST資料番号： F1199A ISSN： 1349-4198 資料種別：逐次刊行物 (A)
記事区分：原著論文発行国：日本 (JPN) 言語：英語 (EN)

通常,ハードウェア文字列照合アーキテクチャは,侵入検出システムなどの高速におけるコンテンツフィルターに必要がある様々なアプリケーションにおけるストリングマッチングを加速するのに使用される。しかしながら,文字によるデータデータキャラクタ点検のハードウェア文字列照合アーキテクチャの処理能力は,達成可能な最も高いクロックレートによって制限される。この報告書では,Aho-Corasickアルゴリズムに基づくストリングマッチングアーキテクチャを提示する。提案されたアーキテクチャは同時に複数の文字を点検できる。そして,ストリングマッチングの処理能力は乗算することができる。最初に,Aho-Corasick接頭語ツリー(AC-trie)に基づく変換あたり複数の文字を受け付ける多文字有限状態マシン(FSM)を組み立てるために直感的なアルゴリズムを記述する。そして,派生している多文字FSMから作り出される遷移規則を処理するための複数のマッチングユニットから成る多文字変換ストリングマッチングのためのアーキテクチャを提案する。提案されたアーキテクチャのデザインは,初期状態にリンクされた不具合関数から得られた遷移規則を減少させるのにAC-trieの不具合リンクの特性を利用する。その結果,一度に点検された文字の数が増大するので,状態成長率は派生している多文字遷移規則の数において適度である。提案されたアーキテクチャはASICデバイス上で評価のため実装された。そして,結果としての処理能力は142MHzのクロック操作された4文字列のマッチングインプリメンテーションのために4.5 Gbpsを実現できる。(翻訳著者抄録)

, , , ,
, , ,

パターン認識 , 自然語処理

引用文献 (11件)：

A. V. Aho and M. J. Corasick, Efficient string matching: An aid to bibliographic search, Commun. ACM, vol.18, pp.333-340, 1975.
SNORT Network Intrusion Detection System, http://www.snort.org.
M. Alicherry, M. Muthuprasanna and V. Kumar, High speed pattern matching for network IDS/IPS, IEEE ICNP, pp.187-196, 2006.
D. Pao, W. Lin and B. Liu, A memory-efficient pipelined implementation of the Aho-Corasick string-matching algorithm, ACM Trans. on Archit. Code Optim., vol.7, pp.1-27, 2010.
W. Lin and B. Liu, Pipelined parallel AC-based approach for multi-string matching, IEEE ICPADS, pp.665-672, 2008.

, , ,

前のページに戻る