パターンを実行時に設定可能な正規表現ストリングマッチングマシンとFPGAによる実現

摘要

In this paper, a high-speed string matching circuit for searching a pattern in a given text is proposed. In the circuit, a pattern is specified by a class of restricted regular expressions. The main feature of the proposed hardware, which is distinct from previous string matching circuits, is that a pattern to be retrieved can be set during the execution time. The proposed hardware was implemented on an FPGA chip, and its effectiveness was evaluated.%ストリングマッチングとは，文字や文字に対する演算からなる文字列をパターンとし，与えられたパターンに一致する文字列を入力系列から検索する操作である．本論文では，正規表現のサブクラスをパターンとするストリングマッチングに対して専用ハードウェアを提案し，FPGA上に実現して評価を行う．提案ハードウェアは従来のハードウェアとは異なり，ストリングマッチングの実行時にパターンの設定が可能という大きな利点がある．