効率良い正規表現照合のための並列ビット分配にもとづいたハードウェア指向アルゴリズム

摘要

In this paper, we study the regular expression matching problem for fast data stream processing. We present an efficient algorithm for based on new bit-parallel methods, called parallel scatter and gather exploiting bit-parallelism in a computer word. Finally, we show an architecture for a hardware implementation of our algorithm. The architecture can change its regular expression patterns on-the-fly without expensive reconfiguration.%本稿では，重要なデータストリーム処理問題の一つである正規表現パターン照合に対して，ビット並列型パターン照合手法に基づいた高速なハードウェア指向アルゴリズムを提案する．並列ビット分配と呼ぶ新しいビット並列手法を用いて，文字と，連接，和，Kleeneプラスから構成される非消去的正規表現のクラスに対して，O（mdlog b＋m|∑|）前処理時間とO（mdlog b/w＋m|∑|/w）領域を用いて，O（mdnlog b/w）実行時間の効率的な正規表現照合アルゴリズムを与える．これはd，b,|∑|が定数の場合に，O（mn/w）実行時間とO（m/w）領域の高速なアルゴリズムを与える．ここで，nは入力長を表し．Mと，d，bは，それぞれ，パターンの長さと，深さ，最大戻り幅を，wは計算機のワード長，|∑|はアルファベットの要素数を表す．さらに，このアルゴリズムを用いて，回路の再構成を伴わずにパターンの変更を可能なハードウェア実装のアーキテクチャを示す．