シストリックアルゴリズムとNFAに基づくパターン非依存正規表現マッチングハードウェア

摘要

本論文では，シストリックアルゴリズムと非決定性有限オートマトン（NFA)に基づくパターン非依存正規表現マッチングハードウェアを提案する.シストリックアルゴリズムに基づくハードウェアは単純な回路構造であるが,扱う正規表現のクラスが制限される.一方，NFAに基づくハードウェアは任意の正規表現を扱うことができるが,回路構造が複雑である.本論文では，各方式のマッチングハードウェアの利点を活かしながら組み合わせることで，任意の正規表現パターンに対応可能かつ回路規模がコンパクトなパターン非依存正規表現マッチングハードウェアを提案する.