Pat

J-GLOBAL ID：200903000332916381

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

Inventor： 長谷川 勇
Applicant, Patent owner： インターナショナル・ビジネス・マシーンズ・コーポレーション
Agent (1)： 坂口 博 (外3名)
Gazette classification：公開公報
Application number (International application number)：2002028736
Publication number (International publication number)：2003242179
Application date： Feb. 05, 2002
Publication date： Aug. 29, 2003
Summary：

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

Claim (excerpt)：

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

IPC (2)：

G06F 17/30 415 ,  G06F 17/30 170

FI (2)：

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

F-Term (2)：

5B075ND03 ,  5B075QM10