講演抄録/キーワード |
講演名 |
2010-01-27 12:40
効率良い正規表現照合のための並列ビット分配にもとづいたハードウェア指向アルゴリズム ○金田悠作・吉澤真吾・湊 真一・有村博紀・宮永喜一(北大) VLD2009-90 CPSY2009-72 RECONF2009-75 |
抄録 |
(和) |
本稿では,重要なデータストリーム処理問題の一つである正規表現パターン照合に対して,ビット並列型パターン照合手法に基づいた高速なハードウェア指向アルゴリズムを提案する.並列ビット分配と呼ぶ新しいビット並列手法を用いて,文字と,連接,和,Kleeneプラスから構成される非消去的正規表現のクラスに対して,$O(md\log b + m|\Sigma|)$前処理時間と$O(md\log b/w + m|\Sigma|/w)$領域を用いて,$O(mdn\log b/w)$実行時間の効率的な正規表現照合アルゴリズムを与える.これは$d, b, |\Sigma|$が定数の場合に,$O(mn/w)$実行時間と$O(m/w)$領域の高速なアルゴリズムを与える.ここで,$n$は入力長を表し,$m$と,$d$,$b$は,それぞれ,パターンの長さと,深さ,最大戻り幅を,$w$は計算機のワード長,$|\Sigma|$はアルファベットの要素数を表す.さらに,このアルゴリズムを用いて,回路の再構成を伴わずにパターンの変更を可能なハードウェア実装のアーキテクチャを示す. |
(英) |
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. |
キーワード |
(和) |
ビット並列アルゴリズム / 正規表現 / パターン照合 / ハードウェアアルゴリズム / / / / |
(英) |
Bit-Parallel algorithm / Regular expression / Pattern matching / Hardware algorithm / / / / |
文献情報 |
信学技報, vol. 109, no. 395, RECONF2009-75, pp. 131-136, 2010年1月. |
資料番号 |
RECONF2009-75 |
発行日 |
2010-01-19 (VLD, CPSY, RECONF) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
VLD2009-90 CPSY2009-72 RECONF2009-75 |