ストリームデータプロセサSDP(2) : パターンマッチング方式  [in Japanese] Stream Data Processor SDP (2) : The Method of Pattern Matching  [in Japanese]

本稿では、大量のデータベースから検索、更新等の処理を高速に行うストリームデータプロセサSDPのパターンマッチング方式とハードウェア構成について報告する。パターンマッチングのハードウェアに適したアルゴリズムとしては有限状態オートマトン方式、連想メモリ方式、セルラアレイ方式等あるが、本方式はストリームデータに適し、かつ柔軟なパターンマッチングが可能な有限状態オートマトン方式を用いる。有限状態オートマトン方式は、文字列を有限の入力文字と状態の2次元からなる遷移関数で表現し、入力文字で遷移関数を参照し状態を変化させることにより検索処理を実現するものである。有限状態オートマトンの利点は、正規表現を用いた複雑なパターンの検索が可能なことと、遷移関数をメモリで実現するとハードウェアが簡単で済むことである。しかし入力文字の種類が多いと遷移関数を格納する領域が非常に大きくなり、かつ前処理時間がかかるという欠点がある。SDPは今後1チップ化を考えており、有限状態オートマトンをそのままインプリメントしたのでは、膨大な作業領域がボトルネックになると考えられる。よって本手法では、作業領域を縮小させ、かつ有限状態オートマトンの特徴を損なわない方式を考案し、インプリメントを行った。