(57)【要約】  本発明は、１文字遷移の有限オートマトンの状態数を増加させることなく、任意の文字数で遷移条件を記述する有限オートマトンへの変換を可能にするシステム、方法、プログラムを提供する。ＮＦＡ変換手段２１は、入力装置１から同時並列処理文字数を受け取り、ＮＦＡ記述行列記憶部３１に記憶されている１文字遷移の有限オートマトンの記述行列と、ＮＦＡ変換結果行列記憶部３２に記憶された途中の変換結果である記述行列を用いて、同時並列処理文字数での遷移条件をもつ有限オートマトンへ変換処理を行う。ＮＦＡ変換手段２１は、途中結果を逐次ＮＦＡ変換結果行列記憶部３２へ結果を記憶させる。変換が完了すれば、結果出力手段２２は、結果のＮＦＡ記述行列をＮＦＡ変換結果行列記憶部３２から読み出し、出力装置４へ出力する。
2008081932.tif 000002
【特許請求の範囲】
【請求項１】
固定文字数の遷移条件から成る有限オートマトンの遷移条件の文字数を、任意に指定する文字数に増加させる手段を有することを特徴とする有限オートマトン生成システム。
【請求項２】
前記有限オートマトンは、行列形式で記述されていることを特徴とする請求項１に記載の有限オートマトン生成システム。
【請求項３】
前記増加させる手段は、元の有限オートマトンの状態数を変化させないことを特徴とする請求項１または請求項２に記載の有限オートマトン生成システム。
【請求項４】
前記増加させる手段は、予め定義された演算規則をもった行列演算に従うように構成されていることを特徴とする請求項２または請求項３に記載の有限オートマトン生成システム。
【請求項５】
前記増加させる手段は、予め定義された演算規則を複数の部分行列を用いた行列演算に適用するように構成されていることを特徴とする請求項２または請求項３に記載の有限オートマトン生成システム。
【請求項６】
前記複数の部分行列を用いた行列演算は、演算を行う度に部分行列を生成し、使用することを特徴とする請求項５に記載の有限オートマトン生成システム。
【請求項７】
前記複数の部分行列を用いた行列演算は、予め部分行列を生成しておき、前記部分行列を使用することを特徴とする請求項５に記載の有限オートマトン生成システム。
【請求項８】
予め行列の形式で記述された固定文字数の遷移条件を有する有限オートマトンを記憶するＮＦＡ記述行列記憶手段と、
前記ＮＦＡ記述行列記憶手段に記憶されている行列で記述された有限オートマトンの遷移条件の文字数を増加させる変換を行うＮＦＡ変換手段と、
前記ＮＦＡ変換手段による変換途中の有限オートマトン記述行列を記憶させるＮＦＡ変換結果行列記憶手段と、
前記遷移条件の文字数を、任意に指定する文字数に増加させた有限オートマトンを出力する結果出力手段と
を備えたことを特徴とする有限オートマトン生成システム。
【請求項９】
前記ＮＦＡ変換手段は、１文字遷移の有限オートマトン記述行列又はp文字遷移の有限オートマトン記述行列を、前記ＮＦＡ記述行列記憶手段又は前記ＮＦＡ変換結果行列記憶手段からそれぞれ読み出し、前記読み出した有限オートマトン記述行列を複数の部分行列に分割してk文字遷移の有限オートマトン記述行列を生成し、生成した前記k文字遷移の有限オートマトン記述行列を前記ＮＦＡ変換結果行列記憶手段へ記憶させる処理を繰り返すことで、指定された同時並列処理文字数の有限オートマトンを生成する、ことを特徴とする請求項８に記載の有限オートマトン生成システム。
【請求項１０】
予め行列の形式で記述された固定文字数の遷移条件を有する有限オートマトンを記憶するＮＦＡ記述行列記憶手段と、
前記ＮＦＡ記述行列記憶手段に記憶されている有限オートマトンを記述した行列を、複数の部分行列に分割するＮＦＡ記述行列分割手段と、
前記分割された複数の部分行列を用いて、元の有限オートマトンの遷移条件の文字数を増加させる変換を行うＮＦＡ変換手段と、
前記ＮＦＡ変換手段による変換途中の有限オートマトン記述行列を記憶させるＮＦＡ変換結果行列記憶手段と、
前記ＮＦＡ変換手段による変換途中の有限オートマトン記述行列の複数の部分行列を記憶させるＮＦＡ変換結果部分行列記憶手段と、
前記遷移条件の文字数を、任意に指定する文字数に増加させた有限オートマトンを出力する結果出力手段と
を備えたことを特徴とする有限オートマトン生成システム。
【請求項１１】
前記増加させる手段は、入力された正規表現を、１文字の遷移条件をもつ有限オートマトンに変換し、変換された有限オートマトンの遷移条件の文字数を任意に増加させることを特徴とする請求項１から請求項３のいずれかに記載の有限オートマトン生成システム。
【請求項１２】
入力された正規表現を、１文字の遷移条件をもつ有限オートマトンを記述する行列に変換するＮＦＡ記述行列生成手段と、
前記ＮＦＡ記述行列生成手段による変換後の行列を記憶するＮＦＡ記述行列記憶手段と、
前記ＮＦＡ記述行列記憶手段に記憶されている行列で記述された有限オートマトンの遷移条件の文字数を増加させる変換を行うＮＦＡ変換手段と、
前記ＮＦＡ変換手段による変換途中の有限オートマトン記述行列を記憶させるＮＦＡ変換結果行列記憶手段と、
前記遷移条件の文字数を、任意に指定する文字数に増加させた有限オートマトンを出力する結果出力手段と
を備えたことを特徴とする有限オートマトン生成システム。
【請求項１３】
入力された正規表現を、１文字の遷移条件をもつ有限オートマトンを記述する行列に変換するＮＦＡ記述行列生成手段と、
前記ＮＦＡ記述行列生成手段による変換後の行列を記憶するＮＦＡ記述行列記憶手段と、
前記ＮＦＡ記述行列記憶手段に記憶されている有限オートマトンを記述した行列を複数の部分行列に分割するＮＦＡ記述行列分割手段と、
前記分割された複数の部分行列を用いて、元の有限オートマトンの遷移条件の文字数を増加させる変換を行うＮＦＡ変換手段と、
前記ＮＦＡ変換手段による変換途中の有限オートマトン記述行列を記憶させるＮＦＡ変換結果行列記憶手段と、
前記ＮＦＡ変換手段による変換途中の有限オートマトン記述行列の複数の部分行列を記憶させるＮＦＡ変換結果部分行列記憶手段と、
前記遷移条件の文字数を、任意に指定する文字数に増加させた有限オートマトンを出力する結果出力手段と
を備えたことを特徴とする有限オートマトン生成システム。
【請求項１４】
前記結果出力手段は、前記任意に指定する文字数に増加させた有限オートマトンを、行列形式及び／又は状態遷移図で、出力することを特徴とする請求項８、９、１０、１２、１３のいずれか一に記載の有限オートマトン生成システム。
【請求項１５】
固定文字数の遷移条件から成る有限オートマトンの遷移条件の文字数を、任意に指定する文字数に増加させることを特徴とする有限オートマトン生成方法。
【請求項１６】
前記有限オートマトンは、行列形式で記述されていることを特徴とする請求項１５に記載の有限オートマトン生成方法。
【請求項１７】
元の有限オートマトンの状態数を変化させないことを特徴とする請求項１５または請求項１６に記載の有限オートマトン生成方法。
【請求項１８】
予め定義された演算規則をもった行列演算に従って、有限オートマトンの遷移条件の文字数を増加させることを特徴とする請求項１６または請求項１７に記載の有限オートマトン生成方法。
【請求項１９】
予め定義された演算規則を複数の部分行列を用いた行列演算に適用することで、有限オートマトンの遷移条件の文字数を増加させることを特徴とする請求項１６または請求項１７に記載の有限オートマトン生成方法。
【請求項２０】
前記複数の部分行列を用いた行列演算は、演算を行う度に部分行列を生成し、使用することを特徴とする請求項１９に記載の有限オートマトン生成方法。
【請求項２１】
前記複数の部分行列を用いた行列演算は、予め部分行列を生成しておき、前記部分行列を使用することを特徴とする請求項１９に記載の有限オートマトン生成方法。
【請求項２２】
予め行列の形式で記述された固定文字数の遷移条件を有する有限オートマトンを記憶しておき、
前記記憶されている行列で記述された有限オートマトンの遷移条件の文字数を増加させる変換を行い、
変換途中の有限オートマトン記述行列を記憶し、
前記遷移条件の文字数を、任意に指定する文字数に増加させた有限オートマトンを出力することを特徴とする有限オートマトン生成方法。
【請求項２３】
予め記憶されている１文字遷移の有限オートマトン記述行列又はp文字遷移の有限オートマトン記述行列を読み出し、前記読み出した有限オートマトン記述行列を複数の部分行列に分割してk文字遷移の有限オートマトン記述行列を生成し、生成した前記k文字遷移の有限オートマトン記述行列を記憶させる処理を繰り返すことで、指定された同時並列処理文字数の有限オートマトンを生成する、ことを特徴とする請求項２２記載の有限オートマトン生成方法。
【請求項２４】
予め行列の形式で記述された固定文字数の遷移条件を有する有限オートマトンを記憶しておき、
前記記憶されている有限オートマトンを記述した行列を複数の部分行列に分割し、
前記分割された複数の部分行列を用いて元の有限オートマトンの遷移条件の文字数を増加させる変換を行い、
変換途中の有限オートマトン記述行列を記憶し、
変換途中の有限オートマトン記述行列の複数の部分行列を記憶し、
前記遷移条件の文字数を、任意に指定する文字数に増加させた有限オートマトンを出力することを特徴とする有限オートマトン生成方法。
【請求項２５】
入力された正規表現を、１文字の遷移条件をもつ有限オートマトンに変換し、
変換された有限オートマトンの遷移条件の文字数を、任意に増加させることを特徴とする請求項１５から請求項１７のいずれかに記載の有限オートマトン生成方法。
【請求項２６】
入力された正規表現を、１文字の遷移条件をもつ有限オートマトンを記述する行列に変換し、
変換後の行列を記憶しておき、
前記記憶されている行列で記述された有限オートマトンの遷移条件の文字数を増加させる変換を行い、
変換途中の有限オートマトン記述行列を記憶し、
前記遷移条件の文字数を、任意に指定する文字数に増加させた有限オートマトンを出力することを特徴とする有限オートマトン生成方法。
【請求項２７】
入力された正規表現を、１文字の遷移条件をもつ有限オートマトンを記述する行列に、変換し、
変換後の行列を記憶しておき、
前記変換後の行列を複数の部分行列に分割し、
前記分割された複数の部分行列を用いて、元の有限オートマトンの遷移条件の文字数を増加させる変換を行い、
変換途中の有限オートマトン記述行列を記憶し、
変換途中の有限オートマトン記述行列の複数の部分行列を記憶し、
前記遷移条件の文字数を、任意に指定する文字数に増加させた有限オートマトンを出力することを特徴とする有限オートマトン生成方法。
【請求項２８】
前記任意に指定する文字数に増加させた有限オートマトンを、行列形式及び／又は状態遷移図で、出力することを特徴とする請求項２２、２３、２４、２６、２７のいずれか一に記載の有限オートマトン生成方法。
【請求項２９】
固定文字数の遷移条件から成る有限オートマトンの遷移条件の文字数を、任意に指定する文字数に増加させる処理をコンピュータに実行させることを特徴とする有限オートマトン生成プログラム。
【請求項３０】
前記有限オートマトンは、行列形式で記述されていることを特徴とする請求項２９に記載の有限オートマトン生成プログラム。
【請求項３１】
前記増加させる処理において、元の有限オートマトンの状態数を変化させないことを特徴とする請求項２９または請求項３０に記載の有限オートマトン生成プログラム。
【請求項３２】
前記増加させる処理において、予め定義された演算規則をもった行列演算処理をコンピュータに実行させることを特徴とする請求項３０または請求項３１に記載の有限オートマトン生成プログラム。
【請求項３３】
前記増加させる処理において、予め定義された演算規則を複数の部分行列を用いた行列演算に適用する処理をコンピュータに実行させることを特徴とする請求項３０または請求項３１に記載の有限オートマトン生成プログラム。
【請求項３４】
前記複数の部分行列を用いた行列演算は、演算を行う度に部分行列を生成し、使用することを特徴とする請求項３３に記載の有限オートマトン生成プログラム。
【請求項３５】
前記複数の部分行列を用いた行列演算は、予め部分行列を生成しておき、前記部分行列を使用することを特徴とする請求項３３に記載の有限オートマトン生成プログラム。
【請求項３６】
予め行列の形式で記述された固定文字数の遷移条件を有する有限オートマトンを記憶するＮＦＡ記述行列記憶処理と、
前記ＮＦＡ記述行列記憶処理により記憶されている行列で記述された有限オートマトンの遷移条件の文字数を増加させる変換を行うＮＦＡ変換処理と、
前記ＮＦＡ変換処理による変換途中の有限オートマトン記述行列を記憶させるＮＦＡ変換結果行列記憶処理と、
前記遷移条件の文字数を、任意に指定する文字数に増加させた有限オートマトンを出力する結果出力処理と
をコンピュータに実行させることを特徴とする有限オートマトン生成プログラム。
【請求項３７】
前記ＮＦＡ変換処理は、前記ＮＦＡ記述行列記憶処理又は前記ＮＦＡ変換結果行列記憶処理で記憶された、１文字遷移の有限オートマトン記述行列又はp文字遷移の有限オートマトン記述行列をそれぞれ読み出し、前記読み出した有限オートマトン記述行列を複数の部分行列に分割してk文字遷移の有限オートマトン記述行列を生成し、生成した前記k文字遷移の有限オートマトン記述行列を記憶させる処理を繰り返すことで、指定された同時並列処理文字数の有限オートマトンを生成する、ことを特徴とする請求項３６記載の有限オートマトン生成プログラム。
【請求項３８】
予め行列の形式で記述された固定文字数の遷移条件を有する有限オートマトンを記憶するＮＦＡ記述行列記憶処理と、
前記記憶された有限オートマトンの記述行列を複数の部分行列に分割するＮＦＡ記述行列分割処理と、
前記分割された複数の部分行列を用いて、元の有限オートマトンの遷移条件の文字数を増加させる変換を行うＮＦＡ変換処理と、
前記ＮＦＡ変換処理による変換途中の有限オートマトン記述行列を記憶させるＮＦＡ変換結果行列記憶処理と、
前記ＮＦＡ変換処理による変換途中の有限オートマトン記述行列の複数の部分行列を記憶させるＮＦＡ変換結果部分行列記憶処理と、
前記遷移条件の文字数を、任意に指定する文字数に増加させた有限オートマトンを出力する結果出力処理と
をコンピュータに実行させることを特徴とする有限オートマトン生成プログラム。
【請求項３９】
前記増加させる処理において、入力された正規表現を、１文字の遷移条件をもつ有限オートマトンに変換し、
変換された有限オートマトンの遷移条件の文字数を、任意に増加させる処理をコンピュータに実行させることを特徴とする請求項２９から請求項３１のいずれかに記載の有限オートマトン生成プログラム。
【請求項４０】
入力された正規表現を、１文字の遷移条件をもつ有限オートマトンを記述する行列に変換するＮＦＡ記述行列生成処理と、
前記ＮＦＡ記述行列生成処理による変換後の行列を記憶するＮＦＡ記述行列記憶処理と、
前記ＮＦＡ記述行列記憶処理により記憶されている行列で記述された有限オートマトンの遷移条件の文字数を増加させる変換を行うＮＦＡ変換処理と、
前記ＮＦＡ変換処理による変換途中の有限オートマトン記述行列を記憶させるＮＦＡ変換結果行列記憶処理と、
前記遷移条件の文字数を、任意に指定する文字数に増加させた有限オートマトンを出力する結果出力処理と
をコンピュータに実行させることを特徴とする有限オートマトン生成プログラム。
【請求項４１】
入力された正規表現を、１文字の遷移条件をもつ有限オートマトンを記述する行列に変換するＮＦＡ記述行列生成処理と、
前記ＮＦＡ記述行列生成処理による変換後の行列を記憶するＮＦＡ記述行列記憶処理と、
前記ＮＦＡ記述行列記憶処理により記憶されている有限オートマトンを記述した行列を複数の部分行列に分割するＮＦＡ記述行列分割処理と、
前記分割された複数の部分行列を用いて元の有限オートマトンの遷移条件の文字数を増加させる変換を行うＮＦＡ変換処理と、
前記ＮＦＡ変換処理による変換途中の有限オートマトン記述行列を記憶させるＮＦＡ変換結果行列記憶処理と、
前記ＮＦＡ変換処理による変換途中の有限オートマトン記述行列の複数の部分行列を記憶させるＮＦＡ変換結果部分行列記憶処理と、
前記遷移条件の文字数を、任意に指定する文字数に増加させた有限オートマトンを出力する結果出力処理と
をコンピュータに実行させることを特徴とする有限オートマトン生成プログラム。
【請求項４２】
前記結果出力処理は、前記任意に指定する文字数に増加させた有限オートマトンを、行列形式及び／又は状態遷移図で出力する、ことを特徴とする請求項３６、３７、３８、４０、４１のいずれか一に記載の有限オートマトン生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
［関連出願の記載］
本発明は、日本国特許出願：特願２００６−３５５５３３号（２００６年１２月２８月日出願）の優先権主張に基づくものであり、同出願の全記載内容は引用をもって本書に組み込み記載されているものとする。【０００２】
本発明は、文字列照合用有限オートマトン生成技術に関し、特に複数文字列の同時並列入力による文字列照合ができる文字列照合用有限オートマトン生成システム、方法、及び生成プログラムに関する。
【背景技術】
【０００３】
従来、文字列照合（パターンマッチ）用の有限オートマトン（Ｆｉｎｉｔｅ  Ａｕｔｏｍａｔｏｎ）として、ある１つの状態から同じ文字に対して複数の遷移先を許す非決定性有限オートマトン（ＮＦＡ: Ｎｏｎ−ｄｅｔｅｒｍｉｎｉｓｔｉｃ  Ｆｉｎｉｔｅ  Ａｕｔｏｍａｔｏｎ）を用いる方法、もしくは、それを許さない決定性有限オートマトン（ＤＦＡ: Ｄｅｔｅｒｍｉｎｉｓｔｉｃ  Ｆｉｎｉｔｅ  Ａｕｔｏｍａｔｏｎ）を用いる方法がある。【０００４】
例えば、特許文献１、非特許文献１に記載されているように、ＮＦＡは、与えられた正規表現等の検索対象条件から構文木を構築し、これに基づいて生成することができる。また、ＤＦＡはＮＦＡを用いて生成することができる。【０００５】
一般的に、ソフトウェアにおけるパターンマッチング処理では、ＮＦＡやＤＦＡ等の状態をメモリに保存し、状態が遷移する度に、状態に関する情報をメモリから取り出しながらパターンマッチングを行う。この際、ＮＦＡではある入力文字に対するある状態からの遷移先として複数の状態が存在するため、どの状態へ遷移すれば正しい結果が得られるか判断できず、ひとまずどれかの状態へ遷移して処理を進め、失敗した場合にバックトラック法を用いて別の状態へ遷移するという処理が必要になる。【０００６】
一方、ＤＦＡではある入力文字に対するある状態からの遷移先が１つしかないことから、ＮＦＡよりも高速に処理が可能であるという利点がある反面、ＮＦＡよりも状態数が増加し、多くのメモリ容量が必要となるという欠点がある。【０００７】
こうしたソフトウェアにおけるパターンマッチング処理の問題を解決するため、近年、ハードウェア回路にＮＦＡを直接組み込むことにより、その並列動作による高速性を活かし、ＮＦＡを用いた高速なパターンマッチングを行う方法がある（非特許文献２）。また、1クロックサイクルにおける入力文字数を増加させることで、より検索スループットの向上を目指す方法もある（非特許文献３）。さらに、ＮＦＡの状態遷移条件を複数文字によって行うことにより、同時に複数文字の文字列入力を行うことで検索スループットの向上を図る方法も提案されてきている（非特許文献４，非特許文献５）。【０００８】
【特許文献１】特開２００３−２４２１７９号公報（第２０−３４段落、図１〜図９）
【非特許文献１】定本Ｃプログラマのためのアルゴリズムとデータ構造（第２９７−３３０頁、近藤嘉雪、１９９８年）
【非特許文献２】Proceedings of the 9th Annual IEEE Symposium on Field-Programmable Custom Computing Machines（第２２７―２３８頁、Reetinder Sidhu，Viktor K. Prasanna、２００１年）
【非特許文献３】Proceedings of 2004 IEEE International Conference on Field-Programmable Technology（第２５―３２頁、Peter Sutton、２００４年）
【非特許文献４】Proceedings of the 12th Annual IEEE Symposium on Field-Programmable Custom Computing Machines（第２４９頁−２５７頁、Christopher R. Clark、David E. Schimmel、２００４年）
【非特許文献５】情報処理学会論文誌：コンピューティングシステム  Vol.46、No.SIG12（ACS11）（第１２０−１２８頁、片下敏宏，前田敦司，小野正人，戸田賢二， 山口喜教、２００５年）
【発明の開示】
【発明が解決しようとする課題】
【０００９】
以上の特許文献１、非特許文献１乃至５の開示事項は、本書に引用をもって繰り込み記載されているものとする。以下に本発明による関連技術の分析を与える。上記したように、ハードウェアにＮＦＡを直接組み込んでパターンマッチングを行う方法には、以下のような複数の問題点があった。【００１０】
第１の問題点は、正規表現等から生成したＮＦＡを組み込むだけでは、より一層の検索スループットの向上ができないことである。【００１１】
その理由は、組み込んだＮＦＡの状態遷移条件は被検索対象文字列の入力1文字に対する条件であるため、１クロックサイクルあたり１文字の検索しか行うことができないためである。【００１２】
第２の問題点は、上記のような１文字遷移のＮＦＡは変化させず、１クロックサイクルあたりでの検索文字数を増加させるだけでは、検索スループットの向上に直接結びつかないことである。【００１３】
その理由は、１クロックサイクルあたりでの検索文字数を増加させただけでは、同時に処理を行う文字数だけパスが長くなるため、クロックサイクルの周期が増加し、結果的に動作周波数が低下してしまうためである。つまり、仮に文字数が４倍になっても、動作周波数が１／４以下になってしまう可能性もある。【００１４】
第３の問題点は、ＮＦＡの状態遷移条件を複数文字によって行う現在の方法では、正規表現のような柔軟な文字列検索ができないことである。【００１５】
その理由は、正規表現から構成されるループを含むようなＮＦＡではなく、それを展開し、ループをなくした単純な文字列検索（厳密一致：Ｅｘａｃｔ  Ｍａｔｃｈ）しか考慮されていないためである。【００１６】
第４の問題点は、ＮＦＡの状態遷移条件を複数文字に拡張する際に状態数が増加してしまうことである。【００１７】
その理由は、同時処理を行う文字数におけるオフセットを考慮し、処理する文字数分だけＮＦＡを生成するためである。【００１８】
従って、本発明が解決しようとする第１の課題は、正規表現等による柔軟な文字列検索を高速に行うための有限オートマトンの生成システム、生成方法、および生成プログラムを提供することにある。【００１９】
さらに、本発明が解決しようとする第２の課題は、１文字で遷移するＮＦＡが構築できるような検索対象を、同時並列処理を行う任意の文字数に合わせた有限オートマトンに生成するシステム、生成方法、および生成プログラムを提供することにある。【００２０】
さらに、本発明が解決しようとする第３の課題は、１文字で遷移するＮＦＡの状態数を増加させずに同時並列処理を行う文字数に合わせた有限オートマトンを生成するシステム、生成方法、および生成プログラムを提供することにある。
【課題を解決するための手段】
【００２１】
本発明によれば、固定文字数の遷移条件から成る有限オートマトンの遷移条件の文字数を、任意に指定する文字数に増加させる有限オートマトン生成システム(方法、プログラム)が提供される。前記有限オートマトンは行列形式で記述されている。本発明おいて、前記増加させる手段は、元の有限オートマトンの状態数を変化させない。あるいは、本発明において、前記増加させる手段は、予め定義された演算規則をもった行列演算に従う。あるいは、本発明において、前記増加させる手段は、予め定義された演算規則を複数の部分行列を用いた行列演算に適用する。本発明において、前記複数の部分行列を用いた行列演算は、演算を行う度に部分行列を生成し、使用する。あるいは、本発明において、前記複数の部分行列を用いた行列演算は、予め部分行列を生成しておき、前記部分行列を使用するようにしてもよい。【００２２】
本発明の第１の側面に係る有限オートマトン生成システムは、１文字遷移のＮＦＡを記述する行列を予め記憶しておくＮＦＡ記述行列記憶部（図１の３１）と、１文字遷移のＮＦＡ記述行列又はp文字遷移のＮＦＡ記述行列を必要に応じて、ＮＦＡ記述行列記憶部（図１の３１）又はＮＦＡ変換結果行列記憶部（図１の３２）からそれぞれ読み出し、生成した行列を再びＮＦＡ変換結果行列記憶部（図１の３２）へ記憶させることを繰り返すことで、指定された同時並列処理文字数のＮＦＡに変換するＮＦＡ変換手段（図１の２１）と、変換後のＮＦＡ記述行列を記憶するＮＦＡ変換結果行列記憶部（図１の３２）と、変換後のＮＦＡを出力するための結果出力手段（図１の２２）とを有する。
本発明の第２の側面に係る有限オートマトン生成システムは、１文字遷移のＮＦＡを記述する行列を予め記憶しておくＮＦＡ記述行列記憶部（図６の３１）と、変換後のＮＦＡ記述行列を記憶するＮＦＡ変換結果行列記憶部（図６の３２）と、ＮＦＡ変換手段（図６の２３）と、結果出力手段（図６の２２）とを有し、ＮＦＡ変換手段（図６の２３）は１文字遷移のＮＦＡ記述行列又はp文字遷移のＮＦＡ記述行列を必要に応じて、ＮＦＡ記述行列記憶部（図６の３１）又はＮＦＡ変換結果行列記憶部（図６の３２）からそれぞれ読み出し、これらを複数の部分行列に分割してk文字遷移のＮＦＡ記述行列を生成し、生成した行列を再びＮＦＡ変換結果行列記憶部（図６の３２）へ記憶させることを繰り返すことで、指定された同時並列処理文字数のＮＦＡを生成する。
本発明の第３の側面に係る有限オートマトン生成システムは、前記ＮＦＡ記述行列記憶部（図９の３１）に記憶されている有限オートマトンを記述した行列を、複数の部分行列に分割するＮＦＡ記述行列分割手段(図９の２４)と、前記分割された複数の部分行列を用いて、元の有限オートマトンの遷移条件の文字数を増加させる変換を行うＮＦＡ変換手段（図９の２５）と、前記ＮＦＡ変換手段による変換途中の有限オートマトン記述行列を記憶させるＮＦＡ変換結果行列記憶部（図９の３２）と、前記ＮＦＡ変換手段による変換途中の有限オートマトン記述行列の複数の部分行列を記憶させるＮＦＡ変換結果部分行列記憶部(図９の３３)と、前記遷移条件の文字数を、任意に指定する文字数に増加させた有限オートマトン記述行列を出力する結果出力手段（図９の２２）と備えている。
本発明の第１乃至第３の有限オートマトン生成システムは、このような構成を採用し、１文字遷移のＮＦＡ記述行列を、行列演算により変換することで、第１から第３の課題を解決することができる。【００２３】
また、本発明の第４の側面に係る有限オートマトン生成システムは、第１または第２または第３の有限オートマトン生成システムの構成に加え、入力された正規表現からＮＦＡ記述行列を生成するＮＦＡ記述行列生成手段（図１２の２６）を有する。このような構成を採用し、予め１文字遷移のＮＦＡ記述行列を得ていなくても、１文字で遷移するＮＦＡが構築できるような検索対象であればそのＮＦＡを生成することにより、同時並列処理文字数のＮＦＡに変換することができる。なお、上記各括弧内の図面の参照番号は、本発明と実施形態と構成との対応を分かりやすくするためのものであり、本発明を限定するためのものでないことは勿論である。
【発明の効果】
【００２４】
第１の効果は、予め記憶された１文字遷移の有限オートマトンを、複数文字の同時並列処理による文字列検索において利用することができる有限オートマトンに変換できることにある。【００２５】
その理由は、１文字遷移の有限オートマトンを所定の行列で記述することにより、ＮＦＡ変換手段によって、同時並列処理を行う文字数での遷移条件をもつ有限オートマトンに変換した後、ＮＦＡ変換結果行列記憶部に記憶するためである。【００２６】
第２の効果は、１文字遷移の有限オートマトンを所定の行列で記述することにより、変換処理が容易になり、常に同様の処理を行うことができることにある。【００２７】
その理由は、１文字遷移の有限オートマトンに関して、その初期状態や終了状態を含めて行列で記述し、ＮＦＡ変換手段によって行列演算を行うことができるためである。また、ＮＦＡ変換手段によって、行列演算の特性を活かした変換を行うことで、目的の同時並列処理を行う文字数での遷移条件をもつ有限オートマトンに変換できるまで処理を逐次的に繰り返す必要もないためである。【００２８】
第３の効果は、変換可能な検索対象に対する制限を大幅になくし、正規表現などの１文字遷移の有限オートマトンが生成できる検索対象であれば、必ず目的の同時並列処理を行う文字数での遷移条件をもつ有限オートマトンに変換できることにある。【００２９】
その理由は、ＮＦＡ記述行列生成手段により、正規表現を必ず１文字遷移のＮＦＡに変換でき、また、変換を行うＮＦＡ変換手段では、検索対象の正規表現を考慮せず、あくまで行列として記述された有限オートマトンに対して変換を行うためである。
【図面の簡単な説明】
【００３０】
【図１】本発明の第１の実施の形態の構成を示すブロック図
【図２】本発明の第１の実施の形態の動作を示す流れ図
【図３】本発明の１文字遷移のＮＦＡ記述行列を説明するための図
【図４】本発明の第１の実施の形態の動作を示す流れ図におけるステップＡ３を示す流れ図
【図５】本発明の４文字遷移のＮＦＡ記述行列を説明するための図
【図６】本発明の第２の実施の形態の構成を示すブロック図
【図７】本発明の第２の実施の形態の動作を示す流れ図
【図８】本発明の第２の実施の形態の動作を示す流れ図におけるステップＡ６を示す流れ図
【図９】本発明の第３の実施の形態の構成を示すブロック図
【図１０】本発明の第３の実施の形態の動作を示す流れ図
【図１１】本発明の第３の実施の形態の動作を示す流れ図におけるステップＡ９を示す流れ図
【図１２】本発明の第４の実施の形態の構成を示すブロック図
【図１３】本発明の第４の実施の形態の動作を示す流れ図
【符号の説明】
【００３１】
１  入力装置
２  データ処理装置
３  記憶装置
４  出力装置
５  データ処理装置
６  データ処理装置
７  記憶装置
８  データ処理装置
２１  ＮＦＡ変換手段
２２  結果出力手段
２３  ＮＦＡ変換手段
２４  ＮＦＡ記述行列分割手段
２５  ＮＦＡ変換手段
２６  ＮＦＡ記述行列生成手段
３１  ＮＦＡ記述行列記憶部
３２  ＮＦＡ変換結果行列記憶部
３３  ＮＦＡ変換結果部分行列記憶部
Ａ１  ｍ文字遷移のＮＦＡ記述行列 Mｍ生成準備ステップ
Ａ２  同時並列処理文字数 m の ＮＦＡ に変換できたかをチェックするステップ
Ａ３  k 文字遷移のＮＦＡ記述行列Mk への変換ステップ
Ａ４  同時並列処理文字数 m の ＮＦＡ 記述行列を整形するステップ
Ａ５  結果を出力するステップ
Ａ６  k 文字遷移のＮＦＡ記述行列Mk への変換ステップ
Ａ７  ＮＦＡ記述行列Sを部分行列へ分割するステップ
Ａ８  ｍ文字遷移のＮＦＡ記述行列 Mｍ生成準備ステップ
Ａ９  k 文字遷移のＮＦＡ記述行列Mk への変換ステップ
Ａ１０  正規表現からＮＦＡ記述行列S への生成ステップ
Ｂ１  k を増加させるステップ
Ｂ２  ＮＦＡ記述行列 Mk-p、Mp を読み込むステップ
Ｂ３  Mk の算出を行うステップ
Ｂ４  Mk の算出が完了したかをチェックするステップ
Ｂ５  部分行列を求めるステップ
Ｂ６  Mk の部分行列を算出するステップ
Ｂ７  部分行列の和をとり Mk  を求めるステップ
Ｂ８  ＮＦＡ記述行列 Mk-p、Mp とそれらの部分行列を読み込むステップ
【発明を実施するための最良の形態】
【００３２】
次に、本発明の実施の形態について図面を参照して詳細に説明する。【００３３】
図１は、本発明を実施するための第１の実施の形態の構成を示すブロック図である。【００３４】
図１を参照すると、本発明の第１の実施の形態は、キーボード等の入力装置１と、プログラム制御により動作するデータ処理装置２と、情報を記憶する記憶装置３と、ディスプレイ装置や印刷装置等の出力装置４とを含む。【００３５】
記憶装置３は、ＮＦＡ記述行列記憶部３１と、ＮＦＡ変換結果行列記憶部３２とを備えている。【００３６】
ＮＦＡ記述行列記憶部３１は、正規表現等から構築された１文字遷移ＮＦＡをＮＦＡ記述行列Sの形で予め記憶している。【００３７】
ＮＦＡ変換結果行列記憶部３２は、ＮＦＡ変換手段において１文字遷移のＮＦＡ記述行列Sから変換されたk文字遷移のＮＦＡの記述行列Mk を記憶する。【００３８】
データ処理装置２は、ＮＦＡ変換手段２１と、結果出力手段２２を備えている。【００３９】
ＮＦＡ変換手段２１は、１文字遷移のＮＦＡ記述行列S 、もしくは、p文字遷移のＮＦＡ記述行列Mp を必要に応じて、ＮＦＡ記述行列記憶部３１、もしくは、ＮＦＡ変換結果行列記憶部３２からそれぞれ読み出し、それらを用いてk文字遷移のＮＦＡ記述行列Mk を生成し、生成した行列Mkを再びＮＦＡ変換結果行列記憶部３２へ記憶させる。このような処理を、入力装置１から入力された同時並列処理文字数m の値に従い、m 文字遷移のＮＦＡ記述行列Mｍ が生成されるまで処理を繰り返す。【００４０】
結果出力手段２２は、m 文字遷移のＮＦＡ記述行列をＮＦＡ変換結果行列記憶部３２から読み出し、ＮＦＡ記述行列、又はそれを状態遷移図に変換して出力装置４へ出力する。ＮＦＡ変換手段２１、結果出力手段２２はデータ処理装置２上で実行されるプログラムによりその処理・機能を実現するようにしてもよいことは勿論である。【００４１】
次に、図１及び図２を参照して本発明を実施するための第１の実施の形態の動作について詳細に説明する。【００４２】
入力装置１から与えられた同時並列処理文字数 m はＮＦＡ変換手段２１に供給される。ＮＦＡ変換手段２１は、まず、目的となるm文字遷移のＮＦＡ記述行列Mmの生成準備として、変数 k  を１に、ＮＦＡ記述行列記憶部３１から読み出した１文字遷移のＮＦＡ記述行列Sを行列M1とし、行列M1をＮＦＡ変換結果行列記憶部３２へ記憶させる（ステップＡ１）。【００４３】
ここで、ｎ個の状態をもつＮＦＡに対する１文字遷移のＮＦＡ記述行列S = { sij } （i  = 1,…,n、j = 1,…, n）、ｋ文字遷移のＮＦＡ記述行列Mk = { mkij}（i = 1,…,n、j = 1,…, n）について以下に説明する。まず、ＮＦＡ記述行列の行i （i = 1,…, n）、又は列i（i = 1,…, n）は、ＮＦＡのｎ個の状態のそれぞれ１つに対応付けられ、各要素sij 、mkij は、行i、列iに対応付けられた状態から、行j、列jに対応付けられた状態への遷移条件である文字、または文字列の集合を表すものとする。このとき、“＋”を用いて複数の条件を表し、任意の文字を表す記号として、以下では“*”を用いる。【００４４】
さらに、行 i 、又は列 iに対応付けられた状態が初期状態である場合には要素sii に is を、行i 、又は列 iに対応付けられた状態が終了状態である場合には、要素sii に fs を持つものとする。例えば、正規表現“a(bc)*(d|e)”の ＮＦＡ として図３のような状態0から状態4をもつＮＦＡが構築され、状態i （i = 0,…, 4）を行i+1に対応付けた場合、記述行列Sは［式１］のように表される。【００４５】
［式１］
2008081932.tif 000003
【００４６】
ＮＦＡ変換手段２１で、上記の処理（ステップＡ１）を行うと、続いて変数 k と同時並列処理文字数 m の大小比較を行う（ステップＡ２）。変数 k よりも同時並列処理文字数m が大きな場合、まだ目的とする m 文字遷移のＮＦＡへ変換できていないと判断し、k文字遷移のＮＦＡへの変換処理を行う（ステップＡ３）。【００４７】
図４に、ステップＡ３におけるより詳細な動作の流れ図を示す。ＮＦＡ変換手段２１は、ステップＡ３において、まず変数k を増加させる（ステップＢ１）。この増加の方法として、変数k ×2が同時並列処理文字数 m 以下であれば、k = k×2、そうでなければ k = k + 1 として増加させる。続いて、ＮＦＡ変換結果行列記憶部３２から、既に記憶されているＮＦＡ記述行列 Mk-p と Mp を読み出す（ステップＢ２）。【００４８】
ここで、変数pは１以上kより小さな整数とし、読み出す Mk-p と Mp はそれらの行列が既に算出されていれば、制限はない。これらの行列を用いて、k文字遷移のＮＦＡ記述行列Mk を行列Mk-p と Mpの積を取ることで算出する。この算出においては、以下のような定義を設け、この定義に従って算出を行う。【００４９】
ａ、ｂは、is、fsを含む文字、又は文字列とし、0は空集合とした場合、各要素の演算において、以下のように定義する。【００５０】
［定義１］：    a × b = ab ≠ ba
［定義２］：    a × 0 = 0 × a = 0
［定義３］：    is × a = is a、 a ×is  = 0、is ×is  = is is
［定義４］：    a ×fs = a fs、fs × a = 0、fs ×fs  = fs fs 【００５１】
［式１］の１文字遷移のＮＦＡ記述行列S = M1を用いてM2 = M1×M1 = { m2ij }（i = 1,…, 5、j = 1,…,5、k = 2、p = 1）を算出する場合、例えば要素m215 は［式２］で求められる。【００５２】
［式２］
2008081932.tif 000004
【００５３】
上記と同様にして、M2 の各要素を算出し、全要素の算出が完了できたことを判断する（ステップＢ４）と、M2  は［式３］のように算出され、ＮＦＡ変換手段２１は２文字遷移のＮＦＡ記述行列M2  をＮＦＡ変換結果行列記憶部３２に記憶させる。【００５４】
［式３］
2008081932.tif 000005
【００５５】
さらに、同時並列処理文字数 m が４であるとした場合、４文字遷移のＮＦＡ記述行列M4  を算出するには、２文字遷移のＮＦＡ記述行列M2  を用いて、M4  ＝M2  ×M2  を算出し（k = 4 、p= 2）、［式４］に示す４文字遷移のＮＦＡ記述行列M4  を得ることができる。【００５６】
［式４］
2008081932.tif 000006
【００５７】
ＮＦＡ変換手段２１では、目的のm文字遷移のＮＦＡ記述行列までを得る（ステップＡ２）と、得た行列Mm の整形を行う（ステップＡ４）。ここでは、行列の各要素に存在するis、fs を任意の文字を表す“*”で置き換える。その結果、例えば［式４］で示す４文字遷移のＮＦＡ記述行列M4  は、［式５］のように整形する。【００５８】
［式５］
2008081932.tif 000007
【００５９】
ＮＦＡ変換手段２１は、目的のm文字遷移のＮＦＡ記述行列Mm  を得ると、結果出力手段２２に結果を得たことを通知し、結果出力手段２２は、ＮＦＡ変換結果行列記憶部３２からMm  を読み出し、出力装置４を通じて結果を出力する。この際、結果出力手段２２では、出力フォームがＮＦＡ記述行列であれば行列形式を、ＮＦＡであればＮＦＡ 記述行列 Mmから状態遷移図を作成して出力装置４に提供する。例えば、［式５］に示す４文字遷移のＮＦＡ記述行列M4  の状態遷移図は図５のようになる。但し、状態0から状態0、状態4から状態4への遷移条件“****”は初期状態、終了状態における任意の文字列を意味し、このような入力文字列は意味をなさない。このため、図中では表していない。このように、前述の［定義１］から［定義４］に示される予め定められた演算規則に従って、式２から式５に見られる行列演算処理が行われる。【００６０】
上記第１の実施の形態においては、ＮＦＡ変換に行列を用いることにより、元々の１文字遷移のＮＦＡの状態数を変化させることなく、同時並列処理文字数遷移のＮＦＡに変換することができる。更に、ＮＦＡ変換の途中結果の行列のみをＮＦＡ変換結果行列記憶部３２に記憶させることにより、少ない記憶容量でＮＦＡ変換することができる。加えて、変換途中に現在の得ているk文字遷移のＮＦＡ記述行列の k と同時並列処理文字数mにより k を増加させることで、k が同時並列処理文字数に達するまで逐次的に k 文字遷移のＮＦＡ記述行列を算出する必要が無く、また、最後にm文字遷移のＮＦＡ記述行列の整形処理を行うため、任意の文字を表す“*”が is、fs のどちらから生成されているかの判断が不要となる。従って、行列演算に関する処理が簡単になり、生成速度を向上させることができる。【００６１】
尚、上記実施例では、変数 k の増加方法を同時並列処理数 m との比較によって決定しているが、常に k = k+ 1 として変数kを増加させる方法をとっても良い。【００６２】
また、非決定性有限オートマトン（ＮＦＡ）だけでなく、決定性有限オートマトン（ＤＦＡ）に対しても、本実施の形態と同様の構成を適用することができる。【００６３】
次に、本発明を実施するための第２の実施の形態について図面を参照して詳細に説明する。【００６４】
図６は、本発明を実施するための第２の実施の形態の構成を示すブロック図である。【００６５】
図６を参照すると、本発明の第２の実施の形態に係わるデータ処理装置５は、図１に示された第１の実施の形態におけるデータ処理装置２の構成において、ＮＦＡ変換手段２１がＮＦＡ変換手段２３に置き換わった構成になる。その他の点は第１の実施の形態と同じである。【００６６】
データ処理装置５は、ＮＦＡ変換手段２３と、結果出力手段２２を備えている。【００６７】
ＮＦＡ変換手段２３は、１文字遷移のＮＦＡ記述行列S 、もしくは、p文字遷移のＮＦＡ記述行列Mp を必要に応じて、ＮＦＡ記述行列記憶部３１、もしくは、ＮＦＡ変換結果行列記憶部３２からそれぞれ読み出し、それらを３つの部分行列に分割してk 文字遷移のＮＦＡ記述行列Mk  を生成し、生成した行列Mkを再びＮＦＡ変換結果行列記憶部３２へ記憶させる。ここで、３つの分割行列として、１文字遷移のＮＦＡ記述行列Sの部分行列をS’、Si、Sa、k 文字遷移のＮＦＡ記述行列Mk  をM’k、Mik、Makとする。このような処理を、入力装置１から入力された同時並列処理文字数m の値に従い、 m 文字遷移の ＮＦＡ が生成されるまで処理を繰り返す。結果出力手段２２は、第１の実施の形態と同じであるため、説明は省略する。ＮＦＡ変換手段２３、結果出力手段２２は、データ処理装置５上で実行されるプログラムによりその処理・機能を実現するようにしてもよいことは勿論である。【００６８】
次に、図６及び図７を参照して本発明を実施するための第２の実施の形態の動作について詳細に説明する。【００６９】
入力装置１から与えられた同時並列処理文字数 m はＮＦＡ変換手段２３に供給される。ＮＦＡ変換手段２３は、まず、目的となるm文字遷移のＮＦＡ記述行列Mmの生成準備として、変数 k を １に、ＮＦＡ記述行列記憶部３１から読み出した１文字遷移のＮＦＡ記述行列Sを行列 M1 とし、行列M1 をＮＦＡ変換結果行列記憶部３２へ記憶させる（ステップＡ１）。ＮＦＡ記述行列S、M1の意味は、第１の実施の形態と同じあるため、説明は省略する。【００７０】
ＮＦＡ変換手段２３で、上記の処理（ステップＡ１）を行うと、続いて変数 k と同時並列処理文字数 m の大小比較を行う（ステップＡ２）。変数 k よりも同時並列処理文字数m が大きな場合、まだ目的とする m 文字遷移のＮＦＡへ変換できていないと判断し、k文字遷移のＮＦＡへの変換処理を行う（ステップＡ６）。【００７１】
図８に、ステップＡ６におけるより詳細な動作の流れ図を示す。ＮＦＡ変換手段２３は、ステップＡ６において、まず変数k を増加させ（ステップＢ１）、ＮＦＡ変換結果行列記憶部３２から、既に記憶されているＮＦＡ記述行列 Mk-p と Mp とを読み出す（ステップＢ２）。これらの方法は第１の実施の形態と同じあるため、説明は省略する。【００７２】
続いて、これらの行列Mk-p と Mpとから、それぞれの部分行列M’k-p、Mik-p、Mak-p、M’p、Mip、Mapを求める（ステップＢ５）。【００７３】
ここで、k文字遷移の ＮＦＡ 記述行列 Mkの部分行列 M’k、Mik 、Mak を以下のように定義する。まず、k = 1 の場合のＮＦＡ 記述行列 Mk  ＝S の部分行列 M’1、Mi1 、Ma1を次のように定義する。【００７４】
［定義５］：    部分行列 M’1  は、各要素共にis、fs 以外の要素のみをもつ行列。【００７５】
［定義６］：    部分行列Mi1  は、is  のみを要素にもち、このis  は任意の文字を表す“*”に置き換える。【００７６】
［定義７］：    部分行列Ma1  は、fs  のみを要素にもち、このfsは任意の文字を表す“*”に置き換える。【００７７】
［定義８］：    M1  ＝ M’1 + Mi1 + Ma1【００７８】
例えば、記述行列Sが［式１］のように表されるとき、M’1、Mi1 、Ma1 、M1 は［式６］のように表す。【００７９】
［式６］
2008081932.tif 000008
2008081932.tif 000009
【００８０】
また、k が 1 より大きい場合のＮＦＡ記述行列 Mk の部分行列 M’k  、Mik  、Mak  は以下の定義によって表す。【００８１】
［定義９］：    部分行列 M’kは、各要素共に最後に“*” を持たない行列。つまり、 “**a…” のような要素はあっていいが、“…a**” のような要素は持たない。【００８２】
［定義１０］：  部分行列 Mikは、各要素共に初期状態を示すisから置き換えられた“*”の積である “**…” のような要素しか持たない。【００８３】
［定義１１］：  部分行列 Makは、各要素共に最後に “*” を持つものだけで構成される行列。つまり、“…a**” のような要素のみを持つ。【００８４】
ＮＦＡ変換手段２３は、上記のような部分行列を用いて、k文字遷移のＮＦＡ記述行列Mk の部分行列M’k、Mik、Mak を求める。このときの算出には、第１の実施の形態でも定義した定義１から定義４を用いる。ここで、Mk = Mk-p×Mp を定義１から定義４を用いて算出すると、［式７］を得る。【００８５】
［式７］
2008081932.tif 000010
【００８６】
定義３、４より、M’k-p×Mip = 0、Mak-p×M’p =0、Mak-p×Mip = 0 となるので、［式７］は［式８］で表される。【００８７】
［式８］
2008081932.tif 000011
【００８８】
定義９、１０、１１と［式８］とにより、k文字遷移のＮＦＡ記述行列Mk の部分行列M’k、Mik、Mak は［式９］のように定義できる。なお、［式９］の演算では、任意の文字を表す“＊”は通常の文字として扱い、計算を行う。
【００８９】
［式９］
2008081932.tif 000012
【００９０】
ＮＦＡ変換手段２３は、ＮＦＡ変換結果行列記憶部３２から読み込んだ行列Mk-p と Mpとから、それぞれの部分行列M’k-p、Mik-p、Mak-p、M’p、Mip、Mapを求める（ステップＢ５）と、上記の［式９］よりM’k、Mik、Mak を求める（ステップＢ６）。それらの和を取ることで、k文字遷移の ＮＦＡ 記述行列 Mkを算出し（ステップＢ７）、全要素の算出が完了できたことを判断する（ステップＢ４）と、ＮＦＡ変換手段２３はk文字遷移のＮＦＡ記述行列Mk  をＮＦＡ変換結果行列記憶部３２に記憶させる。【００９１】
例えば、図３に示す正規表現“a(bc)*(d|e)”の１文字遷移のＮＦＡ記述行列S = M1（式６）の部分行列を用いてM2 の部分行列、及びその和を求めると［式１０］のようになる。【００９２】
［式１０］
2008081932.tif 000013
【００９３】
さらに、同時並列処理文字数 m が４であるとした場合、４文字遷移のＮＦＡ記述行列M4  を算出するには、２文字遷移のＮＦＡ記述行列M2  の部分行列を用いて、M4  を算出し（k = 4 、p= 2）、［式１１］に示す４文字遷移のＮＦＡ記述行列M4  の部分行列、及びM4  を得ることができる。【００９４】
［式１１］
2008081932.tif 000014
【００９５】
ＮＦＡ変換手段２３では、目的のm文字遷移のＮＦＡ記述行列までを得る（ステップＡ２）と、結果出力手段２２に結果を得たことを通知し、その後の動作は第１の実施の形態と同じあるため、説明は省略する。【００９６】
上記第２の実施の形態においては、第１の実施の形態と同様、ＮＦＡ変換に行列を用いることにより、元々の１文字遷移のＮＦＡの状態数を変化させることなく、同時並列処理文字数遷移のＮＦＡに変換することができる。また、ＮＦＡ変換手段における行列演算において、既に定義１から定義４が考慮されているため、演算途中において各要素をチェックする必要がない。このため、各部分行列の生成が必要となるものの、分岐等の処理が不要となり、生成速度を向上させることができる。【００９７】
なお、上記実施例では、第１の実施例と同様、変数 k の増加方法を同時並列処理数 m との比較によって決定しているが、常に k = k + 1 として増加させても良い。また、非決定性有限オートマトン（ＮＦＡ）だけでなく、決定性有限オートマトン（ＤＦＡ）に対しても同様の実施の形態で適用することができる。【００９８】
次に、本発明を実施するための第３の実施の形態について図面を参照して詳細に説明する。【００９９】
図９は、本発明を実施するための第３の実施の形態の構成を示すブロック図である。【０１００】
図９を参照すると、本発明の第３の実施の形態に係わるデータ処理装置６は、図６に示された第２の実施の形態におけるデータ処理装置５の構成において、ＮＦＡ変換手段２３がＮＦＡ変換手段２５に置き換わり、かつ、ＮＦＡ記述行列分割手段２４を備え、記憶装置７は、図６に示された第２の実施の形態における記憶装置３において、ＮＦＡ変換結果部分行列記憶部３３を備えている。その他の点は第２の実施の形態と同じである。【０１０１】
データ処理装置６は、ＮＦＡ記述行列分割手段２４と、ＮＦＡ変換手段２５と、結果出力手段２２を備えている。【０１０２】
ＮＦＡ記述行列分割手段２４は、１文字遷移のＮＦＡ記述行列S をＮＦＡ記述行列記憶部３１から読み出し、部分行列S’、Si、Saに分割し、１文字遷移のＮＦＡ記述行列Sと共にそれらの行列をＮＦＡ変換手段２５へと提供する。【０１０３】
ＮＦＡ変換手段２５は、ＮＦＡ記述行列分割手段２４からのＮＦＡ記述行列S、及びその部分行列S’、Si、Saを１文字遷移のＮＦＡ記述行列M1、及び、その部分行列M’1、Mi1、Ma1として受け取り、M1をＮＦＡ変換結果行列記憶部３２に、部分行列M’1、Mi1、Ma1をＮＦＡ変換結果部分行列記憶部３３に記憶させる。ＮＦＡ変換手段２５は、既に変換され、ＮＦＡ変換結果行列記憶部３２とＮＦＡ変換結果部分行列記憶部３３に記憶されているk-p文字遷移のＮＦＡ記述行列Mk-pとその部分行列M’k-p、Mik-p、Mak-p、また、p文字遷移のＮＦＡ記述行列Mp とその部分行列M’p、Mip、Mapを必要に応じて読み出し、それらを使ってk文字遷移のＮＦＡ記述行列Mkの部分行列M’k、Mik、Makを生成し、それらの和をとることでMk  を生成し、生成したそれらの行列を再びＮＦＡ変換結果行列記憶部３２、ＮＦＡ変換結果部分行列記憶部３３へ記憶させる。ここで、各種の行列の意味と結果出力手段２２は、第２の実施の形態と同じであるため、説明を省略する。【０１０４】
記憶装置７は、ＮＦＡ記述行列記憶部３１と、ＮＦＡ変換結果行列記憶部３２と、ＮＦＡ変換結果部分行列記憶部３３を備えている。【０１０５】
ＮＦＡ変換結果部分行列記憶部３３は、k 文字遷移のＮＦＡ記述行列Mk  の部分行列である M’k、Mik、Makを記憶する。ＮＦＡ記述行列記憶部３１と、ＮＦＡ変換結果行列記憶部３２については、第２の実施の形態と同じであるため、説明を省略する。本実施例において、ＮＦＡ記述行列分割手段２４と、ＮＦＡ変換手段２５と、結果出力手段２２は、データ処理装置６上で実行されるプログラムによりその処理・機能を実現するようにしてもよいことは勿論である。【０１０６】
次に、図９及び図１０を参照して本発明を実施するための第３の実施の形態の動作について詳細に説明する。【０１０７】
入力装置１から与えられた同時並列処理文字数 m はＮＦＡ変換手段２５に供給される。ＮＦＡ記述行列分割手段２４は、ＮＦＡ記述行列記憶部３１から読み出した１文字遷移のＮＦＡ記述行列Sを部分行列S’、Si、Sa に分割する（ステップＡ７）。ＮＦＡ記述行列分割手段２４は、それらの行列をＮＦＡ変換手段２５に提供し、ＮＦＡ変換手段２５は、ＮＦＡ記述行列分割手段２４から受け取ったそれぞれの行列を、１文字遷移のＮＦＡ記述行列M1、及びその部分行列M’1、Mi1、Ma1として、M1をＮＦＡ変換結果行列記憶部３２に、部分行列M’1、Mi1、Ma1をＮＦＡ変換結果部分行列記憶部３３に記憶させる（ステップＡ８）。【０１０８】
なお、ＮＦＡ記述行列S、M1の意味、及びそれら部分行列の意味は、第２の実施の形態と同じであるため、説明を省略する。【０１０９】
ＮＦＡ変換手段２５で上記の処理（ステップＡ８）を行うと、続いて変数 k と同時並列処理文字数 m の大小比較を行う（ステップＡ２）。変数 k よりも同時並列処理文字数m が大きな場合、まだ目的とする m 文字遷移のＮＦＡへ変換できていないと判断し、k文字遷移のＮＦＡへの変換処理を行う（ステップＡ９）。【０１１０】
図１１に、ステップＡ９におけるより詳細な動作の流れ図を示す。ＮＦＡ変換手段２５は、ステップＡ９において、まず変数k を増加させ（ステップＢ１）、ＮＦＡ変換結果行列記憶部３２から、既に記憶されているＮＦＡ記述行列 Mk-p と Mpを、ＮＦＡ変換結果部分行列記憶部３３から、ＮＦＡ記述行列Mk-p と Mp の部分行列M’k-p、Mik-p、Mak-p、M’p、Mip、Mapを読み出す（ステップＢ８）。その後の動作としては、算出したk文字遷移の ＮＦＡ 記述行列 MkをＮＦＡ変換結果行列記憶部３２に記憶させるだけでなく、その部分行列 M’k、Mik 、Mak をＮＦＡ変換結果部分行列記憶部３３に記憶させること以外は、第２の実施の形態と同じであるため、説明は省略する。【０１１１】
上記第３の実施の形態においては、ＮＦＡ変換手段における行列演算において、変換したk文字遷移の ＮＦＡ 記述行列 Mkだけでなく、その部分行列M’k、Mik 、Mak もＮＦＡ変換結果部分行列記憶部３３に記憶させるため、ＮＦＡ変換手段で変換を繰り返す度に部分行列への分割を行う必要がない。このため、k文字遷移のＮＦＡ記述行列の生成速度を向上させることができる。【０１１２】
なお、上記実施例では、第１、第２の実施例と同様、変数 k の増加方法を同時並列処理数 m との比較によって決定しているが、常に k = k + 1 として増加させても良い。また、非決定性有限オートマトン（ＮＦＡ）だけでなく、決定性有限オートマトン（ＤＦＡ）に対しても同様の実施の形態で適用することができる。【０１１３】
次に、本発明を実施するための第４の実施の形態について図面を参照して詳細に説明する。【０１１４】
図１２は、本発明を実施するための第４の実施の形態の構成を示すブロック図である。【０１１５】
図１２を参照すると、本発明の第４の実施の形態に係わるデータ処理装置８は、図９に示された第３の実施の形態におけるデータ処理装置６の構成において、ＮＦＡ記述行列生成手段２６を備え、その他の点は第３の実施の形態と同じである。【０１１６】
データ処理装置８は、ＮＦＡ記述行列生成手段２６と、ＮＦＡ記述行列分割手段２４と、ＮＦＡ変換手段２５と、結果出力手段２２を備えている。【０１１７】
ＮＦＡ記述行列生成手段２６は、入力装置１から正規表現そのものを提供される。ＮＦＡ記述行列生成手段２６は、正規表現を提供されると、正規表現から構文木を構築し、その構文木から１文字遷移のＮＦＡを生成する。生成したＮＦＡからＮＦＡ記述行列S を生成し、ＮＦＡ記述行列記憶部３１へと記憶させる。本実施例において、ＮＦＡ記述行列生成手段２６と、ＮＦＡ記述行列分割手段２４と、ＮＦＡ変換手段２５と、結果出力手段２２は、データ処理装置８上で実行されるプログラムによりその処理・機能を実現するようにしてもよいことは勿論である。【０１１８】
次に、図１２及び図１３を参照して本発明を実施するための第４の実施の形態の動作について詳細に説明する。【０１１９】
入力装置１から与えられた同時並列処理文字数 m はＮＦＡ変換手段２５に供給される。また、入力装置１からは正規表現そのものがＮＦＡ記述行列生成手段２６に供給される。[非特許文献１]に記載されているような正規表現を元に構文木を構築し、その構文木から１文字遷移のＮＦＡを生成する。一般的に、このような方法を用いた正規表現からＮＦＡを構築する方法では、各状態からの遷移先状態、及びその遷移条件を保持したリストがあるため、そのリストからＮＦＡ記述行列S を生成し、ＮＦＡ記述行列記憶部３１へと記憶させる（ステップＡ１０）。その後の処理は、第３の実施の形態と同じであるため、詳細な説明は省略する。【０１２０】
上記第４の実施の形態においては、予めＮＦＡ記述行列がＮＦＡ記述行列記憶部３１に記憶されていない場合において、正規表現を入力することで既存のＮＦＡ構築手法を用いてＮＦＡを構築し、そのＮＦＡ記述行列Sを生成することができる。このため、柔軟に与えられた正規表現を用いて同時並列処理文字数で遷移するＮＦＡ記述行列を生成することができる。【０１２１】
なお、上記第４の実施の形態は、第３の実施の形態の構成にＮＦＡ記述行列生成手段２６を備えた形態であるが、第１の実施の形態、及び第２の実施の形態においても同様のＮＦＡ記述行列生成手段２６を備えることで、与えられた正規表現から、指定された同時並列処理文字数で遷移するＮＦＡ記述行列を生成することができる。【０１２２】
上記第１から第４の実施の形態では、処理装置及び記憶装置の各部をハードウェアで構成したが、各部の一部または全部をプログラムとして情報処理装置に機能させるようにすることもできる。
【産業上の利用可能性】
【０１２３】
本発明の活用例として、ネットワークサービスに対する攻撃や侵入を検知する侵入検知システム（ＩＤＳ：Ｉｎｔｒｕｓｉｏｎ  Ｄｅｔｅｃｔｉｏｎ  Ｓｙｓｔｅｍ）や侵入防止システム（ＩＰＳ：Ｉｎｔｒｕｓｉｏｎ  Ｐｒｅｖｅｎｔｉｏｎ  Ｓｙｓｔｅｍ）における攻撃・侵入ルールのパターンマッチング処理を高速に実現するためのオートマトンを生成するためのプログラムといった用途に適用できる。また、パソコンやワークステーションに搭載されているソフトウェアベースでのパターンマッチング処理におけるオートマトン生成にも適用できる。
本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態ないし実施例の変更・調整が可能である。また、本発明の請求の範囲の枠内において種々の開示要素の多様な組み合わせないし選択が可能である。すなわち、本発明は、請求の範囲を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。
【図１】
2008081932.tif 000015
【図２】
2008081932.tif 000016
【図３】
2008081932.tif 000017
【図４】
2008081932.tif 000018
【図５】
2008081932.tif 000019
【図６】
2008081932.tif 000020
【図７】
2008081932.tif 000021
【図８】
2008081932.tif 000022
【図９】
2008081932.tif 000023
【図１０】
2008081932.tif 000024
【図１１】
2008081932.tif 000025
【図１２】
2008081932.tif 000026
【図１３】
2008081932.tif 000027
【国際調査報告】
2008081932.tif 000028
2008081932.tif 000029
2008081932.tif 000030