(57)【要約】  正規表現に対応し、入力した文字列のどの位置で一致したかを単独で判別できる複数バイト処理向けＮＦＡ回路の生成を可能にする。  １−ｂｙｔｅ  ＮＦＡ変換部２１は、入力装置１から入力された１つ以上の正規表現を正規表現記憶部３１に記憶させ、それを順次読み出しε遷移のない１  ｂｙｔｅ処理のＮＦＡに変換する。Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２２は、前記生成した１  ｂｙｔｅ処理のＮＦＡを、入力装置１から入力された処理バイト数と動作モードに従って、複数バイトで処理する入力された文字列のどの位置でパターンに一致したかが判断できるＮＦＡに変換し、ＮＦＡ記憶部３２へ記憶させる。ＨＤＬ変換部２３は、Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２２から入力された上記ＮＦＡの状態遷移情報から、上記ＮＦＡ回路のハードウェア記述言語（ＨＤＬ）を生成する。
2009116646.tif 000002
【特許請求の範囲】
【請求項１】
正規表現を用いたパターンから、複数の文字数から成る遷移条件をもち、到達した終了状態によって入力された文字列のどの位置で前記パターンに一致したかを単独で判別できるＮＦＡを生成する手段を有するマルチバイト処理向け文字列照合用有限オートマトン生成装置。
【請求項２】
到達した終了状態によって入力された文字列のどの位置でパターンに一致したかを単独で判別できる有限オートマトンか、どの位置でパターンに一致したかを単独では判別できないが、状態数は前記有限オートマトンよりも少なく、回路規模が削減できる有限オートマトンかを選択して生成することができることを特徴とする請求項１に記載のマルチバイト処理向け文字列照合用有限オートマトン生成装置。
【請求項３】
入力された正規表現を記憶する正規表現記憶手段と、
前記正規表現記憶手段に記憶された正規表現からε遷移のない１  ｂｙｔｅで遷移するＮＦＡ（Ｎｏｎ−ｄｅｔｅｒｍｉｎｉｓｔｉｃ  Ｆｉｎｉｔｅ  Ａｕｔｏｍａｔｏｎ）へ変換する１−ｂｙｔｅ  ＮＦＡ変換手段と、
前記ε遷移のない１  ｂｙｔｅで遷移するＮＦＡを、指定された処理バイト数で遷移を行うＮＦＡへ変換するＭｕｌｔｉｂｙｔｅ  ＮＦＡ変換手段と、
Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換手段で変換したＮＦＡを記憶するＮＦＡ記憶手段と、
を備えることを特徴とするマルチバイト処理向け文字列照合用有限オートマトン生成装置。
【請求項４】
前記Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換手段は請求項１又は請求項２に記載のＮＦＡを生成する手段を備えることを特徴とする請求項３に記載のマルチバイト処理向け文字列照合用有限オートマトン生成装置。
【請求項５】
前記Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換手段は、指定された動作モードにより、入力された文字列のどの位置でパターンが一致したかを単独で判別できるＮＦＡを生成するか、入力された文字列のどの位置でパターンが一致したかは単独では判別できないＮＦＡを生成するかを利用目的に応じて選択できる、
ことを特徴とする請求項３又は請求項４に記載のマルチバイト処理向け文字列照合用有限オートマトン生成装置。
【請求項６】
前記１−ｂｙｔｅ  ＮＦＡ変換手段において、正規表現から変換するε遷移のない１  ｂｙｔｅで遷移するＮＦＡに対し、終了状態からは自身も含めた他の状態へ遷移しないという制約を加えることにより、前記Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換手段での変換処理が簡略化できる、
ことを特徴とする請求項３乃至請求項５いずれか一つに記載のマルチバイト処理向け文字列照合用有限オートマトン生成装置。
【請求項７】
正規表現を用いたパターンから、複数の文字数から成る遷移条件をもち、到達した終了状態によって入力された文字列のどの位置でパターンに一致したかを単独で判別できるＮＦＡを生成するＮＦＡ生成手段を有することを特徴とするマルチバイト処理向け文字列照合用有限オートマトン回路生成装置。
【請求項８】
到達した終了状態によって入力された文字列のどの位置でパターンに一致したかを単独で判別できる有限オートマトンか、どの位置でパターンに一致したかを単独では判別できないが、状態数は前記有限オートマトンよりも少なく、回路規模が削減できる有限オートマトンかを選択して生成することができることを特徴とする請求項７に記載のマルチバイト処理向け文字列照合用有限オートマトン回路生成装置。
【請求項９】
入力された正規表現を記憶する正規表現記憶手段と、
前記正規表現記憶手段に記憶された正規表現からε遷移のない１  ｂｙｔｅで遷移するＮＦＡ（Ｎｏｎ−ｄｅｔｅｒｍｉｎｉｓｔｉｃ  Ｆｉｎｉｔｅ  Ａｕｔｏｍａｔｏｎ）へ変換する１−ｂｙｔｅ  ＮＦＡ変換手段と、
前記ε遷移のない１  ｂｙｔｅで遷移するＮＦＡを、指定された処理バイト数で遷移を行うＮＦＡへ変換するＭｕｌｔｉｂｙｔｅ  ＮＦＡ変換手段と、
Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換手段で変換したＮＦＡを記憶するＮＦＡ記憶手段と、
Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換手段で変換したＮＦＡから、そのハードウェア回路を記述するハードウェア記述言語を生成するＨＤＬ変換手段と、
ＨＤＬ変換手段で変換したハードウェア記述言語を記憶するＨＤＬ記憶手段と、
を備えることを特徴とするマルチバイト処理向け文字列照合用有限オートマトン回路生成装置。
【請求項１０】
前記Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換手段は、前記ＮＦＡ生成手段を有することを特徴とする請求項９記載のマルチバイト処理向け文字列照合用有限オートマトン回路生成装置。
【請求項１１】
前記Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換手段は、指定された動作モードにより、入力された文字列のどの位置でパターンが一致したかを単独で判別できるＮＦＡを生成するか、入力された文字列のどの位置でパターンが一致したかは単独では判別できないＮＦＡを生成するかを利用目的に応じて選択できる、
ことを特徴とする請求項９又は請求項１０に記載のマルチバイト処理向け文字列照合用有限オートマトン回路生成装置。
【請求項１２】
前記１−ｂｙｔｅ  ＮＦＡ変換手段において、正規表現から変換するε遷移のない１  ｂｙｔｅで遷移するＮＦＡに対し、終了状態からは自身も含めた他の状態へ遷移しないという制約を加えることにより、前記Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換手段での変換処理が簡略化できる、
ことを特徴とする請求項９乃至請求項１１いずれか一つに記載のマルチバイト処理向け文字列照合用有限オートマトン回路生成装置。
【請求項１３】
正規表現を用いたパターンから、複数の文字数から成る遷移条件をもち、到達した終了状態によって入力された文字列のどの位置で前記パターンに一致したかを単独で判別できるＮＦＡを生成するＮＦＡ生成処理を有することを特徴とするマルチバイト処理向け文字列照合用有限オートマトン生成方法。
【請求項１４】
到達した終了状態によって入力された文字列のどの位置でパターンに一致したかを単独で判別できる有限オートマトンか、どの位置でパターンに一致したかを単独では判別できないが、状態数は前記有限オートマトンよりも少なく、回路規模が削減できる有限オートマトンかを選択して生成することができることを特徴とする請求項１３に記載のマルチバイト処理向け文字列照合用有限オートマトン生成方法。
【請求項１５】
入力された正規表現を記憶し、
前記記憶された正規表現からε遷移のない１  ｂｙｔｅで遷移するＮＦＡへ変換し、
前記ε遷移のない１  ｂｙｔｅで遷移するＮＦＡを、指定された処理バイト数で遷移を行うＮＦＡへ変換し、
前記変換したＮＦＡを記憶する、
ことを特徴とするマルチバイト処理向け文字列照合用有限オートマトン生成方法。
【請求項１６】
さらに、前記ε遷移のない１  ｂｙｔｅで遷移するＮＦＡから指定された処理バイト数で遷移を行うＮＦＡへの変換は、前記ＮＦＡ生成処理であることを特徴とする請求項１５に記載のマルチバイト処理向け文字列照合用有限オートマトン生成方法。
【請求項１７】
前記ε遷移のない１  ｂｙｔｅで遷移するＮＦＡから指定された処理バイト数で遷移を行うＮＦＡへの変換は、指定された動作モードにより、入力された文字列のどの位置でパターンが一致したかを単独で判別できるＮＦＡを生成するか、入力された文字列のどの位置でパターンが一致したかは単独では判別できないＮＦＡを生成するかを利用目的に応じて選択できる、
ことを特徴とする請求項１５又は請求項１６に記載のマルチバイト処理向け文字列照合用有限オートマトン生成方法。
【請求項１８】
前記正規表現から変換するε遷移のない１  ｂｙｔｅで遷移するＮＦＡは、終了状態からは自身も含めた他の状態へ遷移しないという制約を加えることにより、１−ｂｙｔｅ  ＮＦＡから指定された処理バイト数で遷移を行うＭｕｌｔｉｂｙｔｅ  ＮＦＡへの変換が容易になる、
ことを特徴とする請求項１５乃至請求項１７いずれか一つに記載のマルチバイト処理向け文字列照合用有限オートマトン生成方法。
【請求項１９】
正規表現を用いたパターンから、複数の文字数から成る遷移条件をもち、到達した終了状態によって入力された文字列のどの位置で前記パターンに一致したかを単独で判別できるＮＦＡを生成する第二ＮＦＡ生成処理を有することを特徴とするマルチバイト処理向け文字列照合用有限オートマトン回路生成方法。
【請求項２０】
到達した終了状態によって入力された文字列のどの位置でパターンに一致したかを単独で判別できる有限オートマトンか、どの位置でパターンに一致したかを単独では判別できないが、状態数は前記有限オートマトンよりも少なく、回路規模が削減できる有限オートマトンかを選択して生成することができることを特徴とする請求項１９に記載のマルチバイト処理向け文字列照合用有限オートマトン回路生成方法。
【請求項２１】
入力された正規表現を記憶し、
前記記憶された正規表現からε遷移のない１  ｂｙｔｅで遷移するＮＦＡへ変換し、
前記ε遷移のない１  ｂｙｔｅで遷移するＮＦＡを、指定された処理バイト数で遷移を行うＮＦＡへ変換し、
前記変換したＮＦＡを記憶し、
前記記憶されたＮＦＡから、そのハードウェア回路を記述するハードウェア記述言語を生成し、
そのハードウェア記述言語を記憶することを特徴とするマルチバイト処理向け文字列照合用有限オートマトン回路生成方法。
【請求項２２】
さらに、前記ε遷移のない１  ｂｙｔｅで遷移するＮＦＡから指定された処理バイト数で遷移を行うＮＦＡへの変換は、前記第二ＮＦＡ生成処理であることを特徴とする請求項２１に記載のマルチバイト処理向け文字列照合用有限オートマトン回路生成方法。
【請求項２３】
前記ε遷移のない１  ｂｙｔｅで遷移するＮＦＡから指定された処理バイト数で遷移を行うＮＦＡへの変換は、指定された動作モードにより、入力された文字列のどの位置でパターンが一致したかを単独で判別できるＮＦＡを生成する処理か、入力された文字列のどの位置でパターンが一致したかを単独では判別できないＮＦＡを生成する処理かを利用目的に応じて選択できる、
ことを特徴とする請求項２１又は請求項２２に記載のマルチバイト処理向け文字列照合用有限オートマトン回路生成方法。
【請求項２４】
前記正規表現から変換するε遷移のない１  ｂｙｔｅで遷移するＮＦＡは、終了状態からは自身も含めた他の状態へ遷移しないという制約を加えることにより、ε遷移のない１  ｂｙｔｅで遷移するＮＦＡから指定された処理バイト数で遷移を行うＮＦＡへの変換が容易になる、
ことを特徴とする請求項２１乃至請求項２３いずれか一つに記載のマルチバイト処理向け文字列照合用有限オートマトン回路生成方法。
【請求項２５】
正規表現を用いたパターンから、複数の文字数から成る遷移条件をもち、到達した終了状態によって入力された文字列のどの位置で前記パターンに一致したかを単独で判別できるＮＦＡを生成する第三ＮＦＡ生成処理をコンピュータに実行させることを特徴とするマルチバイト処理向け文字列照合用有限オートマトン生成プログラム。
【請求項２６】
到達した終了状態によって入力された文字列のどの位置でパターンに一致したかを単独で判別できる有限オートマトンか、どの位置でパターンに一致したかを単独では判別できないが、状態数は前記有限オートマトンよりも少なく、回路規模が削減できる有限オートマトンかを選択して生成する処理をコンピュータに実行させることを特徴とする請求項２５に記載のマルチバイト処理向け文字列照合用有限オートマトン生成プログラム。
【請求項２７】
入力された正規表現を記憶する正規表現記憶処理と、
前記記憶された正規表現からε遷移のない１  ｂｙｔｅで遷移するＮＦＡへ変換する１−ｂｙｔｅ  ＮＦＡ変換処理と、
前記ε遷移のない１  ｂｙｔｅで遷移するＮＦＡを、指定された処理バイト数で遷移を行うＮＦＡへ変換するＭｕｌｔｉｂｙｔｅ  ＮＦＡ変換処理と、
前記変換したＮＦＡを記憶するＮＦＡ記憶処理と、
をコンピュータに実行させることを特徴とするマルチバイト処理向け文字列照合用有限オートマトン生成プログラム。
【請求項２８】
前記Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換処理は、前記第三ＮＦＡ生成処理をコンピュータに実行させることを特徴とする請求項２７に記載のマルチバイト処理向け文字列照合用有限オートマトン生成プログラム。
【請求項２９】
前記Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換処理は、指定された動作モードにより、入力された文字列のどの位置でパターンが一致したかを単独で判別できるＮＦＡを生成するか、入力された文字列のどの位置でパターンが一致したかを単独では判別できないＮＦＡを生成するかを利用目的に応じて選択できる、
ことを特徴とする請求項２７又は請求項２８に記載のマルチバイト処理向け文字列照合用有限オートマトン生成プログラム。
【請求項３０】
前記１−ｂｙｔｅ  ＮＦＡ変換処理において、正規表現から変換するε遷移のない１  ｂｙｔｅで遷移するＮＦＡに対し、終了状態からは自身も含めた他の状態へ遷移しないという制約を加えることにより、前記Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換処理が簡略化できる、
ことを特徴とする請求項２７乃至請求項２９いずれか一つに記載のマルチバイト処理向け文字列照合用有限オートマトン生成プログラム。  
【請求項３１】
正規表現を用いたパターンから、複数の文字数から成る遷移条件をもち、到達した終了状態によって入力された文字列のどの位置で前記パターンに一致したかを単独で判別できるＮＦＡを生成する第四ＮＦＡ生成処理をコンピュータに実行させることを特徴とするマルチバイト処理向け文字列照合用有限オートマトン回路生成プログラム。
【請求項３２】
到達した終了状態によって入力された文字列のどの位置でパターンに一致したかを単独で判別できる有限オートマトンか、どの位置でパターンに一致したかを単独では判別できないが、状態数は前記有限オートマトンよりも少なく、回路規模が削減できる有限オートマトンかを選択して生成する処理をコンピュータに実行させることを特徴とする請求項３１に記載のマルチバイト処理向け文字列照合用有限オートマトン回路生成プログラム。
【請求項３３】
入力された正規表現を記憶する正規表現記憶処理と、
前記正規表現記憶手段に記憶された正規表現からε遷移のない１  ｂｙｔｅで遷移するＮＦＡへ変換する１−ｂｙｔｅ  ＮＦＡ変換処理と、
前記ε遷移のない１  ｂｙｔｅで遷移するＮＦＡを、指定された処理バイト数で遷移を行うＮＦＡへ変換するＭｕｌｔｉｂｙｔｅ  ＮＦＡ変換処理と、
Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換処理で変換したＮＦＡを記憶するＮＦＡ記憶処理と、
Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換処理で変換したＮＦＡから、そのハードウェア回路を記述するハードウェア記述言語を生成するＨＤＬ変換処理と、
ＨＤＬ変換処理で変換したハードウェア記述言語を記憶するＨＤＬ記憶処理と、
をコンピュータに実行させることを特徴とするマルチバイト処理向け文字列照合用有限オートマトン回路生成プログラム。
【請求項３４】
前記Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換処理は、前記第四ＮＦＡ生成処理をコンピュータに実行させることを特徴とする請求項３３に記載のマルチバイト処理向け文字列照合用有限オートマトン回路生成プログラム。
【請求項３５】
前記Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換処理は、指定された動作モードにより、入力された文字列のどの位置でパターンが一致したかを単独で判別できるＮＦＡを生成するか、入力された文字列のどの位置でパターンが一致したかを単独では判別できないＮＦＡを生成するかを利用目的に応じて選択できる、
ことを特徴とする請求項３３又は請求項３４に記載のマルチバイト処理向け文字列照合用有限オートマトン回路生成プログラム。
【請求項３６】
前記１−ｂｙｔｅ  ＮＦＡ変換処理において、正規表現から変換するε遷移のない１  ｂｙｔｅで遷移するＮＦＡに対し、終了状態からは自身も含めた他の状態へ遷移しないという制約を加えることにより、前記Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換処理が簡略化できる、
ことを特徴とする請求項３３乃至請求項３５いずれか一つに記載のマルチバイト処理向け文字列照合用有限オートマトン回路生成プログラム。
【請求項３７】
請求項７から請求項１２に記載の有限オートマトン回路生成装置、または、請求項１９から請求項２４に記載の有限オートマトン回路生成方法、または、請求項３１から請求項３６に記載の有限オートマトン回路生成プログラムを用いて生成したハードウェア記述言語を用いて、再構成可能ハードウェアデバイス上に前記有限オートマトン回路を用いることを特徴とするパターンマッチング装置。
【請求項３８】
請求項７から請求項１２に記載の有限オートマトン回路生成装置に加え、
前記有限オートマトン回路生成装置で生成したハードウェア記述言語から、再構成ハードウェアデバイスの構成情報であるＣｏｎｆｉｇｕｒａｔｉｏｎ  ｄａｔａを生成するＣｏｎｆｉｇｕｒａｔｉｏｎ  ｄａｔａ変換手段と、
を備え、前記生成したＣｏｎｆｉｇｕｒａｔｉｏｎ  ｄａｔａを用いて再構成可能ハードウェアデバイス上に前記有限オートマトン回路を用いることを特徴とするパターンマッチング装置。
【請求項３９】
請求項７から請求項１２に記載の有限オートマトン回路生成装置、または、請求項１９から請求項２４に記載の有限オートマトン回路生成方法、または、請求項３１から請求項３６に記載の有限オートマトン回路生成プログラムを用いて生成したハードウェア記述言語を用いて構成した、再構成可能ハードウェアデバイス上のマルチバイト処理向け文字列照合用有限オートマトン回路。
【請求項４０】
請求項７から請求項１２に記載の有限オートマトン回路生成装置に加え、
前記有限オートマトン回路生成装置で生成したハードウェア記述言語から、再構成ハードウェアデバイスの構成情報であるＣｏｎｆｉｇｕｒａｔｉｏｎ  ｄａｔａを生成するＣｏｎｆｉｇｕｒａｔｉｏｎ  ｄａｔａ変換手段と、
を備え、前記生成したＣｏｎｆｉｇｕｒａｔｉｏｎ  ｄａｔａを用いて再構成可能ハードウェアデバイス上のマルチバイト処理向け文字列照合用有限オートマトン回路。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、マルチバイト処理向け文字列照合用有限オートマトン生成システム、オートマトン回路生成システム、その生成方法、回路生成方法、生成プログラム、回路生成プログラム及びそれを用いたパターンマッチング装置、マルチバイト処理向け文字列照合用有限オートマトン回路に関する。
【背景技術】
【０００２】
本発明に関する現時点での技術水準をより十分に説明する目的で、本願で引用され或いは特定される特許、特許出願、特許公報、科学論文等の全てを、ここに、参照することでそれらの全ての説明を組入れる。【０００３】
従来、正規表現を用いた文字列照合（パターンマッチ）は、有限オートマトン（ＦＡ：  Ｆｉｎｉｔｅ  Ａｕｔｏｍａｔｏｎ）と呼ばれる状態遷移マシンを用いて行われる。このＦＡは、ある状態における入力文字に対して状態遷移先が複数存在する非決定性有限オートマトン（ＮＦＡ：  Ｎｏｎ−ｄｅｔｅｒｍｉｎｉｓｔｉｃ  Ｆｉｎｉｔｅ  Ａｕｔｏｍａｔｏｎ）と、状態遷移先が１つしか存在しない決定性有限オートマトン（ＤＦＡ：  Ｄｅｔｅｒｍｉｎｉｓｔｉｃ  Ｆｉｎｉｔｅ  Ａｕｔｏｍａｔｏｎ）に大きく分類できる。通常、ＮＦＡは、非特許文献１に記載されているように、与えられた正規表現等の検索対象条件から構文木を構築し、これに基づいて生成することができる。一方、ＤＦＡは上記の手順で生成したＮＦＡから生成することができるが、ＮＦＡの状態数ｎに対し、状態数が最大２ｎ個程度にまで増加してしまう恐れがある（非特許文献２）。【０００４】
一般的に、これらのＦＡを用いたパターンマッチをハードウェアで実現する手法として、状態遷移情報を状態遷移テーブルとしてメモリに格納し、上記テーブルを参照して１つずつ状態を遷移させながらパターンマッチングを行う手法がある。しかし、状態遷移が生じる度にメモリにアクセスして遷移情報を取得する必要があるため、このメモリアクセスが高速化のボトルネックとなる。さらに、上記のようなメモリ上にＮＦＡの状態遷移テーブルを格納した手法では、複数の状態遷移先から１つの遷移先を選択して処理を行うことしかできないため、選択した状態遷移の先でマッチングに失敗した場合、分岐した時点まで戻り、別の候補をテストしていく“バックトラック”という処理が必要になり、このバックトラック自体も高速化の妨げになる。また、ＤＦＡでは、状態数が爆発的に増加する恐れがあるため、大容量のメモリが必要になる。特に、多くの正規表現パターンに対して、高速なパターンマッチングを行う場合には、上記は高速化、構成上のボトルネックとなる。【０００５】
そこで、近年、例えば非特許文献３から非特許文献６及び特許文献１、２に示されるように、ＮＦＡを直接回路化し、ＦＰＧＡ（Ｆｉｅｌｄ  Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙ）のような再構成可能なデバイス上に組み込むことで、高速なパターンマッチングを行う手法が提案されている。通常、ＮＦＡには、入力を読み込まずに次の状態への遷移が可能なε遷移（ε−ｔｒａｎｓｉｔｉｏｎ）という特殊な遷移が含まれるが、上記のような直接ＮＦＡを組み込んだパターンマッチング回路（以下、ＮＦＡ回路と呼ぶ）では、ε遷移を含まないＮＦＡを用いる必要がある。このようなＮＦＡからε遷移を除去する操作をε閉包（ε−ｃｌｏｓｕｒｅ）と言う（非特許文献１、非特許文献２）。【０００６】
上記のようなＮＦＡを直接回路化する手法としては、正規表現から構文木（Ｓｙｎｔａｘ  Ｔｒｅｅ）を経由して直接ＮＦＡを組み込んだＮＦＡ回路を生成する手法や、正規表現を一度ＮＦＡに変換してからＮＦＡ回路を構成する手法等様々提案されており、例えば、図２４に示すような正規表現“ａ（ｂｃ）＊（ｄ｜ｅ）”に対するＮＦＡを考えた場合、ＮＦＡ回路は図２５のような回路として構成される。ここで、上記正規表現に含まれる‘＊’は０回以上マッチを、‘｜’はＯＲを表すメタキャラクタであり、図２４中の白色の矢印は初期状態を、二重丸で示された状態は終了状態を示している。図２５に示すように、元のＮＦＡ（図２４）の状態０から状態４は、それぞれＮＦＡ回路におけるレジスタ２００から２０４で実現され、各レジスタの値が‘１’であれば当該状態がアクティブであると判断される。データとして入力される１文字（１  ｂｙｔｅ）は、比較器３００から３０４で各遷移条件となっている文字（図中では比較器中に記載した文字）と比較され、一致すれば‘１’が出力される。このため、アクティブであると判断された状態において入力された文字が遷移条件と一致すれば、ＡＮＤゲート４００〜４０３の出力も‘１’となり、次状態のレジスタがアクティブとなり、状態遷移が実行される。最終的に、最終状態であるレジスタ２０４がアクティブになった時点で、入力文字列が正規表現“ａ（ｂｃ）＊（ｄ｜ｅ）”のパターンに一致したと判断される。上記のように、ＮＦＡ回路は、各状態を表すレジスタ、遷移条件の入力があったことを判定する比較器をＮＦＡの状態遷移に応じて接続された構成であり、１クロックサイクルあたり１文字（１  ｂｙｔｅ）を処理するため、動作周波数に比例した検索スループット性能をもつ。【０００７】
さらに、上記を拡張させ、１クロックサイクルあたりに処理できる文字数（バイト数）を増加させることで、検索スループットの向上を行う手法もいくつか提案されている。【０００８】
非特許文献４に示された手法では、図２６に示す“ａｂｃｄｅ”のパターンに対する１文字（１  ｂｙｔｅ）処理のＮＦＡ（このような１  ｂｙｔｅ処理のＮＦＡを以下では“１−ｂｙｔｅ  ＮＦＡ”と呼ぶ）に対して、４文字（４  ｂｙｔｅｓ）処理を行う場合（このような複数バイトで処理するＮＦＡを以下では“Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ”と呼び、処理バイト数がｋバイトのＮＦＡを“ｋ−ｂｙｔｅ  ＮＦＡ”と呼ぶ）には、図２７に示すような４つのＮＦＡが生成され、これをハードウェア回路化する。なお、図２６、図２７中の白色の矢印は初期状態を、二重丸で示された状態は終了状態を、記号‘Χ’は任意の文字を示している。図２６、図２７が示すように、この手法では、遷移条件の文字数を複数に拡張し、対象となるパターンが開始されるオフセットの位置を考慮したＮＦＡを生成することで、１クロックサイクルあたりの処理バイト数を増加させている。このため、どの終了状態に到達したかにより、入力した文字列のどの位置でパターンに一致したかが判別できるものの、１つのパターンに対して処理バイト数分のＮＦＡが必要であるため、状態数が増加する恐れがある。さらに、厳密一致（Ｅｘａｃｔ  Ｍａｔｃｈ）を用いた場合しか例示されておらず、状態数の削減と正規表現への対応が課題である。【０００９】
また、非特許文献５および特許文献１に示された手法では、この状態数の増加を軽減するために同じ遷移条件をもつ状態の共有化を行っているが、依然として正規表現への対応が課題として残っている。【００１０】
これらの手法に対し、非特許文献６では、図２４に示すような“ａ（ｂｃ）＊（ｄ｜ｅ）”の正規表現パターンに対する１−ｂｙｔｅ  ＮＦＡを拡張し、４文字（４  ｂｙｔｅｓ）処理を行う場合には、図２８に示すような１つのＮＦＡを生成し、これをハードウェア回路化する。なお、図２６、図２７同様、図中の白色の矢印は初期状態を、二重丸で示された状態は終了状態を、記号‘Χ’は任意の文字を示している。この手法では、１つの正規表現パターンから生成したＮＦＡの遷移条件そのものを複数バイトに拡張させることで、状態数を増加させることなく１クロックサイクルあたりの処理バイト数を増加させることが可能である。このため、正規表現を用いた高速なパターンマッチの実現が期待できるものの、このＮＦＡ回路単独では入力した文字列のどの位置でパターンに一致したかが判別できないという欠点がある。【００１１】
特許文献２では、情報検索システムのストリングサーチ方法に有限オートマトン法を適用することで、複数文字単位の状態遷移による検出速度の向上と状態遷移テーブルの作成時間を短縮する方法が提案されている。【００１２】
この他にも有限オートマトン手法を文字照合に適用するものとして特許文献３乃至６が提案されている。【００１３】
特許文献３は、文脈自由文法から、文脈自由文法を表す有限状態オートマトンまたは有限状態トランスデューサーを生成するシステムである。【００１４】
特許文献４は、有限状態オートマトンは入力文字列内の各文字をチェックしてその２バイト表現が有効範囲内にあるか否かを判定するものであり、小さなメモリ空間で効率的に行うことができるようにすることを目的とする。【００１５】
特許文献５は、オートマトン生成部が正規表現および検索音数範囲の集合から、派生型を遷移条件とする有限状態オートマトンを生成することで文字列を検索する手法を提案するものである。【００１６】
特許文献６は、その実施例で正規表現された検索条件に基づき、ＤＦＡ（決定性有限状態オートマトン）を用いて文字列検索を行う文書処理システムをコンピュータにて実現する旨が開示されている。【００１７】
【非特許文献１】近藤  嘉雪  著、“定本Ｃプログラマのためのアルゴリズムとデータ構造”、ソフトバンククリエイティブ、１９９８年、第２９７−３３０頁
【非特許文献２】野崎  昭弘、高橋  正子、町田  元、山崎  秀記  訳、ジョン・イー・ホップクロフト（Ｊｏｈｎ  Ｅ．  Ｈｏｐｃｒｏｆｔ）、ラジーブ・モトワニ（Ｒａｊｅｅｖ  Ｍｏｔｏｗａｎｉ）、ジェフリー・ディー・ウルマン（Ｊｅｆｆｒｅｙ  Ｄ．  Ｕｌｌｍａｎ）著、“Ｉｎｆｏｒｍａｔｉｏｎ  ＆  ｃｏｍｐｕｔｉｎｇ−３  オートマトン  言語理論  計算論Ｉ  ［第２版］”、サイエンス社、２００３年、第１６８−１７１頁
【非特許文献３】リーティンダー・シドフ（Ｒｅｅｔｉｎｄｅｒ  Ｓｉｄｈｕ）、ビクトル・ケー・プラサナ（Ｖｉｋｔｏｒ  Ｋ．  Ｐｒａｓａｎｎａ）、プロシーディング・オブ・ザ・ナインス・アニュアル・アイ・イー・イー・イー・シンポジウム・オン・フィールドプログラマブル・カスタム・コンピューティング・マシーンズ（Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ９ｔｈ  Ａｎｎｕａｌ  ＩＥＥＥ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｆｉｅｌｄ−Ｐｒｏｇｒａｍｍａｂｌｅ  Ｃｕｓｔｏｍ  Ｃｏｍｐｕｔｉｎｇ  Ｍａｃｈｉｎｅｓ）、２００１年、第２２７−２３８頁
【非特許文献４】クリストファー・アール・クラーク（Ｃｈｒｉｓｔｏｐｈｅｒ  Ｒ．  Ｃｌａｒｋ）、デービッド・イー・シメール（Ｄａｖｉｄ  Ｅ．  Ｓｃｈｉｍｍｅｌ）、  プロシーディング・オブ・ザ・トゥエルフス・アニュアル・アイ・イー・イー・イー・シンポジウム・オン・フィールドプログラマブル・カスタム・コンピューティング・マシーンズ（Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  １２ｔｈ  Ａｎｎｕａｌ  ＩＥＥＥ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｆｉｅｌｄ−Ｐｒｏｇｒａｍｍａｂｌｅ  Ｃｕｓｔｏｍ  Ｃｏｍｐｕｔｉｎｇ  Ｍａｃｈｉｎｅｓ）、２００４年、第２４９−２５７頁
【非特許文献５】片下敏宏、前田敦司、小野正人、戸田賢二、山口喜教、情報処理学会論文誌：コンピューティングシステム、Ｖｏｌ．４６、Ｎｏ．ＳＩＧ１２（ＡＣＳ１１）、２００５年、第１２０−１２８頁
【非特許文献６】山垣則夫、神谷聡史、電子情報通信学会技術研究報告（リコンフィギャラブルシステム）、Ｖｏｌ．１０７、Ｎｏ．２２５、２００７年、第６５−７０頁
【特許文献１】特開２００７−１４２７６７号公報
【特許文献２】特許第２７４５７１０号公報
【特許文献３】特開２００４−００４５２１号公報
【特許文献４】特開平０６−０２８１９６号公報
【特許文献５】特開平０８−３３９３７８号公報
【特許文献６】特許第３８５２７５７号公報
【発明の開示】
【発明が解決しようとする課題】
【００１８】
上記のような、遷移条件の文字数を複数に拡張したＭｕｌｔｉｂｙｔｅ  ＮＦＡからＮＦＡ回路を構築する手法には、以下のような課題がある。【００１９】
第１の課題は、１つの正規表現パターンから生成した１−ｂｙｔｅ  ＮＦＡの遷移条件そのものを複数バイトに拡張させたＭｕｌｔｉｂｙｔｅ  ＮＦＡから構築したＮＦＡ回路では、パターンにマッチした場合に、入力した文字列のどの位置で一致したかをＮＦＡ回路単独では判別できない上、これを知るためには、別途その目的のための回路が必要になるという点である。【００２０】
その理由は、状態数を増加させることなく複数バイト処理に拡張しているため、終了状態へ入力される遷移条件が多重され、マッチング位置が入力文字列のどの位置にあるかというオフセットが判別できないためであり、マッチング位置を知るためには、多重された遷移条件を特定するための追加回路が必要となるためである。【００２１】
第２の課題は、対象となるパターンが開始されるオフセットの位置を考慮した複数のＭｕｌｔｉｂｙｔｅ  ＮＦＡから構築したＮＦＡ回路では、どの終了状態に到達したかにより入力した文字列のどの位置でパターンに一致したかが判別できるものの、厳密一致（Ｅｘａｃｔ  Ｍａｔｃｈ）を用いた場合しか例示されておらず、特殊な意味をもつメタキャラクタを含む正規表現パターンには対応していない点である。【００２２】
その理由は、オフセットの位置をずらしたＮＦＡを構築するためにパターンを一意に決める必要があり、０回以上繰り返しを意味するメタキャラクタ‘＊’等のようなメタキャラクタが入った場合に、そのパターンを一意に決定できないためである。【００２３】
本発明の目的は、ＮＦＡの遷移条件そのものを複数バイトに拡張させ、入力した文字列のどの位置で一致したかを単独で判別できるマルチバイト処理向け文字列照合用有限オートマトン回路生成システム、その生成方法、生成プログラム、及びそれを用いたパターンマッチング装置を提供することにある。【００２４】
本発明の他の目的は、正規表現パターンに対応したマルチバイト処理向け文字列照合用有限オートマトン回路生成システム、その生成方法、生成プログラム、及びそれを用いたパターンマッチング装置を提供することにある。【００２５】
本発明のさらに他の目的は、入力した文字列のどの位置で一致したかを単独で判別できる有限オートマトン回路を生成するかを選択可能にすることにより、目的に応じたＮＦＡ回路を生成することができるマルチバイト処理向け文字列照合用有限オートマトン回路生成システム、その生成方法、生成プログラム、及びそれを用いたパターンマッチング装置を提供することにある。
【課題を解決するための手段】
【００２６】
本発明の第１、第２のマルチバイト処理向け文字列照合用有限オートマトン回路生成システムは、正規表現から変換したε遷移のない１−ｂｙｔｅ  ＮＦＡを、指定されたバイト数で処理し、指定された動作モードに応じて、パターンに一致した位置が単独で判別できるＭｕｌｔｉｂｙｔｅ  ＮＦＡへ変換するＭｕｌｔｉｂｙｔｅ  ＮＦＡ変換部（図１の指示番号２２、図１７の指示番号２５）と、変換したＭｕｌｔｉｂｙｔｅ  ＮＦＡを所定のデータ構造により表したものを記憶するＮＦＡ記憶部（図１、図１７の指示番号３２）と、変換したＭｕｌｔｉｂｙｔｅ  ＮＦＡの状態、状態遷移構造を参照しながら、上記Ｍｕｌｔｉｂｙｔｅ  ＮＦＡをハードウェア回路として記述するＨＤＬ（Ｈａｒｄｗａｒｅ  Ｄｅｓｃｒｉｐｔｉｏｎ  Ｌａｎｇｕａｇｅ）変換部（図１、図１７の指示番号２３）とを有する。また、変換するＭｕｌｔｉｂｙｔｅ  ＮＦＡの処理バイト数は、２の累乗の値で指定することができる。このような構成を採用し、正規表現そのものから単独でパターンに一致した位置が判別できるＭｕｌｔｉｂｙｔｅ  ＮＦＡへ変換するか、単独では判別できないＭｕｌｔｉｂｙｔｅ  ＮＦＡへ変換するかを選択可能とすることにより、本発明の第１、第２、及び第３の目的を達成することができる。【００２７】
また、本発明の第４のマルチバイト処理向け文字列照合用有限オートマトン回路を用いたパターンマッチング装置は、第１、第２のマルチバイト処理向け文字列照合用有限オートマトン回路生成システムに加え、生成したＨＤＬからＦＰＧＡのような再構成可能なハードウェアデバイスの構成情報であるＣｏｎｆｉｇｕｒａｔｉｏｎ  ｄａｔａを生成するＣｏｎｆｉｇｕｒａｔｉｏｎ  ｄａｔａ変換部（図２３の指示番号２６）と、そのＣｏｎｆｉｇｕｒａｔｉｏｎ  ｄａｔａにより構成を設定できる再構成可能なハードウェアデバイス上に構成されたパターンマッチング部（図２３の指示番号１２２）とを有する。このような構成を採用し、正規表現そのものからパターンに一致した位置が単独で判別できるＭｕｌｔｉｂｙｔｅ  ＮＦＡ回路か、単独では判別できないＭｕｌｔｉｂｙｔｅ  ＮＦＡ回路を用いてパターンマッチングを行うことにより、本発明の第１、第２、及び第３の目的を達成することができる。
【発明の効果】
【００２８】
第１の効果は、１  ｂｙｔｅで処理するＮＦＡの遷移条件そのものを複数バイトに拡張させたＮＦＡでも、入力した文字列のどの位置でパターンに一致したかを単独で判別できることにある。【００２９】
その理由は、１  ｂｙｔｅで処理するＮＦＡから指定された処理バイト数のＮＦＡへ変換する際に、終了状態を処理バイト数に応じて増加させることで、どの終了状態に到達したかにより、入力された文字列のどの位置でパターンに一致したかが判別できるためである。【００３０】
第２の効果は、上記入力した文字列のどの位置でパターンに一致したかを単独で判別できるＮＦＡを生成するかを目的に応じて選択でき、入力した文字列のどの位置でパターンに一致したかを単独で判別できないＮＦＡを用いた場合には、一致した位置を単独で判別できるＮＦＡ回路に比べて、回路規模が削減できるＮＦＡ回路が生成できることにある。【００３１】
その理由は、実際に変換する際には、入力された文字列どの位置でパターンに一致したかを単独で判別できるＮＦＡか、単独ではそれを判別できないＮＦＡかを、動作モードとして指定することができ、一致した位置を判別できないＮＦＡを選択した場合には、一致した位置を単独で判別できるＮＦＡとは異なり、処理バイト数に応じて終了状態が増加しないため、その状態数分の回路規模を削減することができるためである。【００３２】
第３の効果は、本発明により生成する複数バイトで処理するＮＦＡは、正規表現にも対応できることにある。【００３３】
その理由は、正規表現そのものを入力し、それを用いて複数バイトで処理するＮＦＡへ変換するためである。【００３４】
第４の効果は、正規表現に対応し、入力した文字列のどの位置でパターンに一致したかが単独で判別できる高速なパターンマッチング装置を構成できることにある【００３５】
その理由は、第１、第２、第３の効果をもつＮＦＡのハードウェア回路を記述したＨＤＬから構成したパターンマッチング回路を用いるためであり、さらに本ＮＦＡ回路は複数バイトで処理することができるためである。
【図面の簡単な説明】
【００３６】
【図１】本発明の第１の実施の形態の構成を示すブロック図である。
【図２】本発明の第１の実施の形態の動作を示す流れ図である。
【図３】本発明の第１の実施の形態のＮＦＡを表すデータ構造の従来例である。
【図４】本発明の第１の実施の形態のＮＦＡを表すデータ構造の状態遷移図である。
【図５】本発明の第１の実施の形態の図２におけるステップＡ６を示す流れ図である。
【図６】本発明の第１の実施の形態の図５の流れ図に従って、図２４の１−ｂｙｔｅ  ＮＦＡを用いてマッチング位置が判別可能な２−ｂｙｔｅ  ＮＦＡ変換を行う途中の例（ステップＢ３終了時）の状態遷移図である。
【図７】本発明の第１の実施の形態の図５の流れ図に従って、図２４の１−ｂｙｔｅ  ＮＦＡを用いてマッチング位置が判別可能な２−ｂｙｔｅ  ＮＦＡ変換を行う途中の例（図６のＮＦＡに対し、状態ｎとして、状態０、状態１を選択し、ステップＢ１５を確認する時点）の状態遷移図である。
【図８】本発明の第１の実施の形態の図５の流れ図に従って、図２４の１−ｂｙｔｅ  ＮＦＡを用いてマッチング位置が判別可能な２−ｂｙｔｅ  ＮＦＡ変換を行う途中の例（ステップＢ１６開始前）の状態遷移図である。
【図９】本発明の第１の実施の形態の図５の流れ図に従って、図２４の１−ｂｙｔｅ  ＮＦＡを用いてマッチング位置が判別可能な２−ｂｙｔｅ  ＮＦＡ変換を行った例の状態遷移図である。
【図１０】本発明の第１の実施の形態の図５の流れ図に従って、図９の２−ｂｙｔｅ  ＮＦＡを用いてマッチング位置が判別可能な４−ｂｙｔｅ  ＮＦＡ変換を行う途中の例（ステップＢ３終了時）の状態遷移図である。
【図１１】本発明の第１の実施の形態の図５の流れ図に従って、図９の２−ｂｙｔｅ  ＮＦＡを用いてマッチング位置が判別可能な４−ｂｙｔｅ  ＮＦＡ変換を行った例の状態遷移図である。
【図１２】本発明の第１の実施の形態の図５の流れ図に従って、図２４の１−ｂｙｔｅ  ＮＦＡを用いてマッチング位置が判別できない２−ｂｙｔｅ  ＮＦＡ変換を行う途中（ステップＢ４終了時）の状態遷移図である。
【図１３】本発明の第１の実施の形態の図５の流れ図に従って、図２４の１−ｂｙｔｅ  ＮＦＡを用いてマッチング位置が判別できない２−ｂｙｔｅ  ＮＦＡ変換を行う途中（図１２のＮＦＡに対し、状態ｎとして、状態０、状態１を選択し、ステップＢ１５を確認する時点）の状態遷移図である。
【図１４】本発明の第１の実施の形態の図５の流れ図に従って、図２４の１−ｂｙｔｅ  ＮＦＡを用いてマッチング位置が判別できない２−ｂｙｔｅ  ＮＦＡ変換を行う途中（ステップＢ１６開始前）の状態遷移図である。
【図１５】本発明の第１の実施の形態の図５の流れ図に従って、図２４の１−ｂｙｔｅ  ＮＦＡを用いてマッチング位置が判別できない２−ｂｙｔｅ  ＮＦＡ変換を行った例の状態遷移図である。
【図１６】本発明の第１の実施の形態の図５の流れ図に従って、図１５の２−ｂｙｔｅ  ＮＦＡを用いてマッチング位置が判別できない４−ｂｙｔｅ  ＮＦＡ変換を行う途中（ステップＢ４終了時）の状態遷移図である。
【図１７】本発明の第２の実施の形態の構成を示すブロック図である。
【図１８】本発明の第２の実施の形態の動作を示す流れ図である。
【図１９】本発明の第２の実施の形態の１−ｂｙｔｅ  ＮＦＡ変換部２４では生成しない１−ｂｙｔｅ  ＮＦＡの状態遷移図である。
【図２０】本発明の第２の実施の形態の１−ｂｙｔｅ  ＮＦＡ変換部２４で生成する１−ｂｙｔｅ  ＮＦＡの状態遷移図である。
【図２１】本発明の第２の実施の形態におけるステップＡ１０を示す流れ図である。
【図２２】本発明の第３の実施の形態の構成を示すブロック図である。
【図２３】本発明の第４の実施の形態の構成を示すブロック図である。
【図２４】従来例を用いた場合の“ａ（ｂｃ）＊（ｄ｜ｅ）”の正規表現パターンに対する１文字（１ｂｙｔｅ）処理のＮＦＡの状態遷移図である。
【図２５】従来例を用いた場合の“ａ（ｂｃ）＊（ｄ｜ｅ）”の正規表現パターンに対する１文字（１ｂｙｔｅ）処理のＮＦＡの回路図である。
【図２６】従来例を用いた場合の“ａｂｃｄｅ”のパターンに対する１文字（１  ｂｙｔｅ）処理のＮＦＡの状態遷移図である。
【図２７】従来例を用いた場合の“ａｂｃｄｅ”のパターンに対する４文字（４  ｂｙｔｅｓ）処理のＮＦＡの状態遷移図である。
【図２８】従来例を用いた場合の“ａ（ｂｃ）＊（ｄ｜ｅ）”の正規表現パターンに対する４文字（４  ｂｙｔｅｓ）処理のＮＦＡの状態遷移図である。
【発明を実施するための最良の形態】
【００３７】
（本発明の第１の実施の形態）
次に、本発明の実施の形態について図面を参照して詳細に説明する。【００３８】
図１は、本発明の第１の実施の形態の構成を示すブロック図である。図１を参照すると、本発明の第１の実施の形態は、キーボード等の入力装置１と、プログラム制御により動作するデータ処理装置２と、情報を記憶する記憶装置３と、ディスプレイ装置や印刷装置等の出力装置４とを含む。【００３９】
記憶装置３は、正規表現記憶部３１と、ＮＦＡ記憶部３２と、ＨＤＬ記憶部３３とを備えている。【００４０】
正規表現記憶部３１は、入力装置から１−ｂｙｔｅ  ＮＦＡ変換部２１に入力された１つ以上の正規表現を記憶する。【００４１】
ＮＦＡ記憶部３２は、Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２２において、１−ｂｙｔｅ  ＮＦＡから変換したＭｕｌｔｉｂｙｔｅ  ＮＦＡを、リスト構造や行列形式等のデータ構造の形で記憶する。【００４２】
ＨＤＬ記憶部３３は、ＨＤＬ変換部２３において、ＮＦＡ記憶部３２に記憶されたＭｕｌｔｉｂｙｔｅ  ＮＦＡのＮＦＡ回路を記述したＶｅｒｉｌｏｇ  ＨＤＬやＶＨＤＬ（Ｖｅｒｙ  Ｈｉｇｈｓｐｅｅｄ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ  ＨＤＬ）等のＨＤＬを記憶する。【００４３】
データ処理装置２は、１−ｂｙｔｅ  ＮＦＡ変換部２１と、Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２２と、ＨＤＬ変換部２３とを備えている。【００４４】
１−ｂｙｔｅ  ＮＦＡ変換部２１は、入力装置１から入力された１つの正規表現、又は複数の正規表現のリストを読み込み、正規表現記憶部３１へ記憶させる。また、１−ｂｙｔｅ  ＮＦＡ変換部２１は、正規表現記憶部３１から読み出した正規表現を、例えば非特許文献１に記載されたような従来の手法を用いてε遷移のない１−ｂｙｔｅ  ＮＦＡに変換し、生成したＮＦＡを表すデータ構造をＭｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２２へ出力し、次の正規表現の変換を開始する。また、正規表現記憶部３１に記憶された最後の正規表現を変換が終了した際には、生成したＮＦＡを表すデータ構造と共に、全ての正規表現が変換したことを意味する信号をＭｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２２へ出力する。【００４５】
Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２２は、入力装置１から入力された処理バイト数と動作モード（ｍｏｄｅ）を読み込む。この処理バイト数は、生成するＭｕｌｔｉｂｙｔｅ  ＮＦＡの処理バイト数であり、動作モードは、生成するＭｕｌｔｉｂｙｔｅ  ＮＦＡの種別を指定する。また、１−ｂｙｔｅ  ＮＦＡ変換部２１からε遷移のない１−ｂｙｔｅ  ＮＦＡを表すデータ構造を受け取り、動作モードに応じてそれらを１つずつ目的の処理バイト数のＭｕｌｔｉｂｙｔｅ  ＮＦＡへ変換していく。１つのＮＦＡに対する変換処理が終了すると、Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２２は、変換したＭｕｌｔｉｂｙｔｅ  ＮＦＡを示すデータ構造をＮＦＡ記憶部３２へ記憶させ、１−ｂｙｔｅ  ＮＦＡ変換部２１から受け取ったＮＦＡがあればその変換を開始し、受け取っていなければ次のＮＦＡを受け取るまで待つ。１−ｂｙｔｅ  ＮＦＡ変換部２１から全ての正規表現が変換したことを意味する信号と共に受け取ったＮＦＡの変換が終了すると、その変換したＮＦＡをＮＦＡ記憶部３２へ記憶させた後、ＮＦＡ記憶部３２からＮＦＡを示すデータ構造を読み込み、ＨＤＬ変換部２３へ出力する。最後のＮＦＡのデータ構造を出力する際には、最後のＮＦＡであることを意味する信号と共に出力する。【００４６】
ＨＤＬ変換部２３は、Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２２から受け取ったＭｕｌｔｉｂｙｔｅ  ＮＦＡのデータ構造から、そのＮＦＡの状態、状態間の遷移、遷移条件等の情報を分析し、各状態をレジスタ、遷移条件を文字（列）比較器に変換し、状態間の遷移に応じて各レジスタ間を接続し、その回路を記述するＶｅｒｉｌｏｇ  ＨＤＬやＶＨＤＬ等のＨＤＬに変換する。また、ＨＤＬ変換部２３は、変換したＨＤＬをＨＤＬ記憶部３３へ記憶させ、ＨＤＬへの変換が終了すると、ＨＤＬ記憶部３３からＨＤＬを読み出し、出力装置４へ出力する。【００４７】
（本発明の第１の実施の形態の動作）
次に、図１、及び図２の流れ図を参照して、本発明の第１の実施の形態の動作について詳細に説明する。【００４８】
入力装置１から１つ、又は複数のリストとして入力された正規表現は、１−ｂｙｔｅ  ＮＦＡ変換部２１に、生成するＭｕｌｔｉｂｙｔｅ  ＮＦＡの処理バイト数と生成するＭｕｌｔｉｂｙｔｅ  ＮＦＡの種別を指定する動作モード（ｍｏｄｅ）はＭｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２２に供給される。【００４９】
１−ｂｙｔｅ  ＮＦＡ変換部２１は、受け取った正規表現を正規表現記憶部３１へ記憶させ、そこから１つずつ正規表現を読み出し、非特許文献１等に記載された公知の手法を用いて正規表現をε遷移のない１−ｂｙｔｅ  ＮＦＡに変換する（ステップＡ１）。１−ｂｙｔｅ  ＮＦＡ変換部２１は変換が終了すると、変換したＮＦＡをＭｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２２へ送信し、次の正規表現を正規表現記憶部３１から読み出し、ε遷移のない１−ｂｙｔｅ  ＮＦＡへの変換を開始する。正規表現記憶部３１に記憶された最後の正規表現を変換が終了した際には、変換したＮＦＡと共に、全ての正規表現が変換したことを意味する信号をＭｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２２へ出力する。【００５０】
ここで、１−ｂｙｔｅ  ＮＦＡ変換部２１がＭｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２２へ送り出すＮＦＡは、ＮＦＡの状態遷移情報をもつデータ構造である。通常、非特許文献１等にも記載されているように、ＮＦＡのある状態に着目した場合に必要な状態遷移情報は、遷移先の状態番号と遷移条件となるラベルである。このため、ここで出力されるデータ構造は、ある状態に着目すると、次に遷移する状態とその際の遷移条件（ラベル）が取得できるデータ構造であればよい。このようなＮＦＡを表すデータ構造としては、例えば、図３に示すような１次元配列とリンクリストによって管理された構造体を用いたデータ構造がある。Ｎ個の状態をもつＮＦＡを考えた場合、１次元配列ＮＦＡ［ｉ］（ｉ＝０、・・・、Ｎ−１）で各状態を特定し、その配列要素から始まる遷移情報のリンクリスト（Ｌｉｎｋｅｄ  Ｌｉｓｔ）では、状態ｉからの遷移先状態と、遷移条件である文字（列）（ラベル）、さらに次の遷移情報へのポインタが格納される。【００５１】
後述するが、本発明の第１の実施の形態の動作としては、ある状態に着目した場合に、その状態からの遷移先状態、その遷移条件だけでなく、着目した状態へ遷移がある遷移元状態とその遷移条件を得る必要があるため、図３のようなデータ構造では遷移元状態とその遷移条件を得るために、全ての遷移情報を調べる必要がある。このため、例えば図４に示すように、２次元配列ＮＦＡ［ｉ］［ｊ］（ｉ、ｊ＝０、・・・、Ｎ−１）で状態ｉから状態ｊへの遷移を特定し、その配列要素から始まる遷移情報のリンクリストでは、状態ｉから状態ｊへの遷移条件であるラベル、次の遷移情報へのポインタが格納されるようなデータ構造を用いてもよい。【００５２】
また、行列形式で表現し、行番号ｉを遷移元の状態番号、列番号ｊを遷移先の状態番号とし、各要素において状態ｉから状態ｊへの遷移条件の文字を表すことで表現することもできる。なお、この場合、ある状態からある状態への複数の条件があれば、‘＋’（例えば、文字‘ａ’と‘ｂ’が遷移条件である場合は“ａ＋ｂ”で表す）で表し、遷移がなければ０で表す等、特定の定義が必要である。【００５３】
Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２２は、１−ｂｙｔｅ  ＮＦＡ変換部２１から受け取った現在のＮＦＡの処理バイト数Ｂを１に、目的とするＭｕｌｔｉｂｙｔｅ  ＮＦＡの処理バイト数ＢＴを入力装置１から入力された処理バイト数に設定する（ステップＡ２）。ここで、目的となるＭｕｌｔｉｂｙｔｅ  ＮＦＡの処理バイト数、つまり、入力装置１から入力されるバイト数としては、２の累乗の値のみが指定可能とし、それ以外のバイト数であった場合には、Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２２は、エラー処理を行い、処理を終了する（ステップＡ３）。【００５４】
続いて、Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２２は、入力装置１から入力された生成するＭｕｌｔｉｂｙｔｅ  ＮＦＡの種別を指定する動作モード（ｍｏｄｅ）を設定する（ステップＡ４）。動作モード（ｍｏｄｅ）としては、入力される文字列のどの位置でパターンに一致したかが単独で判別可能なＭｕｌｔｉｂｙｔｅ  ＮＦＡの生成（ｍｏｄｅ＝ｍａｔｃｈ）と、パターンに一致した位置が単独では判別不可能なＭｕｌｔｉｂｙｔｅ  ＮＦＡの生成（ｍｏｄｅ＝ｎｏｎ−ｍａｔｃｈ）の２種類ある。【００５５】
Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２２は、上記の設定が終了すると、目的とするＭｕｌｔｉｂｙｔｅ  ＮＦＡの処理バイト数ＢＴが１  ｂｙｔｅでなければ（ステップＡ５）、Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２２は、変換手段２１から受け取ったε遷移のない１−ｂｙｔｅ  ＮＦＡを処理バイト数ＢＴのＭｕｌｔｉｂｙｔｅ  ＮＦＡへ変換する（ステップＡ６）。【００５６】
図５は、ステップＡ６のより詳細な動作を説明するための流れ図である。また、例として、図２４に示す正規表現“ａ（ｂｃ）＊（ｄ｜ｅ）”から生成したε遷移のない１−ｂｙｔｅ  ＮＦＡの変換例を挙げて説明する。【００５７】
まず、初期状態から初期状態へ任意の文字での遷移を生成する（ステップＢ１）。ここでは、任意の文字を示す記号を‘Ｘ’とし、ここで生成した遷移をｓｅｌｆ−ｅｄｇｅ−ｉｎｉｔｉａｌと呼ぶ。【００５８】
次に、動作モード（ｍｏｄｅ）をチェックする（ステップＢ２）。以下では、まず動作モードとして、入力される文字列のどの位置でパターンに一致したかが単独で判別可能なＭｕｌｔｉｂｙｔｅ  ＮＦＡの生成（ｍｏｄｅ＝ｍａｔｃｈ）の場合について説明する。【００５９】
動作モードｍｏｄｅがｍａｔｃｈの場合、Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２２は、各終了状態に対して、１つの終了状態を生成し、元の終了状態から生成した終了状態へ任意の文字（ラベル‘Ｘ’）での遷移を生成する（ステップＢ３）。ここで生成した遷移をｅｄｇｅ−ｆｉｎａｌと呼ぶ。図２４のＮＦＡに対して、ステップＢ３までを終えたＮＦＡの例を図６に示す。【００６０】
次に、Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２２は、現在のＮＦＡからこれまでに選択していない１つの状態を選択し、これを状態ｎ、状態ｎへの遷移をもつこれまでに選択していない１つの状態を選択し、これを状態ｉ、状態ｎからの遷移をもつこれまでに選択していない１つの状態を選択し、これを状態ｊとする（ステップＢ５、Ｂ６、Ｂ７）。このとき、状態ｉから状態ｎへのラベルを‘Ｌｉｎ’、状態ｎから状態ｊへのラベルを‘Ｌｎｊ’とする。【００６１】
続いて、Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２２は、‘Ｌｎｊ’がｓｅｌｆ−ｅｄｇｅ−ｉｎｉｔｉａｌのラベルかをチェックし（ステップＢ８）、ｓｅｌｆ−ｅｄｇｅ−ｉｎｉｔｉａｌのラベルである場合は、まだ選択されていない状態ｊの候補があるかをチェックする（ステップＢ１３）。Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２２は、ｓｅｌｆ−ｅｄｇｅ−ｉｎｉｔｉａｌのラベルでない場合は、再度動作モード（ｍｏｄｅ）をチェックする（ステップＢ２）。Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２２は、動作モードｍｏｄｅがｍａｔｃｈの場合、状態ｉから状態ｊへの遷移を生成し（ステップＢ１０）、状態ｉから状態ｎへのラベル‘Ｌｉｎ’と状態ｎから状態ｊへのラベルを‘Ｌｎｊ’を連結させたラベル“Ｌｉｊ”を生成し（ステップＢ１１）、このラベル“Ｌｉｊ”を状態ｉから状態ｊへの遷移条件とする（ステップＢ１２）。例えば、図６のＮＦＡにおいて、状態ｎ、ｉ、ｊとしてそれぞれ状態１、状態０、状態２を選択した場合、ラベルＬｉｎ、Ｌｎｊはそれぞれ‘ａ’、‘ｂ’となるため、状態０から状態２へラベル“ａｂ”の遷移が生成される。ここで、ステップＢ８の‘Ｌｎｊ’がｓｅｌｆ−ｅｄｇｅ−ｉｎｉｔｉａｌのラベルかをチェックするのは、例えば、Ｌｉｎ、Ｌｎｊはそれぞれ‘ａ’、‘Ｘ’の場合に、ラベル“ａＸ”のように、パターンの途中に任意の文字が入ることを防止するためである。【００６２】
上記の処理が終えると、Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２２は、まだ選択されていない状態ｊの候補があるかをチェックし（ステップＢ１３）、まだ候補が存在すればステップＢ７からを繰り返し、候補が無ければまだ選択されていない状態ｉの候補があるかをチェックする（ステップＢ１４）。以下、同様にＭｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２２は、まだ状態ｉの候補が存在すればステップＢ６からを繰り返し、候補が無ければまだ選択されていない状態ｎの候補があるかをチェックし（ステップＢ１５）、あればステップＢ５からを繰り返す。例えば、図６のＮＦＡにおいて、状態ｎとして、状態０、状態１を選択し、ステップＢ１５を確認する時点では、図７のようなＮＦＡが生成されている。但し、点線で示した状態遷移は元のＮＦＡ（図２４）の遷移と、ステップＢ１で追加したｓｅｌｆ−ｅｄｇｅ−ｉｎｉｔｉａｌ、ステップＢ３で追加したｅｄｇｅ−ｆｉｎａｌの遷移であり、実線で記した遷移が本処理によって新たに生成された遷移を表す。【００６３】
上記の処理を繰り返し、状態ｎの候補が無くなる（ステップＢ１５）と、Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２２は、元のＮＦＡの状態遷移（遷移条件が処理バイト数Ｂの遷移）とステップＢ１で追加したｓｅｌｆ−ｅｄｇｅ−ｉｎｉｔｉａｌとｅｄｇｅ−ｆｉｎａｌの遷移を削除し（ステップＢ１６、ステップＢ１７）、現在のＮＦＡの処理バイト数Ｂを２倍にする（ステップＢ１８）。例えば、ステップＢ１６に入る直前のＮＦＡは図８、ステップＢ１７を行った直後のＮＦＡは図９のようになり、元のＮＦＡの処理バイト数を２倍にした入力文字列のどの位置でパターンに一致したかが判別できるＮＦＡが生成される。【００６４】
最後に、Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２２は、この変換したＮＦＡの処理バイト数Ｂと指定された処理バイト数を示すＢＴを比較し、ＢがＢＴよりも小さい、つまり目的とする処理バイト数に満たしていない場合には、再びステップＢ１から処理を繰り返し（ステップＢ１９）、目的の処理バイト数を満たした場合には処理を終了する。例えば、図９に対してさらにステップＢ１からを行った場合のＮＦＡの例として、図１０にステップＢ３直後のＮＦＡの例、図１１に４−ｂｙｔｅ  ＮＦＡの変換例を示す。【００６５】
引き続き、動作モードとして、入力される文字列のどの位置でパターンに一致したかが単独では判別不可能なＭｕｌｔｉｂｙｔｅ  ＮＦＡの生成（ｍｏｄｅ＝ｎｏｎ−ｍａｔｃｈ）の場合について説明する。【００６６】
動作モードｍｏｄｅがｎｏｎ−ｍａｔｃｈの場合も、動作モードｍｏｄｅがｍａｔｃｈの場合と基本的には同じ処理ステップを行うが、ステップＢ３の代わりにステップＢ４、ステップＢ８の後にステップＢ９を行う点が異なる。その他の処理ステップは動作モードｍｏｄｅがｍａｔｃｈの場合と同じなので以下では説明を省略する。【００６７】
動作モードｍｏｄｅとして、ｎｏｎ−ｍａｔｃｈが選択された場合、Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２２は、ステップＢ１、ステップＢ２を行った後に、終了状態から終了状態へラベル‘Ｘ’の遷移を生成し、これをｓｅｌｆ−ｅｄｇｅ−ｆｉｎａｌと呼ぶ（ステップＢ４）。動作モードｍｏｄｅがｍａｔｃｈの場合と同様、図２４に示す正規表現“ａ（ｂｃ）＊（ｄ｜ｅ）”から生成したε遷移のない１−ｂｙｔｅ  ＮＦＡの変換例を挙げて説明すると、ステップＢ４までを終えたＮＦＡの例は図１２のようになる。【００６８】
続いて、Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２２は、ステップＢ５からステップＢ８までを行い、ラベル‘Ｌｎｊ’がｓｅｌｆ−ｅｄｇｅ−ｉｎｉｔｉａｌのラベルである場合は、まだ選択されていない状態ｊの候補があるかをチェックする（ステップＢ１３）。ｓｅｌｆ−ｅｄｇｅ−ｉｎｉｔｉａｌのラベルでない場合は、Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２２は、動作モードをチェック（ステップＢ２）した後に、ラベル‘Ｌｉｎ’がｓｅｌｆ−ｅｄｇｅ−ｆｉｎａｌのラベルであるかをチェックし（ステップＢ９）、ｓｅｌｆ−ｅｄｇｅ−ｆｉｎａｌのラベルである場合は、ステップＢ１３へ、ｓｅｌｆ−ｅｄｇｅ−ｆｉｎａｌのラベルでない場合は、ステップＢ１０へと進み、処理を続ける。ここで、ステップＢ９の‘Ｌｉｎ’がｓｅｌｆ−ｅｄｇｅ−ｆｉｎａｌのラベルかをチェックするのは、例えば、Ｌｉｎ、Ｌｎｊはそれぞれ‘Ｘ’、‘ａ’の場合に、ラベル“Ｘａ”のように、パターンの途中に任意の文字が入ることを防止するためである。【００６９】
例えば、図１２のＮＦＡにおいて、状態ｎとして、状態０、状態１を選択し、ステップＢ１５を確認する時点では、図１３のようなＮＦＡになる。但し、点線で示した状態遷移は元のＮＦＡ（図２４）の遷移と、ステップＢ１、ステップＢ４で追加したｓｅｌｆ−ｅｄｇｅ−ｉｎｉｔｉａｌ、ｓｅｌｆ−ｅｄｇｅ−ｆｉｎａｌの遷移であり、実線で記した遷移が本処理によって新たに生成された遷移を表す。さらに処理を進めた結果、ステップＢ１６に入る直前のＮＦＡは図１４、ステップＢ１７を行った直後のＮＦＡは図１５のようになり、元のＮＦＡの処理バイト数を２倍にした入力文字列のどの位置でパターンに一致したかが判別不可能なＮＦＡが生成される。【００７０】
最後に、ステップＢ１９を行い、目的の処理バイト数を満たした場合には処理を終了する。例えば、図１５に対してさらにステップＢ１からを行った場合、ステップＢ４の直後には図１６のようなＮＦＡになり、最終的に図２８のような４−ｂｙｔｅ  ＮＦＡが生成される。【００７１】
Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２２は、上記のようなステップＡ６が終了すると、生成したＭｕｌｔｉｂｙｔｅ  ＮＦＡをＮＦＡ記憶部３２へ記憶させ、１−ｂｙｔｅ  ＮＦＡ変換部２１から受け取ったＮＦＡがあればその変換を開始し、受け取っていなければ次のＮＦＡを受け取るまで待つ。１−ｂｙｔｅ  ＮＦＡ変換部２１から全ての正規表現が変換したことを意味する信号と共に受け取ったＮＦＡの変換が終了すると、その変換したＮＦＡをＮＦＡ記憶部３２へ記憶させた後、ＮＦＡ記憶部３２からＮＦＡを示すデータ構造を読み込み、ＨＤＬ変換部２３へ出力する。Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２２は、最後のＮＦＡのデータ構造を出力する際には、最後のＮＦＡであることを意味する信号と共に出力する（ステップＡ６）。【００７２】
ＨＤＬ変換部２３は、Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２２から受け取ったＭｕｌｔｉｂｙｔｅ  ＮＦＡのデータ構造から、各ＮＦＡの状態、状態間の遷移、遷移条件等の情報を分析し、各状態をレジスタ、遷移条件を文字（列）比較器に変換し、状態間の遷移に応じて各レジスタ間を接続し、その回路を記述するＶｅｒｉｌｏｇ  ＨＤＬやＶＨＤＬ等のＨＤＬに変換し、変換したＨＤＬをＨＤＬ記憶部３３へ記憶させる（ステップＡ７）。【００７３】
ＨＤＬへの変換が終了すると、ＨＤＬ変換部２３は、要求があればＨＤＬ記憶部３３から生成したＨＤＬを読み出し、出力装置４へ出力する（ステップＡ８）。【００７４】
次に、本発明の第１の実施の形態の作用効果について説明する。【００７５】
本発明の第１の実施の形態においては、正規表現そのものを入力することで、１−ｂｙｔｅ  ＮＦＡから指定された処理バイト数で遷移を行うＭｕｌｔｉｂｙｔｅ  ＮＦＡの変換を行い、そのＮＦＡ回路を記述するＨＤＬを生成することができる。また、本実施の形態によって生成されるＭｕｌｔｉｂｙｔｅ  ＮＦＡは、厳密一致（Ｅｘａｃｔ  Ｍａｔｃｈ）だけでなく、正規表現そのものにも対応している上、動作モードの指定により、入力された文字列のどの位置でパターンに一致したかが単独で判別可能であるＭｕｌｔｉｂｙｔｅ  ＮＦＡを用いたＮＦＡ回路を生成することができる。【００７６】
また、前述した通り、従来の複数バイト処理を行うＮＦＡ回路のうち、１つの正規表現パターンから生成した１−ｂｙｔｅ  ＮＦＡの遷移条件そのものを複数バイトに拡張させたＭｕｌｔｉｂｙｔｅ  ＮＦＡから構築したＮＦＡ回路では、パターンに一致した場合に、入力した文字列のどの位置で一致したかが単独では判別できないという課題があったが、本発明では、処理バイト数に応じて終了状態を新たに生成し、これらの終了状態のどの状態へ到達したかにより、入力した文字列のどの位置で一致したかを単独で判別できることが可能となる。例えば、正規表現“ａ（ｂｃ）＊（ｄ｜ｅ）”に対して、入力された文字列のどの位置でパターンに一致したかが判別可能である４−ｂｙｔｅ  ＮＦＡを生成した場合、図１１のようなＮＦＡが生成される。このＮＦＡを用いた場合には、状態４に到達してマッチした場合、その際に入力した４文字（４  ｂｙｔｅ）のうちの最後の文字で一致したことが分かり、状態５では、文字列の先頭から３文字目に一致したことが分かる。つまり、終了状態４、５、６、７のどの終了状態に到達したかにより、入力された文字列のどの位置でパターンに一致したかをＮＦＡ回路が単独で判別することが可能である。【００７７】
また、入力された文字列のどの位置でパターンに一致したかまでは知る必要がなく、ある正規表現パターンに対してマッチしたかしなかったかが分かればよい場合には、動作モードの指定により、従来のパターンに一致した位置が単独では判別できないＭｕｌｔｉｂｙｔｅ  ＮＦＡ回路を生成することも可能であり、この場合には処理バイト数に応じて終了状態が増加しないため、状態数は元の１−ｂｙｔｅ  ＮＦＡの状態数と変化せず、同じ処理バイト数のパターンに一致した位置が単独で判別できるＮＦＡと比較して、回路規模が削減できる。【００７８】
なお、上記実施の形態では、１−ｂｙｔｅ  ＮＦＡ変換部２１によって変換されたε遷移のない１−ｂｙｔｅ  ＮＦＡは、変換が終わる度にＭｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２２へ送られるが、これを直接ＮＦＡ記憶部３２に記憶させ、ε遷移のない１−ｂｙｔｅ  ＮＦＡの変換が終了した信号のみをＭｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２２へ送出し、Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２２は、ＮＦＡ記憶部３２に記憶されたε遷移のない１−ｂｙｔｅ  ＮＦＡを読み出しながらＭｕｌｔｉｂｙｔｅ  ＮＦＡへの変換を行ってもよい。【００７９】
また、Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２２は、変換したＭｕｌｔｉｂｙｔｅ  ＮＦＡをＮＦＡ記憶部３２へ記憶させ、全ての正規表現に対する変換が終了した後、ＮＦＡ記憶部３２から全てのＭｕｌｔｉｂｙｔｅ  ＮＦＡを読み出し、ＨＤＬ変換部２３へ送出するが、Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２２は変換が終了したことをＨＤＬ変換部２３に伝え、ＨＤＬ変換部２３がＮＦＡ記憶部３２からＭｕｌｔｉｂｙｔｅ  ＮＦＡを読み出しながら、ＨＤＬ変換処理を行っても良い。さらに、Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２２は、１つの変換が終わる度にＮＦＡ記憶部３２へ記憶させる代わりに、ＨＤＬ変換部２３へ送出し、ＨＤＬ変換部２３はＨＤＬ変換処理を開始してもよい。【００８０】
このように、正規表現記憶部３１、ＮＦＡ記憶部３２、ＨＤＬ記憶部３３を備えることにより、入力装置１は、１−ｂｙｔｅ  ＮＦＡ変換部２１の処理が終了するのを待つことなく新しい正規表現を入力することが可能であり、１−ｂｙｔｅ  ＮＦＡ変換部２１は、Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２２の処理が終了することを待つことなく、正規表現記憶部３１に新しい正規表現データが存在すれば、次の１−ｂｙｔｅ  ＮＦＡ変換処理を開始することが可能である。同様に、１−ｂｙｔｅ  ＮＦＡ変換部２１が変換したε遷移のない１−ｂｙｔｅ  ＮＦＡをＮＦＡ記憶部３２へ直接記憶させた場合には、Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２２は、ＮＦＡ記憶部３２に新しいε遷移のない１−ｂｙｔｅ  ＮＦＡが存在すれば、次のＭｕｌｔｉｂｙｔｅ  ＮＦＡ変換処理を開始することができる。また、ＨＤＬ変換部２３が直接ＮＦＡ記憶部３２からＭｕｌｔｉｂｙｔｅ  ＮＦＡを読み出すことができる場合、ＮＦＡ記憶部３２に新しいＭｕｌｔｉｂｙｔｅ  ＮＦＡが存在すれば、ＨＤＬ変換処理を開始することができる。このように、記憶装置３を用いることで、効率的なＮＦＡ回路を記述するＨＤＬ生成処理を行うことが可能である。【００８１】
さらに、上記実施の形態から、ＨＤＬ変換部２３とＨＤＬ記憶部３３を取り除き、Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２２から直接出力装置４へ、生成したＭｕｌｔｉｂｙｔｅ  ＮＦＡのデータ構造を出力することで、ＮＦＡ回路としてではなく、マルチバイト処理向け文字列照合用有限オートマトンを生成することができる。【００８２】
なお、本発明では、本実施の形態と同様の構成を適用し、１−ｂｙｔｅ  ＮＦＡ変換部２１で１  ｂｙｔｅで処理するＤＦＡを生成すれば、ＮＦＡに限らずＤＦＡに対しても、入力文字列のどの位置でパターンに一致したかが判別できる複数バイト処理のＤＦＡを生成することができる。【００８３】
（本発明の第２の実施の形態）
次に、本発明の第２の実施の形態について図面を参照して詳細に説明する。【００８４】
図１７は、本発明の第２の実施の形態の構成を示すブロック図である。図１７を参照すると、本発明の第２の実施の形態において、データ処理装置５は、１−ｂｙｔｅ  ＮＦＡ変換部２４と、Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２５と、ＨＤＬ変換部２３とを備えている。本実施の形態は、図１に示した前記第１の実施の形態のデータ処理装置２の１−ｂｙｔｅ  ＮＦＡ変換部２１、Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２２を、１−ｂｙｔｅ  ＮＦＡ変換部２４、Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２５に置き換えたものである。その他は、前記第１の実施の形態と同じである。【００８５】
１−ｂｙｔｅ  ＮＦＡ変換部２４は、前記第１の実施の形態における１−ｂｙｔｅ  ＮＦＡ変換部２１と同様に、正規表現からε遷移のない１−ｂｙｔｅ  ＮＦＡを生成するが、このＮＦＡに制約を加えている。その他は、前記第１の実施の形態における１−ｂｙｔｅ  ＮＦＡ変換部２１と同じである。【００８６】
Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２５は、１−ｂｙｔｅ  ＮＦＡ変換部２４において生成した制約条件をもつ１−ｂｙｔｅ  ＮＦＡに特化した手順でＭｕｌｔｉｂｙｔｅ  ＮＦＡ変換を行い、その他は、前記第１の実施の形態のＭｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２２と同じである。【００８７】
（本発明の第２の実施の形態の動作）
次に、図１７、及び図１８を参照して本発明の第２の実施の形態の動作について詳細に説明する。【００８８】
入力装置１から１つ、又は複数のリストとして入力された正規表現は、１−ｂｙｔｅ  ＮＦＡ変換部２４に、生成するＭｕｌｔｉｂｙｔｅ  ＮＦＡの処理バイト数と生成するＭｕｌｔｉｂｙｔｅ  ＮＦＡの種別を指定する動作モード（ｍｏｄｅ）はＭｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２５に供給される。【００８９】
１−ｂｙｔｅ  ＮＦＡ変換部２４は、受け取った正規表現を正規表現記憶部３１へ記憶させ、そこから１つずつ正規表現を読み出し、非特許文献１等に記載された公知の手法を用いながら、正規表現からある制約条件を加えたε遷移のない１−ｂｙｔｅ  ＮＦＡに変換する（ステップＡ９）。【００９０】
ここで、１−ｂｙｔｅ  ＮＦＡ変換部２４が生成するε遷移のない１−ｂｙｔｅ  ＮＦＡの制約条件について説明する。例えば、正規表現“ａｂｃｄ＊”を考えた場合、この正規表現に対するε遷移のない１−ｂｙｔｅ  ＮＦＡの例として図１９、図２０の両方が考えられる。これらのＮＦＡの違いは、終了状態から、自身も含めた他の状態への遷移が存在する（ここでは、状態４から状態４へのラベル‘ｄ’の遷移を指す）ＮＦＡ（図１９）か、終了状態から自身も含めた他の状態への遷移が存在しないＮＦＡ（図２０）かである。前記第１の実施の形態における１−ｂｙｔｅ  ＮＦＡ変換部２１では、このどちらのＮＦＡを生成してもよく、前記第１の実施の形態ではどちらのＮＦＡに対しても目的とするＭｕｌｔｉｂｙｔｅ  ＮＦＡを変換することが可能であったが、１−ｂｙｔｅ  ＮＦＡ変換部２４では、上記のＮＦＡのうち、図２０に示すような、終了状態からは自身も含め他の状態への遷移が存在しないＮＦＡを生成するという制約条件を加えることで、本第２の形態では、このような制約条件を加えた１−ｂｙｔｅ  ＮＦＡでなければ目的とするＭｕｌｔｉｂｙｔｅ  ＮＦＡを変換することができない。なお、後述するように、本制約を加えることにより、Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２５における変換処理が一部簡略化できるという利点がある。【００９１】
１−ｂｙｔｅ  ＮＦＡ変換部２４の他の動作は、変換したＮＦＡのデータ構造等も含め、全て前記第１の実施の形態の動作と同じであるので、詳細な説明を省略する。【００９２】
次に、Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２５は、ステップＡ２からステップ４までを行い、目的とするＭｕｌｔｉｂｙｔｅ  ＮＦＡの処理バイト数ＢＴが１  ｂｙｔｅでなければ（ステップＡ５）、Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２２は、１−ｂｙｔｅ  ＮＦＡ変換部２４から受け取ったε遷移のない１−ｂｙｔｅ  ＮＦＡを処理バイト数ＢＴのＭｕｌｔｉｂｙｔｅ  ＮＦＡへ変換する（ステップＡ１０）。なお、ステップＡ２からステップＡ５までは、前記第１の実施の形態の動作と同じであるため、詳細な説明を省略する  図２１は、ステップＡ１０のより詳細な動作を説明するための流れ図である。Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２２は、ステップＢ１からステップＢ８、ステップＢ１０からステップＢ１９の各ステップは、前記第１の実施の形態の動作と同じであるため詳細な説明を省略するが、ステップＡ１０の動作としては（図２１）、状態ｎ、状態ｉ、状態ｊの選択を行った後（ステップＢ５、Ｂ６、Ｂ７）、ラベル‘Ｌｎｊ’がｓｅｌｆ−ｅｄｇｅ−ｉｎｉｔｉａｌのラベルかをチェックし（ステップＢ８）、ｓｅｌｆ−ｅｄｇｅ−ｉｎｉｔｉａｌのラベルでなかった場合には、直ちに状態ｉから状態ｊへの遷移を生成するステップＢ１０を行う点が前記第１の実施の形態のステップＡ６における動作（図５）と異なっている。【００９３】
Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２５において、ステップＡ１０が終了した後の動作（ステップＡ７、ステップＡ８）については、前記第１の実施の形態の動作においてステップＡ６が終了してからの動作と同じであるため、詳細な説明は省略する。【００９４】
次に、本発明の第２の実施の形態の作用効果について説明する。【００９５】
本発明の第２の実施の形態では、前記第１の実施の形態と同様、正規表現そのものを入力することで、１−ｂｙｔｅ  ＮＦＡから指定された処理バイト数で遷移を行うＭｕｌｔｉｂｙｔｅ  ＮＦＡの変換を行い、そのＮＦＡ回路を記述するＨＤＬを生成することができる。また、本実施の形態によって生成されるＭｕｌｔｉｂｙｔｅ  ＮＦＡは、厳密一致（Ｅｘａｃｔ  Ｍａｔｃｈ）だけでなく、正規表現そのものにも対応している上、動作モードの指定により、入力された文字列のどの位置でパターンに一致するかを単独で判別できるＭｕｌｔｉｂｙｔｅ  ＮＦＡを用いたＮＦＡ回路を生成することができる。【００９６】
特に、正規表現からε遷移のない１−ｂｙｔｅ  ＮＦＡへの変換時に前記制約条件を加えることで、その後のＭｕｌｔｉｂｙｔｅ  ＮＦＡへの変換を一部簡略化できるという工夫がある。具体的には、前記第１の実施の形態では、図５に示すようにステップＢ８でステップＢ２、動作モードによってはさらにステップＢ９を行った後に、ステップＢ１０を行うという流れであったが、本第２の実施の形態では、図２１に示すように、Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２２は、ステップＢ８でラベル‘Ｌｎｊ’がｓｅｌｆ−ｅｄｇｅ−ｉｎｉｔｉａｌのラベルでなければ、すぐにステップＢ１０を行うことができる。【００９７】
また、第１の実施の形態と同様、動作モードの指定により、入力された文字列のどの位置でパターンに一致したかが単独で判別可能なＭｕｌｔｉｂｙｔｅ  ＮＦＡ回路と、パターンに一致した位置が単独では判別できないＭｕｌｔｉｂｙｔｅ  ＮＦＡ回路の両方を生成することが可能であり、使用目的に応じて効果的なＮＦＡ回路を生成することができる。【００９８】
なお、上記実施の形態では、第１の実施の形態と同様、１−ｂｙｔｅ  ＮＦＡ変換部２４によって変換されたε遷移のない１−ｂｙｔｅ  ＮＦＡは、変換が終わる度にＭｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２５へ送られるが、これを直接ＮＦＡ記憶部３２に記憶させ、ε遷移のない１−ｂｙｔｅ  ＮＦＡの変換が終了した信号のみをＭｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２５へ送出し、Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２５は、ＮＦＡ記憶部３２に記憶されたε遷移のない１−ｂｙｔｅ  ＮＦＡを読み出しながらＭｕｌｔｉｂｙｔｅ  ＮＦＡへの変換を行ってもよい。【００９９】
また、Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２５は、変換したＭｕｌｔｉｂｙｔｅ  ＮＦＡをＮＦＡ記憶部３２へ記憶させ、全ての正規表現に対する変換が終了した後、ＮＦＡ記憶部３２から全てのＭｕｌｔｉｂｙｔｅ  ＮＦＡを読み出し、ＨＤＬ変換部２３へ送出するが、Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２５は変換が終了したことをＨＤＬ変換部２３に伝え、ＨＤＬ変換部２３がＮＦＡ記憶部３２からＭｕｌｔｉｂｙｔｅ  ＮＦＡを読み出しながら、ＨＤＬ変換処理を行っても良い。さらに、Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２５は、１つの変換が終わる度にＮＦＡ記憶部３２へ記憶させる代わりに、ＨＤＬ変換部２３へ送出し、ＨＤＬ変換部２３はＨＤＬ変換処理を開始してもよい。【０１００】
このように、正規表現記憶部３１、ＮＦＡ記憶部３２、ＨＤＬ記憶部３３を備えることにより、入力装置１は、１−ｂｙｔｅ  ＮＦＡ変換部２４の処理が終了するのを待つことなく新しい正規表現を入力することが可能であり、１−ｂｙｔｅ  ＮＦＡ変換部２４は、Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２５の処理が終了することを待つことなく、正規表現記憶部３１に新しい正規表現データが存在すれば、次の１−ｂｙｔｅ  ＮＦＡ変換処理を開始することが可能である。同様に、１−ｂｙｔｅ  ＮＦＡ変換部２４が変換したε遷移のない１−ｂｙｔｅ  ＮＦＡをＮＦＡ記憶部３２へ直接記憶させた場合には、Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２５は、ＮＦＡ記憶部３２に新しいε遷移のない１−ｂｙｔｅ  ＮＦＡが存在すれば、次のＭｕｌｔｉｂｙｔｅ  ＮＦＡ変換処理を開始することができる。また、ＨＤＬ変換部２３が直接ＮＦＡ記憶部３２からＭｕｌｔｉｂｙｔｅ  ＮＦＡを読み出すことができる場合、ＮＦＡ記憶部３２に新しいＭｕｌｔｉｂｙｔｅ  ＮＦＡが存在すれば、ＨＤＬ変換処理を開始することができる。このように、記憶装置３を用いることで、効率的なＮＦＡ回路を記述するＨＤＬ生成処理を行うことが可能である。【０１０１】
さらに、上記実施の形態から、ＨＤＬ変換部２３とＨＤＬ記憶部３３を取り除き、Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２２から直接出力装置４へ、生成したＭｕｌｔｉｂｙｔｅ  ＮＦＡのデータ構造を出力することで、ＮＦＡ回路としてではなく、マルチバイト処理向け文字列照合用有限オートマトンを生成することができる。【０１０２】
なお、本発明では、本実施の形態と同様の構成を適用し、１−ｂｙｔｅ  ＮＦＡ変換部２４で１  ｂｙｔｅで処理するＤＦＡを生成すれば、ＮＦＡに限らずＤＦＡに対しても、入力文字列のどの位置でパターンに一致したかが判別できる複数バイト処理のＤＦＡを生成することができる。【０１０３】
（本発明の第３の実施の形態）
次に、本発明の第３の実施の形態について図面を参照して詳細に説明する。【０１０４】
図２２は、本発明の第３の実施の形態の構成を示すブロック図である。図２２を参照すると、本発明の第３の実施の形態は、前記第１、第２の実施の形態と同様に、入力装置１、データ処理装置６、記憶装置３、出力装置４を備える。本実施の形態においては、前記第１の実施の形態のデータ処理装置２の１−ｂｙｔｅ  ＮＦＡ変換部２１、Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２２、ＨＤＬ変換部２３、あるいは、前記第２の実施の形態のデータ処理装置５の１−ｂｙｔｅ  ＮＦＡ変換部２４、Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換部２５、ＨＤＬ変換部２３の処理を、データ処理装置で実行される正規表現−ＨＤＬ変換プログラム７で実現したものである。【０１０５】
正規表現−ＨＤＬ変換プログラム７は、データ処理装置６に読み込まれ、データ処理装置６の動作を制御し、記憶装置３に、正規表現記憶部３１とＮＦＡ記憶部３２とＨＤＬ記憶部３３を生成する。【０１０６】
データ処理装置６は、正規表現−ＨＤＬ変換プログラムの制御により、第１、及び第２の実施の形態におけるデータ処理装置２、及び５による処理と同一の処理を実行する。【０１０７】
次に、本発明の第３の実施の形態の作用効果について説明する。【０１０８】
本発明の第３の実施の形態では、第１、第２の実施の形態の作用効果と同様、正規表現そのものを入力することで、指定された処理バイト数で遷移を行うＭｕｌｔｉｂｙｔｅ  ＮＦＡを実現するＮＦＡ回路を記述するＨＤＬを生成することができる。また、本実施の形態によって生成されるＭｕｌｔｉｂｙｔｅ  ＮＦＡは、厳密一致（Ｅｘａｃｔ  Ｍａｔｃｈ）だけでなく、正規表現そのものにも対応している上、動作モードの指定により、入力された文字列のどの位置でパターンに一致したかが単独で判別可能なＭｕｌｔｉｂｙｔｅ  ＮＦＡを用いたＮＦＡ回路を生成することができる。【０１０９】
また、動作モードの指定により、入力された文字列のどの位置でパターンに一致したかを単独で判別できるＭｕｌｔｉｂｙｔｅ  ＮＦＡ回路と、パターンに一致した位置を単独では判別できないＭｕｌｔｉｂｙｔｅ  ＮＦＡ回路の両方を生成することが可能であり、目的に応じて選択することで、効率的なＮＦＡ回路を生成することができる。【０１１０】
さらに、正規表現−ＨＤＬ変換プログラム７は、データ処理装置６に読み込まれ、データ処理装置６の動作を制御し、記憶装置３に、正規表現記憶部３１とＮＦＡ記憶部３２のみを生成し、データ処理装置６から出力装置４へＭｕｌｔｉｂｙｔｅ  ＮＦＡのデータ構造を出力することで、ＮＦＡ回路としてではなく、マルチバイト処理向け文字列照合用有限オートマトンを生成することができる。【０１１１】
なお、本発明の第３の実施の形態でも、第１、第２の実施の形態と同様に、ＮＦＡに限らずＤＦＡに対しても同様の処理を行うことが可能である。【０１１２】
（本発明の第４の実施の形態）
次に、本発明の第４の実施の形態について図面を参照して詳細に説明する。【０１１３】
図２３は、本発明の第４の実施の形態の構成を示すブロック図である。図２３を参照すると、本発明の第４の実施の形態は、キーボード等の入力装置１と、プログラム制御により動作するデータ処理装置８と、情報を記憶する記憶装置９と、ＦＰＧＡ等の再構成可能なハードウェアデバイスに、その構成をコンフィグレーションするためのケーブル等のコンフィグレーション装置１０と、パターンマッチングの被検索対象データをパターンマッチング装置に入力するためのデータ入力装置１１と、ＦＰＧＡ等の再構成可能なハードウェアデバイスを有するパターンマッチング装置１２と、パターンマッチングの結果を出力するためのディスプレイ装置や印刷装置等の結果出力装置１３とを備えている。さらに、データ処理装置８と記憶装置９を制御するのがＣＰＵ１０２であり、データ処理装置８内の各部内のプログラムによってＣＰＵ１０２が動作する。パターンマッチング装置１２は、ＦＰＧＡ等の再構成可能なハードウェアデバイスから構成される。【０１１４】
記憶装置９は、図１に示した前記第１の実施の形態の記憶装置３に、Ｃｏｎｆｉｇｕｒａｔｉｏｎ  ｄａｔａ記憶部３４を加えたものである。その他は、前記第１の実施の形態と同じである。【０１１５】
Ｃｏｎｆｉｇｕｒａｔｉｏｎ  ｄａｔａ記憶部３４は、Ｃｏｎｆｉｇｕｒａｔｉｏｎ  ｄａｔａ変換部２６において、ＨＤＬ記憶部３３から読み出したＭｕｌｔｉｂｙｔｅ  ＮＦＡ回路を記述するＨＤＬから生成した、対象となるデバイスの構成情報であるＣｏｎｆｉｇｕｒａｔｉｏｎ  ｄａｔａを記憶する。【０１１６】
データ処理装置８は、図１に示した前記第１の実施の形態のデータ処理装置２に、Ｃｏｎｆｉｇｕｒａｔｉｏｎ  ｄａｔａ変換部２６を加えたものである。その他は、前記第１の実施の形態と同じである。【０１１７】
Ｃｏｎｆｉｇｕｒａｔｉｏｎ  ｄａｔａ変換部２６は、ＨＤＬ変換部２３にてＨＤＬへの変換が終了したことを意味する信号、もしくは、入力装置１からＣｏｎｆｉｇｕｒａｔｉｏｎ  ｄａｔａの生成開始を意味する信号を受けた場合に、それぞれから指定されたＨＤＬ記憶部３３に記憶されているＭｕｌｔｉｂｙｔｅ  ＮＦＡ回路を記述するＨＤＬを読み込み、ＨＤＬから対象となるデバイスの構成情報であるＣｏｎｆｉｇｕｒａｔｉｏｎ  ｄａｔａへ変換し、変換が終了すると、Ｃｏｎｆｉｇｕｒａｔｉｏｎ  ｄａｔａ記憶部３４に記憶する。なお、ＨＤＬからＣｏｎｆｉｇｕｒａｔｉｏｎ  ｄａｔａの変換については、例えばＦＰＧＡであれば、そのベンダーが提供している開発ツール等を用いるものとし、詳細な説明は省略する。【０１１８】
パターンマッチング装置１２は、データ入力部１２１と、パターンマッチング部１２２と、結果出力部１２３とを備えており、これらは別々の再構成可能なハードウェアデバイス上に構成されるものとする。【０１１９】
データ入力部１２１は、データ入力装置１１から入力されたパケットデータや、テキストデータ等のパターンマッチング対象データ（これを被検索データと呼ぶ）を整形し、データ処理装置８にて生成した処理バイト数で並列化し、パターンマッチング部１２２へ入力する。【０１２０】
パターンマッチング部１２２は、コンフィグレーション装置１０を経由して入力された、データ処理装置８で生成したＣｏｎｆｉｇｕｒａｔｉｏｎ  ｄａｔａにより構成される回路であり、データ処理装置８にて生成したＭｕｌｔｉｂｙｔｅ  ＮＦＡ回路そのものである。パターンマッチング部１２２に構成されたＮＦＡ回路は、データ入力部１２１から入力された被検索データにより条件遷移が起こり、パターンに一致した場合にはその信号が終了状態を構成しているレジスタから出力信号が結果出力部１２３へと出力される。【０１２１】
結果出力部１２３は、パターンマッチング部１２２から入力されたパターンに一致したことを示す信号を受け取る。パターンマッチング部１２２に構成されているＮＦＡ回路が、入力された文字列のどの位置でパターンに一致したかが判別可能なＮＦＡ回路であれば、どの状態から上記の信号を受け取ったかにより、入力された被検索データのどの位置でどのパターンが一致したのか、パターンマッチング部１２２に構成されているＮＦＡ回路が、入力された文字列のどの位置でパターンに位置したのかが判別できないＮＦＡ回路であれば、入力された被検索データがどの入力文字列でどのパターンに一致したのか等の情報を処理して、結果出力装置１３へ出力する。なお、どのパターンに一致したかは、予め定義しておいたパターン番号等により通知するといった方法がある。【０１２２】
次に、本発明の第４の実施の形態の作用効果について説明する。【０１２３】
本発明の第４の実施の形態では、正規表現そのものを入力することで、１−ｂｙｔｅ  ＮＦＡから指定された処理バイト数で遷移を行うＭｕｌｔｉｂｙｔｅ  ＮＦＡの変換を行い、そのＮＦＡ回路を記述するＨＤＬを生成した後に、そのＮＦＡ回路をハードウェアデバイス上に構成し、それを用いたパターンマッチング装置を実現することができる。また、本実施の形態によって生成されるＭｕｌｔｉｂｙｔｅ  ＮＦＡは、厳密一致（Ｅｘａｃｔ  Ｍａｔｃｈ）だけでなく、正規表現そのものにも対応している上、動作モードの指定により、入力された文字列のどの位置でパターンに一致したかが単独で判別可能であるＭｕｌｔｉｂｙｔｅ  ＮＦＡを用いたＮＦＡ回路を用いたパターンマッチング装置を実現することができる。【０１２４】
また、本実施の形態では、第１、第２、第３の実施の形態の作用効果と同様、動作モードの指定によっては、入力された文字列のどの位置でパターンに一致したかを単独では判別できないＭｕｌｔｉｂｙｔｅ  ＮＦＡ回路により構成することもでき、目的に応じて効率的なＮＦＡ回路を用いたパターンマッチング装置を実現できる。【０１２５】
なお、上記実施の形態におけるデータ処理装置８、記憶装置９は、第１の実施の形態におけるデータ処理装置２、記憶装置３にＣｏｎｆｉｇｕｒａｔｉｏｎ  ｄａｔａ変換部２６、Ｃｏｎｆｉｇｕｒａｔｉｏｎ  ｄａｔａ記憶部３４を加えたもので構成されるが、第２の実施の形態におけるデータ処理装置５、記憶装置３にＣｏｎｆｉｇｕｒａｔｉｏｎ  ｄａｔａ変換部２６、Ｃｏｎｆｉｇｕｒａｔｉｏｎ  ｄａｔａ記憶部３４を加えて構成しても良い。【０１２６】
また、第３の実施の形態における正規表現−ＨＤＬ変換プログラム７で実現したものから生成されたＨＤＬからＣｏｎｆｉｇｕｒａｔｉｏｎ  ｄａｔａを生成しても良い。【０１２７】
さらに、本実施の形態では、パターンマッチング装置１２において、データ入力部１２１と、パターンマッチング部１２２と、結果出力部１２３は別々の再構成可能ハードウェアデバイス上に構成されているが、これら３つを同じ再構成可能ハードウェアデバイス上に構成してもよいし、例えばデータ入力部１２１と結果出力部１２３は同じ再構成可能ハードウェアデバイス上に、パターンマッチング部１２２は別の再構成可能ハードウェアデバイス上に構成する等、様々な組み合わせがある上、生成したＨＤＬを用いて、ＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ  Ｓｐｅｃｉｆｉｃ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）化してしまう等、再構成できないハードウェアデバイスに構成しても良い。ここで、データ入力部１２１、結果出力部１２３の両方、または、いずれかを、パターンマッチング部１２２と同じ再構成可能ハードウェアデバイス上に構成する場合、Ｃｏｎｆｉｇｕｒａｔｉｏｎ  ｄａｔａ変換部２６は、ＨＤＬ変換部２３にて生成されたＮＦＡ回路を記述するＨＤＬのみでなく、それらの回路を記述するＨＤＬも読み込んでＣｏｎｆｉｇｕｒａｔｉｏｎ  ｄａｔａを生成することにより対応できる。【０１２８】
なお、本第４の実施の形態でも、第１、第２、第３の実施の形態と同様に、ＮＦＡに限らずＤＦＡに対しても同様の処理を行うことが可能である。
【産業上の利用可能性】
【０１２９】
本発明の活用例として、正規表現を用いたパターンマッチング処理を行うためのＮＦＡ回路を記述したＨＤＬ生成システム、生成プログラムといった用途に適用できる。また、本発明を用いて生成したＨＤＬによりＮＦＡ回路を構成することで、正規表現を用いた高速なパターンマッチング処理を行うためのパターンマッチング装置といった用途に適用できる。さらに、パターンマッチング装置にパケット処理回路を加えることにより、ネットワーク侵入検知システム（ＮＩＤＳ：  Ｎｅｔｗｏｒｋ  Ｉｎｔｒｕｓｉｏｎ  Ｄｅｔｅｃｔｉｏｎ  Ｓｙｓｔｅｍ）やネットワーク侵入防止システム（ＮＩＰＳ：  Ｎｅｔｗｏｒｋ  Ｉｎｔｒｕｓｉｏｎ  Ｐｒｏｔｅｃｔｉｏｎ  Ｓｙｓｔｅｍ）にも適用でき、パソコンやワークステーションに搭載されているソフトウェアベースでのパターンマッチング処理の代替となるハードウェアアクセラレータ用ＮＦＡ回路生成システム、生成プログラム、及び、正規表現検索ハードウェアアクセラレータ装置等にも適用できる。【０１３０】
本発明は、マルチバイト処理向け文字列照合用有限オートマトン生成システム、オートマトン回路生成システム、その生成方法、回路生成方法、生成プログラム、回路生成プログラム及びそれを用いたパターンマッチング装置、マルチバイト処理向け文字列照合用有限オートマトン回路に関するものであれば、あらゆるものに適用することが可能であり、その利用の可能性において何ら限定するものではない。【０１３１】
幾つかの好適な実施の形態及び実施例に関連付けして本発明を説明したが、これら実施の形態及び実施例は単に実例を挙げて発明を説明するためのものであって、限定することを意味するものではないことが理解できる。本明細書を読んだ後であれば、当業者にとって等価な構成要素や技術による数多くの変更および置換が容易であることが明白であるが、このような変更および置換は、添付の請求項の真の範囲及び精神に該当するものであることは明白である。
【符号の説明】
【０１３２】
１  入力装置
２  データ処理装置
３  記憶装置
４  出力装置
５  データ処理装置
６  データ処理装置
７  正規表現−ＨＤＬ変換プログラム
８  データ処理装置
９  記憶装置
１０  コンフィグレーション装置
１１  データ入力装置
１２  パターンマッチング装置
１３  結果出力装置
２１  １−ｂｙｔｅ  ＮＦＡ変換部
２２  Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換部
２３  ＨＤＬ変換部
２４  １−ｂｙｔｅ  ＮＦＡ変換部
２５  Ｍｕｌｔｉｂｙｔｅ  ＮＦＡ変換部
２６  Ｃｏｎｆｉｇｕｒａｔｉｏｎ  ｄａｔａ変換部
３１  正規表現記憶部
３２  ＮＦＡ記憶部
３３  ＨＤＬ記憶部
３４  Ｃｏｎｆｉｇｕｒａｔｉｏｎ  ｄａｔａ記憶部
１０１，１０２  ＣＰＵ
１２１  データ入力部
１２２  パターンマッチング部
１２３  結果出力部
２００〜２０４  レジスタ
３００〜３０４  各文字を比較する比較器
４００〜４０３  ＡＮＤゲート
５００〜５０２  ＯＲゲート
【図１】
2009116646.tif 000003
【図２】
2009116646.tif 000004
【図３】
2009116646.tif 000005
【図４】
2009116646.tif 000006
【図５】
2009116646.tif 000007
【図６】
2009116646.tif 000008
【図７】
2009116646.tif 000009
【図８】
2009116646.tif 000010
【図９】
2009116646.tif 000011
【図１０】
2009116646.tif 000012
【図１１】
2009116646.tif 000013
【図１２】
2009116646.tif 000014
【図１３】
2009116646.tif 000015
【図１４】
2009116646.tif 000016
【図１５】
2009116646.tif 000017
【図１６】
2009116646.tif 000018
【図１７】
2009116646.tif 000019
【図１８】
2009116646.tif 000020
【図１９】
2009116646.tif 000021
【図２０】
2009116646.tif 000022
【図２１】
2009116646.tif 000023
【図２２】
2009116646.tif 000024
【図２３】
2009116646.tif 000025
【図２４】
2009116646.tif 000026
【図２５】
2009116646.tif 000027
【図２６】
2009116646.tif 000028
【図２７】
2009116646.tif 000029
【図２８】
2009116646.tif 000030
【国際調査報告】
2009116646.tif 000031
2009116646.tif 000032
2009116646.tif 000033
2009116646.tif 000034
2009116646.tif 000035
2009116646.tif 000036