実施の形態1.
 図1は本発明の実施の形態1の構成を示すブ� �ック図である。図1を参照すると、本実施の� ��態1は、キーボード等の入力装置11と、プロ� ��ラム制御に基づいて動作するデータ処理装� ��12と、情報を記憶する記憶装置140と、ディ� �プレイ装置や印刷装置等の出力装置13と、を 含む。

 記憶装置140は、繰り返し正規表現リスト� ��憶部141と、1-char NFA記憶部142と、1-char NFA記 述行列記憶部143と、NFA記述行列演算情報記憶 部144と、multi-char NFA記述行列記憶部145と、mul ti-char NFA記憶部146と、を含む。

 データ処理装置12は、1-char NFA生成手段121 と、1-char NFA記述行列生成手段122と、multi-char  NFA記述行列生成手段123と、multi-char NFA生成� ��段124と、HDL変換手段125と、を含む。尚、本� ��施の形態1では、固定文字数の遷移条件から 成る固定文字数単位の有限オートマトンが、 1文字単位の有限オートマトン(1-char NFA)であ� ��場合を例に説明する。このため、固定文字� ��単位有限オートマトン生成手段が、1-char NF A生成手段121に対応する。また、固定文字数� �位行列形式表現生成手段が、1-char NFA記述行 列生成手段122に対応する。

 1-char NFA生成手段121は、入力装置11から1� �以上の正規表現を読み込む。1-char NFA生成手 段121は、読み込んだ正規表現をε遷移の無い1 -char NFAに変換する。1-char NFA生成手段121は、 変換した1-char NFAを1-char NFA記憶部142に記憶� �る。1-char NFA記憶部142への記憶後、1-char NFA� ��成手段121は、次の正規表現をNFAへ変換する� ��理を開始する。

 また、正規表現を1-char NFAに変換する際� �、1-char NFA生成手段121は、繰り返し正規表現 リストを作成する。繰り返し正規表現リスト は、正規表現に含まれる繰り返し正規表現と 、その繰り返し正規表現に対応する1-char NFA� ��状態番号との対応関係を保持するリストで� ��る。1-char NFA生成手段121は、作成した繰り� �し正規表現リストを繰り返し正規表現リス� �記憶部141に記憶する。

 さらに、入力装置11から読み込んだ全て� �正規表現を1-char NFAへと変換する処理を完了 する際には、1-char NFA生成手段121は、全ての� ��規表現を変換したことを示す信号を、1-char� �NFA記述行列生成手段122に通知する。

 1-char NFA記述行列生成手段122は、非特許� �献3に開示される手法に基づいて、1-char NFA� �憶部142に記憶した1-char NFAから1-char NFA記述� ��列を生成する。1-char NFA記述行列生成手段12 2は、生成した1-char NFA記述行列を、1-char NFA� ��述行列記憶部143に記憶する。尚、以下では� ��1-char NFA記述行列記憶部143に記憶した1-char  NFA記述行列を、オリジナル版1-char NFA記述行� ��と称する。

 また、生成した1-char NFA記述行列を1-char  NFA記述行列記憶部143に記憶する際に、1-char N FA生成手段121から全ての正規表現を変換した� ��とを示す信号を受信している場合には、1-ch ar NFA記述行列生成手段122は、全ての1-char NFA 記述行列の生成処理が完了したことを示す信 号を、multi-char NFA記述行列生成手段123に通知 する。

 multi-char NFA記述行列生成手段123は、入力� ��置11から動作文字数を読み込む。動作文字� �は、生成するmulti-char NFAの遷移条件となる� �字(列)の長さであり、以下の説明においては 動作文字数をMを使用して表す。

 multi-char NFA記述行列生成手段123は、繰り� ��し正規表現リスト記憶部141に記憶した繰り� ��し正規表現リストから、行列変換情報リス� ��を作成する。multi-char NFA記述行列生成手段1 23は、作成した行列変換情報リストをNFA記述� ��列演算情報記憶部144に記憶する。尚、multi-c har NFA記述行列生成手段123は、作成した行列� ��換情報リストと、後述する縮小版NFA記述行� ��(縮小版1-char NFA記述行列と、縮小版multi-char  NFA記述行列)とをNFA記述行列演算情報記憶部 144に記憶する。

 multi-char NFA記述行列生成手段123は、1-char� �NFA記述行列記憶部143に記憶した1-char NFA記述 行列から、NFA記述行列演算情報記憶部144に記 憶した行列変換情報リストを参照して、1-char  NFA記述行列の行列サイズの縮小を行う。mult i-char NFA記述行列生成手段123は、行列サイズ� ��縮小した1-char NFA記述行列をNFA記述行列演� �情報記憶部144に記憶する。以下では、行列� �イズを縮小したNFA記述行列を、「縮小版NFA� �述行列」と称する。また、行列サイズを縮� �する前のサイズのNFA記述行列を、「オリジ� �ル版NFA記述行列」と称する。

 multi-char NFA記述行列生成手段123は、NFA記� ��行列演算情報記憶部144に記憶した縮小版1-ch ar NFA記述行列を用いて、動作文字数がMの縮� ��版multi-char NFA記述行列を生成する。multi-char  NFA記述行列生成手段123は、生成した縮小版m ulti-char NFA記述行列をNFA記述行列演算情報記� ��部144に記憶する。そして、multi-char NFA記述� ��列生成手段123は、NFA記述行列演算情報記憶� ��144に記憶した行列変換情報リストを参照し� ��、NFA記述行列演算情報記憶部144に記憶した� ��小版multi-char NFA記述行列からオリジナル版m ulti-char NFA記述行列を生成する。multi-char NFA� ��述行列生成手段123は、生成したオリジナル� ��multi-char NFA記述行列を、multi-char NFA記述行� ��記憶部145に記憶する。

 また、生成したオリジナル版multi-char NFA� ��述行列をmulti-char NFA記述行列記憶部145に記� ��する際に、1-char NFA記述行列生成手段122か� �全ての1-char NFA記述行列の生成処理が完了し たことを示す信号を受信している場合には、 multi-char NFA記述行列生成手段123は、全てのmul ti-char NFA記述行列の生成処理が完了したこと を示す信号を、multi-char NFA生成手段124に通知 する。

 multi-char NFA生成手段124は、非特許文献3に 開示される手法に基づいて、multi-char NFA記述 行列記憶部145に記憶したオリジナル版multi-cha r NFA記述行列から、multi-char NFAを生成する。 multi-char NFA生成手段124は、生成したmulti-char  NFAをmulti-char NFA記憶部146に記憶する。

 また、multi-char NFAをmulti-char NFA記憶部146� ��記憶する際に、multi-char NFA記述行列生成手� ��123から全てのmutli-char NFA記述行列の生成処� ��が完了したことを示す信号を受信している� ��合には、multi-char NFA生成手段124は、全てのm ulti-char NFAの生成処理が完了したことを示す� ��号を、HDL変換手段125に通知する。

 HDL変換手段125は、multi-char NFA記憶部146に� ��憶したmulti-char NFAについて、そのNFAの状態� ��、状態間の遷移と、遷移条件等の情報を分� ��する。HDL変換手段125は、分析結果に基づい� ��、各状態をレジスタに、遷移条件を文字(列 )比較器にそれぞれ変換して、状態間の遷移� �応じて各レジスタの間を接続することで、� �のNFA回路を記述するVerilog HDL等のHDL(Hardware  Description Language)記述に変換する。

 また、HDL変換手段125は、multi-char NFA生成� ��段124から全てのmulti-char NFAの生成処理が完� ��したことを示す信号を受信した場合には、m ulti-char NFAから変換した全てのHDL記述と、正� ��表現からHDLへの変換処理が完了したことを� ��す信号と、を出力装置13に出力する。

 続いて、本実施の形態1の動作について説 明する。以下では、具体例として正規表現"BC D((A{100}|E)S)*TTB{50}U"の場合について詳細に説明 する。

 まず、図2~図6を参照して、1-char NFA生成� �段121の動作について説明する。入力装置11は 、1つ以上の正規表現を含む。1-char NFA生成手 段121は、入力装置11より正規表現を読み込む� ��1-char NFA生成手段121は、読み込んだ正規表� �を、ε遷移の無い1-char NFAに変換する。1-char� �NFA生成手段121は、変換した1-char NFAを1-char N FA記憶部142に記憶する。1-char NFA記憶部142へ� �記憶した後、1-char NFA生成手段121は、次の正 規表現をNFAへ変換する処理を開始する。

 また、正規表現を1-char NFAに変換する際� �、1-char NFA生成手段121は、繰り返し正規表現 リストを作成する。図3は、繰り返し正規表� �リストの構成を示す図である。図に示すよ� �に、繰り返し正規表現リストの各要素を、� �り返し正規表現の繰り返し文字と、繰り返� �正規表現の繰り返し回数と、1-char NFAにおけ る繰り返し正規表現の開始状態番号と、から 構成する。1-char NFA生成手段121は、各繰り返� ��正規表現についてこれらの要素を作成し、� ��り返し正規表現リストに格納する。即ち、1 -char NFA生成手段121は、繰り返し正規表現の� �数分、これらの要素を繰り返し正規表現リ� �トに格納する。1-char NFA生成手段121は、作成 した繰り返し正規表現リストを繰り返し正規 表現リスト記憶部141に記憶する。

 1-char NFA生成手段121は、例えば、正規表� �"BCD((A{100}|E)S)*TTB{50}U"を、図2に示すε遷移の� �い1-char NFAに変換することができる。正規表 現"BCD((A{100}|E)S)*TTB{50}U"は、二つの繰り返し正 規表現"A{100}"と"B{50}"とを含む。図2に示す1-cha r NFAにおいて、繰り返し正規表現"A{100}"が、� ��態3→状態4→・・・・→状態103の状態遷移� �対応している。また、繰り返し正規表現"B{50 }"が、状態105→状態106→・・・・→状態155の� ��態遷移に対応している。この場合に、正規� ��現リストは、図3に示すように2個の要素を� �む。即ち、図3に示す正規表現リストは、一� ��目の要素として、繰り返し正規表現"A{100}"� �対応する要素を含み、その内容は、繰り返� �文字'A'と、繰り返し回数100と、開始状態番� �3と、から構成する。また、図3に示す正規表 現リストは、他の一の要素として、繰り返し 正規表現"B{50}"に対応する要素を含み、その� �容は、繰り返し文字'B'と、繰り返し回数50と 、開始状態番号105と、から構成する。

 尚、ここでは、繰り返し文字として'A'や� ��'B'等の単一文字を例示して説明したが本発� ��はこれに限定されない。即ち、マッチする� ��字の長さが1文字の正規表現である場合には 、繰り返し文字として任意の正規表現を指定 してもよい。繰り返し正規表現の繰り返し文 字としては、例えば、"(A|B)"や、"[A-Za-z0-9]"等� ��複数文字のいずれかを表す正規表現を指定� ��ることもできる。

 ここで、図4~図6を参照しながら、1-char NF A生成手段121が、正規表現からε遷移の無い1-c har NFAを生成する様子を具体的に説明する。� ��4は、1-char NFA生成手段121が、正規表現から� �遷移の無い1-char NFAを生成する処理を示すフ ローチャートである。正規表現からε遷移の� ��い1-char NFAを生成する一般的な手法として� �、非特許文献1に開示されている手法が良く� ��られている。非特許文献1に開示される手法 では、正規表現からε遷移を含む1-char NFAを� �成して、ε遷移を取り除くε-closure(ε-閉包)を 行う。これにより、非特許文献1に開示され� �手法は、生成したε遷移を含む1-char NFAから� ��ε遷移の無い1-char NFAを生成する。以下、こ の手法を用いて、正規表現"BCD((A{100}|E)S)*TTB{50 }U"から1-char NFAを生成する処理について説明� ��る。

 1-char NFA生成手段121は、非特許文献1に開� ��される手法に基づいて、正規表現"BCD((A{100}| E)S)*TTB{50}U"を、ε遷移を含む1-char NFAに変換す る(ステップA1)。図5に、変換後の、ε遷移を� �む1-char NFAを示す。ここで、非特許文献3で� �示されるNFA記述行列を用いたmulti-char NFA生� �手法では、NFA記述行列を生成する前に1-char  NFAを予め1文字単位に展開しておく必要があ� �。このため、1-char NFA生成手段121は、繰り返 し正規表現"A{100}"を、文字'A'に基づく100回の� ��態遷移に展開する(図5において、展開後の� �等範囲を点線枠内に示す。)。また、1-char NF A生成手段121は、繰り返し正規表現"B{50}"を、� ��字'B'に基づく50回の状態遷移に展開する(図5 において、展開後の該等範囲を点線枠内に示 す。)。

 1-char NFA生成手段121は、各繰り返し正規� �現を繰り返し文字へと展開する際に、その� �開時の繰り返し正規表現の開始状態番号を� �持することで、繰り返し正規表現リストを� �成する。即ち、1-char NFA生成手段121は、繰り 返し正規表現"A{100}"を、図5に示す文字'A'に基 づく100回の状態遷移に展開する際に、展開時 の開始状態番号13を保持する。また、1-char NF A生成手段121は、繰り返し正規表現"B{50}"を、� ��5に示す文字'B'に基づく50回の状態遷移に展� ��する際に、展開時の開始状態番号114を保持� ��る。図6に、このようにして1-char NFA生成手� ��121が作成した繰り返し正規表現リストを示� ��。

 図4に戻り説明を続ける。1-char NFA生成手� ��121は、非特許文献1等に開示される手法を用 いて、図5に示すε遷移を含む1-char NFAに対し� ��ε-closureを行うことで、図2に示すε遷移の無 い1-char NFAを生成する(ステップA2)。具体的に は、ε-closureにおいて、1-char NFA生成手段121は 、ε遷移に従って遷移可能な複数の状態を、� ��つの状態に統合する処理を行う。ここで、� ��り返し正規表現の開始状態がε-closureにおけ る状態統合の対象となった場合には、1-char N FA生成手段121は、繰り返し正規表現リストに� ��ける開始状態番号を、ε-closure前の状態番号 からε-closureにおいて統合された後の状態番� �へと変更する。これにより、ε遷移の無い1-c har NFAにおいても、繰り返し正規表現とその� ��始状態番号との対応関係を、繰り返し正規� ��現リストを用いて管理することができる。

 より具体的には、1-char NFA生成手段121は� �ε-closureを行うことで、図5に示す状態3、4、7 、13を一つに統合して、新たに、図2に示す状 態3とする。これに対応して、1-char NFA生成手 段121は、図6に示す繰り返し正規表現リスト� �おいて、繰り返し正規表現"A{100}"に対応する 要素(繰り返し文字'A'、繰り返し回数100、開� �状態番号13である要素。)の開始状態番号を� �ε-closure後の開始状態番号3に書き換える。同 様に、1-char NFA生成手段121は、ε-closureを行う ことで、図5に示す状態114と状態10とを統合し て、新たに図2に示す状態105とする。これに� �応して、1-char NFA生成手段121は、図6に示す� �り返し正規表現リストにおいて、繰り返し� �規表現"B{50}"に対応する要素(図6に示す最下� �の要素。)の開始状態番号を、ε-closure後の開 始状態番号105に書き換える。1-char NFA生成手� ��121は、上述の処理を繰り返すことで、図2に 示すε遷移の無い1-char NFAに対応する繰り返� �正規表現リストを作成する。図3に、作成し� ��繰り返し正規表現リストを示す。

 1-char NFA生成手段121は、図2に示すε遷移� �無い1-char NFAにおいて、各繰り返し正規表現 に対応する部分の状態遷移に関して、状態番 号が昇順の連番となるように状態番号を割り 当て直す(ステップA3)。具体的には、1-char NFA 生成手段121は、図3に示す繰り返し正規表現� �ストの各要素の開始状態番号を起点として� �繰り返し文字に基づく状態遷移を繰り返し� �数分だけ辿り、状態番号が昇順の連番にな� �ているか否かを確認する。状態番号が昇順� �連番になっていない場合には、1-char NFA生成 手段121は、状態番号の割り当て直しを行う。

 図2に示すε遷移の無い1-char NFAでは、既� �、繰り返し正規表現"A{100}"に対応する状態遷 移は、状態3→4→5→・・・→102→103となって いる。即ち、繰り返し正規表現"A{100}"に対応� ��る状態遷移については、既に昇順の連番と� ��る状態番号が割り当てられているため、1-ch ar NFA生成手段121は、状態番号の割り当て直� �を行う必要はない。同様に、図2に示すε遷� �の無い1-char NFAでは、繰り返し正規表現"B{50} "に対応する状態遷移は、状態105→106→・・� �→154→155となっている。即ち、繰り返し正� �表現"B{50}"に対応する状態遷移についても、� ��に昇順の連番となる状態番号が割り当てら� ��ているため、1-char NFA生成手段121は、状態� �号の割り当て直しを行う必要はない。

 一方で、状態番号の割り当て直しが必要� ��なり、繰り返し正規表現に対応する状態遷� ��の開始状態番号に変化が生じた場合には、1 -char NFA生成手段121は、繰り返し正規表現リ� �トの対応する繰り返し正規表現の開始状態� �号を、割り当て直し後の状態番号として更� �する。

 1-char NFA生成手段121は、上述した処理を� �3に示す繰り返し正規表現リストの各要素、� ��ち、全ての繰り返し正規表現に対して繰り� ��す。

 尚、状態番号は、一つの繰り返し正規表� ��に対応する状態遷移の範囲内において、昇� ��の連番となっていればよい。従って、異な� ��繰り返し正規表現に関しては、状態番号に� ��する制約はない。例えば、繰り返し正規表� ��"A{100}"に対応する状態遷移の開始状態番号� �、繰り返し正規表現"B{50}"に対応する状態遷� ��の開始状態番号よりも大きなものとなって� ��てもよい。

 1-char NFA生成手段121は、生成したε遷移の 無い1-char NFAと、作成した繰り返し正規表現� ��ストと、を出力する(ステップA4)。即ち、1-c har NFA生成手段121は、1-char NFAを1-char NFA記憶 部142に記憶する。また、1-char NFA生成手段121� ��、繰り返し正規表現リストを繰り返し正規� ��現リスト記憶部141に記憶する。

 以上説明したようにして、1-char NFA生成� �段121は、一つの正規表現から1-char NFAを生成 する一連の処理を終了する。入力装置11から� ��数の正規表現を受信した場合には、1-char NF A生成手段121は、受信した全ての正規表現に� �いて上述した処理を繰り返して実行する。

 また、1-char NFA生成手段121は、入力装置11 から読み込んだ全ての正規表現の変換処理を 完了する際には、全ての正規表現を変換した ことを示す信号を、1-char NFA記述行列生成手� ��122に通知する。

 次に、図7を参照して、1-char NFA記述行列� ��成手段122の動作について説明する。1-char NF A記述行列生成手段122は、非特許文献3に開示� ��れる手法に基づいて、1-char NFA記憶部142に� �憶した1-char NFAから1-char NFA記述行列を生成� ��る。1-char NFA記述行列生成手段122は、生成� �た1-char NFA記述行列を、1-char NFA記述行列記� ��部143に記憶する。

 図7は、1-char NFA記述行列の一例を示す図� ��ある。1-char NFA記述行列生成手段122は、正� �表現"BCD((A{100}|E)S)*TB{50}U"から生成された1-char  NFA(図2に示す1-char NFA。)に対して、非特許� �献3にて開示される1-char NFA記述行列生成手� �を適用することで、1-char NFA記述行列(図7に� ��す1-char NFA記述行列。)を生成することがで� ��る。

 図7に示す1-char NFA記述行列は、157×157の正� �行列である。図7に示す1-char NFA記述行列に� �いて、遷移条件である値を記載していない� �素の値は0であり、これは状態遷移が存在し� ��いことを表す。ここで、n個の状態を持つ1-c har NFAについて、そのNFAに対応するNFA記述行� ��をS={s _ij } (i=0,1,…,N-1, j=0,1,…,N-1)として示す。NFA記� �行列Sにおいて、その行i(i=0,1,…,N-1)、又は、 列j(j=0,1,…,N-1)は、NFAのn個の状態の1つにそれ ぞれ対応付けられている。また、NFA記述行列 Sの各要素s _ij は、行iに対応付けられた状態から列jに対応� ��けられた状態への遷移条件となる文字、又� ��、文字列の集合を表している。例えば、図7 に示す1-char NFA記述行列において、その3行103 列目の要素は'E'であり、これは、遷移条件'E' に従って、状態3から状態103へと遷移するこ� �を表している。また、0行0列目の'I'は、非特 許文献3において規定される特別な遷移条件� �示しており、初期状態から初期状態への状� �遷移を示すものである。さらに、156行156列� �の'F'は、非特許文献3において規定される特� ��な遷移条件を示しており、終了状態から終� ��状態への状態遷移を示すものである。

 ここで、図7に示す1-char NFA記述行列にお� ��ては、網掛けを用いて示す領域内の要素は� ��値を記載していない要素を除いて、その要� ��の値を0としている。指定された正規表現が 異なる場合には、その正規表現に対応する1-c har NFA記述行列において網掛けを用いて示す� ��域内の要素は、その要素の値は0以外の値と なる可能性がある。これに対して、図7に1-cha r NFA記述行列においては、網掛けを用いて示 していない領域内の要素は、その要素の値が 0でない要素以外は、値が常に0である。即ち� ��図7に示す1-char NFA記述行列においては、網� ��けを用いて示していない領域内の要素は、� ��当する状態遷移が存在しない。

 例えば、図7に示す1-char NFA記述行列にお� ��て、その第4行~第102行の各要素は、状態4~102 から他の状態に遷移する遷移条件を表す。こ の状態4~102は、図2に示すように、繰り返し正 規表現"A{100}"を構成する状態である。また、� ��述したステップA3において、1-char NFA生成手 段121は、繰り返し正規表現に対応する部分の 状態遷移については、状態番号が昇順の連番 となるように状態番号を割り当てていること から、状態X(4≦X≦102)の遷移先は状態X+1だけ� ��ある。従って、図7に示す1-char NFA記述行列� ��おいて、その第4行~第102行の要素のうち、� �り返し文字'A'が設定されている要素以外の� �素は、常にその値は0である。

 同様に、列について着目すると、図7に示 す1-char NFA記述行列において、その第4列~第10 2列の各要素は、状態4~102へ遷移する遷移条件 を表す。この状態4~102は、図2に示すように、 繰り返し正規表現"A{100}"を構成する状態であ� ��。また、上述したステップA3において、1-cha r NFA生成手段121は、繰り返し正規表現に対応 する部分の状態遷移については、状態番号が 昇順の連番となるように状態番号を割り当て ていることから、状態X(4≦X≦102)への遷移元� ��状態X-1だけである。従って、図7に示す1-char  NFA記述行列において、その第4列~第102列の� �素のうち、繰り返し文字'A'が設定されてい� �要素以外の要素は、常にその値は0である。

 さらに、繰り返し正規表現"B{50}"に対応す る、第106行~第154行と、第106列~第154列と、に� ��しても同様にして、繰り返し文字'B'が設定� ��れている要素以外の要素は、常にその値は0 である。

 このように、1-char NFA生成手段121が、繰� �返し正規表現に対応する部分の状態遷移に� �いては状態番号が昇順の連番となるように� �態番号を割り当てておくことで、1-char NFA記 述行列生成手段122は、繰り返し正規表現に対 応する1-char NFA記述行列の領域(図7において� �掛けを用いて示していない領域。)において� ��繰り返し正規表現の繰り返し文字を、第X行 、第(X+1)列に、遷移条件を示す値として設定� ��ることができる。また、1-char NFA記述行列� �成手段122は、それ以外の要素については、� �てその値が0である1-char NFA記述行列を生成� �ることができる。

 1-char NFA記述行列生成手段122は、生成し� �1-char NFA記述行列を、1-char NFA記述行列記憶� ��143に記憶する。以上説明したようにして、1 -char NFA記述行列生成手段122は、1-char NFA記述 行列を生成する処理を終了する。

 また、生成した1-char NFA記述行列を1-char  NFA記述行列記憶部143に記憶する際に、1-char N FA生成手段121から全ての正規表現を変換した� ��とを示す信号を受信している場合には、1-ch ar NFA記述行列生成手段122は、全ての1-char NFA 記述行列の生成処理が完了したことを示す信 号を、multi-char NFA記述行列生成手段123に通知 する。

 次に、図8~図22を参照して、multi-char NFA記 述行列生成手段123の動作について説明する。 multi-char NFA記述行列生成手段123は、multi-char  NFA記述行列生成処理を開始する前に、予め入 力装置11から動作文字数を読み込む。動作文� ��数は、生成するmulti-char NFAの遷移条件とな� ��文字(列)の長さであり、指定する任意の2以� ��の値である。以下の説明においては動作文� ��数をMを使用して表す。以下、具体的な数値 を用いて例を説明する場合には、動作文字数 Mを4として説明する。

 図8は、multi-char NFA記述行列生成手段123が 行う処理を示すフローチャートである。まず 、図8を参照して、multi-char NFA記述行列生成� �段123を用いた処理の概要について説明する� �

 まず、multi-char NFA記述行列生成手段123は� ��繰り返し正規表現リスト記憶部141に記憶し� ��繰り返し正規表現リストから、行列変換情� ��リストを作成する(ステップB1)。繰り返し正 規表現リストは、正規表現に含まれる繰り返 し正規表現と、その繰り返し正規表現に対応 する1-char NFAの状態番号との対応関係を保持� ��るリストである。multi-char NFA記述行列生成� ��段123は、作成した行列変換情報リストをNFA� ��述行列演算情報記憶部144に記憶する。

 次いで、multi-char NFA記述行列生成手段123� ��、NFA記述行列演算情報記憶部144に記憶した� ��列変換情報リストを参照して、1-char NFA記� �行列記憶部143に記憶したオリジナル版1-char  NFA記述行列D(図7に示す1-char NFA記述行列。)を 、縮小版1-char NFA記述行列D'(図12に示す1-char  NFA記述行列。)へと変換する。これにより、mu lti-char NFA記述行列生成手段123は、縮小版1-cha r NFA記述行列D'を生成する(ステップB2)。multi- char NFA記述行列生成手段123は、生成した縮小 版1-char NFA記述行列D'をNFA記述行列演算情報� �憶部144に記憶する。具体的には、multi-char NF A記述行列生成手段123は、オリジナル版1-char  NFA記述行列Dから縮小版1-char NFA記述行列D'へ� ��変換において、オリジナル版1-char NFA記述� �列Dのうち繰り返し正規表現に対応する状態� ��移に関する要素を、動作文字数M分の行また は列に置き換える。より具体的には、multi-cha r NFA記述行列生成手段123は、オリジナル版1-c har NFA記述行列Dの第4行~第102行(100-1=99行分)と 第4列~第102列(100-1=99列分)とにかけての要素(� �ち、繰り返し正規表現"A{100}"に対応する要素 。)を、動作文字数M分の行、又は、列に置き� ��える。また、multi-char NFA記述行列生成手段1 23は、オリジナル版1-char NFA記述行列Dの第106� ��~第154行(50-1=49行分)と第106列~第154列(50-1=49列 分)とにかけての要素(即ち、繰り返し正規表� ��"B{50}"に対応する要素。)を、動作文字数M分� ��行、又は、列に置き換える。

 次いで、multi-char NFA記述行列生成手段123は� ��NFA記述行列演算情報記憶部144に記憶した縮� ��版1-char NFA記述行列D'を用いて、動作文字数 がMの縮小版multi-char NFA記述行列D' ⁴ (図13に示すmulti-char NFA記述行列。)を生成す� �(ステップB3)。multi-char NFA記述行列生成手段1 23は、生成した縮小版multi-char NFA記述行列D' ⁴ をNFA記述行列演算情報記憶部144に記憶する。

 次いで、multi-char NFA記述行列生成手段123は� ��NFA記述行列演算情報記憶部144に記憶した行� ��変換情報リストを参照して、NFA記述行列演� ��情報記憶部144に記憶した縮小版multi-char NFA� ��述行列D' ⁴ から、オリジナル版multi-char NFA記述行列D ⁴ (図14に示すオリジナル版multi-char NFA記述行列 。)を生成する(ステップB4)。具体的には、mult i-char NFA記述行列生成手段123は、縮小版multi-c har NFA記述行列D' ⁴ からオリジナル版multi-char NFA記述行列D ⁴ への変換において、繰り返し正規表現に対応 する状態遷移に関する動作文字数M分の行、� �は、列を、元のサイズに戻す作業を行う。

 次いで、multi-char NFA記述行列生成手段123は� ��生成したオリジナル版multi-char NFA記述行列D ⁴ を出力する(ステップB5)。即ち、multi-char NFA� �述行列生成手段123は、生成したオリジナル� �multi-char NFA記述行列D ⁴ を、multi-char NFA記述行列記憶部145に記憶する 。

 非特許文献3に開示される手法では、図7に� �すオリジナル版1-char NFA記述行列Dを動作文� �数M回分掛け合わせることで、図14に示すオ� �ジナル版multi-char NFA記述行列D ⁴ を求める構成としている。しかし、この手法 では、157×157回の正方行列の演算が必要とな� ��。これに対して、本発明に係るmulti-char NFA� ��述行列生成手段123を用いた処理フローでは� ��multi-char NFA記述行列生成手段123は、まず、� ��述したステップB2において、157×157の正方行 列であるオリジナル版1-char NFA記述行列Dを、 16×16の正方行列である縮小版1-char NFA記述行� ��D'に変換する。multi-char NFA記述行列生成手� �123は、ステップB3において、16×16の正方行列 である縮小版1-char NFA記述行列D'を動作文字� �M回分掛け合わせることで、16×16の正方行列� ��ある縮小版multi-char NFA記述行列D' ⁴ を生成する。multi-char NFA記述行列生成手段123 は、ステップB4において、16×16の正方行列で� ��る縮小版multi-char NFA記述行列D' ⁴ から、157×157の正方行列であるオリジナル版m ulti-char NFA記述行列D ⁴ を生成する。即ち、multi-char NFA記述行列生成 手段123は、ステップB2において、行列サイズ� ��小さなNFA記述行列を生成し、これを用いて� ��算を行うことを特徴とする。ここで、N×Nの 正方行列の演算量はO(N ³ )であるため、非特許文献3に開示される手法� ��用いた場合の演算量はO(157 ³ )=O(3869893)となる。これに対して、本発明によ る演算量はO(16 ³ )=O(4096)となり、演算量を約1000分の1に削減す� ��ことができる。

 尚、上述したステップB1において生成す� �行列変換情報リストは、ステップB2とステッ プB4とにおいて、縮小版NFA記述行列とオリジ� ��ル版NFA記述行列との相互変換を行うために� ��要な情報を保持するものである。このため� ��multi-char NFA記述行列生成手段123は、縮小版N FA記述行列とオリジナル版NFA記述行列の相互� ��換処理を行う前に、ステップB1において行� �変換情報リストを予め生成する。

 以下、図8に示す上述したステップB1~B5に� ��いて、詳細に説明する。まず、図9~図11を参 照して、ステップB1について説明する。

 ステップB1において、multi-char NFA記述行� �生成手段123は、繰り返し正規表現リスト記� �部141に記憶した繰り返し正規表現リストか� �、行列変換情報リストを作成する(ステップB 1)。繰り返し正規表現リストは、正規表現に� ��まれる繰り返し正規表現と、その繰り返し� ��規表現に対応する1-char NFAの状態番号との� �応関係を保持するリストである。

 図9は、行列変換情報リストの構成を示す図 である。図に示すように、行列変換情報リス トの各要素は、その要素のインデックス番号 iと、繰り返し正規表現の繰り返し文字T _i と、繰り返し正規表現の繰り返し回数C _i と、オリジナル版のNFA記述行列における繰り 返し正規表現の開始状態番号S _i と、オリジナル版のNFA記述行列における繰り 返し正規表現の終了状態番号E _i と、縮小版のNFA記述行列における繰り返し正 規表現の開始状態番号S' _i と、縮小版のNFA記述行列における繰り返し正 規表現の終了状態番号E' _i と、の各フィールドを含む。尚、インデック ス番号iは、multi-char NFA記述行列生成手段123� �行う動作の説明を容易とするために用意し� �フィールドであり、本発明を実施する上で� �須のフィールドではない。

 図10は、ステップB1において、multi-char NFA 記述行列生成手段123が行列変換情報リストを 生成する処理を示すフローチャートである。 まず、ステップC1からC4(図において、ループ1 として示す。)において、multi-char NFA記述行� �生成手段123は、繰り返し正規表現リストの� �エントリを行列変換情報リストにコピーす� �。

 具体的には、multi-char NFA記述行列生成手� ��123は、ステップC1においてループ1の処理を� ��始する。multi-char NFA記述行列生成手段123は� ��繰り返し正規表現リストの各エントリにつ� ��て、そのエントリの繰り返し正規表現の繰� ��返し回数が、M+1よりも大きいか否かを確認� ��る(ステップC2)。そのエントリの繰り返し正 規表現の繰り返し回数がM+1よりも大きい場合 には、multi-char NFA記述行列生成手段123は、行 列変換情報リストにそのエントリをコピーす る(ステップC3)。multi-char NFA記述行列生成手� �123が繰り返し正規表現リストのエントリを� �列変換情報リストにコピーする際には、multi -char NFA記述行列生成手段123は、繰り返し正� �表現リストの繰り返し文字と、繰り返し回� �と、開始状態番号と、を、行列変換情報リ� �トの繰り返し文字と、繰り返し回数と、オ� �ジナル版記述行列の開始状態番号とに、そ� �ぞれコピーする。

 一方、繰り返し回数がM+1以下の場合には� ��multi-char NFA記述行列生成手段123は、そのエ� ��トリを正規表現リストから行列変換情報リ� ��トへとコピーしない。これは、繰り返し回� ��がM+1以下の場合には、ステップB2において� �multi-char NFA記述行列生成手段123が縮小版NFA� �述行列を作成することにしても、オリジナ� �版NFA記述行列と比較して行列サイズの削減� �つながらないためである。従って、multi-char� �NFA記述行列生成手段123が行列変換情報リス� �を作成する段階であるステップC1~C4において は、繰り返し回数がM+1以下である繰り返し正 規表現についてはその処理対象から除外する 。これにより、行列変換情報リストに含まれ る各エントリの繰り返し回数は、M+1よりも大 きいことが保証される。

 例えば、動作文字数MがM=4である場合に、 正規表現"BCD((A{100}|E)S)*TTB{50}U"に対応する繰り 返し正規表現リスト(繰り返し正規表現リス� �を図3に示す。)においては、繰り返し回数が M+1(=5)以下の繰り返し正規表現は含まれてい� �い。このため、multi-char NFA記述行列生成手� �123は、図3に示す繰り返し正規表現の全エン� ��リを、行列変換情報リストにコピーする。

 multi-char NFA記述行列生成手段123は、ステ� ��プC4においてループ1の処理を完了する。図1 1は、ループ1の処理が完了した時点での、行� ��変換情報リストを示す図である。

 次いで、multi-char NFA記述行列生成手段123� ��、行列変換情報リストのエントリを、オリ� ��ナル版記述行列の開始状態番号の昇順に従� ��て並び替える(ステップC5)。尚、図11に示す� ��列変換情報リストでは、オリジナル版記述� ��列の開始状態番号の昇順に従って行列変換� ��報リストのエントリが格納されている。こ� ��ため、ステップC5における並び替え処理の� �行後においても、図11に示す行列変換情報リ ストのエントリの順序に変化はなく、図11に� ��すままである。

 次いで、multi-char NFA記述行列生成手段123は� ��縮小版1-char NFA記述行列D'の行列サイズN'を� ��算する(ステップC6)。ステップB2におけるオ� ��ジナル版1-char NFA記述行列Dから縮小版1-char� �NFA記述行列D'への変換では、multi-char NFA記述 行列生成手段123は、図7に示すオリジナル版1- char NFA記述行列Dのうち、その繰り返し正規� �現に対応する状態遷移に関する行と列(具体� ��には、第S _i +1行~第E _i -1行を示す。)を、M行分に縮小する。ここで� �S _i は行列変換情報リストの各エントリのオリジ ナル版NFA記述行列の開始状態番号を示す。E _i は、行列変換情報リストの各エントリのオリ ジナル版NFA記述行列の終了状態番号を示す。 また、Mは動作文字数を示す。これにより、mu lti-char NFA記述行列生成手段123は、行列変換� �報リストの各エントリについて、オリジナ� �版1-char NFA記述行列Dの(E _i -1)-(S _i +1)-1=E _i -S _i -1=C _i -1行分を、縮小版1-char NFA記述行列D'のM行分� �変換する。ここで、行列変換情報リストの� �エントリの繰り返し回数C _i について、繰り返し回数C _i =E _i -S _i の関係が成立する。また、multi-char NFA記述行 列生成手段123は、列についても同様に、第S _i +1列~第E _i -1列を、M列分に縮小する。従って、オリジナ ル版1-char NFA記述行列Dの行列サイズをNとす� �と、縮小版1-char NFA記述行列D'の行列サイズN 'を下記の数(1)を使用して示すことができる� �尚、Kは、正規表現に含まれる繰り返し正規� ��現の個数を示す。

 次に、ステップC7からC13(図において、ル� ��プ2として示す。)において、multi-char NFA記� �行列生成手段123は、行列変換情報リストの� �エントリについて、エントリ中の空欄であ� �内容を計算する。ここで、空欄の内容とは� �図11においては空白の部分である。具体的に は、空欄の内容は、オリジナル版NFA記述行列 の終了状態番号と、縮小版NFA記述行列の開始 状態番号と、終了状態番号と、を示す。

 上述したステップC6の説明において述べた� �うに、ステップB2におけるオリジナル版1-char  NFA記述行列Dから縮小版1-char NFA記述行列D'� �の変換では、multi-char NFA記述行列生成手段12 3は、オリジナル版1-char NFA記述行列Dのうち� �その繰り返し正規表現に対応する状態遷移� �関する行と列(具体的には、第S _i +1行~第E _i -1行を示す。)を、M行分に縮小する。ここで� �S _i は行列変換情報リストの各エントリのオリジ ナル版NFA記述行列の開始状態番号を示す。E _i は、行列変換情報リストの各エントリのオリ ジナル版NFA記述行列の終了状態番号を示す。 また、Mは動作文字数を示す。

 以下、図7に示すオリジナル版1-char NFA記� ��行列Dと、図12に示す縮小版1-char NFA記述行� �D'とを用いて具体的に説明する。multi-char NFA 記述行列生成手段123は、指定された正規表現 "BCD((A{100}|E)S)*TTB{50}U"の繰り返し正規表現"A{100 }"に対応するオリジナル版1-char NFA記述行列D� ��第4行~第102行を、縮小版1-char NFA記述行列D'� ��第4行~第7行に変換する。また、multi-char NFA� ��述行列生成手段123は、指定された正規表現" BCD((A{100}|E)S)*TTB{50}U"の繰り返し正規表現"B{50}" に対応するオリジナル版1-char NFA記述行列Dの 第106行~第154行を、縮小版1-char NFA記述行列D'� ��第11行~第14行に変換する。また、multi-char NF A記述行列生成手段123は、列についても同様� �変換する。

 ループ2を示すステップC7~C13においては、 multi-char NFA記述行列生成手段123は、繰り返し 正規表現に対応する部分のオリジナル版1-char  NFA記述行列Dと縮小版1-char NFA記述行列D'と� �おける対応関係を求め、その対応関係を行� �変換情報リストに保持する。multi-char NFA記� �行列生成手段123は、続くステップC8~C12にお� �て、行列変換情報リストの各エントリにつ� �ての処理を行う。

 具体的には、multi-char NFA記述行列生成手段1 23は、ステップC7においてループ2の処理を開� ��して、i番目のエントリの処理を開始する(� �テップC8)。multi-char NFA記述行列生成手段123� �、オリジナル版NFA記述行列Dの終了状態番号E _i を計算する(ステップC9)。ここで、multi-char NF A記述行列生成手段123は、E _i =S _i +C _i の関係が成立することを利用して、この関係 に基づいてE _i を計算する。

 multi-char NFA記述行列生成手段123は、縮小版� ��述行列D'の開始状態番号S' _i を計算する(ステップC10)。multi-char NFA記述行� ��生成手段123は、オリジナル版1-char NFA記述� �列Dから縮小版1-char NFA記述行列D'への変換に おいて、繰り返し正規表現に関連しない状態 遷移を保持する。例えば、multi-char NFA記述行 列生成手段123は、図7に示すオリジナル版1-cha r NFA記述行列Dの第103行~第105行を、図12に示� �縮小版1-char NFA記述行列D'の第8行~第10行にコ ピーする。繰り返し正規表現に関連しない部 分の行数・列数は、オリジナル版1-char NFA記� ��行列Dと縮小版1-char NFA記述行列D'とで同じ� �ある。このため、S' _i =E' _i-1 +(S _i -E _i-1 )の関係式が成立する。multi-char NFA記述行列� �成手段123は、この関係式に基づいて、S' _i を計算する。尚、行列変換情報リストの最初 のエントリ(インデックスi=0)の計算を行う際� ��は、multi-char NFA記述行列生成手段123は、E ₀ =0、E' ₀ =0と仮定して計算を行う。

 multi-char NFA記述行列生成手段123は、縮小版� ��述行列D'の終了状態番号E' _i を計算する(ステップC11)。縮小版1-char NFA記� �行列D'では、繰り返し正規表現に対応する状 態遷移の開始状態番号と終了状態番号との間 に、動作文字数M個だけの差がある。このた� �、E' _i =S' _i +Mの関係が成立する。multi-char NFA記述行列生� ��手段123は、この関係に基づいてE' _i を計算する。

 multi-char NFA記述行列生成手段123は、ステ� ��プC12においてi番目のエントリの処理を完了 した後、ステップC13においてループ2の処理� �完了する。以上により、multi-char NFA記述行� �生成手段123は、ステップB1における行列変換 情報の生成処理を完了する。

 次に、図15~図17を参照して、ステップB2につ いて説明する。まず、ステップB2の説明に先� ��ち、ステップB2以降の説明において用いる� �号について以下のように定義する(尚、既に� ��述したようにして定義した符号も含む)。角 括弧内の値は、本実施の形態1における動作� �明で使用する具体例を示す値である。
 M:動作文字数(M≧2)[M=4]
 K:行列変換情報リストのエントリ数(K≧0)[K=2 ]
 N:オリジナル版NFA記述行列の行列サイズ(Nは 自然数)[N=157]
 N':縮小版NFA記述行列の行列サイズ(N'は自然� ��、N'≦N)[N'=17]
 尚、以下では、「NFA記述行列」として記載� ��た場合には、「1-char NFA記述行列」と「multi -char NFA記述行列」とのいずれをも示すもの� �する。従って、Nは1-char NFA記述行列の行列� �イズを示す。N'はmulti-char NFA記述行列の行列 サイズを示す。S _i と、E _i と、S' _i と、E' _i と、C _i と、は、行列変換情報リストにおける各エン トリの要素(1≦i≦K、但しK≧1である。)を示� �。K=0の場合には、行列変換情報リストは空� �ある。E ₀ =E' ₀ =0、S _K+1 =N-1、S' _K+1 =N'-1であるものと定義する。

 また、以下に説明するステップB2~B4におい� �は、オリジナル版NFA記述行列を、図15に示す ような(2K+1)×(2K+1)個の領域に分割して考える� ��のとする。領域の境界をS _i とE _i とに基づいて定める(1≦i≦K)。即ち、S _i 番目(1≦i≦K)の行と列とを用いて、領域の境� ��を定める。また、E _i 番目(1≦i≦K)の行と列とを用いて、領域の境� ��を定める。S _i とE _i 自身は、それぞれ奇数番目の領域側に含まれ る。具体的には、S _i とE _i 自身を、図15に示す太線を用いて示す。図15� �示すオリジナル版NFA記述行列において、上� �らx番目、かつ、左からy番目に位置する領域 を、領域(x,y)と称する。xとyの値は、いずれ� �1から開始する。例えば、上から1番目、かつ 、左から1番目に位置する領域を、領域(1,1)と して示す。図7に示すオリジナル版1-char NFA記 述行列Dを領域分割した例を、図15に示す。図 15に示すように、multi-char NFA記述行列生成手� ��123は、オリジナル版1-char NFA記述行列Dを5×5 個の領域に分割する。同様に、縮小版NFA記述 行列についても、(2K+1)×(2K+1)個の領域に分割� ��て考えるものとする。図16にその具体例を� �す。図16では、S _i とE _i とに代えて、S' _i とE' _i とを用いて領域の境界を決定する。

 次に、ステップB2における縮小版1-char NFA 記述行列D'の生成処理について説明する。図1 7は、multi-char NFA記述行列生成手段123が縮小� �1-char NFA記述行列D'を生成する処理を示すフ� ��ーチャートである。最初に、multi-char NFA記� ��行列生成手段123は、縮小版1-char NFA記述行� �D'を保持するためのN'×N'行列をNFA記述行列演 算情報記憶部144に用意する(ステップD1)。こ� �とき、multi-char NFA記述行列生成手段123は、� �意したN'×N'行列の全要素を0として初期化す� ��。尚、縮小版1-char NFA記述行列D'の行列サイ ズN'は、上述したステップB1内のステップC6に おいて算出済みである。

 次に、ステップD2~D6のループ1において、m ulti-char NFA記述行列生成手段123は、オリジナ� ��版1-char NFA記述行列Dの領域のうち、上から� ��奇数番目であり、かつ、左からも奇数番目� ��ある領域(2i-1,2j-1)(i,jは整数であり、1≦i≦K+ 1,1≦j≦K+1を満たす。)を、縮小版1-char NFA記� �行列D'の同じ位置の領域(2i-1,2j-1)にコピーす� ��。即ち、multi-char NFA記述行列生成手段123は� ��図15において網掛けを用いて示す領域を、� �16において網掛けを用いて示す領域にコピー する。この網掛けを用いて示す領域は、繰り 返し正規表現に関係のない領域を示す。図7� �示す1-char NFA記述行列Dでは、網掛けを用い� �示す領域内の要素は、その値が0である要素� ��示す。図15において網掛けを用いて示す領� �内の要素は、入力された正規表現が異なる� �合には、0以外の値となる可能性がある。こ� ��ため、縮小版1-char NFA記述行列D'においても 、網掛けを用いて示す領域の行列要素につい ては、値をそのまま利用するものとする。尚 、図17に示すステップD3~D5は、各領域(2i-1,2j-1) に関する上述した処理を一般的に示したもの である。即ち、ステップD3~D5において、multi-c har NFA記述行列生成手段123は、各領域(2i-1,2j-1 )についての処理を行う。

 次に、ステップD7~D13において、multi-char N FA記述行列生成手段123は、生成する縮小版1-ch ar NFA記述行列D'の残りの領域(図16において網 掛けを用いて示していない領域)について、� �から偶数番目、又は、左から偶数番目であ� �領域についての処理を行う。

 ここで、図16において網掛けを用いて示� �ていない領域は、図15に示すオリジナル版1-c har NFA記述行列Dにおいて、繰り返し正規表現 に対応する領域である。このため、繰り返し 正規表現の繰り返し回数の増加に応じて、図 16において網掛けを用いて示していない領域� ��行と列の数は、その繰り返し回数に比例し� ��多くなる。この網掛けを用いて示していな� ��領域は、繰り返し正規表現に対応する領域� ��あり、上述したステップA3において、1-char  NFA生成手段121が、繰り返し正規表現に対応す る部分の状態遷移に関して、状態番号が昇順 の連番となるように状態番号を割り当ててい る。このため、この網掛けを用いて示してい ない領域に存在する可能性のある状態遷移は 、状態Xから状態X+1への状態遷移だけである� �

 従って、行列変換情報リストのi番目のエン トリに対応する繰り返し正規表現について、 multi-char NFA記述行列生成手段123は、図15に示� ��オリジナル版1-char NFA記述行列Dにおいて、� ��り返し文字A _i の配置を領域(2i-1,2i)の左下の位置から開始し て、これに続けて領域(2i,2i)を右斜め下方向� �横切るように連続して位置し、さらに続け� �領域(2i,2i+1)の左下にかけて位置するように� �成する。従って、領域(2i-1,2i)の左下の位置� �ら領域(2i,2i+1)の左下にかけて、繰り返し文� �A _i がC _i 個並ぶ構成となる。網掛けを用いて示してい ない領域において、その行列要素は繰り返し 文字だけとなり、繰り返し正規表現に該当し ない要素は全て0となる(図7参照)。

 同様にして、行列変換情報リストのi番目の エントリに対応する繰り返し正規表現につい て、multi-char NFA記述行列生成手段123は、生成 する縮小版1-char NFA記述行列に関しても、図1 6に示すように、繰り返し文字A _i の配置を領域(2i-1,2i)の左下の位置から開始し て、これに続けて領域(2i,2i)を右斜め下方向� �横切るように連続して位置し、さらに続け� �領域(2i,2i+1)の左下にかけて位置するように� �行列の要素を設定する。

 ただし、図16に示す、生成する縮小版1-char  NFA記述行列においては、上から偶数番目、又 は、左から偶数番目の領域は、行、又は、列 の幅が、動作文字数Mとなるように用意して� �る。このため、繰り返し文字A _i が斜めに並ぶ個数は、M+1個となる。図7に示� �オリジナル版1-char NFA記述行列を参照して具 体例を説明すると、行列変換情報リストの一 つめのエントリは、繰り返し正規表現"A{100}"� ��関するものであり、繰り返し文字A ₁ ='A'、縮小版NFA記述行列における開始状態番� �S' ₁ =3、終了状態番号E' ₁ =8である。このため、縮小版1-char NFA記述行� �の要素(3行,4列)から要素(7行,8列)にかけて、� ��り返し文字'A'がM+1(=5)個並ぶ。また同様に、 行列変換情報リストの二番目のエントリは、 繰り返し正規表現"B{50}"に関するものであり� �縮小版1-char NFA記述行列の要素(10行,11列)か� �要素(14行,15列)にかけて、繰り返し文字'B'がM +1(=5)個並ぶ。尚、図17に示すステップD8~D12は� ��行列変換情報リストのi番目のエントリにつ いて、そのエントリに対応する繰り返し正規 表現に関する領域内に繰り返し文字を設定す る処理を一般的に示したものである。即ち、 ステップD8~D12において、multi-char NFA記述行列 生成手段123は、i番目のエントリに関する範� �についての処理を行う。

 以上説明したように、multi-char NFA記述行� ��生成手段123は、ステップB2における、縮小� �1-char NFA記述行列D'の生成処理を終了する。m ulti-char NFA記述行列生成手段123は、図7に示す オリジナル版1-char NFA記述行列に対して、ス� ��ップB2の処理を行う。図12は、multi-char NFA記 述行列生成手段123が生成する、縮小版1-char N FA記述行列である。尚、図12に示す縮小版1-cha r NFA記述行列においては、行列要素を記載し ていない要素の値は0であり、対応する状態� �移がないことを示す。また、行列要素が記� �されている場合には、要素として記載され� �いる文字(群)が状態遷移の遷移条件であるこ とを示す。例えば、図12に示す縮小版1-char NF A記述行列において、(3行,8列)の要素は'E'であ り、これは、状態3から状態8に文字'E'に基づ� ��て状態遷移があることを示す。

 次に、ステップB3について説明する。ステ� �プB3において、multi-char NFA記述行列生成手段 123は、縮小版multi-char NFA記述行列D' ⁴ を生成する。上述したステップB3において、m ulti-char NFA記述行列生成手段123は、非特許文� ��3にて開示されている手法に基づいて、縮小 版1-char NFA記述行列D'をM回掛け合わせること� ��より、縮小版multi-char NFA記述行列D' ^M を計算する。ここで、D' ⁴ =D'×D'×D'×D'である。尚、NFA記述行列同士の掛 け算時の演算定義については、非特許文献3� �68ページ、3.3章 変換手法と、3.4章 変換例� �に詳述されている。動作文字数M=4の場合に� �ステップB3において、multi-char NFA記述行列生 成手段123は、図12に示す縮小版1-char NFA記述� �列D'から、図13に示す縮小版multi-char(4-char) NF A記述行列D' ⁴ を生成する。動作文字数Mは4であるため、図1 3に示す縮小版4-char NFA記述行列D' ⁴ は4文字単位のNFAの遷移条件を定義するNFA記� �行列である。また、遷移条件を示す縮小版4- char NFA記述行列D' ⁴ の各要素は、長さ4の文字列となる。尚、図13 において、具体的な要素の値が記載されてい ない要素の値は0であり、遷移条件が存在し� �いことを示す。

 次に、図18~図22を参照して、ステップB4につ いて説明する。図18は、ステップB4において� �multi-char NFA記述行列生成手段123が、オリジ� �ル版multi-char NFA記述行列D ⁴ を生成する処理を示すフローチャートである 。図18に示すフローチャートは、以下に示す5 つの処理(1)~(5)を含む。
