特許

J-GLOBAL ID：200903062992507315

パターンマッチング装置および方法ならびにプログラム

発明者： 榑林 亮介 ,  片山 勝 ,  山中 直明 ,  塩本 公平
出願人/特許権者： 日本電信電話株式会社
代理人 (2件)： 井出 直孝 ,  下平 俊直
公報種別：公開公報
出願番号（国際出願番号）：特願2004-051654
公開番号（公開出願番号）：特開2005-242668
出願日： 2004年02月26日
公開日（公表日）： 2005年09月08日
要約：

【課題】 パターンマッチングをハードウェアで実現する際に、メモリおよび回路規模を削減し、かつスループットの向上を可能とする。【解決手段】 入力されたテキストのサフィックスに対するパターンにハッシュ関数を適用した結果として得られる文字列の最長プリフィックスを状態として持つオートマトンを構成し、そのオートマトンに同一のハッシュ関数をテキストに適用した結果として得られる文字列を入力し、パターンに一致する可能性のある入力文字列と、パターンに一致する可能性のない入力文字列との識別を行う。次に、ハッシュ関数の適用によって生成される複数の独立した文字列単位でパイプライン並列処理する。最後に、ハッシュを適用したオートマトンによって特定される、パターンと一致する可能性のあるテキスト中の文字列とそのテキストに一致する可能性のあるパターンとを正確に照合する。【選択図】 図1

請求項（抜粋）：

入力文字列であるテキストから複数種類の任意文字列であるパターンを検索するパターンマッチング装置において、 これまでに入力されたテキストのサフィックスに対するパターンにハッシュ関数を適用した結果として得られる文字列の最長プリフィックスを状態として持つオートマトンを構成する手段と、 このオートマトンに同一のハッシュ関数をテキストに適用した結果として得られる文字列を入力することによって、パターンに一致する可能性のある部分テキストと、パターンに一致する可能性のない部分テキストとの識別を行う手段と を備えたことを特徴とするパターンマッチング装置。

IPC (1件)：

G06F17/30

FI (3件)：

G06F17/30 415 ,  G06F17/30 170A ,  G06F17/30 412

Fターム (5件)：

5B075ND03 ,  5B075NK45 ,  5B075QS01 ,  5B075QS05 ,  5B075UU06

引用特許：

審査官引用 (2件)

• 特開昭63-141127
  
• テーブルを用いたデータ処理装置および処理システム
  公報種別：公開公報   出願番号：特願2000-036874   出願人：富士通株式会社