特許

J-GLOBAL ID：200903000332916381

文字列照合方法、これを用いた文書処理装置及びプログラム

発明者： 長谷川 勇
出願人/特許権者： インターナショナル・ビジネス・マシーンズ・コーポレーション
代理人 (1件)： 坂口 博 (外3名)
公報種別：公開公報
出願番号（国際出願番号）：特願2002-028736
公開番号（公開出願番号）：特開2003-242179
出願日： 2002年02月05日
公開日（公表日）： 2003年08月29日
要約：

【要約】【課題】 部分正規表現や最長一致を含むPOSIX正規表現、また複数文字照合要素を含む正規表現を、決定性有限状態オートマトンにて処理できるようにする。【解決手段】 文字列の正規表現から非決定性有限状態オートマトンを構築し、この非決定性有限状態オートマトンに基づいて決定性有限状態オートマトンを構築するオートマトン構築部210と、この決定性有限状態オートマトンを用いて文字列のマッチングを行うオートマトン判定部240とを備える。そして、このオートマトン判定部240は、マッチした文字列に関し、さらに非決定性有限状態オートマトンと決定性有限状態オートマトンとを用いて、文字列のマッチ範囲を特定する。また、このオートマトン判定部240は、処理対象である文字列の各要素に対して、決定性有限状態オートマトンの状態遷移における遷移先の状態を動的に決定しながらマッチングを行う。

請求項（抜粋）：

コンピュータを用いて文字列の照合を行う文字列照合方法において、文字列の正規表現から非決定性有限状態オートマトンを作成し、メモリに格納するステップと、前記メモリから前記非決定性有限状態オートマトンを読み出し、当該非決定性有限状態オートマトンに基づいて決定性有限状態オートマトンを作成し、メモリに格納するステップと、前記メモリから前記決定性有限状態オートマトンを読み出し、当該決定性有限状態オートマトンを用いて文字列のマッチングを行うステップと、マッチした前記文字列に関し、前記メモリから読み出した前記非決定性有限状態オートマトンと前記決定性有限状態オートマトンとを用いて、当該文字列のマッチ範囲を特定するステップとを含むことを特徴とする文字列照合方法。

IPC (2件)：

G06F 17/30 415 ,  G06F 17/30 170

FI (2件)：

G06F 17/30 415 ,  G06F 17/30 170 A

Fターム (2件)：

5B075ND03 ,  5B075QM10