(1)上から奇数番目であり、かつ、左から奇数 番目の領域に対する処理(ステップE2~E4におけ る処理を示す。)。
(2)上から奇数番目であり、かつ、左から偶数 番目の領域に対する処理(ステップE5~E7におけ る処理を示す。)。
(3)上から偶数番目であり、かつ、左から奇数 番目の領域に対する処理(ステップE8~E10にお� �る処理を示す。)。
(4)上から偶数番目であり、かつ、左から偶数 番目の領域に対する処理(ステップE11~E13にお� ��る処理を示す。)。
(5)繰り返し正規表現に関する補正(ステップE1 4~E18における処理を示す。)。
 尚、NFA記述行列の領域の考え方は、図15と� �16に示す通りである。また、上記(1)~(5)の処� �は互いに独立であり、図18に示すフローチャ ートにおいては(1)から(5)の順番に従って実行 するものとして説明しているが、実行順序に 制約はなく、その実効順序を変更してもよい 。以下では、図18に示すフローチャートの順� ��に従って説明する。上記(1)から(5)の処理に� ��立ち、multi-char NFA記述行列生成手段123は、N ×N行列D ^M を用意しておく。

 まず、ステップE2~E4における処理を示す(1 )の処理について説明する。(1)の処理は、上� �ら奇数番目であり、かつ、左から奇数番目� �領域に対する処理である。上から奇数番目� �あり、かつ、左から奇数番目である領域は� �遷移元状態と遷移先状態ともに、繰り返し� �規表現に関係のない状態に関する遷移条件� �示している。

 例えば、図13に示す縮小版4-char NFA記述行 列において、領域(1,1)の第1行、第3列目の要� �"CDES"は、図2に示す状態遷移において状態1→ 状態2→状態3→状態103→状態3へと1文字単位� �遷移を4回行った場合に、状態1→状態3へと� �移条件"CDES"に基づいて遷移することを示す� �上から奇数番目であって、かつ、左から奇� �番目である領域内の他の要素についても、� �様に示す。縮小版4-char NFA記述行列の領域内 の各要素と、オリジナル版4-char NFA記述行列� ��同じ位置の領域内の各要素とは一対一に対� ��している。このため、multi-char NFA記述行列� ��成手段123は、上から奇数番目であって、左� ��ら奇数番目である領域については、縮小版4 -char NFA記述行列の各領域を、オリジナル版4- char NFA記述行列の同じ位置の領域にコピーす る(ステップE3)。

 尚、図18に示すステップE2~E4は、上述した 処理を一般的に示したものである。即ち、ス テップE2~E4において、multi-char NFA記述行列生� ��手段123は、各領域についての処理を行う。� ��テップE3における領域毎の処理では、multi-ch ar NFA記述行列生成手段123は、ステップB1にお いて計算した行列変換情報リストを参照する ことで、コピー先の座標を一意に特定するこ とができる。図19は、ステップE4までの処理� �終えた時点での、オリジナル版4-char NFA記述 行列を示す図である。網掛けを用いて示す部 分は、ステップE2~E4の処理において、multi-char  NFA記述行列生成手段123が、縮小版4-char NFA� �述行列からコピーした要素である。

 次いで、ステップE5~E7における(2)の処理� �ついて説明する。(2)の処理は、上から奇数� �目であり、かつ、左から偶数番目の領域に� �する処理である。上から奇数番目であり、� �つ、左から偶数番目である領域は、遷移元� �態が繰り返し正規表現に関係のない状態で� �って、遷移先状態が繰り返し正規表現に関� �する状態に関する遷移条件を示している。

 例えば、図13に示す縮小版4-char NFA記述行 列において、領域(1,2)の第1行、第5列目の要� �"CDAA"は、図2に示す状態遷移において状態1→ 状態2→状態3→状態4→状態5へと1文字単位の� ��移を4回行った場合に、状態1→状態5へ遷移� ��件"CDAA"に基づいて遷移することを示す。上� ��ら奇数番目であって、かつ、左から偶数番� ��である領域内の他の要素についても、同様� ��示す。ここで、繰り返し正規表現に関係し� ��い状態から繰り返し正規表現に関係する状� ��へとM文字単位の状態遷移を行う場合には、 遷移先状態となり得るのは繰り返し正規表現 の先頭からM番目の状態だけであることに着� �する。これにより、multi-char NFA記述行列生� �手段123は、縮小版multi-char NFA記述行列にお� �て、上から奇数番目であって、かつ、左か� �偶数番目である領域を、オリジナル版multi-ch ar NFA記述行列の同じ位置の領域のうち左側� �境界に接する範囲にコピーする(ステップE6)� ��

 尚、図18に示すステップE5~E7は、上述した 処理を一般的に示したものである。即ち、ス テップE5~E7において、multi-char NFA記述行列生� ��手段123は、各領域についての処理を行う。� ��テップE6における領域毎の処理では、multi-ch ar NFA記述行列生成手段123は、ステップB1にお いて計算した行列変換情報リストを参照する ことで、コピー先の座標を一意に特定するこ とができる。図20は、ステップE7までの処理� �終えた時点での、オリジナル版4-char NFA記述 行列を示す図である。図20ではM=4の場合を示� ��ているので、multi-char NFA記述行列は4-char NF A記述行列となる。網掛けを用いて示す部分(� ��において、R1を用いて示す部分。)は、上述� ��たステップE2~E4の処理において、multi-char NF A記述行列生成手段123が、縮小版4-char NFA記述 行列からコピーした要素である。濃い網掛け を用いて示す部分(図において、R2を用いて示 す部分。)は、ステップE5~E7の処理において、 multi-char NFA記述行列生成手段123が、縮小版4-c har NFA記述行列から新たにコピーした要素で� ��る。尚、薄い網掛けを用いて示す部分R1は� �multi-char NFA記述行列生成手段123が、上述し� �ステップE4までの処理においてコピーした要 素を示す。

 次いで、ステップE8~E10における(3)の処理� ��ついて説明する。(3)の処理は、上から偶数� ��目であり、かつ、左から奇数番目の領域に� ��する処理である。上から偶数番目であり、� ��つ、左から奇数番目である領域は、遷移元� ��態が繰り返し正規表現に関係する状態であ� ��て、遷移先状態が繰り返し正規表現に関係� ��ない状態に関する遷移条件を示している。

 例えば、図13に示す縮小版4-char NFA記述行 列において、領域(2,3)の第6行、第9列目の要� �"AAST"は、図2に示す状態遷移において状態101� ��状態102→状態103→状態3→状態104へと1文字� �位の遷移を4回行った場合に、状態101→状態1 04へ遷移条件"AAST"に基づいて遷移することを� ��す。上から偶数番目であって、かつ、左か� ��奇数番目である領域内の他の要素について� ��、同様に示す。ここで、繰り返し正規表現� ��関係する状態から繰り返し正規表現に関係� ��ない状態へとM文字単位の状態遷移を行う場 合には、遷移元状態となり得るのは繰り返し 正規表現の末尾からM番目の状態だけである� �とに着目する。これにより、multi-char NFA記� �行列生成手段123は、縮小版multi-char NFA記述� �列において、上から偶数番目であって、か� �、左から奇数番目である領域を、オリジナ� �版multi-char NFA記述行列の同じ位置の領域の� �ち下側の境界に接する範囲にコピーする(ス� ��ップE9)。

 尚、図18に示すステップE8~E10は、上述し� �処理を一般的に示したものである。即ち、� �テップE8~E10において、multi-char NFA記述行列� �成手段123は、各領域についての処理を行う� �ステップE9における領域毎の処理では、multi- char NFA記述行列生成手段123は、ステップB1に� ��いて計算した行列変換情報リストを参照す� ��ことで、コピー先の座標を一意に特定する� ��とができる。図21は、ステップE10までの処� �を終えた時点での、オリジナル版4-char NFA記 述行列を示す図である。図21においては、濃� ��網掛けを用いて示す部分(図において、R4を� ��いて示す部分。)は、ステップE8~E10の処理に おいて、multi-char NFA記述行列生成手段123が、 縮小版4-char NFA記述行列から新たにコピーし� ��要素である。尚、薄い網掛けを用いて示す� ��分(図において、R3を用いて示す部分。)は、 multi-char NFA記述行列生成手段123が、上述した ステップE7までの処理においてコピーした要� ��を示す。

 次いで、ステップE11~E13における(4)の処理 について説明する。(4)の処理は、上から偶数 番目であり、かつ、左から偶数番目の領域に 対する処理である。上から偶数番目であり、 かつ、左から偶数番目である領域は、遷移元 状態と遷移先状態ともに、繰り返し正規表現 に関係する状態に関する遷移条件を示してい る。

 例えば、図13に示す縮小版4-char NFA記述行 列において、領域(2,2)の第6行、第4列目の要� �"AASA"は、図2に示す状態遷移において状態101� ��状態102→状態103→状態3→状態4へと1文字単� ��の遷移を4回行った場合に、状態101→状態104 へ遷移条件"AAST"に基づいて遷移することを示 す。繰り返し正規表現内の状態101から状態遷 移を開始し、一度、繰り返し正規表現に対応 する状態を抜けて状態103から状態3の遷移を� �った後、再度、繰り返し正規表現に対応す� �状態4に達している。上から偶数番目であっ� ��、かつ、左から奇数番目である領域内の他� ��要素についても、同様に示す。

 図13に示す縮小版4-char NFA記述行列におい ては、上から偶数番目であって、かつ、左か ら偶数番目である領域のうち、0以外の要素� �存在するのは領域(2,2)だけであり、他の3つ� �領域(2,4)、(4,2)、(4,4)については、全ての要� �が0となっている。これは、領域(4,2)、(4,4)に ついては、遷移元状態が繰り返し正規表現"B{ 50}"に対応する状態であり、図2に示す状態遷� ��図において繰り返し正規表現"B{50}"に関する 状態遷移を行った後は、状態156に文字'U'で遷 移する遷移条件しか存在しないため、領域(4, 2)や(4,4)に対応する状態遷移が存在しないた� �である。また、領域(2,4)は、繰り返し正規表 現"A{100}"に関連する状態から繰り返し正規表� ��"B{50}"に関連する状態への状態遷移を表して いるが、繰り返し正規表現"A{100}"に関連する� ��後の状態である状態102から、繰り返し正規� ��現"B{50}"に関連する最初の状態である状態106 へと達するには5文字分の状態遷移が必要で� �る。このため、領域(2,4)に対応する状態遷移 は存在しない。尚、本実施の形態1では、正� �表現の一例として"BCD((A{100}|E)S)*TTB{50}U"を用� �たが、別の正規表現が指定された場合には� �これらの領域(2,4)、(4,2)、(4,4)に対しても、0� ��外の要素が存在する場合がある。

 繰り返し正規表現に関係する状態から繰� ��返し正規表現に関係する状態へとM文字単位 の状態遷移を行う場合には、遷移先状態とな り得るのは繰り返し正規表現の先頭からM番� �の状態だけであり、遷移元状態になり得る� �は繰り返し正規表現の末尾からM番目の状態� ��けであることに着目する。これにより、mult i-char NFA記述行列生成手段123は、縮小版multi-c har NFA記述行列において、上から偶数番目で� ��って、かつ、左から奇数番目である領域を� ��オリジナル版multi-char NFA記述行列の同じ位� ��の領域のうち、左側と下側の境界に接する� ��囲にコピーする(ステップE12)。

 尚、図18に示すステップE11~E13は、上述し� ��処理を一般的に示したものである。即ち、� ��テップE11~E13において、multi-char NFA記述行列 生成手段123は、各領域についての処理を行う 。ステップE12における領域毎の処理では、mul ti-char NFA記述行列生成手段123は、ステップB1� ��おいて計算した行列変換情報リストを参照� ��ることで、コピー先の座標を一意に特定す� ��ことができる。図22は、ステップE13までの� �理を終えた時点での、オリジナル版4-char NFA 記述行列を示す図である。図22においては、� ��い網掛けを用いて示す部分(図において、R6� ��用いて示す部分。)は、ステップE1~E13の処理 において、multi-char NFA記述行列生成手段123が 、縮小版4-char NFA記述行列から新たにコピー� ��た要素である。尚、薄い網掛けを用いて示� ��部分(図において、R5を用いて示す部分。)は 、multi-char NFA記述行列生成手段123が、上述し たステップE10までの処理においてコピーした 要素を示す。

 次いで、ステップE14~E18における(5)の処理 について説明する。(5)の処理は、繰り返し正 規表現に関する補正である。図22に示すよう� ��、ステップE13までの処理を終えた時点での� ��リジナル版multi-char NFA記述行列においては� ��繰り返し正規表現に対応する状態遷移のう� ��、繰り返し正規表現"A{100}"に対応する状態� �は、状態4~98からの状態遷移と、状態8~102へ� �状態遷移と、が規定されていない。また、� �り返し正規表現"B{50}"に対応する状態では、� ��態106~150からの状態遷移と、状態110~154への� �態遷移と、が規定されていない。

 状態4~98からの状態遷移について着目する と、状態4~98は繰り返し正規表現"A{100}"に対応 する状態である。図2を参照すると、1文字単� ��の状態遷移をM(=4)回行った場合には、途中� �経由する状態と、M回の状態遷移を行った結� ��達することができる状態とは、いずれも繰� ��返し正規表現"A{100}"に対応する状態だけで� �る。このため、遷移条件は、繰り返し正規� �現の繰り返し文字M個である。上述したステ� ��プA3において、1-char NFA生成手段121は、繰り 返し正規表現に対応する状態について、状態 番号が昇順の連番となるように状態番号を割 り当てている。このため、状態4~98からの状� �遷移は、遷移条件'A'のM回繰り返し(M=4なので "AAAA")での、状態X(4≦X≦98)から状態X+Mへの状� ��遷移だけとなる。

 同様にして、状態8~102への状態遷移につ� �て着目すると、状態8~102への状態遷移に関し て有効な状態遷移は、遷移条件'A'のM回繰り� �し(M=4なので"AAAA")での、状態X(4≦X≦98)から� �態X+Mへの状態遷移だけである。これは、状� �4~98からの状態遷移と全く同じ状態遷移であ� ��。従って、multi-char NFA記述行列生成手段123� ��、繰り返し正規表現"A{100}"に対応する状態� �移として、遷移条件'A'のM(=4)回繰り返しでの 、状態X(4≦X≦98)から状態X+Mへの状態遷移を� �オリジナル版4-char NFA記述行列に追加する。 また、同様にして、multi-char NFA記述行列生成 手段123は、繰り返し正規表現"B{50}"に対応す� �状態遷移として、遷移条件'B'のM(=4)回繰り返 しでの、状態X(106≦X≦150)から状態X+Mへの状� �遷移を、オリジナル版4-char NFA記述行列に追 加する。

 尚、図18に示すステップE14~E18は、上述した� ��理を一般的に示したものである。即ち、ス� ��ップE14~E18において、multi-char NFA記述行列生 成手段123は、それぞれの繰り返し正規表現に 対応して、遷移条件として繰り返し文字C _i のM回繰り返しでの、状態X(S _i ≦X≦E _i -M)から状態X+Mへの状態遷移を、オリジナル版 4-char NFA記述行列に追加する処理を行う。尚� ��iは、行列変換情報リストのエントリに割り 当てられたインデックス番号を示し、個々の 繰り返し正規表現に対応する。図14は、図18� �示す処理(ステップE1~E18)を全て終了した後の 、完成したオリジナル版4-char NFA記述行列D ⁴ を示す図である。

 次に、ステップB5について説明する。ステ� �プB5において、multi-char NFA記述行列生成手段 123は、上述したステップB4までに生成したオ� ��ジナル版4-char NFA記述行列D ⁴ を、multi-char NFA記述行列記憶部145に記憶する 。

 また、multi-char NFA記述行列生成手段123は� ��生成したオリジナル版multi-char NFA記述行列� ��multi-char NFA記述行列記憶部145に記憶する際� ��、1-char NFA記述行列生成手段122から全ての1- char NFA記述行列の生成処理が完了したことを 示す信号を受信している場合には、全てのmul ti-char NFA記述行列の生成処理が完了したこと を示す信号を、multi-char NFA生成手段124に通知 する。以上説明したようにして、multi-char NFA 記述行列生成手段123は、multi-char NFA記述行列 生成処理を完了する。

 次に、図23を参照して、multi-char NFA生成手� �124の動作について説明する。multi-char NFA生� �手段124は、NFA記述行列の定義に基づいて、M� ��字単位の状態遷移(multi-char NFA)を生成する� �multi-char NFA生成手段124は、非特許文献3に開� ��される手法に基づいて、multi-char NFA記述行� ��記憶部145に記憶したオリジナル版multi-char N FA記述行列から、multi-char NFAを生成する。mult i-char NFA生成手段124は、生成したmulti-char NFA� ��multi-char NFA記憶部146に記憶する。具体的に� ��、まず、multi-char NFA生成手段124は、図14に� �すオリジナル版4-char NFA記述行列D ⁴ の要素の中で、初期状態を示すIと、終了状� �を示すFと、を任意の1文字にマッチすること を示す'*'に変換する。次いで、multi-char NFA生 成手段124は、オリジナル版4-char NFA記述行列� ��り、4-char NFA(M文字単位の状態遷移)を生成� �る。図23は、multi-char NFA生成手段124が生成し た4-char NFAを示す図である。multi-char NFA生成� ��段124は、生成したmulti-char NFAをmulti-char NFA� ��憶部146に記憶して、その処理を終了する。

 また、multi-char NFAをmulti-char NFA記憶部146� ��記憶する際に、multi-char NFA記述行列生成手� ��123から全てのmutli-char NFA記述行列の生成処� ��が完了したことを示す信号を受信している� ��合には、multi-char NFA生成手段124は、全てのm ulti-char NFAの生成処理が完了したことを示す� ��号を、HDL変換手段125に通知する。

 次に、HDL変換手段125の動作について説明� ��る。HDL変換手段125は、multi-char NFA記憶部146� ��記憶したmulti-char NFAについて、そのNFAの状� ��と、状態間の遷移と、遷移条件等の情報を� ��析する。HDL変換手段125は、分析結果に基づ� ��て、各状態をレジスタに、遷移条件を文字( 列)比較器にそれぞれ変換して、状態間の遷� �に応じて各レジスタの間を接続することで� �そのNFA回路を記述するVerilog HDL等のHDL(Hardwar e Description Language)記述に変換する。

 また、HDL変換手段125は、multi-char NFA生成� ��段124から全てのmulti-char NFAの生成処理が完� ��したことを示す信号を受信した場合には、m ulti-char NFAから変換した全てのHDL記述と、正� ��表現からHDLへの変換処理が完了したことを� ��す信号と、を出力装置13に出力する。

 以上説明したように、本実施の形態1によれ ば、繰り返し正規表現を含む正規表現におい て繰り返し正規表現の繰り返し回数が増加し た場合においても、NFAの遷移条件を複数文字 単位に拡張したNFAを生成するためのNFA記述行 列の演算量の増加を抑制することができる。 即ち、本実施の形態1に係る手法は、オリジ� �ル版1-char NFA記述行列において、繰り返し正 規表現に対応する状態遷移に関する行と列の 数を、繰り返し正規表現の繰り返し文字数か ら動作文字数Mにまで削減する。そして、行� �サイズの小さい縮小版1-char NFA記述行列を作 成した上で、縮小版の動作文字数M文字単位� �NFA記述行列を計算する。そして、オリジナ� �版1-char NFA記述行列の状態数に対応するM文� �単位のNFA記述行列を計算することで、M文字� ��位のNFAを得る。オリジナル版のNFA記述行列� ��おいては、行列サイズは、繰り返し正規表� ��の繰り返し回数に比例するものであったの� ��対して、上述したようにして作成した縮小� ��のNFA記述行列においては、繰り返し正規表� ��の数に比例する行列サイズに削減すること� ��できる。従って、行列サイズがNである行列 同士の演算量はO(N ³ )であるため、本実施の形態1に係る手法は、m ulti-char NFA記述行列を計算する際の行列演算� ��を、関連技術と比較して大幅に削減するこ� ��ができる。multi-char NFA記述行列を計算する� ��の演算量を削減することができるため、M文 字単位のNFAを作成するためのmulti-char NFA記述 行列を生成する際に要する計算時間を削減す ることができる。これにより、正規表現が入 力されてからM文字単位のNFAを求めて、最終� �に、指定された正規表現を検索する回路のHD L記述を得るために要する所用時間を削減す� �ことができる。

 また、本実施の形態1によれば、行列サイ ズの小さい縮小版の1-char NFA記述行列を用い� ��multi-char NFA記述行列を生成するための演算� ��行うことで、その演算の際に使用するメモ� ��に関して、行列演算情報を一時的に保持す� ��ためのメモリ容量を削減することができる� ��

 また、本実施の形態1によれば、1文字単� �のNFAを生成する際に、繰り返し正規表現に� �応する状態には状態番号が昇順となるよう� �状態番号を割り当てることで、縮小版multi-ch ar NFA記述行列からオリジナル版multi-char NFA� �述行列を生成する際に、繰り返し正規表現� �対応した状態遷移の追加を、状態Xから状態X +Mへの状態遷移を追加するという単純な処理� ��実現することができる。これにより、縮小� ��multi-char NFA記述行列からオリジナル版multi-c har NFA記述行列へと変換するために保持すべ� ��情報量を削減することができる。

 尚、上述した実施の形態1では、本発明を NFAに適用する場合を説明したが本発明はこれ に限定されない。即ち、実施の形態1と同様� �構成を適用し、1-char NFA生成手段121において 、1文字単位のNFAを生成する代わりに1文字単� ��のDFAを生成し、1文字単位のDFAを生成する際 には、繰り返し正規表現に対応する状態遷移 の開始状態番号を保持するように構成するよ うにしてもよい。これにより、NFAに限らずDFA に対しても、行列サイズの小さな縮小版の記 述行列を用いて、同時に複数文字を処理可能 なM文字単位のDFAを生成することができる。

 実施の形態2.
 次に、図24を参照して、本発明の実施の形� �2について説明する。図24は、本発明の実施� �形態2の構成を示すブロック図である。図24� �参照すると、本実施の形態2は、上述した実� ��の形態1と同様に、キーボード等の入力装置 11と、プログラム制御に従って動作するデー� ��処理装置14と、情報を記憶する記憶装置140� �、ディスプレイ装置や印刷装置等の出力装� �13と、を含む。

 本実施の形態2においては、上述した実施 の形態1のデータ処理装置12に含まれる、1-char  NFA生成手段121と、1-char NFA記述行列生成手� �122と、multi-char NFA記述行列生成手段123と、mu lti-char NFA生成手段124と、HDL変換手段125とが� �行する処理を、データ処理装置14が実行する 正規表現-HDL変換プログラム15に基づいて実現 するものである。

 データ処理装置14は、正規表現-HDL変換プ� ��グラム15を読み込む。正規表現-HDL変換プロ� ��ラム15は、データ処理装置14の動作を制御す る。データ処理装置14は、正規表現-HDL変換プ ログラム15の制御が、上述した実施の形態1に おけるデータ処理装置12が実行する処理と同� ��の処理を実行する。

 尚、本実施の形態2においても、上述した 実施の形態1と同様に、NFAに限定されずDFAに� �しても同様の処理を行うことができる。

 実施の形態3.
 次に、図25を参照して、本発明の実施の形� �3について説明する。図25は、本発明の実施� �形態3の構成を示すブロック図である。図25� �参照すると、本実施の形態3は、キーボード� ��の入力装置11と、プログラム制御に従って� �作するデータ処理装置16と、情報を記憶する 記憶装置140と、FPGA等の再構成可能なハード� �ェアデバイスにその構成をコンフィグレー� �ョンするためのコンフィグレーション装置16 4と、パターンマッチングの被検索対象デー� �をパターンマッチング装置17に入力するデー タ入力装置174と、FPGA等の再構成可能なハー� �ウェアデバイスを有するパターンマッチン� �装置17と、パターンマッチングの出力結果を 表示するためのディスプレイ装置や印刷装置 等の結果出力装置175と、を含む。

 データ処理装置16は、図1に示す上述した� ��施の形態1のデータ処理装置12に対して、コ� ��フィグレーションデータ変換手段161を加え� ��ものである。その他の要素は、上述した実� ��の形態1と同じであるため、説明を省略する 。

 コンフィグレーションデータ変換手段161� ��、HDL変換手段125より、正規表現からHDLへの� ��換処理が完了したことを示す信号を受け取� ��。正規表現からHDLへの変換処理が完了した� ��とを示す信号を受け取った場合には、コン� ��ィグレーションデータ変換手段161は、HDL変� ��手段125から受信したmulti-char NFAを記述するH DL記述に基づいて、パターンマッチング装置1 7が有する再構成可能なハードウェアデバイ� �の構成情報となるコンフィグレーションデ� �タへと変換する。変換処理を完了すると、� �ンフィグレーションデータ変換手段161は、� �ンフィグレーションデータをコンフィグレ� �ション装置164に出力する。尚、HDLからコン� �ィグレーションデータへの変換については� �例えば、FPGAである場合には、そのベンダー� ��提供している開発ツールを使用することが� ��きるため、その変換方法の詳細については� ��略する。

 コンフィグレーション装置164は、コンフ� ��グレーションデータ変換手段161からコンフ� ��グレーションデータを受信する。コンフィ� ��レーションデータを受信したコンフィグレ� ��ション装置164は、コンフィグレーションデ� ��タを受信したコンフィグレーション装置164� ��、パターンマッチング装置17のパターンマ� �チング部172を実現する再構成可能なハード� �ェアデバイスを構成・設定する。コンフィ� �レーション装置164は、FPGA等の再構成可能な� ��ードウェアデバイスにその構成をコンフィ� ��レーションするための制御プログラムや、� ��ードウェアデバイスにデータを転送するた� ��の書き込みケーブル等にを用いて構成する� ��コンフィグレーション装置164を構成するこ� ��らの構成要素は、例えばFPGAである場合には 、デバイスベンダーが提供している開発ツー ルに含まれている。コンフィグレーション装 置164がコンフィグレーションデータを用いて 再構成可能なハードウェアデバイスを構成・ 設定する詳細な手順については、FPGA等のデ� �イスベンダーの提供する開発ツールを使用� �ることができる。このため、ここではその� �細な説明を省略する。

 パターンマッチング装置17は、データ入� �部171と、パターンマッチング部172と、結果� �力部173と、を含む。データ入力部171と、パ� �ーンマッチング部172と、結果出力部173とは� �それぞれ別々の再構成可能なハードウェア� �バイス上に構成する。

 データ入力部171は、データ入力装置174か� ��入力されたパケットデータや、テキストデ� ��タ等のパターンマッチング対象データ(以下 、これらデータを被検索データと称する。)� �整形して、データ処理装置16にて生成した同 時動作数に等しい同時処理文字数へと並列化 する。データ入力部171は、同時処理文字数単 位に、被検索データをパターンマッチング部 172へ入力する。

 パターンマッチング部172は、コンフィグ� ��ーション装置164を経由して入力された、デ� ��タ処理装置16が生成したコンフィグレーシ� �ンデータを用いて構成される回路である。� �ち、パターンマッチング部172は、データ処� �装置16が生成したmulti-char NFA回路そのものを 示す。パターンマッチング部172に構成された NFA回路は、データ入力部171から被検索データ が入力される都度、状態遷移が起こる。そし て、NFA回路は、入力された被検索データがパ ターンと一致した場合には、その信号が終了 状態を構成しているレジスタからパターンに 一致した旨を示す信号と、パターンに一致し た被検索データに関する情報(例えば、パタ� �ンに一致した被検索データの位置等を示す� �報。)と、を結果出力部173へと出力する。

 結果出力部173は、パターンマッチング部1 72から入力されたパターンに一致したことを� ��す信号と、パターンに一致した被検索デー� ��に関する情報と、を受信する。結果出力部1 73は、入力された被検索データがどの入力文� ��列に応じてどのパターンに一致したのか等� ��情報を処理して、その処理結果を結果出力� ��置175へと出力する。尚、どのパターンに一� ��したかの通知は、例えば、予め定義してお� ��たパターン番号等を用いて通知することが� ��きる。

 本実施の形態3では、正規表現そのものを 入力することで、1-char NFAから、指定された� ��理文字数で遷移を行うmulti-char NFAの変換を� ��う。そして、本実施の形態3に係る手法は、 multi-char NFAのNFA回路を記述するHDL記述を生成 し、そのHDL記述を用いて記述されるNFA回路を パターンマッチング装置内のハードウェアデ バイス上に構成する。これにより、本実施の 形態3に係る手法は、ハードウェアデバイス� �に構成したNFA回路を用いた、パターンマッ� �ング装置を実現することができる。上述し� �実施の形態1にて説明したように、本発明は� ��multi-char NFA記述行列を計算する際の演算量� ��削減することができる。これにより、本発� ��は、M文字単位のNFAを作成するためのmulti-cha r NFA記述行列の生成に要する計算時間を削減 することができる。従って、本発明は、正規 表現が入力されてからM文字単位のNFAを得て� �最終的に、指定された正規表現を検索する� �路のHDL記述を得る、までの所用時間を削減� �ることができる。このため、本発明は、入� �装置11より新たな正規表現が入力された際に は、短時間でmulti-char NFA回路を記述したHDL記 述を得ることができる。これにより、そのNFA 回路を記述したHDL記述を変換したコンフィグ レーションデータを短時間で得ることができ 、入力装置11より新たな正規表現が入力され� ��からその正規表現がパターンマッチング部1 72の構成に反映されるまでの時間を短縮する� ��とができる。

 尚、本実施の形態3は、上述した実施の形 態2における正規表現-HDL変換プログラム15で� �御されるデータ処理装置が生成するmulti-char� �NFAであって、そのmulti-char NFAを記述するHDL� �述をコンフィグレーションデータ変換手段16 1に入力し、そのHDL記述からコンフィグレー� �ョンデータを生成するようにしてもよい。

 さらに、本実施の形態3では、パターンマ ッチング装置17において、データ入力部171と� ��パターンマッチング部172と、結果出力部173� ��は、それぞれ別々の再構成可能なハードウ� ��アデバイス上に構成するものとしたが本発� ��はこれに限定されない。即ち、これら3つを 同じ再構成可能なハードウェアデバイス上に 構成してもよい。また、例えば、データ入力 部171と、結果出力部173と、を同じ再構成可能 なハードウェアデバイス上に構成し、パター ンマッチング部172を別の再構成可能なハード ウェアデバイス上に構成する等してもよい。 データ入力部171と、パターンマッチング部172 と、結果出力部173と、これらを配備する再構 成可能なハードウェアデバイスと関係につい ては、制約はない。

 さらに、データ入力部171と、結果出力部1 73とについては、ASIC(Application Specific Integrate d Circuit)等の再構成できないハードウェアデ� ��イス上に構成することも可能である。

 また、ハードウェアデバイスの一部のみ� ��再構成可能であり、他の部分は再構成でき� ��いハードウェアデバイスを用いて、パター� ��マッチング部172を再構成可能な部分に構成� ��、データ入力部171と結果出力部173とを再構� ��できないハードウェアデバイス上に構成す� ��ようにしてもよい。ここで、データ入力部1 71と結果出力部173の両方、又は、これらのい� ��れか1つを、パターンマッチング部122と同じ 再構成可能なハードウェアデバイス上に構成 する場合には、コンフィグレーションデータ 変換手段161は、HDL変換手段125が生成したNFA回 路を記述するHDL記述に加えて、データ入力部 171や結果出力部173の回路を記述するHDLについ ても読み込むようにしてもよい。これにより 、コンフィグレーションデータ変換手段161は 、読み込んだコンフィグレーションデータを 生成することで、データ入力部171と結果出力 部173の両方、又は、これらのいずれか1つを� �パターンマッチング部122と同じ再構成可能� �ハードウェアデバイス上に構成する場合に� �対応することができる。

 上述した実施の形態3の動作の説明では、 コンフィグレーション装置164は、コンフィグ レーションデータを格納せずに、受信したコ ンフィグレーションデータを使用して、パタ ーンマッチング装置17のパターンマッチング� ��172を実現する再構成可能なハードウェアデ� ��イスを構成・設定する構成としたが本発明� ��これに限定されない。即ち、コンフィグレ� ��ションデータを記憶するコンフィグレーシ� ��ンデータ記憶装置を更に備え、コンフィグ� ��ーション装置164は、コンフィグレーション� ��ータ変換手段161よりコンフィグレーション� ��ータを受信した場合には、その受信したコ� ��フィグレーションデータを前記コンフィグ� ��ーションデータ記憶装置に記憶させた後に� ��前記コンフィグレーションデータ記憶装置� ��らコンフィグレーションデータを読み出す� ��成としてもよい。

 また、上述した実施の形態3の動作の説明 では、コンフィグレーション装置164は、コン フィグレーションデータ変換手段161よりコン フィグレーションデータを受信した場合には 、パターンマッチング部172を実現する再構成 可能なハードウェアデバイスの構成を開始す る構成としたが、本発明はこれに限定されな い。即ち、コンフィグレーション装置164は、 コンフィグレーションデータ変換手段161より コンフィグレーションデータを受信した際に パターンマッチング部172を実現する再構成可 能なハードウェアデバイスの構成を開始する 必要はなく、パターンマッチング装置17のパ� ��ーンマッチング部172の動作状況を考慮して� ��パターンマッチング装置17のパターンマッ� �ング部172の動作に都合のよいタイミングで� �パターンマッチング部172を実現する再構成� �能なハードウェアデバイスの構成を開始す� �ようにしてもよい。

 尚、本実施の形態3においても、上述した 実施の形態1、2と同様に、NFAに限定されずDFA� ��対しても同様の処理を行うことができる。

 以下、本発明による効果について説明す� ��。第1の効果は、繰り返し正規表現を含む正 規表現において、繰り返し正規表現の繰り返 し回数が多くなった場合でも、NFA記述行列の 演算量を少なくできることである。NFA記述行 列は、NFAの遷移条件を複数文字単位に拡張し たNFAを生成するための行列である。

 その理由は、本発明は、1-char NFA記述行� �からmulti-char NFA記述行列を生成する際に、1- char NFA記述行列から、行列サイズの小さい1-c har NFA記述行列を作成し、作成した行列サイ� ��の小さい1-char NFA記述行列を用いてmulti-char� �NFA記述行列を求めるための演算を行い、最� �に行列サイズ縮小前の1-char NFA記述行列と同 じ大きさのmulti-char NFA記述行列に変換してい るためである。即ち、1文字単位の遷移のNFA� �記述する1-char NFA記述行列から指定された文 字単位の遷移のNFAを記述するmulti-char NFA記述 行列を生成する際に、1-char NFA記述行列から� ��繰り返し正規表現に対応する状態遷移に関� ��る行および列の数を指定された文字数にま� ��縮小した、行列サイズの小さい1-char NFA記� �行列を作成し、作成した行列サイズの小さ� �1-char NFA記述行列を用いてmulti-char NFA記述行 列を求めるための演算を行い、最後に行列サ イズ縮小前の1-char NFA記述行列と同じ大きさ� ��multi-char NFA記述行列に変換することで、行� ��サイズの小さい1-char NFA記述行列を用いてmu lti-char NFA記述行列を求めるための演算を行� �ことができるためである。

 第2の効果は、繰り返し正規表現を含む正 規表現において、繰り返し正規表現の繰り返 し回数が多くなった場合でも、NFA記述行列の 演算に必要な記憶領域を少なくできることで ある。

 その理由は、第1の効果と同様に、multi-cha r NFA記述行列を求めるための演算を行う前に 、行列サイズの小さい1-char NFA記述行列を生� ��し、生成した行列サイズの小さい1-char NFA� �述行列を用いてmulti-char NFA記述行列を求め� �ための演算を行うことで、演算対象となる� �列のサイズを小さく抑えることができるた� �である。

 さらに、本発明は、1文字単位の遷移のNFA を記述する1-char NFA記述行列からmulti-char NFA� ��述行列を生成する際に、1-char NFA記述行列� �ら、繰り返し正規表現に対応する状態遷移� �関する行および列の数を指定された文字数� �まで縮小した、行列サイズの小さい1-char NFA 記述行列を作成する。そして、作成した行列 サイズの小さい1-char NFA記述行列を用いてmult i-char NFA記述行列を求めるための演算を行い� ��最後に行列サイズ縮小前の1-char NFA記述行� �と同じ大きさのmulti-char NFA記述行列に変換� �る。NFA記述行列の各行と各列はそれぞれ有� �オートマトンの状態に対応している。行列� �イズを小さくすることは行列の一部の行、� �は、列を削除することを示す。行列の行、� �は、列の一部を削除することは、記述行列� �と変換する前の有限オートマトンにおいて� �、一部の状態を削除していることと等価で� �る。即ち、本発明において、行列サイズを� �小した1-char NFA記述行列を用いてmulti-char NFA 記述行列を求めるための演算を行うことは、 有限オートマトンの状態数を削減した記述行 列を作成した上で当該演算を行うことに相当 する。従って、本発明では、multi-char NFA記述 行列を求める際の演算において、有限オート マトンの状態数を削減することができる。

 尚、本発明は上述した実施例のみに限定� ��れるものではなく、本発明の要旨を逸脱し� ��い範囲において種々の変更が可能であるこ� ��は勿論である。

 この出願は、2008年6月4日に出願された日� ��出願特願2008―146909を基礎とする優先権を主 張し、その開示のすべてをここに取り込む。