(57)【要約】【課題】正規表現を再構成可能な有限オートマトン回路上に構成するための構成データ生成方法と、それを用いたパターンマッチング装置を提供する。【解決手段】正規表現を３種類のメタキャラクタのみを使った構文木で表現し、この構文木に対して通りがけ順を基本とした方法で辿ることによって、正規表現に含まれるメタキャラクタとテキスト文字を所定の回路モジュールに割り当て、接続関係に応じて所定の構成データを生成する構成データ生成装置１と、構成データを生成する上で必要となる各種情報を記憶する記憶装置２とを備えた構成データ生成装置により、正規表現を再構成可能な有限オートマトン回路上に構成するための構成データを生成することが可能である。【選択図】図１
2011141627.tif 000002
【特許請求の範囲】
【請求項１】
任意の正規表現に基づいて、所定の再構成可能有限オートマトン回路用の構成データを生成する装置であって、
前記構成データは、前記所定の再構成可能有限オートマトン回路の内部にある設定レジスタおよび設定メモリに設定することで、前記任意の正規表現を用いたパターンマッチを実現する回路を構成することができる形式であって、
前記所定の再構成可能有限オートマトン回路は、
前記任意の正規表現においてテキスト文字であるキャラクタに対応するデータを格納するキャラクタノード回路と、
前記キャラクタノード回路に接続されて、前記任意の正規表現において所定の機能的意味を持つメタキャラクタに対応するデータを格納するメタキャラクタノード回路と、
前記メタキャラクタノード回路に接続されたスイッチノード回路と、
前記メタキャラクタノード回路と、前記スイッチノード回路とに接続されたマルチプレクサと
を具備し、
前記キャラクタノード回路と、前記メタキャラクタノード回路と、前記スイッチノード回路と、前記マルチプレクサとは、所定の構文木形式に変換された前記任意の正規表現のキャラクタノードおよびメタキャラクタノードにおける接続関係に対応する接続関係を再構成可能に設定し、
前記所定の構文木形式に変換された前記任意の正規表現において、前記キャラクタノードおよび前記メタキャラクタノードについて、前記所定の再構成可能有限オートマトン回路上に割り当てるための構文木の変更と、接続チャネルの指定とに必要となるレイヤ番号を算出するレイヤ番号算出部と、
前記レイヤ番号を記憶する構文木記憶部と、
前記任意の正規表現および前記レイヤ番号に基づいて、前記任意の正規表現の前記キャラクタノードおよび前記メタキャラクタノードのレイアウト順序を算出するレイアウト順序算出部と、
前記レイアウト順序を記憶するレイアウト順序記憶部と、
前記レイヤ番号と、前記レイアウト順序とに基づいて、前記構成データを生成する構成データ生成部と、
前記構成データを記憶する構成データ記憶部と、
前記構成データを出力する構成データ出力部と
を具備する
再構成可能有限オートマトン回路の構成データ生成装置。
【請求項２】
請求項１に記載の再構成可能有限オートマトン回路の構成データ生成装置において、
前記所定の構文木形式では、前記メタキャラクタとして、
「ＯＲ」を意味する「｜」と、
「０回以上マッチ」を意味する「＊」と、
「連結」を意味する「・」と
のみを用い、かつ、
前記メタキャラクタノードが子ノードを実質的に１つしか持たず、前記子ノードがメタキャラクタである場合には、前記メタキャラクタノードとマージされ、
前記メタキャラクタノードが子ノードを実質的に１つしか持たず、前記子ノードがテキスト文字である場合には、前記メタキャラクタに第２の子ノードとして空を表す「φ」が追加されている
再構成可能有限オートマトン回路の構成データ生成装置。
【請求項３】
請求項１に記載の再構成可能有限オートマトン回路の構成データ生成装置において、
前記所定の構文木形式では、前記メタキャラクタとして、
「ＯＲ」を意味する「｜」と、
「０回以上マッチ」を意味する「＊」と、
「連結」を意味する「・」と
のみを用い、かつ、
前記メタキャラクタノードが子ノードを実質的に１つしか持たない場合は、前記子ノードが前記メタキャラクタノードとマージされている
再構成可能有限オートマトン回路の構成データ生成装置。
【請求項４】
請求項１〜３のいずれかに記載の再構成可能有限オートマトン回路の構成データ生成装置において、
前記レイヤ番号算出部の前段に接続されて、前記任意の正規表現を、前記所定の構文木形式に変換する構文木生成部
をさらに具備する
再構成可能有限オートマトン回路の構成データ生成装置。
【請求項５】
請求項１〜４のいずれかに記載の再構成可能有限オートマトン回路の構成データ生成装置において、
前記レイヤ番号算出部は、
前記キャラクタノードおよび前記メタキャラクタノードのうち、注目ノードに左右の子ノードがあり、かつ、前記左右の子ノードのレイヤ番号が互いに異なる場合は、前記注目ノードのレイヤ番号に、前記左右の子ノードのレイヤ番号の最大値を設定する第１のレイヤ番号設定部と、
前記キャラクタノードおよび前記メタキャラクタノードのうち、注目ノードに左右の子ノードがあり、かつ、前記左右の子ノードのレイヤ番号が等しい場合は、前記注目ノードのレイヤ番号に、前記左右の子ノードのレイヤ番号に１を加算した値を設定する第２のレイヤ番号設定部と
を具備し、
前記第１および前記第２のレイヤ番号設定部は、前記キャラクタノードおよび前記メタキャラクタノードの全てについてレイヤ番号に初期値を設定した後に、前記構文木形式の正規表現のキャラクタノードおよびメタキャラクタノードの全てに対して帰りがけ順に用いられる
再構成可能有限オートマトン回路の構成データ生成装置。
【請求項６】
請求項５に記載の再構成可能有限オートマトン回路の構成データ生成装置において、
前記レイアウト順序算出部は、
前記キャラクタノードおよび前記メタキャラクタノードの全てについて、前記構文木形式の通りがけ順に前記注目ノードを辿りつつ、注目ノードのレイヤ番号が、前記注目ノードの親ノードから見た他方の子ノードのレイヤ番号よりも小さい場合に、前記注目ノードおよび前記他方の子ノードを根に持つ部分木を入れ替える部分木入れ替え部と、
前記キャラクタノードおよび前記メタキャラクタノードの全てについて、前記構文木形式の通りがけ順に前記注目ノードを辿りつつ、レイアウト順序を示す変数に１を加算し、前記注目ノードのレイアウト順序に設定するレイアウト順序設定部と
を具備する
再構成可能有限オートマトン回路の構成データ生成装置。
【請求項７】
請求項６に記載の再構成可能有限オートマトン回路の構成データ生成装置において、
前記構成データ生成部は、
前記レイアウト順序に従い、前記キャラクタノードおよび前記メタキャラクタノードを、前記キャラクタノード回路および前記メタキャラクタノード回路に割り当てるキャラクタノード回路およびメタキャラクタノード回路の割り当て部と、
前記メタキャラクタノード回路の、前記キャラクタノード回路および他の前記メタキャラクタノード回路との接続関係を、前記メタキャラクタノード回路に対応するメタキャラクタノードが親ノードから見て左右いずれの子ノードであるかと、前記メタキャラクタノードの左右の子ノードがキャラクタノードであるかとにしたがって、所定の８つのパターンから１つを選択して設定するパターン選択部と、
前記メタキャラクタノード回路の、前記スイッチノード回路および前記マルチプレクサとの接続関係に従って接続に用いる前記スイッチ回路および前記マルチプレクサの決定部と、
前記キャラクタノード回路、前記メタキャラクタノード回路、前記スイッチノード回路および前記マルチプレクサ同士の接続関係にしたがって、前記キャラクタノード回路、前記メタキャラクタノード回路、前記スイッチノード回路および前記マルチプレクサの出力信号を、前記キャラクタノード回路、前記メタキャラクタノード回路、前記スイッチノード回路および前記マルチプレクサの入力信号を用いる論理演算として設定する論理演算設定部と
を具備する
再構成可能有限オートマトン回路の構成データ生成装置。
【請求項８】
請求項１〜７のいずれかに記載の再構成可能有限オートマトン回路の構成データ生成装置と、
前記再構成可能有限オートマトン回路の構成データ生成装置の後段に接続されたパターンマッチング装置と
を具備し、
前記パターンマッチング装置は、
任意のデータを入力するデータ入力部と、
前記キャラクタノード回路と、前記メタキャラクタノード回路と、前記スイッチノード回路と、前記マルチプレクサとを有し、前記任意のデータに対して前記任意の正規表現のパターンマッチを行うＧｅｎｅｒｉｃ  Ｌｏｇｉｃと、
前記構成データに基づいて前記接続関係を前記Ｇｅｎｅｒｅｉｃ  Ｌｏｇｉｃ上に設定するＣｏｎｆｉｇｕｒａｔｉｏｎ  Ｃｏｎｔｒｏｌｌｅｒと、
前記パターンマッチの結果を出力するパターンマッチ結果出力部と
を具備する
再構成可能パターンマッチングシステム。
【請求項９】
任意の正規表現に基づいて、所定の再構成可能有限オートマトン回路用の構成データを生成する方法であって、
前記構成データは、前記所定の再構成可能有限オートマトン回路の内部にある設定レジスタおよび設定メモリに設定することで、前記任意の正規表現を用いたパターンマッチを実現する回路を構成することができる形式であって、
前記所定の再構成可能有限オートマトン回路は、
前記任意の正規表現においてテキスト文字であるキャラクタに対応するデータを格納するキャラクタノード回路と、
前記キャラクタノード回路に接続されて、前記任意の正規表現において所定の機能的意味を持つメタキャラクタに対応するデータを格納するメタキャラクタノード回路と、
前記メタキャラクタノード回路に接続されたスイッチノード回路と、
前記メタキャラクタノード回路と、前記スイッチノード回路とに接続されたマルチプレクサと
を具備し、
前記キャラクタノード回路と、前記メタキャラクタノード回路と、前記スイッチノード回路と、前記マルチプレクサとは、所定の構文木形式に変換された前記任意の正規表現のキャラクタノードおよびメタキャラクタノードにおける接続関係に対応する接続関係を再構成可能に設定し、
（ａ）所定の構文木形式に変換された前記任意の正規表現を入力するステップと、
（ｂ）前記所定の構文木形式に変換された前記任意の正規表現において、前記キャラクタノードおよび前記メタキャラクタノードについて、前記所定の再構成可能有限オートマトン回路上に割り当てるための構文木の変更と、接続チャネルの指定とに必要となるレイヤ番号を算出するステップと、
（ｃ）前記レイヤ番号を構文木記憶部に記憶するステップと、
（ｄ）前記任意の正規表現および前記レイヤ番号に基づいて、前記任意の正規表現の前記各キャラクタノードおよび前記各メタキャラクタノードのレイアウト順序を算出するステップと、
（ｅ）前記レイアウト順序をレイアウト順序記憶部に記憶するステップと、
（ｆ）前記レイヤ番号と、前記レイアウト順序とに基づいて、前記構成データを生成するステップと、
（ｇ）前記構成データを構成データ記憶部に記憶するステップと、
（ｈ）前記構成データを出力するステップと
を具備する
再構成可能有限オートマトン回路の構成データ生成方法。
【請求項１０】
任意の正規表現に基づいて、所定の再構成可能有限オートマトン回路用の構成データを生成する方法を計算機で実行可能に記載したプログラムであって、
前記構成データは、前記所定の再構成可能有限オートマトン回路の内部にある設定レジスタおよび設定メモリに設定することで、前記任意の正規表現を用いたパターンマッチを実現する回路を構成することができる形式であって、
前記所定の再構成可能有限オートマトン回路は、
前記任意の正規表現においてテキスト文字であるキャラクタに対応するデータを格納するキャラクタノード回路と、
前記キャラクタノード回路に接続されて、前記任意の正規表現において所定の機能的意味を持つメタキャラクタに対応するデータを格納するメタキャラクタノード回路と、
前記メタキャラクタノード回路に接続されたスイッチノード回路と、
前記メタキャラクタノード回路と、前記スイッチノード回路とに接続されたマルチプレクサと
を具備し、
前記キャラクタノード回路と、前記メタキャラクタノード回路と、前記スイッチノード回路と、前記マルチプレクサとは、所定の構文木形式に変換された前記任意の正規表現のキャラクタノードおよびメタキャラクタノードにおける接続関係に対応する接続関係を再構成可能に設定し、
（ａ）所定の構文木形式に変換された前記任意の正規表現を入力するステップと、
（ｂ）前記所定の構文木形式に変換された前記任意の正規表現において、前記キャラクタノードおよび前記メタキャラクタノードについて、前記所定の再構成可能有限オートマトン回路上に割り当てるための構文木の変更と、接続チャネルの指定とに必要となるレイヤ番号を算出するステップと、
（ｃ）前記レイヤ番号を構文木記憶部に記憶するステップと、
（ｄ）前記任意の正規表現および前記レイヤ番号に基づいて、前記任意の正規表現の前記各キャラクタノードおよび前記各メタキャラクタノードのレイアウト順序を算出するステップと、
（ｅ）前記レイアウト順序をレイアウト順序記憶部に記憶するステップと、
（ｆ）前記レイヤ番号と、前記レイアウト順序とに基づいて、前記構成データを生成するステップと、
（ｇ）前記構成データを構成データ記憶部に記憶するステップと、
（ｈ）前記構成データを出力するステップと
を具備する
再構成可能有限オートマトン回路の構成データ生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、オートマトン回路と、この回路を用いるパターンマッチ（文字列照合）装置と、この装置を用いるパターンマッチ方法とに係り、特に、任意の正規表現を再構成可能な有限オートマトン回路上に構成するための回路構成データ生成手法に関する。
【背景技術】
【０００２】
正規表現とは、通常の文字と、メタキャラクタ（ｍｅｔａｃｈａｒａｃｔｅｒ）と呼ばれる特定の意味を持った特殊な記号を組み合わせて、任意の文字列をパターンとして表現する記法である。
【０００３】
この正規表現を用いた文字列照合（パターンマッチ）は、例えば、ある文書ファイルからの文字列検索や、ネットワークセキュリティの分野においてネットワーク中のパケットペイロードから特定の文字列を検索する等、様々な分野で用いられている。特に、ネットワーク中のパケットペイロードに対するパターンマッチでは、ネットワーク帯域に合う高速な検索スループットが求められる。
【０００４】
一般的に、マイクロプロセッサ上では、正規表現を用いたパターンマッチは、与えられた正規表現の検索対象パターンから生成したＮＦＡ（Ｎｏｎ−ｄｅｔｅｒｍｉｎｉｓｔｉｃ  Ｆｉｎｉｔｅ  Ａｕｔｏｍａｔｏｎ：非決定性有限オートマトン）、又は、ＤＦＡ（Ｄｅｔｅｒｍｉｎｉｓｔｉｃ  Ｆｉｎｉｔｅ  Ａｕｔｏｍａｔｏｎ：決定性有限オートマトン）と呼ばれる状態遷移マシンを用いて行われる。ＮＦＡは、ある状態における入力文字に対して状態遷移先が複数個存在することが許されており、ＤＦＡでは１つしか存在しない。
【０００５】
正規表現からＮＦＡ、ＤＦＡへの変換方法については、例えば、非特許文献１に記載されている。非特許文献１には、正規表現を構文木（Ｓｙｎｔａｘ  Ｔｒｅｅ）に変換し、この構文木からＮＦＡを生成し、このＮＦＡからＤＦＡを生成できることが記載されている。
【０００６】
図３０は、正規表現“ａｂ＊（ｃ｜ｄ）（ｅ｜ｆ）ｇ”の構文木の一例である。図３１は、正規表現“ａｂ＊（ｃ｜ｄ）（ｅ｜ｆ）ｇ”の構文木を変換して得られるＮＦＡの一例である。なお、図３１のＮＦＡは、ε遷移（ｅｐｓｉｌｏｎ−ｔｒａｎｓｉｔｉｏｎ）を含まないＮＦＡの一例である。ε遷移とは、入力を待たずに遷移が可能な特殊な遷移である。
【０００７】
ある状態における入力文字に対して状態遷移先が１つしか存在しないＤＦＡでは、１文字あたり一定の速度、つまり、Ｏ（１）の処理時間で、パターンマッチングを行うことができ、長さｍの入力ストリーム（検索対象の文字列）に対してはＯ（ｍ）の処理時間が必要となる。ＤＦＡの状態数は、正規表現の長さｎに対して、最悪の場合、Ｏ（２ｎ）で増加する恐れがある。したがって、状態を保持するために必要なメモリ量が爆発的に増大する可能性がある。
【０００８】
一方、ＮＦＡには、ある状態における入力文字に対して状態遷移先が複数存在する場合がある。この場合のＮＦＡは、逐次処理を行うマイクロプロセッサ上において、１文字あたりＯ（ｎ）の処理時間でパターンマッチングを行う。ここで、ｎは正規表現の長さである。このため、長さｍの入力ストリームに対しては、Ｏ（ｍｎ）の処理時間が必要となるが、その状態数は、Ｏ（ｎ）でしか増加せず、ＤＦＡに比べて小さいことが知られている。
【０００９】
これらのことは、特許文献１、非特許文献１、非特許文献２にも記載されている。
【００１０】
近年、例えば、非特許文献２では、ＮＦＡを直接回路化し、ＦＰＧＡ（Ｆｉｅｌｄ  Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙ）のような再構成可能なデバイス上に組み込むことで、高速なパターンマッチングを行う手法が提案されている。
【００１１】
非特許文献２では、ＮＦＡの各状態をＦｌｉｐ−Ｆｌｏｐ（レジスタ）で構成し、このＦｌｉｐ−Ｆｌｏｐの保持する値（‘１’（Ｈｉｇｈ）か‘０’（Ｌｏｗ））によって当該状態がアクティブであるかどうかを判断する。また、各状態からの遷移条件であるテキスト文字が予め設定されたＣｏｍｐａｒａｔｏｒ（比較器）に入力文字列を入力し、この結果と状態を表すＦｌｉｐ−Ｆｌｏｐの出力との論理積（ＡＮＤ）を取ることで、状態遷移信号を生成する。このような構成を基本ブロックとし、基本ブロックを複数用意すると共に、それらをＡＮＤゲート、ＯＲゲート等の組み合わせ回路で接続することによって、対象となるＮＦＡを回路化している。
【００１２】
図３２は、非特許文献２の手法を用いて構成した正規表現“ａｂ＊（ｃ｜ｄ）（ｅ｜ｆ）ｇ”に対応するパターンマッチング回路の回路図である。このような手法では、ハードウェアによる並列処理の特徴を活かし、ＮＦＡの状態数はＯ（ｎ）のままで、１文字あたりの処理時間をＤＦＡと同じＯ（１）に減少させることが可能である。このため、長さｍの入力ストリームに対してＯ（ｍ）の処理時間でパターンマッチングを行うことが可能となる。
【００１３】
一方で、上記のような手法は、ＦＰＧＡ上に組み込む正規表現パターンの変更・追加・削除等の更新を行う場合、ｖｅｒｉｌｏｇ−ＨＤＬやＶＨＤＬ（Ｖｅｒｙ  ｈｉｇｈ−ｓｐｅｅｄ  ｉｎｔｅｇｒａｔｅｄ  ｃｉｒｃｕｉｔ  Ｈａｒｄｗａｒｅ  Ｄｅｓｃｒｉｐｔｉｏｎ  Ｌａｎｇｕａｇｅ）等のＨＤＬ（Ｈａｒｄｗａｒｅ  Ｄｅｓｃｒｉｐｔｉｏｎ  Ｌａｎｇｕａｇｅ：ハードウェア記述言語）の修正、その合成（Ｓｙｎｔｈｅｓｉｓ）、ＦＰＧＡに対するＰＡＲ（Ｐｌａｃｅ  ａｎｄ  Ｒｏｕｔｅ：配置配線）、プログラミングといったＦＰＧＡの再構成処理（以下、ＦＰＧＡのコンパイルと呼ぶ）が必要となる。したがって、１つのパターンだけを更新するためであっても、当該ＦＰＧＡを含むシステム全体の処理を、再構成の間、停止する必要がある。また、正規表現パターンの更新を考えると、ＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ  Ｓｐｅｃｉｆｉｃ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）化による専用回路化にも適していないという課題がある。
【００１４】
そこで、上記の課題を解決する目的で、非特許文献３、特許文献１に記載されているような回路アーキテクチャが提案されている。これらの手法では、ＦＰＧＡにおける回路構成を決定するＬＵＴ（Ｌｏｏｋ−Ｕｐ  Ｔａｂｌｅ）の内容や、レジスタ配列等の値等を構成データとして変更することが可能である。つまり、これらの構成データを必要に応じて変更することによって、回路アーキテクチャそのものを再構成することなく、回路上に構成する正規表現、又は、それが表すＮＦＡを動的に変更することが可能である。
【００１５】
一方で、非特許文献３、特許文献１に記載されているような回路アーキテクチャにおいても、構成できる正規表現に制限がある、又は、それを表すＮＦＡの状態数Ｎに対するハードウェア量がＯ（Ｎ２）で増加するといったスケーラビリティの面での課題が存在すると考えられる。
【００１６】
そこで、上述したハードウェア回路による正規表現を用いたパターンマッチング回路の課題を解決するために、図３３に示すような再構成可能なオートマトン回路アーキテクチャが提案されている。図３３は、再構成可能なオートマトン回路の一例の構成図である。
【００１７】
図３３の再構成可能なオートマトン回路アーキテクチャは、任意の正規表現を所定の形式に変換した後、この所定の形式の正規表現を物理的な回路としてＧｅｎｅｒｉｃ  Ｌｏｇｉｃ１０７上に構成可能である。さらに、このアーキテクチャは、さらに異なる正規表現を再構成可能である。なお、図３３の再構成可能なオートマトン回路アーキテクチャの構成は、本発明の内容に密接に関係するので、その詳細は本発明の実施形態と同時に説明する。
【００１８】
しかし、上述した、任意の正規表現を所定の形式に変換する具体的な方法が、定義されていないという課題がある。
【先行技術文献】
【特許文献】
【００１９】
【特許文献１】特表２００５−５３７５５０号公報
【非特許文献】
【００２０】
【非特許文献１】近藤嘉雪著、「定本Ｃプログラマのためのアルゴリズムとデータ構造」、ソフトバンクパブリッシング、１９９８年、第２９７−３３０頁
【非特許文献２】Ｒｅｅｔｉｎｄｅｒ  Ｓｉｄｈｕ、Ｖｉｋｔｏｒ  Ｋ．  Ｐｒａｓａｎｎａ、「Ｆａｓｔ  Ｒｅｇｕｌａｒ  Ｅｘｐｒｅｓｓｉｏｎ  Ｍａｔｃｈｉｎｇ  ｕｓｉｎｇ  ＦＰＧＡｓ」、Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ９ｔｈ  Ａｎｎｕａｌ  ＩＥＥＥ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｆｉｅｌｄ−Ｐｒｏｇｒａｍｍａｂｌｅ  Ｃｕｓｔｏｍ  Ｃｏｍｐｕｔｉｎｇ  Ｍａｃｈｉｎｅｓ、２００１年、第２２７−２３８頁
【非特許文献３】Ｄｉｖｙａｓｒｅｅ  Ｊ、Ｒａｊａｓｈｅｋａｒ  Ｈ、Ｋｕｒｕｖｉｌｌａ  Ｖａｒｇｈｅｓｅ、「Ｄｙｎａｍｉｃａｌｌｙ  Ｒｅｃｏｎｆｉｇｕｒａｂｌｅ  Ｒｅｇｕｌａｒ  Ｅｘｐｒｅｓｓｉｏｎ  Ｍａｔｃｈｉｎｇ  Ａｒｃｈｉｔｅｃｔｕｒｅ」、Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  １９ｔｈ  ＩＥＥＥ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ａｐｐｌｉｃａｔｉｏｎ−Ｓｐｅｃｉｆｉｃ  Ｓｙｓｔｅｍｓ，Ａｒｃｈｉｔｅｃｔｕｒｅｓ  ａｎｄ  Ｐｒｏｃｅｓｓｏｒｓ、２００８年、第１２０−１２５頁
【非特許文献４】Ｒｅｅｔｉｎｄｅｒ  Ｓｉｄｈｕ、「Ｅｆｆｉｃｉｅｎｔ  Ｃｏｍｐｕｔａｔｉｏｎ  Ｕｓｉｎｇ  Ｓｅｌｆ−Ｒｅｃｏｎｆｉｇｕｒａｔｉｏｎ」、Ｕｎｉｖｅｒｓｉｔｙ  ｏｆ  Ｓｏｕｔｈｅｒｎ  Ｃａｌｉｆｏｒｎｉａ博士論文（Ｐｈ．Ｄ  Ｔｈｅｓｉｓ）、２００５年、第１５９−１６２頁
【発明の概要】
【発明が解決しようとする課題】
【００２１】
上記のＧｅｎｅｒｉｃ  Ｌｏｇｉｃのような再構成可能オートマトン回路には、以下のような問題点がある。
【００２２】
すなわち、再構成可能オートマトン回路上に構成できる条件を満たした正規表現の各構成要素を、再構成可能オートマトン回路の各構成要素にどのように配置すれば良いかが定義されていない。
【００２３】
本発明の目的は、再構成可能オートマトン回路上に構成できる条件を満たした正規表現の各構成要素を、再構成可能オートマトン回路の各構成要素にどのように配置すれば良いかを決定する具体的な配置方法と、この方法を実行する装置と、この装置でこの方法を実行するためのプログラムとを提供することにある。
【課題を解決するための手段】
【００２４】
本発明の再構成可能有限オートマトン回路の構成データ生成装置は、任意の正規表現に基づいて、所定の再構成可能有限オートマトン回路用の構成データを生成する装置である。ここで、構成データは、所定の再構成可能有限オートマトン回路の内部にある設定レジスタおよび設定メモリに設定することで、任意の正規表現を用いたパターンマッチを実現する回路を構成することができる形式である。所定の再構成可能有限オートマトン回路は、キャラクタノード回路と、メタキャラクタノード回路と、スイッチノード回路と、マルチプレクサとを具備する。キャラクタノード回路は、任意の正規表現においてテキスト文字であるキャラクタに対応するデータを格納する。メタキャラクタノード回路は、キャラクタノード回路に接続されて、任意の正規表現において所定の機能的意味を持つメタキャラクタに対応するデータを格納する。スイッチノード回路は、メタキャラクタノード回路に接続されている。マルチプレクサは、メタキャラクタノード回路と、スイッチノード回路とに接続されている。キャラクタノード回路と、メタキャラクタノード回路と、スイッチノード回路と、マルチプレクサとは、所定の構文木形式に変換された任意の正規表現のキャラクタノードおよびメタキャラクタノードにおける接続関係に対応する接続関係を再構成可能に設定する。再構成可能有限オートマトン回路の構成データ生成装置は、レイヤ番号算出モジュールと、構文木記憶モジュールと、レイアウト順序算出モジュールと、レイアウト順序記憶モジュールと、構成データ生成モジュールと、構成データ記憶モジュールと、構成データ出力モジュールとを具備する。ここで、レイヤ番号算出モジュールは、所定の構文木形式に変換された任意の正規表現において、キャラクタノードおよびメタキャラクタノードについて、所定の再構成可能有限オートマトン回路上に割り当てるための構文木の変更と、接続チャネルの指定とに必要となるレイヤ番号を算出する。構文木記憶モジュールは、レイヤ番号を記憶する。レイアウト順序算出モジュールは、任意の正規表現およびレイヤ番号に基づいて、任意の正規表現の各キャラクタノードおよび各メタキャラクタノードのレイアウト順序を算出する。レイアウト順序記憶モジュールは、レイアウト順序を記憶する。構成データ生成モジュールは、レイヤ番号と、レイアウト順序とに基づいて、構成データを生成する。構成データ記憶モジュールは、構成データを記憶する。構成データ出力モジュールは、構成データを出力する。
【００２５】
本発明の再構成可能有限オートマトン回路の構成データ生成方法は、任意の正規表現に基づいて、所定の再構成可能有限オートマトン回路用の構成データを生成する方法である。ここで、構成データは、所定の再構成可能有限オートマトン回路の内部にある設定レジスタおよび設定メモリに設定することで、任意の正規表現を用いたパターンマッチを実現する回路を構成することができる形式である。所定の再構成可能有限オートマトン回路は、キャラクタノード回路と、メタキャラクタノード回路と、スイッチノード回路と、マルチプレクサとを具備する。キャラクタノード回路は、任意の正規表現においてテキスト文字であるキャラクタに対応するデータを格納する。メタキャラクタノード回路は、キャラクタノード回路に接続されて、任意の正規表現において所定の機能的意味を持つメタキャラクタに対応するデータを格納する。スイッチノード回路は、メタキャラクタノード回路に接続されている。マルチプレクサは、メタキャラクタノード回路と、スイッチノード回路とに接続されている。キャラクタノード回路と、メタキャラクタノード回路と、スイッチノード回路と、マルチプレクサとは、所定の構文木形式に変換された任意の正規表現のキャラクタノードおよびメタキャラクタノードにおける接続関係に対応する接続関係を再構成可能に設定する。本発明の再構成可能有限オートマトン回路の構成データ生成方法は、（ａ）所定の構文木形式に変換された任意の正規表現を入力するステップと、（ｂ）所定の構文木形式に変換された任意の正規表現において、キャラクタノードおよびメタキャラクタノードについて、前記所定の再構成可能有限オートマトン回路上に割り当てるための構文木の変更と、接続チャネルの指定とに必要となるレイヤ番号を算出するステップと、（ｃ）レイヤ番号を構文木記憶部に記憶するステップと、（ｄ）任意の正規表現およびレイヤ番号に基づいて、任意の正規表現の各キャラクタノードおよび各メタキャラクタノードのレイアウト順序を算出するステップと、（ｅ）レイアウト順序をレイアウト順序記憶部に記憶するステップと、（ｆ）レイヤ番号と、レイアウト順序とに基づいて、構成データを生成するステップと、（ｇ）構成データを構成データ記憶部に記憶するステップと、（ｈ）構成データを出力するステップとを具備する。
【００２６】
本発明の再構成可能有限オートマトン回路の構成データ生成プログラムは、任意の正規表現に基づいて、所定の再構成可能有限オートマトン回路用の構成データを生成する方法を計算機で実行可能に記載したプログラムである。ここで、構成データは、所定の再構成可能有限オートマトン回路の内部にある設定レジスタおよび設定メモリに設定することで、任意の正規表現を用いたパターンマッチを実現する回路を構成することができる形式である。所定の再構成可能有限オートマトン回路は、キャラクタノード回路と、メタキャラクタノード回路と、スイッチノード回路と、マルチプレクサとを具備する。キャラクタノード回路は、任意の正規表現においてテキスト文字であるキャラクタに対応するデータを格納する。メタキャラクタノード回路は、キャラクタノード回路に接続されて、任意の正規表現において所定の機能的意味を持つメタキャラクタに対応するデータを格納する。スイッチノード回路は、メタキャラクタノード回路に接続されている。マルチプレクサは、メタキャラクタノード回路と、スイッチノード回路とに接続されている。キャラクタノード回路と、メタキャラクタノード回路と、スイッチノード回路と、マルチプレクサとは、所定の構文木形式に変換された任意の正規表現のキャラクタノードおよびメタキャラクタノードにおける接続関係に対応する接続関係を再構成可能に設定する。本発明の再構成可能有限オートマトン回路の構成データ生成方法は、（ａ）所定の構文木形式に変換された任意の正規表現を入力するステップと、（ｂ）所定の構文木形式に変換された任意の正規表現において、キャラクタノードおよびメタキャラクタノードについて、前記所定の再構成可能有限オートマトン回路上に割り当てるための構文木の変更と、接続チャネルの指定とに必要となるレイヤ番号を算出するステップと、（ｃ）レイヤ番号を構文木記憶部に記憶するステップと、（ｄ）任意の正規表現およびレイヤ番号に基づいて、任意の正規表現の各キャラクタノードおよび各メタキャラクタノードのレイアウト順序を算出するステップと、（ｅ）レイアウト順序をレイアウト順序記憶部に記憶するステップと、（ｆ）レイヤ番号と、レイアウト順序とに基づいて、構成データを生成するステップと、（ｇ）構成データを構成データ記憶部に記憶するステップと、（ｈ）構成データを出力するステップとを具備する。
【発明の効果】
【００２７】
本発明の再構成可能有限オートマトン回路の構成方法、構成装置および構成プログラムによれば、再構成可能オートマトン回路上に構成できる条件を満たした正規表現の各構成要素を、再構成可能オートマトン回路の各構成要素に具体的に配置することが出来る。
【図面の簡単な説明】
【００２８】
【図１】図１は、本発明の第１の実施の形態の再構成可能有限オートマトン回路の構成データ生成装置の構成を示すブロック図である。
【図２】図２は、本発明の第１の実施の形態の再構成可能有限オートマトン回路の構成データ生成装置の動作を示す流れ図である。
【図３】図３は、本発明の第１の実施の形態において用いる構文木で表現された正規表現を管理するデータ構造の例を示す表である。
【図４】図４は、本発明の第１の実施の形態の再構成可能有限オートマトン回路の構成データ生成方法のステップＡ１のより詳細な動作を示す流れ図である。
【図５】図５は、本発明の第１の実施の形態においてメタキャラクタ‘＊’の子ノードに空（φ）を追加した正規表現“ａｂ＊（ｃ｜ｄ）（ｅ｜ｆ）ｇ”の構文木の一例である。
【図６】図６は、本発明の第１の実施の形態において処理対象とする正規表現“ａｂ＊（ｃ｜ｄ）（ｅ｜ｆ）ｇ”の構文木の一例である。
【図７】図７は、本発明の第１の実施の形態においてレイヤ番号算出処理（ステップＡ１）が終了した時点での正規表現“ａｂ＊（ｃ｜ｄ）（ｅ｜ｆ）ｇ”の構文木の一例である。
【図８ａ】図８ａは、通りがけ順による２分木のノード配置における、セルとｌａｙｅｒｓ（ｔ）について説明するための概念図である。
【図８ｂ】図８ｂは、通りがけ順による２分木のノード配置における、セルとｌａｙｅｒｓ（ｔ）について説明するための概念図である。
【図８ｃ】図８ｃは、通りがけ順による２分木のノード配置における、セルとｌａｙｅｒｓ（ｔ）について説明するための概念図である。
【図９】図９は、ノード数が１５である図３５の２分木の各ノードを、通りがけ順によってセルに配置した結果を示す図である。
【図１０】図１０は、本発明の第１の実施の形態のステップＡ２のより詳細な動作を説明するための流れ図である。
【図１１】図１１は、レイアウト順序管理配列ｌａｙｏｕｔの一例を示す表である。
【図１２】図１２は、本発明の第１の実施の形態においてレイアウト順序算出処理（ステップＡ２）が終了した時点での正規表現“ａｂ＊（ｃ｜ｄ）（ｅ｜ｆ）ｇ”の構文木の一例である。
【図１３】図１３は、本発明の第１の実施の形態のステップＡ３のより詳細な動作を説明するための流れ図である。
【図１４】図１４は、本発明の第１の実施の形態において正規表現“ａｂ＊（ｃ｜ｄ）（ｅ｜ｆ）ｇ”をＧｅｎｅｒｉｃ  Ｌｏｇｉｃの各ｃｈａｒ＿ｎｏｄｅ、ｍｃｈａｒ＿ｎｏｄｅに割り当てた場合の一例である。
【図１５ａ】図１５ａは、自身が親ノードから見て左の子ノードであり、自身の左の子ノード、右の子ノードが共にテキスト文字であるノードに対する構成モデルを示す図である。
【図１５ｂ】図１５ｂは、自身が親ノードから見て右の子ノードであり、自身の左の子ノード、右の子ノードが共にテキスト文字であるノードに対する構成モデルを示す図である。
【図１５ｃ】図１５ｃは、自身が構文木の根ノードであり、自身の左の子ノード、右の子ノードが共にテキスト文字であるノードに対する構成モデルを示す図である。
【図１５ｄ】図１５ｄは、自身が親ノードから見て左右どちらかの子ノードであり、自身の左の子ノードがテキスト文字であるノードに対する構成モデルを示す図である。
【図１５ｅ】図１５ｅは、自身が構文木の根ノードであり、自身の左の子ノードがテキスト文字であるノードに対する構成モデルを示す図である。
【図１５ｆ】図１５ｆは、自身が親ノードから見て左右どちらかの子ノードであり、自身の右の子ノードがテキスト文字であるノードに対する構成モデルを示す図である。
【図１５ｇ】図１５ｇは、自身が構文木の根ノードであり、自身の右の子ノードがテキスト文字であるノードに対する構成モデルを示す図である。
【図１５ｈ】図１５ｈは、自身が親ノードから見て左右どちらかの子ノード、又は構文木の根ノードであり、自身の左右の子ノードはどちらもテキスト文字でないノードに対する構成モデルを示す図である。
【図１６】図１６は、本発明の第１の実施の形態において図１４のＧｅｎｅｒｉｃ  Ｌｏｇｉｃに対して構成モデルの決定処理（ステップＤ２）を行った後のＧｅｎｅｒｉｃ  Ｌｏｇｉｃの一例を示す図である。
【図１７】図１７は、本発明の第１の実施の形態において図１６のＧｅｎｅｒｉｃ  Ｌｏｇｉｃに対して利用するｓｎｏｄｅ、ＭＵＸを確定した場合の一例を示す図である。
【図１８】図１８は、ステップＡ４のより詳細な動作を説明するための流れ図である。
【図１９】図１９は、本発明の第２の実施の形態の再構成可能有限オートマトン回路の構成データ生成装置の構成を示すブロック図である。
【図２０】図２０は、本発明の第２の実施の形態の再構成可能有限オートマトン回路の構成データ生成装置の動作を示す流れ図である。
【図２１】図２１は、本発明の第２の実施の形態においてメタキャラクタ‘＊’をその子ノードとマージした正規表現“ａｂ＊（ｃ｜ｄ）（ｅ｜ｆ）ｇ”の構文木の一例である。
【図２２】図２２は、本発明の第２の実施の形態において図２１に示す正規表現“ａｂ＊（ｃ｜ｄ）（ｅ｜ｆ）ｇ”の構文木に対してレイアウト順序の決定（ステップＡ２）までを行った正規表現データを示す。
【図２３】図２３は、本発明の第２の実施の形態において図２２に示す正規表現“ａｂ＊（ｃ｜ｄ）（ｅ｜ｆ）ｇ”の構文木に対応するレイアウト順序管理配列ｌａｙｏｕｔの一例を示す図である。
【図２４】図２４は、本発明の第２の実施の形態において図２２に示す正規表現に対して、ステップＡ３までの処理を行った場合のＧｅｎｅｒｉｃ  Ｌｏｇｉｃを示す図である。
【図２５】図２５は、本発明の第２の実施の形態のステップＡ６のより詳細な動作を説明するための流れ図である。
【図２６】図２６は、本発明の第３の実施の形態の再構成可能有限オートマトン回路の構成データ生成装置の構成を示すブロック図である。
【図２７】図２７は、本発明の第３の実施の形態の再構成可能有限オートマトン回路の構成データ生成装置の動作を示す流れ図である。
【図２８】図２８は、本発明の第４の実施の形態の再構成可能有限オートマトン回路の構成データ生成装置の構成を示すブロック図である。
【図２９】図２９は、本発明の第５の実施の形態の再構成可能有限オートマトン回路の構成データ生成装置の構成を示すブロック図である。
【図３０】図３０は、正規表現“ａｂ＊（ｃ｜ｄ）（ｅ｜ｆ）ｇ”の構文木の一例である。
【図３１】図３１は、正規表現“ａｂ＊（ｃ｜ｄ）（ｅ｜ｆ）ｇ”の構文木を変換して得られるＮＦＡの一例である。
【図３２】図３２は、非特許文献２の手法を用いて構成した正規表現“ａｂ＊（ｃ｜ｄ）（ｅ｜ｆ）ｇ”に対応するパターンマッチング回路の回路図である。
【図３３】図３３は、再構成可能なオートマトン回路の一例の構成図である。
【図３４ａ】図３４ａは、２分木のノード配置における、セルとｌａｙｅｒｓ（ｔ）について説明するための概念図（ｌａｙｅｒｓ（ｌ）＞ｌａｙｅｒｓ（ｒ）の場合）である。
【図３４ｂ】図３４ｂは、２分木のノード配置における、セルとｌａｙｅｒｓ（ｔ）について説明するための概念図（ｌａｙｅｒｓ（ｌ）＝ｌａｙｅｒｓ（ｒ）の場合）である。
【図３５】図３５は、ノード数が１５である２分木の一例について説明するためのグラフである。
【図３６ａ】図３６ａは、図３５の２分木に基づいて、本発明で用いる配置方法に従ってセルを配置した結果を示す図である。
【図３６ｂ】図３６ｂは、図３６ａに示した配置方法をＧｅｎｅｒｉｃ  Ｌｏｇｉｃに当てはめた場合の概念図である。
【図３７】図３７は、ｓｔｒｅｅを４分木で構成した場合のＧｅｎｅｒｉｃ  Ｌｏｇｉｃの構成例である。
【図３８ａ】図３８ａは、メタキャラクタ‘＊’とテキスト文字のマージが不可能なキャラクタノード（ｃｈａｒ＿ｎｏｄｅ）の構成を示すブロック図である。
【図３８ｂ】図３８ｂは、メタキャラクタ‘＊’とテキスト文字のマージが可能なキャラクタノード（ｃｈａｒ＿ｎｏｄｅ）の構成を示すブロック図である。
【図３９】図３９は、メタキャラクタノード（ｍｃｈａｒ＿ｎｏｄｅ）の構成を示すブロック図である。
【図４０ａ】図４０ａは、ｓｔｒｅｅが２分木で構成される場合のスイッチノード（ｓｎｏｄｅ）の構成を示すブロック図である。
【図４０ｂ】図４０ｂは、ｓｔｒｅｅが４分木で構成される場合のスイッチノード（ｓｎｏｄｅ）の構成を示すブロック図である。
【発明を実施するための形態】
【００２９】
本発明の再構成可能有限オートマトン回路の構成データ生成方法、生成装置および生成プログラムについて説明する前に、まず、上述した図３３の再構成可能なオートマトン回路アーキテクチャについて詳細に説明する。
【００３０】
このアーキテクチャは、Ｃｏｎｆｉｇｕｒａｔｉｏｎ  Ｃｏｎｔｒｏｌｌｅｒ１０５と、記憶装置１０６と、Ｇｅｎｅｒｉｃ  Ｌｏｇｉｃ１０７を具備している。Ｇｅｎｅｒｉｃ  Ｌｏｇｉｃ１０７は、ＮＦＡを実際に構成するための再構成可能有限オートマトン回路であり、記憶装置１０６に保持された構成データ（Ｃｏｎｆｉｇｕｒａｔｉｏｎ  Ｄａｔａ）、又は外部から入力される構成データ（Ｃｏｎｆｉｇｕｒａｔｉｏｎ  Ｄａｔａ）をＣｏｎｆｉｇｕｒａｔｉｏｎ  Ｃｏｎｔｒｏｌｌｅｒ１０５によって、Ｇｅｎｅｒｉｃ  Ｌｏｇｉｃ１０７中に存在する設定レジスタ、又は設定メモリに設定することで、回路上に構成する正規表現を変更することが可能である。なお、図３３の再構成可能有限オートマトン回路には、１つの有限オートマトンを構成することができるＧｅｎｅｒｉｃ  Ｌｏｇｉｃが１つだけ描かれているが、このＧｅｎｅｒｉｃ  Ｌｏｇｉｃを複数個含むことができ、さらに評価結果を示す追加の制御信号を含むものである。
【００３１】
図３３のＧｅｎｅｒｉｃ  Ｌｏｇｉｃ１０７は、キャラクタノード（ｃｈａｒ＿ｎｏｄｅ）２１６〜２２０と、メタキャラクタノード（ｍｃｈａｒ＿ｎｏｄｅ）３１４〜３１７と、３入力３出力のスイッチ（ｓｎｏｄｅ）４２８〜４３３と、マルチプレクサ（ＭＵＸ）５１５〜５１８とを具備する。ｃｈａｒ＿ｎｏｄｅ２１６〜２２０は正規表現におけるテキスト文字に、ｍｃｈａｒ＿ｎｏｄｅ３１４〜３１７はメタキャラクタに、それぞれ対応する。また、各ｃｈａｒ＿ｎｏｄｅには入力文字列（１クロックサイクルに１文字（＝８ｂｉｔ））が入力される。
【００３２】
ｃｈａｒ＿ｎｏｄｅは、左右の上位に隣接するｍｃｈａｒ＿ｎｏｄｅとそれぞれ相互接続し、ｍｃｈａｒ＿ｎｏｄｅは、さらに左右の隣接するｍｃｈａｒ＿ｎｏｄｅとの相互接続、上位にあるｓｎｏｄｅへの出力、ＭＵＸからの入力を持つ。ｓｎｏｄｅは、上位に存在する１つのｓｎｏｄｅ、下位に存在する左右の隣接する２つのｓｎｏｄｅ、又はＭＵＸ、ｍｃｈａｒ＿ｎｏｄｅと相互に接続し、２分木（ｂｉｎａｒｙ  ｔｒｅｅ）構造で接続されており、この２分木構造が複数個（図３３では２つ）存在している。つまり、Ｇｅｎｅｒｉｃ  Ｌｏｇｉｃは、ｍｃｈａｒ＿ｎｏｄｅを葉、ｓｎｏｄｅを葉でないノードとした２分木（ｂｉｎａｒｙ  ｔｒｅｅ）が複数存在する形で構成される。具体的には、葉ノードであるｍｃｈａｒ＿ｎｏｄｅは各２分木に共通であり、ＭＵＸはこの葉ノードを複数の２分木で共通に使用するための役割を果たす。以降、この２分木構造をＳｗｉｔｃｈ  Ｔｒｅｅ（ｓｔｒｅｅ）と呼ぶ。
【００３３】
本手法では、正規表現を構文木として表現し、構文木の各ノードをｃｈａｒ＿ｎｏｄｅ、ｍｃｈａｒ＿ｎｏｄｅに配置する。なお、正規表現を構文木として表した場合、葉ノードはテキスト文字、葉でないノードはメタキャラクタとなる。また、本手法で扱うことができる正規表現は、ＯＲを意味する‘｜’、０回以上マッチすることを意味する‘＊’に加え、連結（Ｃｏｎｃａｔｅｎａｔｉｏｎ）を意味する記号‘・’（以降、この連結を意味する記号‘・’もメタキャラクタとして扱う）とテキスト文字を用いて構文木で表現できる正規表現である。例えば、Ｎ１、Ｎ２がそれぞれ正規表現だとすると、正規表現“Ｎ１｜Ｎ２”はＮ１、もしくは、Ｎ２に一致することを意味する。同様に、正規表現“Ｎ１＊”は、Ｎ１が０回以上一致することを意味する。さらに、正規表現“Ｎ１・Ｎ２”は、Ｎ１の次にＮ２が連続することを意味する。これ以外のメタキャラクタを含む正規表現は、これらのメタキャラクタのみを含む正規表現に書き換えることで対応している。また、Ｇｅｎｅｒｉｃ  Ｌｏｇｉｃに含まれるｃｈａｒ＿ｎｏｄｅ、ｍｃｈａｒ＿ｎｏｄｅの数を超える長さ（含まれるテキスト文字とメタキャラクタの数）の正規表現は扱うことができない。
【００３４】
図３３に示すＧｅｎｅｒｉｃ  Ｌｏｇｉｃは、５文字以内のテキスト文字と、４文字以内のメタキャラクタから構成される正規表現を構成できる有限オートマトン回路である。また、２つの２分木を具備しており、第１の２分木は、ｓｎｏｄｅ４２８を根ノードとして、ｓｎｏｄｅ４２９、４３０、ｍｃｈａｒ＿ｎｏｄｅ３１４〜３１７を具備する。また、第２の２分木は、ｓｎｏｄｅ４３１を根ノードとして、ｓｎｏｄｅ４３２、４３３、ｍｃｈａｒ＿ｎｏｄｅ３１４〜３１７を具備する。
【００３５】
なお、図３３に示すＧｅｎｅｒｉｃ  Ｌｏｇｉｃは一例であり、より多くのテキスト文字、メタキャラクタを含む正規表現を構成することができるＧｅｎｅｒｉｃ  Ｌｏｇｉｃについても構成可能である。すなわち、より多くの数のｃｈａｒ＿ｎｏｄｅ、及びｍｃｈａｒ＿ｎｏｄｅを具備しても良い。その場合、ＭＵＸの数はｍｃｈａｒ＿ｎｏｄｅの数と同様に変化する。さらに、ｓｎｏｄｅの総数は葉ノードであるｍｃｈａｒ＿ｎｏｄｅの数に応じて変化し、多段式に接続されているｓｎｏｄｅの段数はｓｎｏｄｅの総数に応じて変化する。Ｇｅｎｅｒｉｃ  Ｌｏｇｉｃの具体的な構成方法に関しては、後ほど説明する。
Ｇｅｎｅｒｉｃ  Ｌｏｇｉｃの具体的な構成方法に関する説明の前段階として、まず、Ｇｅｎｅｒｉｃ  Ｌｏｇｉｃ上に２分木である構文木の各ノードを一列に並べた際の配置方法について説明する。２分木の各ノードを一列に並べた際の配置方法については、非特許文献４に記載があり、非特許文献４では、
（１）  ノード数ｎ（ｎ＞０）の任意の２分木ｔは、ｎ×（ｌａｙｅｒｓ（ｔ）＋１）個のセル（ｃｅｌｌ）で配置できる
（２）  ノード数２ｎ−１（ｎ＞１）の任意の２分木ｔにおけるｌａｙｅｒｓ（ｔ）は、高々ｎ−１である
（３）  （１）、（２）より、ノード数２ｎ−１（ｎ＞１）の任意の２分木ｔは、高々（２ｎ−１）×ｎ個のセルで配置できる
ことが示されている。以下では、上記の非特許文献４が示している配置方法（１）について説明する。
【００３６】
図３４ａ、図３４ｂは、２分木ｔのノード配置における、セルとｌａｙｅｒｓ（ｔ）について説明するための概念図である。２分木ｔの根ノードの左右の子ノードを根とする部分木をそれぞれ、部分木（Ｌｅｆｔ−Ｓｕｂｔｒｅｅ）ｌ、部分木（Ｒｉｇｈｔ−Ｓｕｂｔｒｅｅ）ｒとすると、図３４ａはｌａｙｅｒｓ（ｌ）＞ｌａｙｅｒｓ（ｒ）の場合、図３４ｂはｌａｙｅｒｓ（ｌ）＝ｌａｙｅｒｓ（ｒ）の場合の概念図である。また、ｌａｙｅｒｓ（ｌ）＜ｌａｙｅｒｓ（ｒ）の場合には、部分木ｌ、部分木ｒを入れ替えることで図３４ａに対応する。なお、図３４ａ、図３４ｂは、非特許文献４で示されている図に、補足説明を加えた図である。
【００３７】
セルは、ノード自身と、ノードを中心に上下左右の４方向に接続ポートを持ち得るブロックとして定義される。すなわち、ノードを含まず、ノード間の接続のために配置されるセルも存在し得る。
【００３８】
セルがノードを含む場合、そのセルは最下位層に配置されるものとする。このため、ノードを含むセルは、４方向のうち、上と左右の３方向の接続ポートのみを使用できる。
【００３９】
また、ノードを含まないセルが、例えば、上下のポートを接続した配線と左右のポートを接続した配線とを具備する場合、これら２本の配線はお互いに交差することはできないものとする。
【００４０】
通常、２分木では、任意の１ノードは最大で３ノードと接続する。ここで、使用されていない上方向のポートが存在する場合は、この上方向のポートを、隣接するノードが上方向のセルと接続するためのポートとして使用しても良い。
【００４１】
本配置方法では、２分木ｔの各ノードを帰りがけ順（ｐｏｓｔｏｒｄｅｒ  ｔｒａｖｅｒｓａｌ）によって辿ればノードの配置順が決まる。これによると、根ノードは最も右端に配置され、根ノードの左の子ノードを根とする部分木ｌと、根ノードの右の子ノードを根とする部分木ｒは左から順に配置する。但し、ｌａｙｅｒｓ（ｌ）とｌａｙｅｒｓ（ｒ）のうち、大きなｌａｙｅｒｓの値をもつ部分木を左の部分木としている。つまり、ｌａｙｅｒｓ（ｌ）よりもｌａｙｅｒｓ（ｒ）の方が大きければ、左の部分木ｌと右の部分木ｒを入れ替える。
【００４２】
このとき、ノード数ｎ（ｎ＞０）の任意の２分木ｔは、ｎ×（ｌａｙｅｒｓ（ｔ）＋１）個のセルで配置できることが知られている。非特許文献４では、これらの縦横に並んだセルに２分木ｔを配置する際、ノードを含まないセルの高さをもってｌａｙｅｒｓ（ｔ）と定義しており、その算出方法は以下のように定義されている。
１．  ２分木ｔがノード数０の場合、ｌａｙｅｒｓ（ｔ）＝−１
２．  ２分木ｔが根ノードの左の子ノードを根とする部分木ｌ、根ノードの右の子ノードを根とする部分木ｒで構成されるとき、
（ア）  ｌａｙｅｒｓ（ｌ）とｌａｙｅｒｓ（ｒ）が異なる場合、
ｌａｙｅｒｓ（ｔ）＝ｍａｘ｛ｌａｙｅｒｓ（ｌ），ｌａｙｅｒｓ（ｒ）｝
（イ）  ｌａｙｅｒｓ（ｌ）とｌａｙｅｒｓ（ｒ）が等しい場合、
ｌａｙｅｒｓ（ｔ）＝ｌａｙｅｒｓ（ｌ）＋１
【００４３】
図３４ａの場合、２分木ｔは、ｎ×（ｌａｙｅｒｓ（ｌ）＋１）セルで配置されている。この場合、上記の算出方法から、ｌａｙｅｒｓ（ｔ）＝ｌａｙｅｒｓ（ｌ）となるため、ｎ×（ｌａｙｅｒｓ（ｔ）＋１）セルで配置可能である。一方、図３４ｂの場合、２分木ｔは、ｎ×（ｌａｙｅｒｓ（ｌ）＋２）セルで配置されている。この場合、ｌａｙｅｒｓ（ｔ）＝ｌａｙｅｒｓ（ｌ）＋１と等しくなるため、ｎ×（ｌａｙｅｒｓ（ｔ）＋１）セルで配置可能となる。つまり、ノード数２ｎ−１（ｎ＞１）の任意の２分木ｔは、高々（２ｎ−１）×ｎ個のセルで配置できる。
【００４４】
図３５は、ノード数が１５である２分木の一例について説明するためのグラフである。図３６ａは、図３５の２分木に基づいて、本発明で用いる配置方法に従ってセルを配置した結果を示す図である。ここで、１５＝２４−１なので、ｎ＝４が得られる。この場合、上記より、最大（２ｎ−１）×ｎ＝１５×４個のセルで配置することが分かる。図３５、図３６ａの例では、２分木ｔのｌａｙｅｒｓ（ｔ）は２であり、実際に１５×３個のセルで配置できていることから、上記に示した必要セル数の条件（１）、（２）、（３）を満たしている。詳細は省略するが、ノード数１５の完全２分木を考えた場合、ｌａｙｅｒｓ（ｔ）＝３となり、これも上記条件を満たす。
【００４５】
なお、上記から、２分木ｔに対するｌａｙｅｒｓ（ｔ）は、２分木ｔの各ノードを一列に配置した場合に、その接続を正しく行うために必要な水平方向のチャネル数を示していることが分かる。以降、この水平方向のチャネルを“Ｒｏｕｔｉｎｇ  Ｌａｙｅｒ”と呼ぶ。
【００４６】
上記を踏まえて、Ｎ文字のメタキャラクタと、Ｍ文字のテキスト文字を含む正規表現を表す有限オートマトン回路であるＧｅｎｅｒｉｃ  Ｌｏｇｉｃの構成方法を考える。
【００４７】
図３３に示すように、Ｇｅｎｅｒｉｃ  Ｌｏｇｉｃでは、テキスト文字に対応するｃｈａｒ＿ｎｏｄｅは、メタキャラクタに対応するｍｃｈａｒ＿ｎｏｄｅの下位層に配置されている。また、ｃｈａｒ＿ｎｏｄｅの数はｍｃｈａｒ＿ｎｏｄｅの数よりも１つ多い。つまり、Ｍ＝Ｎ＋１となる。このとき、このＧｅｎｅｒｉｃ  Ｌｏｇｉｃは、メタキャラクタをＮ文字、テキスト文字をＮ＋１文字含む長さ２Ｎ＋１の正規表現に対応することができる。
【００４８】
このとき、ノード数Ｎの２分木に必要なＲｏｕｔｉｎｇ  Ｌａｙｅｒ数は、上記の非特許文献４より、最大ｌｏｇ２（Ｎ＋１）−１となる。なお、ノード数２ｎ−１＝Ｎとすると、ｎ＝ｌｏｇ２（Ｎ＋１）であることから、Ｒｏｕｔｉｎｇ  Ｌａｙｅｒ数は最大ｎ−１＝ｌｏｇ２（Ｎ＋１）−１であることは明らかである。
【００４９】
上述したように、このＲｏｕｔｉｎｇ  Ｌａｙｅｒは、２分木の各ノードを一列に配置した場合に、その接続を正しく行うために必要な水平方向のチャネルであり、Ｇｅｎｅｒｉｃ  Ｌｏｇｉｃにおけるｍｃｈａｒ＿ｎｏｄｅを葉ノード、ｓｎｏｄｅをノードとした２分木構造（ｓｔｒｅｅ）の必要数に関連する。ｓｔｒｅｅには、あるｍｃｈａｒ＿ｎｏｄｅ間を接続した場合に利用できる当該ｍｃｈａｒ＿ｎｏｄｅ間には双方向の信号線が具備されている。しかし、同じレイヤ番号に相当するｍｃｈａｒ＿ｎｏｄｅ間の接続が、同一ｓｎｏｄｅ間の信号線を利用しなければならない場合がある。例えば、図３６ｂは、図３６ａに示した配置方法をＧｅｎｅｒｉｃ  Ｌｏｇｉｃに当てはめた場合の概念図である。但し、正規表現の構文木においては、葉ノードはテキスト文字を示すため、図３６ａの配置とは若干異なっている。図３６ｂにおいて、丸で表したノードはｃｈａｒ＿ｎｏｄｅ、四角で表したノードはｍｃｈａｒ＿ｎｏｄｅ、三角形で表したノードはｓｎｏｄｅに相当する。図３６ｂでは、ノード１とノード３のｍｃｈａｒ＿ｎｏｄｅの実線で示した接続（図では、ノード４を経由させて接続している）と、ノード３とノード６の破線で示した接続は、図中では太線で示した同一ｓｎｏｄｅ間の接続を利用している。このため、Ｇｅｎｅｒｉｃ  Ｌｏｇｉｃにおけるｍｃｈａｒ＿ｎｏｄｅを葉ノード、ｓｎｏｄｅをノードとした２分木の数は、Ｒｏｕｔｉｎｇ  Ｌａｙｅｒの２倍の数が必要となる。厳密に言えば、Ｇｅｎｅｒｉｃ  Ｌｏｇｉｃに具備されるｍｃｈａｒ＿ｎｏｄｅの数が少ない場合には、Ｒｏｕｔｉｎｇ  Ｌａｙｅｒと同数でも良いが、一般的には、２倍の数だけ必要となる。
【００５０】
以上をまとめると、本発明において、Ｎ文字のメタキャラクタと、Ｎ＋１文字のテキスト文字を含む正規表現を構築する場合、Ｇｅｎｅｒｉｃ  Ｌｏｇｉｃは、以下の方法で構築することができる。
（１）  ｍｃｈａｒ＿ｎｏｄｅをＮ個、ｃｈａｒ＿ｎｏｄｅをＮ＋１個配置する。
（２）  Ｎ個のｍｃｈａｒ＿ｎｏｄｅを葉ノードとし、ｓｎｏｄｅを葉ではないノードとする２分木（ｓｔｒｅｅ）をＢ個用意する。ここで、２分木の必要数Ｂは、Ｂ＝［ｌｏｇ２（Ｎ＋１）−１］×２であり、［ｘ］は、ｘを下回らない最小の整数を意味する。
（３）  各ＭＵＸはＢ入力のＭＵＸとする。
【００５１】
なお、図３３に示すＧｅｎｅｒｉｃ  Ｌｏｇｉｃでは、ｓｔｒｅｅが２個しか表示していないが、実際は同様のｓｔｒｅｅがさらに２個、合計４個必要である。これは、上記（２）より、必要数Ｂがｌｏｇ２５−１を下回らない最小の整数である２の２倍、つまり４となることから明らかである。但し、上述したように、ｍｃｈａｒ＿ｎｏｄｅ数が少ない場合、特に、図３３では、あるｍｃｈａｒ＿ｎｏｄｅ間を、同一の２分木上で同一のｓｎｏｄｅ間の接続信号を用いて接続する場合は考えられないため、事実上２個あれば問題はないが、一般的に上記Ｂ個用意すれば良い。
【００５２】
また、図３３に示すＧｅｎｅｒｉｃ  Ｌｏｇｉｃにおけるｓｔｒｅｅは２分木構成であるが、ｓｎｏｄｅの入出力信号数を変更し、これをＭ分木（Ｍ≧２）として構成することも可能であり、Ｍ分木で構成した場合も必要なｓｔｒｅｅの数は上記と変わらない。例えば、ｍｃｈａｒ＿ｎｏｄｅを４個、ｃｈａｒ＿ｎｏｄｅを５個具備するＧｅｎｅｒｉｃ  Ｌｏｇｉｃのｓｔｒｅｅを４分木で構成した場合、図３７のようなＧｅｎｅｒｉｃ  Ｌｏｇｉｃが構成される。図３７は、ｓｔｒｅｅを４分木で構成した場合のＧｅｎｅｒｉｃ  Ｌｏｇｉｃの構成例である。但し、２分木構成のｓｔｒｅｅと同様、Ｇｅｎｅｒｉｃ  Ｌｏｇｉｃに具備されるｍｃｈａｒ＿ｎｏｄｅの数が少ない場合には、Ｒｏｕｔｉｎｇ  Ｌａｙｅｒと同数でも良いが、一般的には、２倍の数だけ必要となる。例えば、図３７に示す４分木構成のｓｔｒｅｅを用いた構造の場合、ｓｔｒｅｅは２個しか表示していない。この場合、あるｍｃｈａｒ＿ｎｏｄｅ間を、同一の２分木上で同一のｓｎｏｄｅ間の接続信号を用いて接続する場合は考えられないため、事実上２個あれば問題はないが、一般的には上記Ｂ個用意すれば良い。
【００５３】
一方、一般的に、Ｎ＋１文字のテキスト文字を含む正規表現には、最大Ｎ＋１文字のメタキャラクタ‘｜’、‘＊’、‘・’が含まれる可能性がある。これは、メタキャラクタ‘＊’が１つの子ノードしか持たないためであり、メタキャラクタ‘＊’を含む正規表現の構文木は全てのノードが２つの子ノードを持つ全２分木にならない場合がある。一方、本Ｇｅｎｅｒｉｃ  Ｌｏｇｉｃ回路では、Ｎ文字のメタキャラクタと、Ｎ＋１文字のテキスト文字から成る正規表現しか構成できない。そこで、本発明においては、メタキャラクタ‘＊’を（１）  子ノードのメタキャラクタとマージする、もしくは、メタキャラクタ‘＊’に空のテキスト文字を子ノードとして追加することで構文木を生成する、又は、（２）  （１）に加えて、子ノードのメタキャラクタ、もしくはテキスト文字とマージする、の２つ手法により、上記の課題を解決している。上記、（１）、（２）のどちらの手法を利用できるかは、ｃｈａｒ＿ｎｏｄｅの内部構成に依存する。
【００５４】
続いて、Ｇｅｎｅｒｉｃ  Ｌｏｇｉｃの各ノードの構成について説明する。
【００５５】
図３８ａは、メタキャラクタ‘＊’とテキスト文字のマージが不可能なキャラクタノード（ｃｈａｒ＿ｎｏｄｅ）の構成を示すブロック図である。すなわち、図３８ａは、メタキャラクタ‘＊’に対する処理として、上記（１）子ノードのメタキャラクタとマージする、もしくは、メタキャラクタ‘＊’に空のテキスト文字を子ノードとして追加する場合のｃｈａｒ＿ｎｏｄｅの構成を示すブロック図である。ｃｈａｒ＿ｎｏｄｅ４０は、ｌｉ信号入力部と、ｒｉ信号入力部と、テキスト文字入力部と、ｌｏ信号出力部と、ｒｏ信号出力部を具備する。ここで、ｌｉ信号は、そのｃｈａｒ＿ｎｏｄｅの左に隣接するｍｃｈａｒ＿ｎｏｄｅから入力する１ｂｉｔの入力信号である。ｒｉ信号は、そのｃｈａｒ＿ｎｏｄｅの右に隣接するｍｃｈａｒ＿ｎｏｄｅから入力する１ｂｉｔの入力信号である。ｌｏ信号は、そのｃｈａｒ＿ｎｏｄｅの左に隣接するｍｃｈａｒ＿ｎｏｄｅへ出力する１ｂｉｔの出力信号である。ｒｏ信号は、そのｃｈａｒ＿ｎｏｄｅの右に隣接するｍｃｈａｒ＿ｎｏｄｅへ出力する１ｂｉｔの出力信号である。また、テキスト文字入力部には、パターンマッチングを行う対象となるテキスト文字が１クロックサイクル毎に１文字ずつ供給される。なお、左右一列に並んで配置されている複数のｃｈａｒ＿ｎｏｄｅのうち、左端のｃｈａｒ＿ｎｏｄｅは、当然ながらｌｉ信号入力部とｌｏ信号出力部に接続がない。同様に、右端のｃｈａｒ＿ｎｏｄｅは、当然ながらｒｉ信号入力部とｒｏ信号出力部に接続がない。
【００５６】
ｃｈａｒ＿ｎｏｄｅ４０のｌｉ信号入力部は、ＬＵＴ１０００の第１の入力部と、ＬＵＴ１００１の第１の入力部とに接続されている。ｒｉ信号入力部は、ＬＵＴ１０００の第２の入力部と、ＬＵＴ１００１の第２の入力部とに接続されている。ＬＵＴ１０００の出力部は、Ｆｌｉｐ−Ｆｌｏｐ６０８の入力部に接続されている。Ｆｌｉｐ−Ｆｌｏｐ６０８の出力部およびＣｏｍｐａｒａｔｏｒ７０７の出力部は、ＡＮＤゲート８０７の両入力部にそれぞれ接続されている。ＡＮＤゲート８０７の出力部は、ＬＵＴ１００１の第３の入力部に接続されている。ＬＵＴ１００１の出力部は、ｏ信号出力部に接続されている。この信号ｏは、出力信号ｌｏおよび出力信号ｒｏとして、ｃｈａｒ＿ｎｏｄｅ４０の左右に隣接するｍｃｈａｒ＿ｎｏｄｅに向けて出力される。
【００５７】
図３８ａのように構成されたｃｈａｒ＿ｎｏｄｅ４０は、２つの信号ｌｉ、ｒｉを入力すると、そのどちらかをＬＵＴ１０００の設定により選択することができ、選択された入力信号がＦｌｉｐ−Ｆｌｏｐ６０８に保持される。また、Ｃｏｍｐａｒａｔｏｒ７０７には、構成データによって比較すべきテキスト文字が設定されている。Ｃｏｍｐａｒａｔｏｒ７０７は、この設定された文字と、入力されたパターンマッチング対象となるテキスト文字とを比較し、一致していれば‘１’（Ｈｉｇｈ）を、一致していなければ‘０’（Ｌｏｗ）を出力する。ＬＵＴ１００１は、ＡＮＤゲート８０７が出力する信号と、入力信号ｌｉと、入力信号ｒｉのうち、ＬＵＴ１００１の設定に応じて選択されたいずれかを出力する。ＬＵＴ１００１により、本ｃｈａｒ＿ｎｏｄｅに空のテキスト文字が割り当てられた場合にも、入力信号ｌｉ、又はｒｉのどちらかをそのまま出力することが可能となる。
【００５８】
なお、図３８ａでは、ｃｈａｒ＿ｎｏｄｅ４０の左右のｍｃｈａｒ＿ｎｏｄｅへの出力信号ｌｏ、ｒｏとして、共に、出力信号ｏがそのまま出力される。しかし、ｃｈａｒ＿ｎｏｄｅ４０の内部でそれぞれの出力信号を選択するＬＵＴを用意し、それらのＬＵＴの設定により、個別に出力してもよい。この場合、ＬＵＴ１００１と同じ接続関係をもったＬＵＴが別途１つ必要となる。
【００５９】
上記のような構成によって、ｃｈａｒ＿ｎｏｄｅは、構成データに従って設定された動作を行う。
【００６０】
また、図３８ｂは、メタキャラクタ‘＊’とテキスト文字のマージが可能なキャラクタノード（ｃｈａｒ＿ｎｏｄｅ）の構成を示すブロック図である。すなわち、図３８ｂは、メタキャラクタ‘＊’に対する処理として、上記（２）子ノードのメタキャラクタ、もしくはテキスト文字とマージする場合のｃｈａｒ＿ｎｏｄｅの構成を示すブロック図である。ｃｈａｒ＿ｎｏｄｅ５０は、ｃｈａｒ＿ｎｏｄｅ４０のＬＵＴ１０００が、ＬＵＴ１００２に置き換わる以外は、全てｃｈａｒ＿ｎｏｄｅ４０と同じ構成となる。
【００６１】
ｃｈａｒ＿ｎｏｄｅ５０のＬＵＴ１００２には、ｌｉ信号入力部と、ｒｉ信号入力部に加え、ＡＮＤゲート８０７の出力信号が入力され、ＬＵＴ１００２の設定によりそのうちいずれか、又は２つの入力信号の論理和をとった結果が出力される。このような構成により、メタキャラクタ‘＊’がテキスト文字とマージされた場合に、ＬＵＴ１００２の設定によってマージされたテキスト文字が繰り返し入力された際に、出力信号ｏとして一致した結果を出力することができる。
【００６２】
次に、図３９は、メタキャラクタノード（ｍｃｈａｒ＿ｎｏｄｅ）の構成を示すブロック図である。このｍｃｈａｒ＿ｎｏｄｅ６０は、５つの入力部と、５つの５入力１出力ＬＵＴ１００３〜１００７と、５つの出力部とを具備する。５つの入力部には、ｐｉ信号入力部と、Ｌｉ信号入力部と、Ｒｉ信号入力部と、ｌｉ信号入力部と、Ｒｉ信号入力部とがあり、それぞれ、当該ｍｃｈａｒ＿ｎｏｄｅの上部にあるＭＵＸ、左に隣接するｍｃｈａｒ＿ｎｏｄｅ、右に隣接するｍｃｈａｒ＿ｎｏｄｅ、左に隣接するｃｈａｒ＿ｎｏｄｅ、右に隣接するｃｈａｒ＿ｎｏｄｅから入力される１ｂｉｔの入力信号である。また、５つの出力部には、ｐｏ信号出力部と、Ｌｏ信号出力部と、Ｒｏ信号出力部と、ｌｏ信号出力部と、ｒｏ信号出力部とがあり、それぞれ、当該ｍｃｈａｒ＿ｎｏｄｅの上部にある複数のｓｎｏｄｅ、左に隣接するｍｃｈａｒ＿ｎｏｄｅ、右に隣接するｍｃｈａｒ＿ｎｏｄｅ、左に隣接するｃｈａｒ＿ｎｏｄｅ、右に隣接するｃｈａｒ＿ｎｏｄｅへ出力される１ｂｉｔの出力信号である。
【００６３】
ＬＵＴ１００３の５つの入力部には、ｐｉ、Ｌｉ、Ｒｉ、ｌｉ、ｒｉの５つの信号入力部がそれぞれ接続されている。この、５つの信号入力部が、ＬＵＴにおける５つの信号入力部にそれぞれ接続されている構成は、他のＬＵＴ１００４〜１００７においても同様である。また、ＬＵＴ１００３〜１００７の出力部は、それぞれ、ｐｏ信号出力部と、Ｌｏ信号出力部と、Ｒｏ信号出力部と、ｌｏ信号出力部と、ｒｏ信号出力部とに接続されている。
【００６４】
ｍｃｈａｒ＿ｎｏｄｅ６０において、各出力信号がどの入力信号の値によって出力されるかは、ＬＵＴ１００３〜１００７の設定に応じた論理演算によって任意に設定可能である。
【００６５】
続いて、図４０ａは、ｓｔｒｅｅが２分木で構成される場合のスイッチノード（ｓｎｏｄｅ）の構成を示すブロック図である。ｓｎｏｄｅ７０は、３つのＬＵＴ１００８〜１０１０と、ｉ０信号入力部と、ｉ１信号入力部と、ｉ２信号入力部と、ｏ０信号出力部と、ｏ１信号出力部と、ｏ２信号出力部とを具備する。ｉ０、ｉ１、ｉ２信号入力部は、それぞれ当該ｓｎｏｄｅの上位にあるｓｎｏｄｅ、左右の子ノードとなるｓｎｏｄｅからの１ｂｉｔの入力信号であり、同様に、ｏ０、ｏ１、ｏ２信号出力部は、それぞれ当該ｓｎｏｄｅの上位にあるｓｎｏｄｅ、左右の子ノードとなるｓｎｏｄｅへの１ｂｉｔの出力信号である。
【００６６】
ＬＵＴ１００８は、ｉ１信号入力部に接続された入力部と、ｉ２信号入力部に接続された入力部と、ｏ０信号出力部に接続された出力部とを具備する。ＬＵＴ１００８の設定に応じて、入力信号ｉ１またはｉ２のいずれかが、信号ｏ０として出力される。
【００６７】
同様に、ＬＵＴ１００９は、ｉ０信号入力部に接続された入力部と、ｉ２信号入力部に接続された入力部と、ｏ１信号出力部に接続された出力部とを具備する。ＬＵＴ１００９の設定に応じて、入力信号ｉ０またはｉ２のいずれかが、信号ｏ１として出力される。
【００６８】
さらに、ＬＵＴ１０１０は、ｉ０信号入力部に接続された入力部と、ｉ１信号入力部に接続された入力部と、ｏ２信号出力部に接続された出力部とを具備する。ＬＵＴ１０１０の設定に応じて、入力信号ｉ０またはｉ１のいずれかが、信号ｏ２として出力される。
【００６９】
また、図４０ｂは、ｓｔｒｅｅが４分木で構成される場合のスイッチノード（ｓｎｏｄｅ）の構成を示すブロック図である。ｓｎｏｄｅ８０は、５つのＬＵＴ１０１１〜１０１５と、ｉ０信号入力部と、ｉ１信号入力部と、ｉ２信号入力部と、ｉ３信号入力部と、ｉ４信号入力部と、ｏ０信号出力部と、ｏ１信号出力部と、ｏ２信号出力部、ｏ３信号出力部と、ｏ４信号出力部とを具備する。ｉ０、ｉ１、ｉ２、ｉ３、ｉ４信号入力部は、それぞれ当該ｓｎｏｄｅの上位にあるｓｎｏｄｅ、４つの子ノードとなるｓｎｏｄｅからの１ｂｉｔの入力信号であり、同様に、ｏ０、ｏ１、ｏ２、ｏ３、ｏ４信号出力部は、それぞれ当該ｓｎｏｄｅの上位にあるｓｎｏｄｅ、４つの子ノードとなるｓｎｏｄｅへの１ｂｉｔの出力信号である。
【００７０】
ＬＵＴ１０１１は、ｉ１信号入力部に接続された入力部と、ｉ２信号入力部に接続された入力部と、ｉ３信号入力部に接続された入力部と、ｉ４信号入力部に接続された入力部と、ｏ０信号出力部に接続された出力部とを具備する。ＬＵＴ１０１１の設定に応じて、入力信号ｉ１、ｉ２、ｉ３、ｉ４のいずれかが、信号ｏ０として出力される。
【００７１】
ＬＵＴ１０１２は、ｉ０信号入力部に接続された入力部と、ｉ２信号入力部に接続された入力部と、ｉ３信号入力部に接続された入力部と、ｉ４信号入力部に接続された入力部と、ｏ１信号出力部に接続された出力部とを具備する。ＬＵＴ１０１２の設定に応じて、入力信号ｉ０、ｉ２、ｉ３、ｉ４のいずれかが、信号ｏ１として出力される。
【００７２】
ＬＵＴ１０１３は、ｉ０信号入力部に接続された入力部と、ｉ１信号入力部に接続された入力部と、ｉ３信号入力部に接続された入力部と、ｉ４信号入力部に接続された入力部と、ｏ２信号出力部に接続された出力部とを具備する。ＬＵＴ１０１３の設定に応じて、入力信号ｉ０、ｉ１、ｉ３、ｉ４のいずれかが、信号ｏ２として出力される。
【００７３】
ＬＵＴ１０１４は、ｉ０信号入力部に接続された入力部と、ｉ１信号入力部に接続された入力部と、ｉ２信号入力部に接続された入力部と、ｉ４信号入力部に接続された入力部と、ｏ３信号出力部に接続された出力部とを具備する。ＬＵＴ１０１４の設定に応じて、入力信号ｉ０、ｉ１、ｉ２、ｉ４のいずれかが、信号ｏ３として出力される。
【００７４】
同様に、ＬＵＴ１０１５は、ｉ０信号入力部に接続された入力部と、ｉ１信号入力部に接続された入力部と、ｉ２信号入力部に接続された入力部と、ｉ３信号入力部に接続された入力部と、ｏ４信号出力部に接続された出力部とを具備する。ＬＵＴ１０１５の設定に応じて、入力信号ｉ０、ｉ１、ｉ２、ｉ３のいずれかが、信号ｏ４として出力される。
【００７５】
上記ｓｎｏｄｅは、ｓｔｒｅｅがＭ分木で構成された場合、隣接するＭ＋１個のｓｎｏｄｅからの入出力信号、及びＭ＋１個のＬＵＴを用いて、同様に構成することが可能である。
【００７６】
最後に、Ｇｅｎｅｒｉｃ  Ｌｏｇｉｃにおける各ＭＵＸは、各ｍｃｈａｒ＿ｎｏｄｅに供給される信号を、複数のｓｔｒｅｅからの信号候補の中から選択するための回路である。これら複数の候補の数は、Ｇｅｎｅｒｉｃ  Ｌｏｇｉｃが具備するｓｔｒｅｅと同じである。各ＭＵＸの構成は、いわゆる当業者にとって自明であるので、詳細な説明を省略する。
【００７７】
なお、上記のＧｅｎｅｒｉｃ  Ｌｏｇｉｃは、ＦＰＧＡ上で構成する場合を想定したものであり、各ＬＵＴの内部データを、Ｃｏｎｆｉｇｕｒａｔｉｏｎ  Ｃｏｎｔｒｏｌｌｅｒ１から設定されるＣｏｎｆｉｇｕｒａｔｉｏｎ  Ｄａｔａによって書き換えることで、Ｇｅｎｅｒｉｃ  Ｌｏｇｉｃ上に構成する正規表現を動的に再構成することが可能となる。なお、このようなＦＰＧＡに存在するＬＵＴの内容を変更する具体的な方法については、非特許文献３でも利用されているが、例えば、Ｘｉｌｉｎｘ社のＦＰＧＡでは、ＬＵＴをＳｈｉｆｔ  Ｒｅｇｉｓｔｅｒとして利用することが可能なＬＵＴが存在するため、このような既知の方法を利用することになる。
【００７８】
また、上記で示した各ノードの構成はあくまでも一例であって、これに限定されず、各ＬＵＴと同様の機能を複数のＬＵＴを使って構成しても良い。
【００７９】
さらに、上記のＧｅｎｅｒｉｃ  Ｌｏｇｉｃは、ＦＰＧＡ上ではなく、ＡＳＩＣのように専用ハードウェア化してチップ上に実装することもできる。この場合、各ＬＵＴによる論理真理値表を用いた論理演算がＭＵＸやＡＮＤゲートやＯＲゲート等の論理素子によって演算処理を行うハードウェア回路として実現され、Ｃｏｎｆｉｇｕｒａｔｉｏｎ  Ｄａｔａによってその動作を変更可能にする部分は、Ｆｌｉｐ−Ｆｌｏｐ（レジスタ）やメモリ等の記憶素子によって構成される。
【００８０】
上記のＧｅｎｅｒｉｃ  Ｌｏｇｉｃにおいて、状態数ＮのＮＦＡを配置することを考える。この場合、Ｎ個のｃｈａｒ＿ｎｏｄｅが存在することになるので、ｍｃｈａｒ＿ｎｏｄｅの数はＮ−１個、ＭＵＸの数はＮ−１個になる。このとき、必要なｓｔｒｅｅの数は、最大で（ｌｏｇ２Ｎ−１）×２個であり、１つのｓｔｒｅｅに存在するｓｎｏｄｅの増加量は、Ｏ（Ｎ）である。このことから、状態数Ｎに対して、全体でハードウェア量がＯ（Ｎｌｏｇ２Ｎ）で増加することになる。さらに、ｓｔｒｅｅをＭ分木で構成する場合には、ハードウェア量の増加量はＯ（ＮｌｏｇＭＮ）となることから、最大でもＯ（Ｎｌｏｇ２Ｎ）の増加量であると言える。
【００８１】
上記のような再構成可能オートマトン回路を用いることで、構文木で表現できる正規表現を、Ｇｅｎｅｒｉｃ  Ｌｏｇｉｃのｍｃｈａｒ＿ｎｏｄｅ、ｃｈａｒ＿ｎｏｄｅのノード数が許す範囲で構成することができる。利用可能なメタキャラクタに制限はあるものの、任意の正規表現の大部分は、Ｇｅｎｅｒｉｃ  Ｌｏｇｉｃが利用できる‘｜’（ＯＲ）、‘＊’（０回以上マッチ）、‘・’（連結）を用いて表現できるため、非特許文献３の課題である、構成できる正規表現の制限が緩和できるという利点がある。また、ＮＦＡの状態数Ｎに対するハードウェア量の増加量は、最大でもＯ（Ｎｌｏｇ２Ｎ）であり、特許文献１に記載されているような回路アーキテクチャにおけるハードウェア量の増加量Ｏ（Ｎ２）よりも少ないという利点がある。
【００８２】
その一方で、上記のような再構成可能オートマトン回路上に、構文木で表現された正規表現を配置するための具体的な手法が定義されていないという課題がある。特に、非特許文献４のような配置方法を用いた場合、構文木を帰りがけ順（ｐｏｓｔｏｒｄｅｒ  ｔｒａｖｅｒｓａｌ）で辿り、その順番で配置することになる。例えば、図３０に示す正規表現“ａｂ＊（ｃ｜ｄ）（ｅ｜ｆ）ｇ”の構文木を考え、メタキャラクタ‘＊’とその子ノードである‘ｂ’をマージし，‘＊ｂ’というノードを構成した場合、この構文木を辿ると、“ａ＊ｂ・ｃｄ｜・ｅｆ｜ｇ・・”となり、テキスト文字のノードと、その親ノードのメタキャラクタの対応情報を保持しておく必要があるという課題がある。
【００８３】
添付図面を参照して、本発明による再構成可能有限オートマトン回路の構成データ生成方法、生成装置および生成プログラムを実施するための形態を以下に説明する。
【００８４】
（第１の実施形態）
図１は、本発明の第１の実施の形態の再構成可能有限オートマトン回路の構成データ生成装置の構成を示すブロック図である。図１を参照すると、本発明の第１の実施の形態は、プログラム制御により動作する構成データ生成装置１と、メモリ等の記憶媒体で構成される情報を記憶する記憶装置２と、入力３と、出力４とを含む。
【００８５】
なお、本発明の第１の実施の形態では、対象とする再構成可能オートマトン回路であるＧｅｎｅｒｉｃ  Ｌｏｇｉｃにおけるｃｈａｒ＿ｎｏｄｅとして、図３８ａのような構成を考える。つまり、メタキャラクタ‘｜’、‘＊’、‘・’（連結）のみを用いた構文木で表現された正規表現のうち、メタキャラクタ‘＊’を持つノードは、子ノードのメタキャラクタとマージする、又は子ノードがテキスト文字である場合、メタキャラクタ‘＊’に空のテキスト文字を子ノードとして追加する場合の実施の形態である。
【００８６】
記憶装置２は、構文木記憶モジュール２１と、レイアウト順序記憶モジュール２２と、構成データ記憶モジュール２３とを備えている。
【００８７】
構文木記憶モジュール２１は、入力３からレイヤ番号算出モジュール１１に入力された構文木で表現された正規表現を、レイヤ番号算出モジュール１１で算出したレイヤ番号を含んだデータ構造として記憶する。また、本正規表現データは、レイアウト順序算出モジュール１２、構成データ生成モジュール１３から、それぞれの要求に応じて読み出される。
【００８８】
レイアウト順序記憶モジュール２２は、処理中の構文木で表現された正規表現の各ノードを、再構成可能オートマトン回路であるＧｅｎｅｒｉｃ  Ｌｏｇｉｃに含まれる複数のｃｈａｒ＿ｎｏｄｅ、又はｍｃｈａｒ＿ｎｏｄｅのどこに配置するかを決定するため、レイアウト順序算出モジュール１２で算出される配置順序データを記憶する。
【００８９】
構成データ記憶モジュール２３は、処理中の構文木で表現された正規表現を、Ｇｅｎｅｒｉｃ  Ｌｏｇｉｃに配置した際、構成データ生成モジュール１３で生成されるＧｅｎｅｒｉｃ  Ｌｏｇｉｃに含まれる各ｃｈａｒ＿ｎｏｄｅ、ｍｃｈａｒ＿ｎｏｄｅ、ｓｎｏｄｅ、ＭＵＸに対する構成データを記憶する。
【００９０】
構成データ生成装置１は、レイヤ番号算出モジュール１１と、レイアウト順序算出モジュール１２と、構成データ生成モジュール１３と、構成データ出力モジュール１４とを備え、入力３と出力４と接続されている。
【００９１】
レイヤ番号算出モジュール１１は、入力３から入力された構文木で表現された正規表現を読み込み、構文木の各ノードに対するレイヤ番号（ｌａｙｅｒ  ｎｕｍｂｅｒ）を算出する。また、レイヤ番号算出モジュール１１は、構文木で表現された正規表現、及びその各ノードに対して算出したレイヤ番号を記憶できるデータ構造を、構文木記憶モジュール２１に記憶させると共に、レイアウト順序算出モジュール１２に対して、処理を開始させるための信号、及び処理対象となる正規表現データを特定する信号を出力する。
【００９２】
レイアウト順序算出モジュール１２は、レイヤ番号算出モジュール１１から処理を開始する信号と、その処理対象となる正規表現データを特定する信号を受け取ると、構文木記憶モジュール２１から、対象となる構文木で表現された正規表現データを読み込み、各ノードに対するレイヤ番号を参照しながら、必要に応じて構文木における一部の部分木の入れ替え等を行い、各ノードのレイアウト順序を決定する。決定した各ノードのレイアウト順序は、それに対応する構文木の各ノードの識別子と共にレイアウト順序記憶モジュール２２に記憶させ、変更した後の構文木データを構文木記憶モジュール２１に記憶させる。また、構成データ生成モジュール１３に対して、処理を開始させるための信号、構文木記憶モジュール２１において処理対象となる構文木で表現された正規表現データを特定する信号、及び、レイアウト順序記憶モジュール２２において処理対象となるレイアウト順序データを特定する信号を出力する。
【００９３】
構成データ生成モジュール１３は、レイアウト順序算出モジュール１２から処理を開始させるための信号、構文木記憶モジュール２１において処理対象となる構文木で表現された正規表現データを特定する信号、及び、レイアウト順序記憶モジュール２２において処理対象となるレイアウト順序データを特定する信号を受け取ると、構文木記憶モジュール２１から処理対象となる構文木で表現された正規表現データを、レイアウト順序記憶モジュール２２から処理対象となるレイアウト順序データを読み出し、レイアウト順序データからＧｅｎｅｒｉｃ  Ｌｏｇｉｃ中に含まれる各ｃｈａｒ＿ｎｏｄｅ、ｍｃｈａｒ＿ｎｏｄｅに対して、構文木で表現された正規表現の各ノードを割り当てる。また、正規表現データから、各ノードに対して自身がその親ノードから見て左の子ノードなのか、右の子ノードなのか、また、自身の左右の子ノードがテキスト文字なのかを確認しながら、各ｃｈａｒ＿ｎｏｄｅ、ｍｃｈａｒ＿ｎｏｄｅが持つ複数の入出力信号のどれを用いるかを決定する。また、必要に応じてｓｔｒｅｅを利用しながら適切なｍｃｈａｒ＿ｎｏｄｅ間の接続を設定する。最後に、各ｃｈａｒ＿ｎｏｄｅ、ｍｃｈａｒ＿ｎｏｄｅ、ｓｎｏｄｅ、ＭＵＸに含まれるＬＵＴに対する構成データを生成し、その生成データをノード毎に構成データ記憶モジュール２３に記憶させると共に、構成データ出力モジュール１４に対して、処理を開始させるための信号、構成データ記憶モジュール２３において処理対象となる構成データを特定する信号を出力する。
【００９４】
なお、上記の各データを特定する信号としては、例えば、メモリに対するアドレス値等が挙げられる。
【００９５】
構成データ出力モジュール１４は、構成データ生成モジュール１３から処理を開始させるための信号、構成データ記憶モジュール２３において処理対象となる構成データを特定する信号を受け取ると、構成データ記憶モジュール２３から構成データを読み出し、実際のＧｅｎｅｒｉｃ  Ｌｏｇｉｃに設定するためのビット列として整形し、出力信号４から出力する。
【００９６】
次に、図１及び図２を参照して、本発明の第１の実施の形態の動作について詳細に説明する。図２は、本発明の第１の実施の形態の再構成可能有限オートマトン回路の構成データ生成装置の動作を示す流れ図である。言い換えれば、図２は、本発明の第１の実施の形態の再構成可能有限オートマトン回路の構成データ生成方法および生成プログラムの構成を示す流れ図である。
【００９７】
図２の流れ図は、ステップＡ１〜Ａ５を具備する。本発明の第１の実施の形態の再構成可能有限オートマトン回路の構成データ生成方法および生成プログラムが開始すると、まず、ステップＡ１に進み、その後、ステップＡ２〜Ａ５をこの順番に実行する。ステップＡ５が終了すると、本発明の第１の実施の形態の再構成可能有限オートマトン回路の構成データ生成方法および生成プログラムも終了する。
【００９８】
入力３から入力された構文木で表現された正規表現は、レイヤ番号算出モジュール１１に供給される。
【００９９】
レイヤ番号算出モジュール１１は、受け取った構文木で表現された正規表現に対して、レイヤ番号を算出する（ステップＡ１）。
【０１００】
なお、レイヤ番号算出モジュール１１において、レイヤ番号を算出する処理を行うために、図３に示すようなデータ構造を用いる。図３は、本発明の第１の実施の形態において用いる構文木で表現された正規表現を管理するデータ構造の例を示す表である。本データ構造は、構文木のノードを保持するためのものであり、自ノードの親ノードへのポインタ（ｐａｒｅｎｔ（ｐｐ））、ノードを特定するＩＤ（ｎｏｄｅ＿ｉｄ（ｉｄ））、ノードのテキスト文字、又はメタキャラクタ（ｎｏｄｅ）、自ノードが根ノードであるのか、又は自身の親ノードから見て左右のどちらの子ノードであるかを示すフラグ（ｌｅｆｔ＿ｒｉｇｈｔ（ｌｒ））、レイヤ番号（ｌａｙｅｒ＿ｎｏ（ｌｎｏ））、後で説明するが、自ノードの左右の子ノードを根とする部分木を入れ替えたことを示すフラグ（ｅｘｃｈａｎｇｅ（ｅｆｌａｇ））、自ノードの左の子ノードへのポインタ（ｌｅｆｔ＿ｃｈｉｌｄ（ｌｐ））、自ノードの右の子ノードへのポインタ（ｒｉｇｈｔ＿ｃｈｉｌｄ（ｒｐ））を保持する。なお、このうち親ノードへのポインタ、自ノードへの左右の子ノードへのポインタとしては、対象となるノードのデータ構造へのアドレス値やノードを特定するＩＤ等が考えられる。また、ノードを特定するＩＤはデータ構造に含まれなくても良いが、この際、親ノードや左右の子ノードに対するポインタとしてノードＩＤを用いることはできない。入力３から入力される構文木で表現された正規表現は、予め図３に示すデータ構造を用いて表現されていても良いし、入力後にレイヤ番号算出モジュール１１が図３に示すデータ構造を用いて表現するように変換しても良い。
【０１０１】
また、本発明の第１の実施の形態では、構文木で表現された正規表現において、メタキャラクタ‘＊’のノードに対しては、子ノードであるメタキャラクタとマージする、又は子ノードがテキスト文字である場合には、空（‘φ’）の子ノードを追加したものを対象としている。本処理は、入力３から入力される構文木で表現された正規表現に対して予め処理しておいても良いし、入力後にレイヤ番号算出モジュール１１において処理しても良い。
【０１０２】
図４は、本発明の第１の実施形態の再構成可能有限オートマトン回路の構成データ生成方法のステップＡ１のより詳細な動作を示す流れ図である。本処理は、非特許文献４に定義されている２分木ｔに対するｌａｙｅｒｓ（ｔ）に従ったものであるが、具体的に各ノードに対するレイヤ番号を算出する処理手順を示している。
【０１０３】
図４の流れ図は、第１および第２の再帰的ステップＡ１と、ステップＢ１〜Ｂ５とを具備する。
【０１０４】
ステップＡ１の動作について説明する。ステップＡ１が開始すると、まず、ステップＢ１に進む。
【０１０５】
ステップＢ１では、処理ノードが子ノードを持つかどうかを判断する。処理ノードが子ノードを持つ場合（Ｙｅｓ）は第１の再帰的ステップＡ１に進む。処理ノードが子ノードを持たない場合（Ｎｏ）はステップＢ２に進む。
【０１０６】
ステップＢ２では、処理ノードのレイヤ番号に０を代入する。ステップＢ２が終了すると、ステップＡ１自体も終了する。
【０１０７】
第１の再帰的ステップＡ１では、ステップＡ１を再帰的に呼び出して、左の子ノードに対してレイヤ番号の算出を行う。第１の再帰的ステップＡ１が終了すると、第２の再帰的ステップＡ２に進む。
【０１０８】
第２の再帰的ステップＡ１では、ステップＡ１を再帰的に呼び出して、右の子ノードに対してレイヤ番号の算出を行う。第２の再帰的ステップＡ１が終了すると、ステップＢ３に進む。
【０１０９】
ステップＢ３では、左右の子ノードのレイヤ番号が等しいかどうかを判断する。左右の子ノードのレイヤ番号が等しい場合（Ｙｅｓ）は、ステップＢ４に進む。左右の子ノードのレイヤ番号が異なる場合（Ｎｏ）は、ステップＢ５に進む。
【０１１０】
ステップＢ４では、左の子ノードのレイヤ番号＋１を算出して、処理ノードのレイヤ番号に代入する。ステップＢ４が終了すると、ステップＡ１自体も終了する。
【０１１１】
ステップＢ５では、左の子ノードのレイヤ番号と、右の子ノードのレイヤ番号から、最大の値を選んで、処理ノードのレイヤ番号に代入する。ステップＢ５が終了すると、ステップＡ１自体も終了する。
【０１１２】
ここで、本発明の再構成可能有限オートマトン回路の構成データ生成装置のレイヤ番号算出モジュールは、上記の各ステップにそれぞれ対応する機能モジュールを具備する構成とすることが可能である。この場合、レイヤ番号算出モジュールは、特に、ステップＢ４およびＢ５の動作をそれぞれ行う第１および第２のレイヤ番号設定モジュールを具備する構成とすることが出来る。
【０１１３】
また、ステップＡ１のより具体的な動作例として、図３０に示す構文木で表現された正規表現“ａｂ＊（ｃ｜ｄ）（ｅ｜ｆ）ｇ”を挙げて説明する。なお、以下では、レイヤ番号算出モジュール１１に入力された構文木で表現された正規表現データは、図３に示すデータ構造を用いて表現されており、また、メタキャラクタ‘＊’の子ノードがテキスト文字であるため、図５に示すように、空（φ）の子ノードが追加されているものとする。図５は、本発明の第１の実施の形態においてメタキャラクタ‘＊’の子ノードに空（φ）を追加した正規表現“ａｂ＊（ｃ｜ｄ）（ｅ｜ｆ）ｇ”の構文木の一例である。このため、このときの構文木で表現された正規表現“ａｂ＊（ｃ｜ｄ）（ｅ｜ｆ）ｇ”は図６のようなデータ構造となっているものとする。図６は、本発明の第１の実施の形態において処理対象とする正規表現“ａｂ＊（ｃ｜ｄ）（ｅ｜ｆ）ｇ”の構文木の一例である。なお、図６では、図３のデータ構造のうち、自ノードの親ノードへのポインタ（ｐａｒｅｎｔ（ｐｐ））、自ノードの左の子ノードへのポインタ（ｌｅｆｔ＿ｃｈｉｌｄ（ｌｐ））、自ノードの右の子ノードへのポインタ（ｒｉｇｈｔ＿ｃｈｉｌｄ（ｒｐ））は双方向の矢印で図示しており、レイヤ番号（ｌａｙｅｒ＿ｎｏ（ｌｎｏ））の初期値を−１、自ノードの左右の子ノードを根とする部分木を入れ替えたことを示すフラグ（ｅｘｃｈａｎｇｅ（ｅｆｌａｇ））の初期値を入れ替えていないことを示す０としている。
【０１１４】
レイヤ番号算出モジュール１１は、入力された構文木で表現された正規表現の根ノードから処理を開始する。まず、当該処理ノードが子ノードを持つかどうかを判断する（ステップＢ１）。当該処理ノードが子ノードを持つ場合、必ず左右の子ノードをもつため、まず左の子ノードに対して、レイヤ番号算出処理（ステップＡ１）を行う。以下、同様に、当該処理ノードが子ノードを持たない、つまり葉ノードに辿り着くと、当該処理ノードは子ノードを持たないため、処理ノードのレイヤ番号を０とし（ステップＢ２）、処理を終了する。
【０１１５】
一方、左の子ノードに対してレイヤ番号算出処理（ステップＡ１）が終了すると、今度は同様に、右の子ノードに対してレイヤ番号算出処理（ステップＡ１）を行う。
【０１１６】
右の子ノードに対するレイヤ番号算出処理（ステップＡ１）が終了すると、左右の子ノードに対するレイヤ番号が既に算出されているため、これら左右の子ノードのレイヤ番号を比較する（ステップＢ３）。左右の子ノードのレイヤ番号が等しい場合、処理ノードのレイヤ番号は、左の子ノードのレイヤ番号に１を加えたものとし、処理を終了する。一方、左右の子ノードのレイヤ番号が異なる場合には、処理ノードのレイヤ番号は、処理ノードの左右の子ノードのレイヤ番号のうち、大きい方のレイヤ番号とし、処理を終了する。
【０１１７】
上記の処理を、図６に示す構文木に対して行った例を以下に説明する。レイヤ番号算出モジュール１１は、構文木の根ノードから処理を開始するため、この場合、図６に示すノードＩＤが０（以下、ノード０のように表す）の根ノードは子ノードを持つため、左の子ノード（ノード１）に対して、レイヤ番号算出処理（ステップＡ１）を行う。同様にして、ノード３、ノード７と再帰的にレイヤ番号算出処理（ステップＡ１）を進める。ノード７に対するレイヤ番号算出処理を開始すると、ノード７は子ノードを持たないため（ステップＢ１）、ノード７のレイヤ番号は０とし（ステップＢ２）、処理を終了して、ノード３の処理に戻る。
【０１１８】
次に、ノード３の右の子ノードであるノード８に対してレイヤ番号算出処理（ステップＡ１）を行うが、ノード８は子ノードを持つため、左の子ノード１３に対してレイヤ番号算出処理（ステップＡ１）を行い、ノード１３のレイヤ番号が０となる。
【０１１９】
以下、同様に処理を行っていくことで、全てのノードのレイヤ番号が算出される。図７は、本発明の第１の実施の形態においてレイヤ番号算出処理（ステップＡ１）が終了した時点での正規表現“ａｂ＊（ｃ｜ｄ）（ｅ｜ｆ）ｇ”の構文木の一例である。各ノードのレイヤ番号（ｌｎｏ）に算出された値が保持されている。
【０１２０】
レイヤ番号算出モジュール１１は、レイヤ番号算出処理（ステップＡ１）が終了すると、図７のようなデータ構造で保持した構文木で表現された正規表現データを、構文木記憶モジュール２１に記憶させると共に、レイアウト順序算出モジュール１２に対して、処理を開始させるための信号、及び処理対象となる正規表現データを特定する信号を出力する。
【０１２１】
レイアウト順序算出モジュール１２は、レイヤ番号算出モジュール１１から処理を開始する信号と、その処理対象となる正規表現データを特定する信号を受け取ると、構文木記憶モジュール２１から、対象となる構文木で表現された正規表現データを読み込む。次に、各ノードに対するレイヤ番号を参照しながら、各ノードのレイアウト順序を決定する（ステップＡ２）。
【０１２２】
ここで、再構成可能オートマトン回路であるＧｅｎｅｒｉｃ  Ｌｏｇｉｃでは、非特許文献４に記載されたように、２分木である構文木で表現された各ノードを、帰りがけ順（ｐｏｓｔｏｒｄｅｒ  ｔｒａｖｅｒｓａｌ）にて辿り、それぞれ配置していくが、本手法では、通りがけ順（ｉｎｏｒｄｅｒ  ｔｒａｖｅｒｓａｌ）を基本とした辿り方で辿り、配置順序を決定する。以下では、この配置方法について説明する。
【０１２３】
図８ａ、図８ｂ、図８ｃは、通りがけ順による２分木のノード配置における、セルとｌａｙｅｒｓ（ｔ）について説明するための概念図である。２分木ｔの根ノードの左右の子ノードを根とする部分木をそれぞれ、部分木（Ｌｅｆｔ−Ｓｕｂｔｒｅｅ）ｌ、部分木（Ｒｉｇｈｔ−Ｓｕｂｔｒｅｅ）ｒとすると、図８ａはｌａｙｅｒｓ（ｌ）≧ｌａｙｅｒｓ（ｒ）の場合の２分木ｔに対する配置、図８ｂはｌａｙｅｒｓ（ｌ’）≧ｌａｙｅｒｓ（ｒ’）の場合の２分木ｔの根ノードの左の部分木に対する配置、図８ｃはｌａｙｅｒｓ（ｌ’）≦ｌａｙｅｒｓ（ｒ’）の場合の２分木ｔの根ノードの右の部分木に対する配置を示す概念図である。なお、図８ｂにおいて、部分木ｌの根ノードの左の子ノードを根とする部分木、右の子ノードを根とする部分木をそれぞれ部分木（Ｌｅｆｔ−Ｓｕｂｔｒｅｅ）ｌ’、部分木（Ｒｉｇｈｔ−Ｓｕｂｔｒｅｅ）ｒ’とする。図８ｃにおいても同様、部分木ｒの根ノードの左の子ノードを根とする部分木、右の子ノードを根とする部分木をそれぞれ部分木（Ｌｅｆｔ−Ｓｕｂｔｒｅｅ）ｌ’、部分木（Ｒｉｇｈｔ−Ｓｕｂｔｒｅｅ）ｒ’とする。また、図８ａでは、ｌａｙｅｒｓ（ｌ）＜ｌａｙｅｒｓ（ｒ）の場合には、部分木ｌ、部分木ｒを入れ替えることで図８ａに対応し、図８ｂでは、ｌａｙｅｒｓ（ｌ’）＜ｌａｙｅｒｓ（ｒ’）の場合、図８ｃでは、ｌａｙｅｒｓ（ｌ’）＞ｌａｙｅｒｓ（ｒ’）の場合に、部分木ｌ’と部分木ｒ’を入れ替えることで、それぞれ図８ｂ、図８ｃに対応する。その他、２分木ｔに対するｌａｙｅｒｓ（ｔ）、セルの構成等については非特許文献４に記載の２分木ｔのノード配置の説明と同様であるため、説明を省略する。
【０１２４】
本配置方法では、２分木ｔの各ノードを通りがけ順によって辿ればノードの配置順が決まる。これによると、図８ａに示すように、根ノードは根ノードの左の子ノードを根とする部分木ｌの各ノードと右の子ノードの根とする部分木ｒの間に配置され、根ノードの左の子ノードを根とする部分木ｌは根ノードの左側、根ノードの右の子ノードを根とする部分木ｒは根ノードの右側に配置する。但し、ｌａｙｅｒｓ（ｌ）とｌａｙｅｒｓ（ｒ）のうち、大きなｌａｙｅｒｓの値をもつ部分木を左の部分木としている。つまり、ｌａｙｅｒｓ（ｌ）よりもｌａｙｅｒｓ（ｒ）の方が大きければ、左の部分木ｌと右の部分木ｒを入れ替える。また、図８ｂに示すように、部分木ｌの根ノードの左の子ノードを根とする部分木ｌ’と右の子ノードを根とする部分木ｒ’に対しては、ｌａｙｅｒｓ（ｌ’）とｌａｙｅｒｓ（ｒ’）のうち、大きなｌａｙｅｒｓの値をもつ部分木を左の部分木とし、ｌａｙｅｒｓ（ｌ’）よりもｌａｙｅｒｓ（ｒ’）の方が大きければ、左の部分木ｌ’と右の部分木ｒ’を入れ替える。一方、図８ｃに示すように、部分木ｒの根ノードの左の子ノードを根とする部分木ｌ’と右の子ノードを根とする部分木ｒ’に対しては、ｌａｙｅｒｓ（ｌ’）とｌａｙｅｒｓ（ｒ’）のうち、大きなｌａｙｅｒｓの値をもつ部分木を右の部分木とし、ｌａｙｅｒｓ（ｒ’）よりもｌａｙｅｒｓ（ｌ’）の方が大きければ、左の部分木ｌ’と右の部分木ｒ’を入れ替える。
【０１２５】
このとき、ノード数ｎ（ｎ＞０）の任意の２分木ｔは、ｎ×（ｌａｙｅｒｓ（ｔ））個のセルで配置できることが分かる。
【０１２６】
図８ａの場合、２分木ｔは、ｎ×（ｌａｙｅｒｓ（ｌ）＋１）セルで配置されている。この場合、ｌａｙｅｒｓ（ｔ）＝ｌａｙｅｒｓ（ｌ）となるため、ｎ×（ｌａｙｅｒｓ（ｔ）＋１）セルで配置可能である。また、この配置に必要なセルは、ｌａｙｅｒｓ（ｌ）とｌａｙｅｒｓ（ｒ）が等しい場合も同様であり、ｎ×（ｌａｙｅｒｓ（ｔ）＋１）セルで配置可能である。
【０１２７】
これは、以下のように説明することができる。ある２分木ｔの根ノードではなく、葉ノードでもないノードｉに対して、このノードｉを根とする部分木ｉに対するｌａｙｅｒｓ（ｉ）を考える。これを帰りがけ順で辿った場合、ノードｉから、ｌａｙｅｒｓ（ｉ）に相当するＲｏｕｔｉｎｇ  Ｌａｙｅｒを経由して接続する相手ノードは、ノードｉの左の子ノードとなる。一方、通りがけ順で辿った場合、ノードｉから、ｌａｙｅｒｓ（ｉ）に相当するＲｏｕｔｉｎｇ  Ｌａｙｅｒを経由して接続する相手ノードは、ノードｉの親ノードとなる。つまり、２分木ｔを通りがけ順で配置する場合、根ノードの左の子ノードを根とする部分木ｌでは、ｌａｙｅｒｓの値が大きな部分木を左側（根ノードから見て外側）に配置し、根ノードの右の子ノードを根とする部分木ｒでは、ｌａｙｅｒｓの値が大きな部分木を右側（根ノードから見て外側）に配置することにより、根ノードから左の子ノード、右の子ノードへの接続を根ノードの両隣のノードを経由して行うことで、それぞれ部分木ｌ、部分木ｒを配置するセルの中に隠蔽できるためである。
【０１２８】
ここで、Ｎ文字のメタキャラクタと、Ｎ＋１文字のテキスト文字を含む正規表現を表す有限オートマトン回路であるＧｅｎｅｒｉｃ  Ｌｏｇｉｃを考える。このとき、ノード数Ｎの２分木に必要なＲｏｕｔｉｎｇ  Ｌａｙｅｒ数は、上記の非特許文献４より、最大ｌｏｇ２（Ｎ＋１）−１となる。なお、ノード数２ｎ−１＝Ｎとすると、ｎ＝ｌｏｇ２（Ｎ＋１）であることから、Ｒｏｕｔｉｎｇ  Ｌａｙｅｒ数は最大ｎ−１＝ｌｏｇ２（Ｎ＋１）−１であることは明らかである。
【０１２９】
このＲｏｕｔｉｎｇ  Ｌａｙｅｒは、２分木の各ノードを一列に配置した場合に、その接続を正しく行うために必要な水平方向のチャネルであり、Ｇｅｎｅｒｉｃ  Ｌｏｇｉｃにおけるｍｃｈａｒ＿ｎｏｄｅを葉ノード、ｓｎｏｄｅをノードとした２分木構造（ｓｔｒｅｅ）の必要数に関連する。本手法が対象とする再構成可能オートマトン回路であるＧｅｎｅｒｉｃ  Ｌｏｇｉｃでは、２分木ｔの各ノードを帰りがけ順によって辿ったが、本手法では、これを通りがけ順で辿る。帰りがけ順で辿った場合には、各ノードに対して算出されたレイヤ番号に対して、利用するＲｏｕｔｉｎｇ  Ｌａｙｅｒは、当該ノードと当該ノードの左の子ノードとの接続に相当するが、本手法のように通りがけ順で辿って配置する場合には、各ノードに対して算出されたレイヤ番号に対して、利用するＲｏｕｔｉｎｇ  Ｌａｙｅｒは、当該ノードと当該ノードの親ノードとの接続に相当する。つまり、必要なＲｏｕｔｉｎｇ  Ｌａｙｅｒ数は、帰りがけ順で辿った場合よりも、見かけ上１少なくて済むという利点がある。
【０１３０】
また、ｓｔｒｅｅには、あるｍｃｈａｒ＿ｎｏｄｅ間を接続した場合に利用できる当該ｍｃｈａｒ＿ｎｏｄｅ間には双方向の信号線が具備されているが、帰りがけ順で辿った場合の説明で用いた図３６ｂと同様、同じレイヤ番号に相当するｍｃｈａｒ＿ｎｏｄｅ間の接続が、同一ｓｎｏｄｅ間の信号線を利用しなければならない場合がある。このため、Ｇｅｎｅｒｉｃ  Ｌｏｇｉｃにおけるｓｔｒｅｅの数は、必要なＲｏｕｔｉｎｇ  Ｌａｙｅｒの２倍の数が必要となる。厳密に言えば、Ｇｅｎｅｒｉｃ  Ｌｏｇｉｃに具備されるｍｃｈａｒ＿ｎｏｄｅの数が少ない場合には、Ｒｏｕｔｉｎｇ  Ｌａｙｅｒと同数でも良いが、一般的には、２倍の数だけ必要となる。
【０１３１】
以上をまとめると、本発明において、Ｎ文字のメタキャラクタと、Ｎ＋１文字のテキスト文字を含む正規表現を構築する場合、Ｇｅｎｅｒｉｃ  Ｌｏｇｉｃは、以下の方法で構築することができる。
（１）  ｍｃｈａｒ＿ｎｏｄｅをＮ個、ｃｈａｒ＿ｎｏｄｅをＮ＋１個配置する。
（２）  Ｎ個のｍｃｈａｒ＿ｎｏｄｅを葉ノードとし、ｓｎｏｄｅを葉ではないノードとする２分木（ｓｔｒｅｅ）をＢ個用意する。ここで、２分木の必要数Ｂは、Ｂ＝［ｌｏｇ２（Ｎ＋１）−２］×２であり、［ｘ］は、ｘを下回らない最小の整数を意味する。但し、Ｂが負になった場合、Ｂ＝０とする。
（３）  各ＭＵＸはＢ入力のＭＵＸとする。
【０１３２】
図９は、ノード数が１５である図３５に示す２分木を、上記通りがけ順に従ってセルに配置した結果を示す図である。
【０１３３】
図１０は、本発明の第１の実施の形態のステップＡ２のより詳細な動作を説明するための流れ図である。
【０１３４】
レイアウト順序算出モジュール１２は、構文木記憶モジュール２１から読み込んだ構文木で表現された正規表現の根ノードから処理を開始する。本ステップでは、グローバル変数ｃｏｌを用いる。これは、本処理で算出する通りがけ順で辿った順番を示したものであり、レイアウト順序である。なお、変数ｃｏｌの初期値を−１とする。
【０１３５】
まず、ステップＣ１処理ノードが存在するかを確認する（ステップＣ１）。処理ノードが存在しない場合（Ｎｏ）は、そのまま処理を終了する。処理ノードが存在する場合（Ｙｅｓ）、構文木記憶モジュール２１から読み込んだ構文木で表現された正規表現データのｌｅｆｔ＿ｒｉｇｈｔ（ｌｒ）をチェックし、本処理ノードが左の子ノードであるかを確認する（ステップＣ２）。ここで、根ノード（ｒｏｏｔ）については左の子ノードとして扱う。なお、根ノード（ｒｏｏｔ）については、右の子ノードとして扱って、レイアウト順序算出処理（ステップＡ２）を行っても良いが、どちらの子ノードとして扱うかは、統一しておく必要がある。
【０１３６】
次に、当該処理ノードが左の子ノードであった場合（Ｙｅｓ）、自身の左の子ノードのレイヤ番号よりも自身の右の子ノードのレイヤ番号の方が大きいかをチェックし（ステップＣ３）、大きい場合（Ｙｅｓ）には、自身のノードの左右の子ノードを根とする部分木を入れ替え、入れ替えた後の左右の子ノードのｌｅｆｔ＿ｒｉｇｈｔ（ｌｒ）が入れ替えた後の正しい値（ｌｅｆｔかｒｉｇｈｔか）に再設定すると共に、自ノードの左右の子ノードを根とする部分木を入れ替えたことを示すフラグ（ｅｘｃｈａｎｇｅ（ｅｆｌａｇ））を１に設定する（ステップＣ５）。逆に、当該処理ノードが右の子ノードであった場合（Ｎｏ）、自身の左の子ノードのレイヤ番号が自身の右の子ノードのレイヤ番号よりも大きいかをチェックし（ステップＣ４）、大きい場合（Ｙｅｓ）には、自身のノードの左右の子ノードを根とする部分木を入れ替え、入れ替えた後の左右の子ノードのｌｅｆｔ＿ｒｉｇｈｔ（ｌｒ）が入れ替えた後の正しい値（ｌｅｆｔかｒｉｇｈｔか）に再設定すると共に、自ノードの左右の子ノードを根とする部分木を入れ替えたことを示すフラグ（ｅｘｃｈａｎｇｅ（ｅｆｌａｇ））を１に設定する（ステップＣ５）。
【０１３７】
上記の処理を行った上で、自ノードの左の子ノードに対してレイアウト順序算出処理を行う（ステップＡ２）。なお、この際の左の子ノードは、ステップＣ５にて左右の部分木を入れ替えた場合には、入れ替えた後の構文木に対して行う。
【０１３８】
左の子ノードに対するレイアウト順序算出処理（ステップＡ２）が終了すると、現在の変数ｃｏｌを１だけ増加させ（ステップＣ６）、当該処理ノードのレイアウト順序を変数ｃｏｌの値として設定する（ステップＣ７）。ここで、レイアウト順序算出モジュール１２において、レイアウト順序を管理するため、図１１に示すようなレイアウト順序管理配列ｌａｙｏｕｔを用いる。図１１は、レイアウト順序管理配列ｌａｙｏｕｔの一例を示す表である。本配列には、ｌａｙｏｕｔ［ｉ］は、レイアウト順序ｉに対応するｎｏｄｅ＿ｉｄを格納し、レイアウト順序と正規表現のノードの対応関係を管理する。なお、ｎｏｄｅ＿ｉｄは、構文木で表現された正規表現データの各ノードに対するポインタでも良い。また、管理するためのデータ構造は、配列でなくても良く、構文木で表現された正規表現データ内に直接レイアウト順序を保持させ、以降の処理では、各ノードを辿りながら対象となるレイアウト順序と当該ノードを特定させても良い。
【０１３９】
続いて、当該処理ノードの右の子ノードに対してレイアウト順序算出処理を行い（ステップＡ２）、その処理が終わると、本処理を終了する。
【０１４０】
レイアウト順序算出モジュール１２は、全てのノードに対して上記処理を終了させると、レイアウト順序管理配列ｌａｙｏｕｔをレイアウト順序記憶モジュール２２、変更した後の構文木データを構文木記憶モジュール２１に記憶させると共に、構成データ生成モジュール１３に対して、処理を開始させるための信号、構文木記憶モジュール２１において処理対象となる構文木で表現された正規表現データを特定する信号、及び、レイアウト順序記憶モジュール２２において処理対象となるレイアウト順序データを特定する信号を出力する。
【０１４１】
ここで、本発明の再構成可能有限オートマトン回路の構成データ生成装置のレイアウト順序算出モジュールは、上記の各ステップにそれぞれ対応する機能モジュールを具備する構成とすることが可能である。この場合、レイアウト順序算出モジュールは、特に、ステップＣ５の動作を行う部分木入れ替えモジュールと、ステップＣ６およびＣ７の動作を行うレイアウト順序設定モジュールとを具備する構成とすることが出来る。
【０１４２】
上記の処理を、図７に示す構文木に対して行った例を以下に説明する。レイアウト順序算出モジュール１２は、構文木記憶モジュール２１から図７に示す構文木データを読み込み、根ノードから処理を開始する。
【０１４３】
この場合、図７に示すノード０から処理を開始する。処理ノードは存在するため（ステップＣ１）、ノード０が左の子ノードであるかをチェックする（ステップＣ２）。この場合、根ノードを左の子ノードとして扱うものとすると、ノード０は左の子ノードであるため、ノード０の左の子ノード（ノード１）と右の子ノード（ノード２）のレイヤ番号の大小比較を行う（ステップＣ４）。この場合、左の子ノードであるノード１のレイヤ番号の方が大きいため、左の子ノードであるノード１に対して、レイアウト順序算出処理（ステップＡ２）を行う。
【０１４４】
続いて、ノード１は存在するため（ステップＣ１）、ノード１が左の子ノードであるかをチェックし（ステップＣ２）、ノード１の左の子ノード（ノード３）と右の子ノード（ノード４）のレイヤ番号の大小比較を行う（ステップＣ４）。この場合、左の子ノードであるノード３のレイヤ番号は右の子ノードであるノード４のレイヤ番号と等しいため、左の子ノードであるノード３に対して、レイアウト順序算出処理（ステップＡ２）を行う。
【０１４５】
同様に、ノード３は存在するため（ステップＣ１）、ノード３が左の子ノードであるかをチェックし（ステップＣ２）、ノード３の左の子ノード（ノード７）と右の子ノード（ノード８）のレイヤ番号の大小比較を行う（ステップＣ３）。この場合、左の子ノードであるノード７のレイヤ番号は右の子ノードであるノード８のレイヤ番号よりも小さいため、ノード７を根とする部分木とノード８を根とする部分木を入れ替え、ノード７、ノード８の親ノードから見て左右どちらの子ノードであるかを示すフラグｌｅｆｔ＿ｒｉｇｈｔ（ｌｒ）をそれぞれ右ノード、左ノードに再設定すると共に、処理ノードであるノード３の左右の子ノードを根とする部分木を入れ替えたことを示すフラグ（ｅｘｃｈａｎｇｅ（ｅｆｌａｇ））を１に設定し、入れ替えた後の左の子ノードであるノード８に対して、レイアウト順序算出処理（ステップＡ２）を行う。
【０１４６】
同様に、ノード８、ノード１３に対して処理を行う。ノード１３に対する処理において、ノード１３には左の子ノードが存在しないため、変数ｃｏｌを１増加させ（ｃｏｌ＝０となる）（ステップＣ６）、処理ノードであるノード１３のレイアウト順序を変数ｃｏｌの０と設定し、ノード８の処理に戻る。
【０１４７】
上記のように、各ノードに対して、再帰的にレイアウト順序算出処理（ステップＡ２）を行うことで、全てのノードに対するレイアウト順序が決定する。図１２は、本発明の第１の実施の形態においてレイアウト順序算出処理（ステップＡ２）が終了した時点での正規表現“ａｂ＊（ｃ｜ｄ）（ｅ｜ｆ）ｇ”の構文木の一例である。図７の構文木に対して、一部の部分木が左右入れ替わっていると共に、入れ替えた部分木の根ノードの親ノードにおける左右の子ノードを根とする部分木を入れ替えたことを示すフラグ（ｅｘｃｈａｎｇｅ（ｅｆｌａｇ））が１に設定されている。また、図１１に示すレイアウト順序管理配列の一例は、上記の例の処理を完了させた際のレイアウト順序とそれに対応する各ノードを示している。
【０１４８】
構成データ生成モジュール１３は、レイアウト順序算出モジュール１２から処理を開始させるための信号、構文木記憶モジュール２１において処理対象となる構文木で表現された正規表現データを特定する信号、及び、レイアウト順序記憶モジュール２２において処理対象となるレイアウト順序データを特定する信号を受け取ると、構文木記憶モジュール２１から処理対象となる構文木で表現された正規表現データを、レイアウト順序記憶モジュール２２から処理対象となるレイアウト順序データを読み出し、レイアウト順序データからＧｅｎｅｒｉｃ  Ｌｏｇｉｃ中に含まれる各ｃｈａｒ＿ｎｏｄｅ、ｍｃｈａｒ＿ｎｏｄｅに対して、構文木で表現された正規表現の各ノードを割り当てる（ステップＡ３）。また、正規表現データから、各メタキャラクタノードに対して自身がその親ノードから見て左の子ノードなのか、右の子ノードなのか、また、自身の左右の子ノードがテキスト文字なのかを確認しながら、各ｍｃｈａｒ＿ｎｏｄｅが持つ複数の入出力信号のどれを用いるかを決定する。また、必要に応じてｓｔｒｅｅを利用しながら適切なｍｃｈａｒ＿ｎｏｄｅ間の接続を設定する（ステップＡ３）。最後に、各ｃｈａｒ＿ｎｏｄｅ、ｍｃｈａｒ＿ｎｏｄｅ、ｓｎｏｄｅ、ＭＵＸに含まれるＬＵＴに対する構成データを生成し、その生成データをノード毎に構成データ記憶モジュール２３に記憶させると共に、構成データ出力モジュール１４に対して、処理を開始させるための信号、構成データ記憶モジュール２３において処理対象となる構成データを特定する信号を出力する（ステップＡ４）。
【０１４９】
図１３は、本発明の第１の実施の形態のステップＡ３のより詳細な動作を説明するための流れ図である。これを参照しながら、図１２に示す構文木に対する処理例を用いて以下に説明する。構成データ生成モジュール１３は、構文木記憶モジュール２１から図１２のような正規表現データを、レイアウト順序記憶モジュール２２から図１１のようなレイアウト順序データを読み出す。
【０１５０】
図１１のレイアウト順序データは、テキスト文字を示すノードから始まっており、テキスト文字を示すノードとメタキャラクタを示すノードが交互に繰り返される。このため、当該Ｇｅｎｅｒｉｃ  Ｌｏｇｉｃの左端にあるｃｈａｒ＿ｎｏｄｅ、ｍｃｈａｒ＿ｎｏｄｅから、レイアウト順序データの順番にそれぞれのテキスト文字、メタキャラクタを各ノードに割り当てる（ステップＤ１）。例えば、レイアウト順序管理配列の最初のノードであるノード１３は、テキスト文字‘ｂ’であり、これはＧｅｎｅｒｉｃ  Ｌｏｇｉｃにおける最も左のｃｈａｒ＿ｎｏｄｅに、レイアウト順序管理配列の次のノードであるノード８はメタキャラクタノードであり、これはＧｅｎｅｒｉｃ  Ｌｏｇｉｃにおける最も左のｍｃｈａｒ＿ｎｏｄｅに、続くノード１４は、テキスト文字‘φ’（空を示す）であり、これはＧｅｎｅｒｉｃ  Ｌｏｇｉｃにおける最も左のｃｈａｒ＿ｎｏｄｅの１つ右隣のｃｈａｒ＿ｎｏｄｅに、といった具合に順次割り当てを行っていく。図１４は、本発明の第１の実施の形態において正規表現“ａｂ＊（ｃ｜ｄ）（ｅ｜ｆ）ｇ”をＧｅｎｅｒｉｃ  Ｌｏｇｉｃの各ｃｈａｒ＿ｎｏｄｅ、ｍｃｈａｒ＿ｎｏｄｅに割り当てた場合の一例である。なお、図１４のＧｅｎｅｒｉｃ  Ｌｏｇｉｃは、ｍｃｈａｒ＿ｎｏｄｅを７個、ｃｈａｒ＿ｎｏｄｅを８個有する場合の構成であり、割り当てが確定したｍｃｈａｒ＿ｎｏｄｅ、ｃｈａｒ＿ｎｏｄｅのみ太線で示し、その他は点線で示している。また、Ｇｅｎｅｒｉｃ  Ｌｏｇｉｃの下に示すレイアウト順序管理配列は、レイアウト順序記憶モジュール２２に記憶されているレイアウト順序データに対して、当該ノードに対応するノードを示す領域を追記したものである。
【０１５１】
さらに、上記割り当て処理が完了したｍｃｈａｒ＿ｎｏｄｅに対して、当該メタキャラクタノードが、自身の親ノードから見て左の子ノードなのか、右の子ノードなのか、また、自身の左右の子ノードがテキスト文字なのかを確認しながら、ｍｃｈａｒ＿ｎｏｄｅが持つ複数の入出力信号のどれを用いるかを示す構成モデルを決定する（ステップＤ２）。ここで、図１５ａ〜図１５ｈは、各メタキャラクタノードが自身の親ノードから見て左の子ノードなのか、右の子ノードなのか、自身は左の子ノードとしてテキスト文字のノードをもつのか、右の子ノードとしてテキスト文字のノードを持つのかによって決定される構成モデルを示す。
【０１５２】
図１５ａは、自身が親ノードから見て左の子ノードであり、自身の左の子ノード、右の子ノードが共にテキスト文字であるノードに対する構成モデルを示す図である。図１５ｂは、自身が親ノードから見て右の子ノードであり、自身の左の子ノード、右の子ノードが共にテキスト文字であるノードに対する構成モデルを示す図である。図１５ｃは、自身が構文木の根ノードであり、自身の左の子ノード、右の子ノードが共にテキスト文字であるノードに対する構成モデルを示す図である。図１５ｄは、自身が親ノードから見て左右どちらかの子ノードであり、自身の左の子ノードがテキスト文字であるノードに対する構成モデルを示す図である。図１５ｅは、自身が構文木の根ノードであり、自身の左の子ノードがテキスト文字であるノードに対する構成モデルを示す図である。図１５ｆは、自身が親ノードから見て左右どちらかの子ノードであり、自身の右の子ノードがテキスト文字であるノードに対する構成モデルを示す図である。図１５ｇは、自身が構文木の根ノードであり、自身の右の子ノードがテキスト文字であるノードに対する構成モデルを示す図である。図１５ｈは、自身が親ノードから見て左右どちらかの子ノード、又は構文木の根ノードであり、自身の左右の子ノードはどちらもテキスト文字でないノードに対する構成モデルを示す図である。
【０１５３】
なお、本手法のように通りがけ順を用いた場合、この構成モデルは、上記の組み合わせによって、図１５ａ〜図１５ｈまでの８パターンに分類することができる。なお、図１５ａ〜図１５ｈにおいて、中心の丸が自身のｍｃｈａｒ＿ｎｏｄｅを示し、上、左右、下の左右にある５つの黒丸（Ｐ、Ｌ、Ｒ、ｌ、ｒ）のノードは、それぞれ、当該ｍｃｈａｒ＿ｎｏｄｅの上部にあるｓｎｏｄｅ、左に隣接するｍｃｈａｒ＿ｎｏｄｅ、右に隣接するｍｃｈａｒ＿ｎｏｄｅ、左に隣接するｃｈａｒ＿ｎｏｄｅ、右に隣接するｃｈａｒ＿ｎｏｄｅを示す。また、各ノードからの実線で示された入出力信号を用いるものとし、自身のｍｃｈａｒ＿ｎｏｄｅ内を通過して接続されている実線は、自ノード内を通過させることを意味する。また、ｎｐ、ｎｌ、ｎｒは、自ノードの親ノード、左の子ノード、右の子ノードの位置関係を示している。
【０１５４】
ステップＤ１までが完了した図１４の各ノードに対する処理例を以下に示す。Ｇｅｎｅｒｉｃ  Ｌｏｇｉｃにおける各ｃｈａｒ＿ｎｏｄｅ、ｍｃｈａｒ＿ｎｏｄｅに対する割り当て処理（ステップＤ１）が完了すると、続いて各ｍｃｈａｒ＿ｎｏｄｅに注目し、構成モデルを決定する（ステップＤ２）。図１４に示す例の場合、まずｍｃｈａｒ＿ｎｏｄｅ３００に注目する。本ノードに割り当てられたメタキャラクタ‘＊’（ノード８）は、図１２の正規表現データから、親ノード３の左の子ノードであり、自身の左右の子ノードは共にテキスト文字であることから、図１５ａに示す構成モデルが適用されることが分かり、どの入出力信号線を利用するべきかが判定できる。同様に、ｍｃｈａｒ＿ｎｏｄｅ３０１のメタキャラクタ‘・’（ノード３）は、親ノード１の左の子ノードであり、自身の右の子ノードであるノード７だけがテキスト文字であるため、図１５ｆの構成モデルを、ｍｃｈａｒ＿ｎｏｄｅ３０２のメタキャラクタ‘・’（ノード１）は、親ノード０の左の子ノードであり、自身の左右の子ノードはいずれもテキスト文字ではないため、図１５ｈの構成モデルを適用し、それぞれのモデルに応じた入出力信号線を利用することが判定できる。図１６は、本発明の第１の実施の形態において図１４の全てのｍｃｈａｒ＿ｎｏｄｅに対して構成モデルの決定処理（ステップＤ２）を行った後のＧｅｎｅｒｉｃ  Ｌｏｇｉｃの一例を示す。図１４と同様に、利用することが決定した入出力信号線は実線で示しており、Ｇｅｎｅｒｉｃ  Ｌｏｇｉｃの下に示すレイアウト順序管理配列は、レイアウト順序記憶モジュール２２に記憶されているレイアウト順序データに対して、当該ノードに対応するノード、レイヤ番号を示す領域を追記したものである。
【０１５５】
ステップＤ２が完了すると、続いて利用するｓｔｒｅｅ、具体的には、利用するｓｎｏｄｅ、ＭＵＸを決定する（ステップＤ３）。図１６に示すように、利用する入出力信号線が確定すると、ｓｔｒｅｅを利用する信号線も確定している。そこで、ｓｔｒｅｅへの入出力信号線を持っているｍｃｈａｒ＿ｎｏｄｅに注目し、レイヤ番号２以上の接続をもつｍｃｈａｒ＿ｎｏｄｅ同士を接続する。このとき、レイヤ番号の定義から、レイヤ番号０はｍｃｈａｒ＿ｎｏｄｅとｃｈａｒ＿ｎｏｄｅの接続、レイヤ番号１は、隣接するｍｃｈａｒ＿ｎｏｄｅ同士の接続を利用することができるため、レイヤ番号２以上が処理対象となる。最も左端のｍｃｈａｒ＿ｎｏｄｅからチェックしていき、ｓｔｒｅｅへの入出力信号線を持つｍｃｈａｒ＿ｎｏｄｅを見付けると、その接続先のｍｃｈａｒ＿ｎｏｄｅを検索する。ここで、本手法では、図９の配置例からも分かるように、通りがけ順でのレイアウトを行っていることから、当該ｍｃｈａｒ＿ｎｏｄｅの親ノードに相当するｍｃｈａｒ＿ｎｏｄｅが対象となる。但し、本来その接続をもつ親ノードに相当するｍｃｈａｒ＿ｎｏｄｅの左右どちらかのｍｃｈａｒ＿ｎｏｄｅを経由している場合もある。接続すべき２つのｍｃｈａｒ＿ｎｏｄｅからのｓｔｒｅｅを経由する接続が見つかると、複数のｓｔｒｅｅのうち１つのｓｔｒｅｅを用いてそれらを接続する。なお、このとき、同じレイヤ番号をもつ接続に対しては、同一のｓｔｒｅｅを利用することも可能であるが、１つのｍｃｈａｒ＿ｎｏｄｅの組を接続するために利用している同一の信号線を利用することはできないため、このような場合は、別のｓｔｒｅｅを利用することになる。
【０１５６】
例えば、図１６に示すような正規表現の場合、ｍｃｈａｒ＿ｎｏｄｅ３０２とｍｃｈａｒ＿ｎｏｄｅ３０３のｓｔｒｅｅに対する入出力信号を接続するため、２つあるｓｔｒｅｅのうち、１つのｓｔｒｅｅを選択し、ｓｎｏｄｅ４０４と、ＭＵＸ５０２、５０３を利用することとなる。なお、これらの接続はレイヤ番号２に相当するものであり、ｍｃｈａｒ＿ｎｏｄｅ３０３のｓｔｒｅｅに対する入出力信号は、その親ノードであるノード３が割り当てられたｍｃｈａｒ＿ｎｏｄｅ３０４のものである。また、ｍｃｈａｒ＿ｎｏｄｅ３０４もｓｔｒｅｅに対する入出力信号線を利用するようになっているが、これは根ノードの親ノードに対する接続であるため、無視する。上記のような処理を行うことで、ｓｔｒｅｅ中の利用するｓｎｏｄｅ、ＭＵＸが確定する。図１７は、第１の実施の形態において図１６のＧｅｎｅｒｉｃ  Ｌｏｇｉｃに対して利用するｓｎｏｄｅ、ＭＵＸを確定した場合の一例を示す図である。
【０１５７】
ここで、本発明の再構成可能有限オートマトン回路の構成データ生成装置の構成データ生成モジュールは、上記の各ステップにそれぞれ対応する機能モジュールを具備する構成とすることが可能である。この場合、本発明の構成データ生成モジュールは、特に、ステップＤ１の動作を行うキャラクタノード回路およびメタキャラクタノード回路の割り当てモジュールと、ステップＤ２の動作を行うパターン選択モジュールと、ステップＤ３の動作を行うスイッチノード回路およびＭＵＸの決定モジュール、およびステップＡ４の論理演算設定モジュールとを具備する構成とすることが出来る。
【０１５８】
上記の処理を行った後、構成データ生成モジュール１３は、具体的な各種ノードに対する構成データの生成処理を開始する（ステップＡ４）。図１８は、ステップＡ４のより詳細な動作を説明するための流れ図である。
【０１５９】
構成データ生成モジュール１３は、最後に全てのｍｃｈａｒ＿ｎｏｄｅ、ｃｈａｒ＿ｎｏｄｅ、ｓｎｏｄｅ、ＭＵＸに対して、具体的な構成データの生成処理を行う。
【０１６０】
まず、全てのｍｃｈａｒ＿ｎｏｄｅに対して、構成データの生成処理を行う（ステップＥ１）。ここでは、当該ｍｃｈａｒ＿ｎｏｄｅに割り当てられたメタキャラクタの種別に応じて構成データの決定を行う。その方針は以下の通りである。なお、下記の処理において、左の子ノード、右の子ノードは、レイアウト順序算出処理において、左右の部分木を入れ替える前のものであり、実際の処理においては自ノードの入れ替えフラグ（ｅｘｃｈａｎｇｅ  ｆｌａｇ）を参照し、入れ替わっているか確認する必要がある。また、構文木の根ノードにおいては、左の子ノードに対する出力信号として、常に‘１’を設定する。この設定を行うことで、状態遷移の初期状態に対する入力信号とすることができる。
・  メタキャラクタ‘・’（連結）の場合
−  親ノード（図１５ａ〜図１５ｈにおけるｎｐ）からの入力信号を、左の子ノード（図１５ａ〜図１５ｈにおけるｎｌ）への出力信号に接続する。
−  左の子ノード（図１５ａ〜図１５ｈにおけるｎｌ）からの入力信号を、右の子ノード（図１５ａ〜図１５ｈにおけるｎｒ）への出力信号に接続する。
−  右の子ノード（図１５ａ〜図１５ｈにおけるｎｒ）からの入力信号を、親ノード（図１５ａ〜図１５ｈにおけるｎｐ）への出力信号に接続する。
・  メタキャラクタ‘｜’（ＯＲ）の場合
−  親ノード（図１５ａ〜図１５ｈにおけるｎｐ）からの入力信号を、左の子ノード（図１５ａ〜図１５ｈにおけるｎｌ）と右の子ノード（図１５ａ〜図１５ｈにおけるｎｒ）への出力信号に接続する。
−  左の子ノード（図１５ａ〜図１５ｈにおけるｎｌ）からの入力信号と右の子ノード（図１５ａ〜図１５ｈにおけるｎｒ）からの入力信号を親ノード（図１５ａ〜図１５ｈにおけるｎｐ）への出力信号に接続する。
・  メタキャラクタ‘＊’（０回以上マッチ）と子ノードであるメタキャラクタ‘・’（連結）がマージされている場合
−  親ノード（図１５ａ〜図１５ｈにおけるｎｐ）からの入力信号を、左の子ノード（図１５ａ〜図１５ｈにおけるｎｌ）への出力信号と親ノード（図１５におけるｎｐ）への出力信号に接続する。
−  左の子ノード（図１５ａ〜図１５ｈにおけるｎｌ）からの入力信号を、右の子ノード（図１５ａ〜図１５ｈにおけるｎｒ）への出力信号に接続する。
−  右の子ノード（図１５ａ〜図１５ｈにおけるｎｒ）からの入力信号を、左の子ノード（図１５ａ〜図１５ｈにおけるｎｌ）への出力信号と親ノード（図１５ａ〜図１５ｈにおけるｎｐ）への出力信号に接続する。
・  メタキャラクタ‘＊’（０回以上マッチ）と子ノードであるメタキャラクタ‘｜’（ＯＲ）がマージされている場合、又は、メタキャラクタ‘＊’（０回以上マッチ）単独の場合（子ノードがテキスト文字であり、空の子ノードを追加した場合）
−  親ノード（図１５ａ〜図１５ｈにおけるｎｐ）からの入力信号を、左の子ノード（図１５ａ〜図１５ｈにおけるｎｌ）と右の子ノード（図１５ａ〜図１５ｈにおけるｎｒ）への出力信号と親ノード（図１５におけるｎｐ）への出力信号に接続する。
−  左の子ノード（図１５ａ〜図１５ｈにおけるｎｌ）からの入力信号を、左の子ノード（図１５ａ〜図１５ｈにおけるｎｌ）と右の子ノード（図１５ａ〜図１５ｈにおけるｎｒ）への出力信号と親ノード（図１５におけるｎｐ）への出力信号に接続する。
−  右の子ノード（図１５ａ〜図１５ｈにおけるｎｒ）からの入力信号を、左の子ノード（図１５ａ〜図１５ｈにおけるｎｌ）と右の子ノード（図１５ａ〜図１５ｈにおけるｎｒ）への出力信号と親ノード（図１５におけるｎｐ）への出力信号に接続する。
上記以外に、ｓｔｒｅｅへの接続をもつｍｃｈａｒ＿ｎｏｄｅのｓｔｒｅｅへの接続が左右いずれかのｍｃｈａｒ＿ｎｏｄｅを経由している場合がある（図１５ａと図１５ｂに相当する場合）。この場合には、本来ｓｔｒｅｅへの接続をもつｍｃｈａｒ＿ｎｏｄｅからの入力信号をｓｔｒｅｅへの出力信号へ、ｓｔｒｅｅからの入力信号を本来ｓｔｒｅｅへの接続をもつｍｃｈａｒ＿ｎｏｄｅへの出力信号へ接続する。この接続は、上記とは独立に行われる。
【０１６１】
例えば、図３９に示すｍｃｈａｒ＿ｎｏｄｅ６０に対して、図１７の各ｍｃｈａｒ＿ｎｏｄｅの構成データは、下記のような論理演算を実行する構成データをＬＵＴ１００３〜１００７に設定することを意味する。
・  ｍｃｈａｒ＿ｎｏｄｅ３００：（ｐｏ，Ｌｏ，Ｒｏ，ｌｏ，ｒｏ）＝（０，０，Ｒｉ＋ｌｉ＋ｒｉ，Ｒｉ＋ｌｉ＋ｒｉ，Ｒｉ＋ｌｉ＋ｒｉ）
・  ｍｃｈａｒ＿ｎｏｄｅ３０１：（ｐｏ，Ｌｏ，Ｒｏ，ｌｏ，ｒｏ）＝（０，ｒｉ，Ｌｉ，０，Ｒｉ）
・  ｍｃｈａｒ＿ｎｏｄｅ３０２：（ｐｏ，Ｌｏ，Ｒｏ，ｌｏ，ｒｏ）＝（Ｒｉ，ｐｉ，Ｌｉ，０，０）
・  ｍｃｈａｒ＿ｎｏｄｅ３０３：（ｐｏ，Ｌｏ，Ｒｏ，ｌｏ，ｒｏ）＝（Ｒｉ，ｌｉ＋ｒｉ，ｐｉ，Ｌｉ，Ｌｉ）
・  ｍｃｈａｒ＿ｎｏｄｅ３０４：（ｐｏ，Ｌｏ，Ｒｏ，ｌｏ，ｒｏ）＝（０，１，Ｌｉ，０，０）
・  ｍｃｈａｒ＿ｎｏｄｅ３０５：（ｐｏ，Ｌｏ，Ｒｏ，ｌｏ，ｒｏ）＝（０，ｌｉ，Ｌｉ，Ｒｉ，０）
・  ｍｃｈａｒ＿ｎｏｄｅ３０６：（ｐｏ，Ｌｏ，Ｒｏ，ｌｏ，ｒｏ）＝（０，ｌｉ＋ｒｉ，０，Ｌｉ，Ｌｉ）
【０１６２】
全てのｍｃｈａｒ＿ｎｏｄｅに対する処理（ステップＥ１）が終了すると、次に全てのｃｈａｒ＿ｎｏｄｅに対して、構成データの生成処理を行う（ステップＥ２）。ここでは、当該ｃｈａｒ＿ｎｏｄｅに割り当てられたテキスト文字の種別に応じて構成データの決定を行う。その方針は以下の通りである。
・  空（‘φ’）でないテキスト文字の場合
−  文字比較器（ｃｏｍｐａｒａｔｏｒ）に、割り当てられたテキスト文字に相当するＡＳＣＩＩコードを設定する。
−  隣接する左右のどちらかのｍｃｈａｒ＿ｎｏｄｅと接続するため、入出力を接続されているｍｃｈａｒ＿ｎｏｄｅに合うように設定する。
・  空（‘φ’）の場合
−  割り当てられたテキスト文字は空であるので、文字比較器（ｃｏｍｐａｒａｔｏｒ）の出力はｄｏｎ’ｔ  ｃａｒｅになる。例えば、ＡＳＣＩＩコードのＮＵＬＬ文字を示す０ｘ００（１６進数表示）を設定する等が考えられる。
−  隣接する左右のどちらかのｍｃｈａｒ＿ｎｏｄｅと接続するため、当該ｍｃｈａｒ＿ｎｏｄｅから入力信号をそのまま当該ｍｃｈａｒ＿ｎｏｄｅへの出力信号として出力するように設定する。
【０１６３】
本実施の形態では、図３８ａに示すｃｈａｒ＿ｎｏｄｅ４０を想定している。このため、図１７の各ｃｈａｒ＿ｎｏｄｅの構成データは、ｃｈａｒ＿ｎｏｄｅ４０のＬＵＴ１０００の出力信号をｏ’、ＡＮＤゲート８０７の出力信号をａとすると、ＬＵＴ１０００、１００１、及びｃｏｍｐａｒａｔｏｒ７０７に対する構成データは、下記のような論理演算を実行する構成データ、及びテキスト文字を表すＡＳＣＩＩコードとなる。なお、下記において、ｃｏｍｐａｒａｔｏｒの‘−’はｄｏｎ’ｔ  ｃａｒｅを示し、括弧内は１６進数表示を示す。
・  ｃｈａｒ＿ｎｏｄｅ２００：（ｏ’，ｏ）＝（ｒｉ，ａ）、ｃｏｍｐａｒａｔｏｒ＝‘ｂ’（０ｘ６２）
・  ｃｈａｒ＿ｎｏｄｅ２０１：（ｏ’，ｏ）＝（０，ｌｉ）、ｃｏｍｐａｒａｔｏｒ＝‘−’（ｄｏｎ’ｔ  ｃａｒｅ）
・  ｃｈａｒ＿ｎｏｄｅ２０２：（ｏ’，ｏ）＝（ｌｉ，ａ）、ｃｏｍｐａｒａｔｏｒ＝‘ａ’（０ｘ６１）
・  ｃｈａｒ＿ｎｏｄｅ２０３：（ｏ’，ｏ）＝（ｒｉ，ａ）、ｃｏｍｐａｒａｔｏｒ＝‘ｃ’（０ｘ６３）
・  ｃｈａｒ＿ｎｏｄｅ２０４：（ｏ’，ｏ）＝（ｌｉ，ａ）、ｃｏｍｐａｒａｔｏｒ＝‘ｄ’（０ｘ６４）
・  ｃｈａｒ＿ｎｏｄｅ２０５：（ｏ’，ｏ）＝（ｒｉ，ａ）、ｃｏｍｐａｒａｔｏｒ＝‘ｇ’（０ｘ６７）
・  ｃｈａｒ＿ｎｏｄｅ２０６：（ｏ’，ｏ）＝（ｒｉ，ａ）、ｃｏｍｐａｒａｔｏｒ＝‘ｅ’（０ｘ６５）
・  ｃｈａｒ＿ｎｏｄｅ２０７：（ｏ’，ｏ）＝（ｌｉ，ａ）、ｃｏｍｐａｒａｔｏｒ＝‘ｆ’（０ｘ６６）
【０１６４】
全てのｃｈａｒ＿ｎｏｄｅに対する処理（ステップＥ２）が終了すると、次に全てのｓｎｏｄｅに対して、構成データの生成処理を行う（ステップＥ３）。ここでは、当該ｓｎｏｄｅを用いた接続状況に応じて構成データの決定を行う。例えば、図４０ａに示すｓｎｏｄｅ７０に対して、図１７の各ｓｎｏｄｅの構成データは、下記のような論理演算を実行する構成データをＬＵＴ１００８〜１０１０に設定することを意味する。
・  ｓｎｏｄｅ４０４：（ｏ０，ｏ１，ｏ２）＝（０，ｉ２，ｉ１）
・  ｓｎｏｄｅ４０４以外のｓｎｏｄｅ：（ｏ０，ｏ１，ｏ２）＝（０，０，０）
【０１６５】
全てのｓｎｏｄｅに対する処理（ステップＥ３）が終了すると、最後に全てのＭＵＸに対して、構成データの生成処理を行う（ステップＥ４）。ＭＵＸに関しては、いわゆる当業者にとって自明であるので、詳細な説明を省略するが、どのｓｔｒｅｅからの信号線を選択するかを指定する構成データを生成する。
【０１６６】
構成データ生成モジュール１３は、上記のような処理を行うことで、Ｇｅｎｅｒｉｃ  Ｌｏｇｉｃ上の各種ノードの構成データを生成することが可能となる。なお、各ＬＵＴに対する実際の構成データは、各信号線がどのように接続されているかに依存するため、ここでは省略するが、上記のような論理演算を行うようなＬＵＴの構成データを生成する処理を行うことには変わりはない。また、ＬＵＴを用いずにレジスタ等の記憶素子を用いてＧｅｎｅｒｉｃ  Ｌｏｇｉｃを構成した場合も同様である。さらに、ｓｔｒｅｅとして、ここで例として挙げた２分木構成ではない場合においても同様である。また、実際のＧｅｎｅｒｉｃ  Ｌｏｇｉｃでは、パターンマッチが成立した場合の信号線が含まれることも考えられる。この場合には、構文木の根ノードに到達した入力信号（例えば、図１７のｍｃｈａｒ＿ｎｏｄｅ３０４における入力信号Ｒｉ）をその信号線に接続する等の方法で、パターンマッチが成立したことを示す信号を生成する手法が考えられる。
【０１６７】
構成データ生成モジュール１３は、上記のように生成した構成データを、ノード単位に、構成データ記憶モジュール２３に記憶させると共に、構成データ出力モジュール１４に対して、処理を開始させるための信号、構成データ記憶モジュール２３において処理対象となる構成データを特定する信号を出力する。なお、上記では、ｍｃｈａｒ＿ｎｏｄｅ、ｃｈａｒ＿ｎｏｄｅ、ｓｎｏｄｅ、ＭＵＸの順に構成データを生成したが、この順番は上記のように限定されるものではなく、当該Ｇｅｎｅｒｉｃ  Ｌｏｇｉｃに含まれる全てのノードに対する構成データが生成されれば問題はない。
【０１６８】
構成データ出力モジュール１４は、構成データ生成モジュール１３から処理を開始させるための信号、構成データ記憶モジュール２３において処理対象となる構成データを特定する信号を受け取ると、構成データ記憶モジュール２３から構成データを読み出し、実際のＧｅｎｅｒｉｃ  Ｌｏｇｉｃに設定するためのビット列として整形し、出力信号４から出力する（ステップＡ５）。ここで、ビット列として整形する方針は、実際のＧｅｎｅｒｉｃ  Ｌｏｇｉｃの設定方法に依存するため、ここでは省略するが、ノード種別毎に並び替えたり、当該ノードの同じＬＵＴ毎に並び替えたりする等、いくつかのパターンが考えられる。
【０１６９】
また、構成データ出力モジュール１４の動作として、外部から正規表現を特定する信号を与えられ、それをトリガとして構成データ記憶モジュール２３から該当する構成データを読み出し、ビット列として整形した上で出力する構成も考えられる。
【０１７０】
なお、本実施の形態は、Ｇｅｎｅｒｉｃ  Ｌｏｇｉｃにおけるｓｔｒｅｅが２分木構成の場合を例に説明したが、本手法は、ｓｎｏｄｅの入出力信号数を変更し、これをＭ分木（Ｍ≧２）として構成したｓｔｒｅｅを用いたＧｅｎｅｒｉｃ  Ｌｏｇｉｃに対しても同様に利用できる。また、その際の必要なｓｔｒｅｅの数も上記と同様、帰りがけ順で辿った場合よりも見かけ上１少ない数でよく、結果として必要なｓｔｒｅｅ数は２分木構成の場合と変わらない。
【０１７１】
また、本実施の形態では、レイアウト順序算出処理（ステップＡ２）において、当該処理ノードの左右の子ノードを寝とする部分木を入れ替える際に、それぞれの子ノードが親ノードから見て左右のどちらの子ノードかを示すフラグ（ｌｅｆｔ＿ｒｉｇｈｔ（ｌｒ））を入れ替えた後の構成に合うように再設定を行ったが、これを省略することも可能である。その場合、それ以降の処理において、入れ替えた後の構文木において自ノードが親ノードから見て左右いずれの子ノードであるかは、自ノードのｌｅｆｔ＿ｒｉｇｈｔ（ｌｒ）と、親ノードにおいて左右の子ノードを根とする部分木を入れ替えたことを示すフラグ（ｅｘｃｈａｎｇｅ（ｅｆｌａｇ））の両方を確認することで把握でき、入れ替えを行う前の構文木において自ノードが親ノードから見て左右いずれの子ノードであるかは、自ノードのｌｅｆｔ＿ｒｉｇｈｔ（ｌｒ）を確認することで把握できる。
【０１７２】
次に、本発明の第１の実施の形態の作用効果について説明する。
【０１７３】
上記のように、本実施の形態では、Ｇｅｎｅｒｉｃ  Ｌｏｇｉｃ上に構成できる条件を満たした構文木で表現された正規表現を、Ｇｅｎｅｒｉｃ  Ｌｏｇｉｃ上のｃｈａｒ＿ｎｏｄｅ、ｍｃｈａｒ＿ｎｏｄｅをはじめとする各種ノードを用いてどのように配置すれば良いかを決定する具体的な配置方法を提供することが可能となる。
【０１７４】
また、本手法では、構文木の各ノードを帰りがけ順ではなく、通りがけ順によって辿り、配置を決定していくため、Ｇｅｎｅｒｉｃ  Ｌｏｇｉｃにおける必要なｓｔｒｅｅ数が実質２個少なくなるため、回路規模の増加を抑えることが可能である。
【０１７５】
さらに、構文木記憶モジュール２１、レイアウト順序記憶モジュール２２、構成データ記憶モジュール２３を用いることで、各ステップの処理が独立して行うことができるため、パイプライン化による構成データ生成処理の高速化が図れる。なお、各記憶モジュールに対するアクセスは、本実施の形態により限定されるものではなく、必要に応じて各処理モジュールからアクセスすることで、より効率的な処理が可能となる。また、本実施の形態において、各記憶モジュールで記憶するデータは、本実施の形態で述べたデータに限定されるものではなく、各種処理に関連するデータを一緒に記憶させても良い。
【０１７６】
（第２の実施形態）
次に、本発明の第２の実施の形態について図面を参照して詳細に説明する。
【０１７７】
図１９は、本発明の第２の実施の形態の再構成可能有限オートマトン回路の構成データ生成装置の構成を示すブロック図である。図１９を参照すると、本発明の第２の実施の形態において、プログラム制御により動作する構成データ生成装置５は、レイヤ番号算出モジュール１５と、レイアウト順序算出モジュール１２と、構成データ生成モジュール１６と、構成データ出力モジュール１４とを備えている。本実施の形態は、図１に示した前記第１の実施の形態の構成データ生成装置１のレイヤ番号算出モジュール１１、構成データ生成モジュール１３を、レイヤ番号算出モジュール１５、構成データ生成モジュール１６に置き換えたものである。その他は、前記第１の実施の形態と同じである。
【０１７８】
なお、本発明の第２の実施の形態は、再構成可能オートマトン回路であるＧｅｎｅｒｉｃ  Ｌｏｇｉｃにおけるｃｈａｒ＿ｎｏｄｅとして、図３８ｂのような構成を考える。つまり、メタキャラクタ‘｜’、‘＊’、‘・’（連結）のみを用いた構文木で表現された正規表現のうち、メタキャラクタ‘＊’を持つノードは、子ノードがメタキャラクタであっても、テキスト文字であっても、どちらでもマージすることができる場合の実施の形態である。
【０１７９】
レイヤ番号算出モジュール１５は、基本的な処理は前記第１の実施の形態と同様であるが、上記メタキャラクタ‘＊’が予め子ノードとマージされていない場合に、子ノードがメタキャラクタ、テキスト文字のどちらでも子ノードとマージできる処理が追加されたものである。なお、本実施の形態では、メタキャラクタ‘＊’が子ノードのメタキャラクタとマージされた場合はメタキャラクタノード、子ノードのテキスト文字とマージされた場合は、キャラクタノードとして扱う。
【０１８０】
構成データ生成モジュール１６は、基本的な処理は前記第１の実施の形態と同様であるが、メタキャラクタ‘＊’がテキスト文字である子ノードとマージされた場合の構成データ生成処理が追加されたものである。
【０１８１】
次に、図１９、及び図２０を参照して本発明の第２の実施の形態の動作について詳細に説明する。図２０は、本発明の第２の実施の形態の再構成可能有限オートマトン回路の構成データ生成装置の動作を示す流れ図である。
【０１８２】
入力３から入力された構文木で表現された正規表現は、レイヤ番号算出モジュール１５に供給され、レイヤ番号算出モジュール１５は、受け取った構文木で表現された正規表現に対して、レイヤ番号を算出する（ステップＡ１）。
【０１８３】
ここで、本発明の第２の実施の形態では、構文木で表現された正規表現において、メタキャラクタ‘＊’のノードに対しては、子ノードとマージしたものを対象としている。本処理は、入力３から入力される構文木で表現された正規表現に対して予め処理しておいても良いし、入力後にレイヤ番号算出モジュール１５において処理しても良い。
【０１８４】
レイヤ番号算出モジュール１５の処理としては、上記の入力後にメタキャラクタ‘＊’のノードに対する処理を行うことができる以外は、前記第１の実施の形態におけるレイヤ番号算出モジュール１１と同様なので、詳細は省略する。
【０１８５】
例として、図３０に示す構文木で表現された正規表現“ａｂ＊（ｃ｜ｄ）（ｅ｜ｆ）ｇ”を挙げて説明する。本実施の形態の場合、レイヤ番号算出モジュール１５では、図２１のような構文木に対して処理を行うことになる。図２１は、本発明の第２の実施の形態においてメタキャラクタ‘＊’をその子ノードとマージした正規表現“ａｂ＊（ｃ｜ｄ）（ｅ｜ｆ）ｇ”の構文木の一例である。
【０１８６】
レイアウト順序算出モジュール１２は、レイヤ番号算出モジュール１５から処理を開始する信号と、その処理対象となる正規表現データを特定する信号を受け取ると、構文木記憶モジュール２１から、対象となる構文木で表現された正規表現データを読み込む。次に、各ノードに対するレイヤ番号を参照しながら、各ノードのレイアウト順序を決定する（ステップＡ２）が、本処理は前記第１の実施の形態における処理と同様なので、詳細は省略する。
【０１８７】
図２２は、本発明の第２の実施の形態において図２１に示す正規表現“ａｂ＊（ｃ｜ｄ）（ｅ｜ｆ）ｇ”の構文木に対してレイアウト順序の決定（ステップＡ２）までを行った正規表現データを示す。また、図２３は、本発明の第２の実施の形態において図２２に示す正規表現データに対応するレイアウト順序管理配列ｌａｙｏｕｔの一例を示す図である。
【０１８８】
構成データ生成モジュール１６は、レイアウト順序算出モジュール１２から処理を開始させるための信号、構文木記憶モジュール２１において処理対象となる構文木で表現された正規表現データを特定する信号、及び、レイアウト順序記憶モジュール２２において処理対象となるレイアウト順序データを特定する信号を受け取ると、前記第１の実施の形態と同様、構文木記憶モジュール２１から処理対象となる構文木で表現された正規表現データを、レイアウト順序記憶モジュール２２から処理対象となるレイアウト順序データを読み出し、レイアウト順序データからＧｅｎｅｒｉｃ  Ｌｏｇｉｃ中に含まれる各ｃｈａｒ＿ｎｏｄｅ、ｍｃｈａｒ＿ｎｏｄｅに対して、構文木で表現された正規表現の各ノードを割り当てると共に、各メタキャラクタノードがその親ノードから見て左の子ノードなのか、右の子ノードなのか、また、自身の左右の子ノードがテキスト文字なのかを確認しながら、各ｍｃｈａｒ＿ｎｏｄｅが持つ複数の入出力信号のどれを用いるかを決定し、必要に応じてｓｔｒｅｅを利用しながら適切なｍｃｈａｒ＿ｎｏｄｅ間の接続を設定する（ステップＡ３）。本ステップＡ３は、前記第１の実施の形態と同様なので、詳細は省略する。図２４は、本発明の第２の実施の形態において図２２に示す正規表現に対して、ステップＡ３までの処理を行った場合のＧｅｎｅｒｉｃ  Ｌｏｇｉｃを示す図である。
【０１８９】
次に、構成データ生成モジュール１６は、各ｃｈａｒ＿ｎｏｄｅ、ｍｃｈａｒ＿ｎｏｄｅ、ｓｎｏｄｅ、ＭＵＸに含まれるＬＵＴに対する構成データを生成し、その生成データをノード毎に構成データ記憶モジュール２３に記憶させると共に、構成データ出力モジュール１４に対して、処理を開始させるための信号、構成データ記憶モジュール２３において処理対象となる構成データを特定する信号を出力する（ステップＡ６）。
【０１９０】
図２５は、本発明の第２の実施の形態のステップＡ６のより詳細な動作を説明するための流れ図である。
【０１９１】
ステップＡ６は、全てのｍｃｈａｒ＿ｎｏｄｅに対する構成データを生成するステップＥ５と全てのｃｈａｒ＿ｎｏｄｅに対する構成データを生成するステップＥ６以外は全て前記第１の実施の形態におけるステップＡ３と同様であるため、詳細は省略し、以下では、全てのｍｃｈａｒ＿ｎｏｄｅに対する構成データを生成するステップＥ５と全てのｃｈａｒ＿ｎｏｄｅに対する構成データを生成するステップＥ６についてのみ説明する。
【０１９２】
構成データ生成モジュール１６では、構成データを生成する処理（ステップＡ６）において、まず、全てのｍｃｈａｒ＿ｎｏｄｅに対して、構成データの生成処理を行う（ステップＥ５）。ここで、本実施の形態においては、メタキャラクタ‘＊’は全てその子ノードであるメタキャラクタノード、又はテキスト文字とマージされている。このため、メタキャラクタ‘＊’が単独の場合における構成データの生成方法が対象外になる以外は、全て前記第１の実施の形態における全てのｍｃｈａｒ＿ｎｏｄｅに対する構成データを生成するステップＥ１と同様であるため、その他の詳細は省略する。
【０１９３】
構成データ生成モジュール１６では、全てのｍｃｈａｒ＿ｎｏｄｅに対する処理（ステップＥ５）が終了すると、次に全てのｃｈａｒ＿ｎｏｄｅに対して、構成データの生成処理を行う（ステップＥ６）。ここでは、当該ｃｈａｒ＿ｎｏｄｅに割り当てられたテキスト文字の種別に応じて構成データの決定を行う。その方針は以下の通りである。
・  テキスト文字のみの場合
−  文字比較器（ｃｏｍｐａｒａｔｏｒ）に割り当てられたテキスト文字に相当するＡＳＣＩＩコードを設定する。
−  隣接する左右のどちらかのｍｃｈａｒ＿ｎｏｄｅと接続するため、入出力を接続されているｍｃｈａｒ＿ｎｏｄｅに合うように設定する。
・  メタキャラクタ‘＊’とテキスト文字がマージされている場合
−  文字比較器（ｃｏｍｐａｒａｔｏｒ）にメタキャラクタ‘＊’とマージされたテキスト文字に相当するＡＳＣＩＩコードを設定する。
−  隣接する左右のどちらかのｍｃｈａｒ＿ｎｏｄｅと接続するため、入出力を接続されているｍｃｈａｒ＿ｎｏｄｅに合うように設定する。
−  接続先のｍｃｈａｒ＿ｎｏｄｅからの入力信号をそのまま当該ｍｃｈａｒ＿ｎｏｄｅへの出力信号として出力すると共に、その出力を、状態を示すＦｌｉｐ−Ｆｌｏｐの入力に接続する。
【０１９４】
本実施の形態では、図３８ｂに示すｃｈａｒ＿ｎｏｄｅ５０を想定している。このため、図２４の各ｃｈａｒ＿ｎｏｄｅの構成データは、ｃｈａｒ＿ｎｏｄｅ５０のＬＵＴ１００２の出力信号をｏ’、ＡＮＤゲート８０７の出力信号をａとすると、ＬＵＴ１００２、１００３、及びｃｏｍｐａｒａｔｏｒ７０７に対する構成データは、下記のような論理演算を実行する構成データ、及びテキスト文字を表すＡＳＣＩＩコードとなる。なお、下記において、ｃｏｍｐａｒａｔｏｒの‘−’はｄｏｎ’ｔ  ｃａｒｅを示し、括弧内は１６進数表示を示す。
・  ｃｈａｒ＿ｎｏｄｅ２０８：（ｏ’，ｏ）＝（ｒｉ，ａ）、ｃｏｍｐａｒａｔｏｒ＝‘ａ’（０ｘ６１）
・  ｃｈａｒ＿ｎｏｄｅ２０９：（ｏ’，ｏ）＝（ｌｉ＋ａ，ｌｉ＋ａ）、ｃｏｍｐａｒａｔｏｒ＝‘ｂ’（０ｘ６２）
・  ｃｈａｒ＿ｎｏｄｅ２１０：（ｏ’，ｏ）＝（ｒｉ，ａ）、ｃｏｍｐａｒａｔｏｒ＝‘ｃ’（０ｘ６３）
・  ｃｈａｒ＿ｎｏｄｅ２１１：（ｏ’，ｏ）＝（ｌｉ，ａ）、ｃｏｍｐａｒａｔｏｒ＝‘ｄ’（０ｘ６４）
・  ｃｈａｒ＿ｎｏｄｅ２１２：（ｏ’，ｏ）＝（ｒｉ，ａ）、ｃｏｍｐａｒａｔｏｒ＝‘ｇ’（０ｘ６７）
・  ｃｈａｒ＿ｎｏｄｅ２１３：（ｏ’，ｏ）＝（ｒｉ，ａ）、ｃｏｍｐａｒａｔｏｒ＝‘ｅ’（０ｘ６５）
・  ｃｈａｒ＿ｎｏｄｅ２１４：（ｏ’，ｏ）＝（ｌｉ，ａ）、ｃｏｍｐａｒａｔｏｒ＝‘ｆ’（０ｘ６６）
・  ｃｈａｒ＿ｎｏｄｅ２１５：（ｏ’，ｏ）＝（０，０）、ｃｏｍｐａｒａｔｏｒ＝‘−’（ｄｏｎ’ｔ  ｃａｒｅ）
【０１９５】
全てのｃｈａｒ＿ｎｏｄｅに対する処理（ステップＥ５）が終了すると、次に全てのｓｎｏｄｅ、全てのＭＵＸに対して、構成データの生成処理を行い（ステップＥ３、Ｅ４）、構成データの生成処理（ステップＡ６）を終了する。
【０１９６】
なお、構成データの生成処理を終了した時点での、各ｍｃｈａｒ＿ｎｏｄｅの各出力信号の構成例、及び各ｓｎｏｄｅの各出力信号の構成例を以下に示す。但し、ｓｎｏｄｅとしては、図４０ａに示すｓｎｏｄｅ７０の構成を対象としている。なお、ＭＵＸに関しては、いわゆる当業者にとって自明であるので、詳細な説明を省略するが、どのｓｔｒｅｅからの信号線を選択するかを指定する構成データを生成する。
・  ｍｃｈａｒ＿ｎｏｄｅ３０７：（ｐｏ，Ｌｏ，Ｒｏ，ｌｏ，ｒｏ）＝（０，０，ｒｉ，Ｒｉ，ｌｉ）
・  ｍｃｈａｒ＿ｎｏｄｅ３０８：（ｐｏ，Ｌｏ，Ｒｏ，ｌｏ，ｒｏ）＝（Ｒｉ，ｐｉ，Ｌｉ，０，０）
・  ｍｃｈａｒ＿ｎｏｄｅ３０９：（ｐｏ，Ｌｏ，Ｒｏ，ｌｏ，ｒｏ）＝（Ｒｉ，ｌｉ＋ｒｉ，ｐｉ，Ｌｉ，Ｌｉ）
・  ｍｃｈａｒ＿ｎｏｄｅ３１０：（ｐｏ，Ｌｏ，Ｒｏ，ｌｏ，ｒｏ）＝（０，１，Ｌｉ，０，０）
・  ｍｃｈａｒ＿ｎｏｄｅ３１１：（ｐｏ，Ｌｏ，Ｒｏ，ｌｏ，ｒｏ）＝（０，ｌｉ，Ｌｉ，Ｒｉ，０）
・  ｍｃｈａｒ＿ｎｏｄｅ３１２：（ｐｏ，Ｌｏ，Ｒｏ，ｌｏ，ｒｏ）＝（０，ｌｉ＋ｒｉ，０，Ｌｉ，Ｌｉ）
・  ｍｃｈａｒ＿ｎｏｄｅ３１３：（ｐｏ，Ｌｏ，Ｒｏ，ｌｏ，ｒｏ）＝（０，０，０，０，０）
・  ｓｎｏｄｅ４１５：（ｏ０，ｏ１，ｏ２）＝（０，ｉ２，ｉ１）
・  ｓｎｏｄｅ４１７：（ｏ０，ｏ１，ｏ２）＝（ｉ２，０，ｉ０）
・  ｓｎｏｄｅ４１８：（ｏ０，ｏ１，ｏ２）＝（ｉ１，ｉ０，０）
・  ｓｎｏｄｅ４１５、４１７、４１８以外のｓｎｏｄｅ：（ｏ０，ｏ１，ｏ２）＝（０，０，０）
【０１９７】
構成データ生成モジュール１６は、上記のような処理を行うことで、メタキャラクタ‘＊’がテキスト文字である子ノードとマージされた場合においても、Ｇｅｎｅｒｉｃ  Ｌｏｇｉｃ上の各種ノードの構成データを生成することが可能となる。なお、前記第１の実施の形態と同様、各ＬＵＴに対する実際の構成データは、各信号線がどのように接続されているかに依存するため、ここでは省略するが、上記のような論理演算を行うようなＬＵＴの構成データを生成する処理を行うことには変わりはない。また、ＬＵＴを用いずにレジスタ等の記憶素子を用いてＧｅｎｅｒｉｃ  Ｌｏｇｉｃを構成した場合も同様である。さらに、ｓｔｒｅｅとして、ここで例として挙げた２分木構成ではない場合においても同様である。また、実際のＧｅｎｅｒｉｃ  Ｌｏｇｉｃでは、パターンマッチが成立した場合の信号線が含まれることも考えられる。この場合には、構文木の根ノードに到達した入力信号（例えば、図２４のｍｃｈａｒ＿ｎｏｄｅ３１０における入力信号Ｒｉ）をその信号線に接続する等の方法で、パターンマッチが成立したことを示す信号を生成する手法が考えられる。
【０１９８】
最後に、構成データ出力モジュール１４の動作については、前記第１の実施の形態と同様であるため、ここでは説明を省略する。
【０１９９】
なお、本実施の形態においても、第１の実施の形態と同様、ｓｎｏｄｅの入出力信号数を変更し、これをＭ分木（Ｍ≧２）として構成したｓｔｒｅｅを用いたＧｅｎｅｒｉｃ  Ｌｏｇｉｃに対しても同様に利用できる。
【０２００】
また、本実施の形態においても、前記第１の実施の形態と同様、レイアウト順序算出処理（ステップＡ２）においては、当該処理ノードの左右の子ノードを寝とする部分木を入れ替える際に、それぞれの子ノードが親ノードから見て左右のどちらの子ノードかを示すフラグ（ｌｅｆｔ＿ｒｉｇｈｔ（ｌｒ））を入れ替えた後の構成に合うように再設定を行うが、これを省略することも可能である。その場合、それ以降の処理において、入れ替えた後の構文木において自ノードが親ノードから見て左右いずれの子ノードであるかは、自ノードのｌｅｆｔ＿ｒｉｇｈｔ（ｌｒ）と、親ノードにおいて左右の子ノードを根とする部分木を入れ替えたことを示すフラグ（ｅｘｃｈａｎｇｅ（ｅｆｌａｇ））の両方を確認することで把握でき、入れ替えを行う前の構文木において自ノードが親ノードから見て左右いずれの子ノードであるかは、自ノードのｌｅｆｔ＿ｒｉｇｈｔ（ｌｒ）を確認することで把握できる。
【０２０１】
次に、本発明の第２の実施の形態の作用効果について説明する。
【０２０２】
本実施の形態では、前記第１の実施の形態と同様、Ｇｅｎｅｒｉｃ  Ｌｏｇｉｃ上に構成できる条件を満たした構文木で表現された正規表現を、Ｇｅｎｅｒｉｃ  Ｌｏｇｉｃ上のｃｈａｒ＿ｎｏｄｅ、ｍｃｈａｒ＿ｎｏｄｅをはじめとする各種ノードを用いてどのように配置すれば良いかを決定する具体的な配置方法を提供することが可能であり、構文木の各ノードを帰りがけ順ではなく、通りがけ順によって辿り、配置を決定していくため、Ｇｅｎｅｒｉｃ  Ｌｏｇｉｃにおける必要なｓｔｒｅｅ数が実質２個少なくなるため、回路規模の増加を抑えることが可能である。
【０２０３】
また、構文木記憶モジュール２１、レイアウト順序記憶モジュール２２、構成データ記憶モジュール２３を用いることで、各ステップの処理が独立して行うことができるため、パイプライン化による構成データ生成処理の高速化が図れる。また、本実施の形態では、メタキャラクタ‘＊’のテキスト文字の子ノードを持つ場合にも、子ノードとマージすることができるため、Ｇｅｎｅｒｉｃ  Ｌｏｇｉｃ上のｃｈａｒ＿ｎｏｄｅ、ｍｃｈａｒ＿ｎｏｄｅを効率的に活用することができる。これは、前記第１の実施の形態の場合、メタキャラクタ‘＊’がテキスト文字の子ノードをもつ場合、空を示す‘φ’をｃｈａｒ＿ｎｏｄｅとして追加する必要があり、かつ、メタキャラクタ‘＊’自身はｍｃｈａｒ＿ｎｏｄｅを利用する必要があるためである。なお、前記第１の実施の形態と同様、各記憶モジュールに対するアクセスは、本実施の形態により限定されるものではなく、必要に応じて各処理モジュールからアクセスすることで、より効率的な処理が可能となる。また、本実施の形態において、各記憶モジュールで記憶するデータは、本実施の形態で述べたデータに限定されるものではなく、各種処理に関連するデータを一緒に記憶させても良い。
【０２０４】
（第３の実施形態）
次に、本発明の第３の実施の形態について図面を参照して詳細に説明する。
【０２０５】
図２６は、本発明の第３の実施の形態の再構成可能有限オートマトン回路の構成データ生成装置の構成を示すブロック図である。図２６を参照すると、本発明の第３の実施の形態において、プログラム制御により動作する構成データ生成装置６は、入力７と接続し、構文木生成モジュール１７と、レイヤ番号算出モジュール１１と、レイアウト順序算出モジュール１２と、構成データ生成モジュール１３と、構成データ出力モジュール１４とを備えている。本実施の形態は、図１に示した前記第１の実施の形態の構成データ生成装置１に、構文木生成モジュール１７が加わり、入力３が入力７に置き換わったものである。その他は、前記第１の実施の形態と同じである。
【０２０６】
構文木生成モジュール１７は、入力７から入力された正規表現を読み込み、メタキャラクタ‘｜’（ＯＲ）、‘＊’（０回以上マッチ）、‘・’（連結）のみを用いた正規表現に書き換える。また、書き換えた正規表現を構文木に変換し、その構文木で表された正規表現を、レイヤ番号算出モジュール１１に出力する。
【０２０７】
次に、図２６、及び図２７を参照して本発明の第３の実施の形態の動作について詳細に説明する。図２７は、本発明の第３の実施の形態の再構成可能有限オートマトン回路の構成データ生成装置の動作を示す流れ図である。
【０２０８】
まず、構文木生成モジュール１７は、入力７から入力された正規表現を読み込み、メタキャラクタ‘｜’（ＯＲ）、‘＊’（０回以上マッチ）、‘・’（連結）のみを用いた正規表現に書き換える（ステップＡ７）。
【０２０９】
一般的に、正規表現において、上記３つ以外のメタキャラクタを用いたものは、上記３つのメタキャラクタを用いて書き換えることが可能である。例えば、Ｎを任意の正規表現とすると、“Ｎ？”（正規表現Ｎの０回、又は１回のみマッチ）は“（Ｎ｜φ）”、“Ｎ＋”（正規表現Ｎの１回以上マッチ）は“Ｎ・Ｎ＊”のように書き換える。
【０２１０】
続いて、構文木生成モジュール１７は、その書き換えた正規表現を構文木に変換する（ステップＡ７）。
【０２１１】
ここで、正規表現を構文木に変換する方法については、例えば、非特許文献１に記載されているような既存の方法を用いる。但し、この構文木で表された正規表現は、図３に示すようなデータ構造を用いてその構成を管理する。また、本実施の形態は、前記第１の実施の形態に、本構文木生成モジュール１７を加えた構成であるため、メタキャラクタ‘＊’については、子ノードであるメタキャラクタとマージする、又は子ノードがテキスト文字である場合には、空（‘φ’）の子ノードを追加する処理を行う。
【０２１２】
最後に、構文木生成モジュール１７は、変換した構文木で表された正規表現データをレイヤ番号算出モジュール１１に出力する。
【０２１３】
以降、レイヤ番号算出モジュール１１、レイアウト順序算出モジュール１２、構成データ生成モジュール１３、構成データ出力モジュール１４における処理は、前記第１の実施の形態と同様であるため、詳細な説明は省略する。
【０２１４】
なお、本実施の形態は、前記第２の実施の形態における構成データ生成装置５に、構文木生成モジュール１７を加えたものでもよい。この場合、構文木生成モジュール１７におけるメタキャラクタ‘＊’ノードへの対応については、子ノードがメタキャラクタであってもテキスト文字であっても、子ノードとマージを行う処理となる。
【０２１５】
さらに、本実施の形態においても、前記第１、第２の実施の形態と同様、ｓｎｏｄｅの入出力信号数を変更し、これをＭ分木（Ｍ≧２）として構成したｓｔｒｅｅを用いたＧｅｎｅｒｉｃ  Ｌｏｇｉｃに対しても同様に利用できる。
【０２１６】
次に、本発明の第３の実施の形態の作用効果について説明する。
【０２１７】
本実施の形態では、前記第１、第２の実施の形態の効果に加え、入力が構文木ではなく正規表現そのもので良くなるという効果がある。また、前記第１、第２の実施の形態と同様、各記憶モジュールに対するアクセスは、本実施の形態により限定されるものではなく、必要に応じて各処理モジュールからアクセスすることで、より効率的な処理が可能となる。さらに、本実施の形態において、各記憶モジュールで記憶するデータは、本実施の形態で述べたデータに限定されるものではなく、各種処理に関連するデータを一緒に記憶させても良い。
【０２１８】
（第４の実施形態）
次に、本発明の第４の実施の形態について図面を参照して詳細に説明する。
【０２１９】
図２８は、本発明の第４の実施の形態の再構成可能有限オートマトン回路の構成データ生成装置の構成を示すブロック図である。図２８を参照すると、本発明の第４の実施の形態は、前記第１、第２、第３の実施の形態と同様に、構成データ生成装置８、記憶装置２、入力３、出力４を備える。本実施の形態においては、前記第１の実施の形態における構成データ生成装置１のレイヤ番号算出モジュール１１、レイアウト順序算出モジュール１２、構成データ生成モジュール１３、構成データ出力モジュール１４の処理、あるいは、前記第２の実施の形態における構成データ生成装置５のレイヤ番号算出モジュール１５、レイアウト順序算出モジュール１２、構成データ生成モジュール１６、構成データ出力モジュール１４の処理、あるいは、前記第３の実施の形態における構成データ生成装置６の構文木生成モジュール１７、レイヤ番号算出モジュール１１、レイアウト順序算出モジュール１２、構成データ生成モジュール１３、構成データ出力モジュール１４の処理を、構成データ生成装置８で実行される構成データ生成用プログラム９で実現したものである。
【０２２０】
構成データ生成用プログラム９は、構成データ生成装置８に読み込まれ、構成データ生成装置８の動作を制御し、記憶装置２に、構文木記憶モジュール２１と、レイアウト順序記憶モジュール２２と、構成データ記憶モジュール２３を生成する。
【０２２１】
構成データ生成装置８は、構成データ生成用プログラムの制御により、前記第１、第２、及び第３の実施の形態における構成データ生成装置１、５、及び６による処理と同一の処理を実行する。
次に、本発明の第４の実施の形態の作用効果について説明する。
本発明の第４の実施の形態では、前記第１、第２、第３の実施の形態の作用効果と同様、構文木で表現された正規表現、又は、正規表現そのものを入力することにより、再構成可能オートマトン回路であるＧｅｎｅｒｉｃ  Ｌｏｇｉｃ上のｃｈａｒ＿ｎｏｄｅ、ｍｃｈａｒ＿ｎｏｄｅをはじめとする各種ノードを用いてどのように配置すれば良いかを決定する具体的な配置方法を提供することが可能となる。また、前記第２、又は第３の実施の形態の処理を構成データ生成用プログラム９で実現した場合には、前記第２、又は第３の実施の形態における作用効果と同様、メタキャラクタ‘＊’のテキスト文字の子ノードを持つ場合にも、子ノードとマージすることができるため、Ｇｅｎｅｒｉｃ  Ｌｏｇｉｃ上のｃｈａｒ＿ｎｏｄｅ、ｍｃｈａｒ＿ｎｏｄｅを効率的に活用することができる。
【０２２２】
（第５の実施形態）
次に、本発明の第５の実施の形態について図面を参照して詳細に説明する。
【０２２３】
図２９は、本発明の第５の実施の形態の再構成可能有限オートマトン回路の構成データ生成装置の構成を示すブロック図である。図２９を参照すると、本発明の第５の実施の形態は、プログラム制御により動作する構成データ生成装置１と、情報を記憶する記憶装置２と、構成データ生成装置１への入力３と、構成データ生成装置１からの出力４と、再構成可能オートマトン回路であるＧｅｎｅｒｉｃ  Ｌｏｇｉｃ上に正規表現を構成するための、構成データをコンフィギュレーションするためのケーブル等のコンフィギュレーション装置１０と、パターンマッチングの被検索対象データをパターンマッチング装置に入力するためのデータ入力装置３０と、ＦＰＧＡ等のハードウェアデバイスで構成されたＧｅｎｅｒｉｃ  Ｌｏｇｉｃを種とするパターンマッチング装置３１と、パターンマッチングの結果を出力するためのディスプレイ装置や印刷装置等の結果出力装置３２とを備えている。
【０２２４】
構成データ生成装置１、記憶装置２、入力３、出力４は、図１に示した前記第１の実施の形態と同じであるため、詳細な説明は省略する。
【０２２５】
パターンマッチング装置３１は、Ｃｏｎｆｉｇｕｒａｔｉｏｎ  Ｃｏｎｔｒｏｌｌｅｒ１００と、構成データ記憶装置１０１と、データ入力回路１０２と、Ｇｅｎｅｒｉｃ  Ｌｏｇｉｃ１０３と、結果出力回路１０４とを備えている。このうち、構成データ記憶装置１０１は、メモリ等の記憶素子によって構成され、コンフィギュレーション装置１０を経由して入力された構成データを記憶する。その他の回路は、同一のハードウェアデバイス上に構成されてもよいし、別々のハードウェアデバイス上に構成され、それらが互いに接続されていても良い。また、ハードウェアデバイスは、ＦＰＧＡ等の再構成可能なハードウェアデバイスでも良いし、ＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ  Ｓｐｅｃｉｆｉｃ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）化されたチップでも良く、回路によって異なったハードウェアデバイスを用いても良い。
【０２２６】
パターンマッチング装置３１は、図３３に示した再構成可能オートマトン回路に、データ入力装置３０から入力されたパケットデータや、テキストデータ等のパターンマッチング対象データ（これを被検索データと呼ぶ）を整形し、Ｇｅｎｅｒｉｃ  Ｌｏｇｉｃ１０３に１文字ずつ入力するデータ入力回路１０２と、その結果、パターンマッチが成立した場合の情報を、結果出力装置３２へ出力するための結果出力回路１０４を加えたものである。
【０２２７】
パターンマッチング装置３１におけるＣｏｎｆｉｇｕｒａｔｉｏｎ  Ｃｏｎｔｒｏｌｌｅｒ１００は、コンフィギュレーション装置１０を経由して入力された、  Ｇｅｎｅｒｉｃ  Ｌｏｇｉｃ１０３上に正規表現を構成するための構成データを直接Ｇｅｎｅｒｉｃ  Ｌｏｇｉｃ１０３上に設定する処理はもちろん、入力された構成データを構成データ記憶装置１０１に記憶させる処理、既に構成データ記憶装置１０１に記憶されている構成データを読み出し、Ｇｅｎｅｒｉｃ  Ｌｏｇｉｃ１０３上に設定する処理等を行う。これらの処理は、データ入力装置３０等、外部からの命令信号によって行う。
【０２２８】
ある正規表現に対する構成データが設定されたＧｅｎｅｒｉｃ  Ｌｏｇｉｃ１０３に対して、データ入力装置３０からデータ入力回路１０２を経由して被検索データがＧｅｎｅｒｉｃ  Ｌｏｇｉｃ１０３に入力されると、Ｇｅｎｅｒｉｃ  Ｌｏｇｉｃ１０３は、回路上に構成された正規表現に対応する状態遷移を起動させる。この結果、パターンに一致した場合には、その一致した結果を示す信号を、結果出力回路１０４に出力する。ここで、Ｇｅｎｅｒｉｃ  Ｌｏｇｉｃ１０３には、１つの正規表現だけでなく複数の正規表現を構成するための複数のＧｅｎｅｒｉｃ  Ｌｏｇｉｃが構成されている場合もあるため、結果出力回路１０４は、それら全てのＧｅｎｅｒｉｃ  Ｌｏｇｉｃからの一致結果を制御し、結果出力装置３２に出力する。なお、どのパターンに一致したかは、予め定義しておいたパターン番号等により通知するといった方法がある。
【０２２９】
コンフィギュレーション装置１０は、正規表現をＧｅｎｅｒｉｃ  Ｌｏｇｉｃ上に構成するために、構成データ生成装置１で生成した構成データを、パターンマッチング装置３１におけるＣｏｎｆｉｇｕｒａｔｉｏｎ  Ｃｏｎｔｒｏｌｌｅｒ１００に受け渡すためのＰＣＩ  Ｅｘｐｒｅｓｓ等のケーブルなどであっても良い。
【０２３０】
なお、本実施の形態では、前記第１の実施の形態における構成データ生成装置１を用いた形態について説明したが、この構成データ生成装置については、前記第２、又は第３の実施の形態における構成データ生成装置５、又は６を用いても良い。
【０２３１】
また、第４の実施の形態における構成データ生成用プログラム９で実現したものから生成された構成データを用いて実現しても良い。
【０２３２】
次に、本発明の第５の実施の形態の作用効果について説明する。
【０２３３】
本発明の第５の実施の形態では、構文木で表現された正規表現、あるいは、正規表現そのものを入力することで、その正規表現をＧｅｎｅｒｉｃ  Ｌｏｇｉｃ上のｃｈａｒ＿ｎｏｄｅ、ｍｃｈａｒ＿ｎｏｄｅをはじめとする各種ノードを用いてどのように配置すれば良いかを決定し、その構成データを生成し、それを用いたパターンマッチング装置を実現することができる。
【０２３４】
本発明の活用例として、正規表現を用いたパターンマッチング処理をハードウェア回路にて高速に行い、かつ、動的にその正規表現を再構成するためのハードウェア回路、及びパターンマッチング装置のための構成データ生成装置に適用できる。
【０２３５】
また、本構成データ生成装置を用いて生成した構成データによって実現できるパターンマッチング装置は、パソコンやワークステーションに搭載されているソフトウェアベースでのパターンマッチング処理におけるオフロードエンジン、アクセラレーションの分野にも適用できる。
【符号の説明】
【０２３６】
１  構成データ生成装置
２  記憶装置
３  入力
４  出力
５  構成データ生成装置
６  構成データ生成装置
７  入力
８  構成データ生成装置
９  構成データ生成用プログラム
１０  コンフィギュレーション装置
１１  レイヤ番号算出モジュール
１２  レイアウト順序算出モジュール
１３  構成データ生成モジュール
１４  構成データ出力モジュール
１５  レイヤ番号算出モジュール
１６  構成データ生成モジュール
１７  構文木生成モジュール
２１  構文木記憶モジュール
２２  レイアウト順序記憶モジュール
２３  構成データ記憶モジュール
３０  データ入力装置
３１  パターンマッチング装置
３２  結果出力装置
４０  キャラクタノード（ｃｈａｒ＿ｎｏｄｅ）
５０  キャラクタノード（ｃｈａｒ＿ｎｏｄｅ）
６０  メタキャラクタノード（ｍｃｈａｒ＿ｎｏｄｅ）
７０  スイッチノード（ｓｎｏｄｅ）
８０  スイッチノード（ｓｎｏｄｅ）
１００  Ｃｏｎｆｉｇｕｒａｔｉｏｎ  Ｃｏｎｔｒｏｌｌｅｒ
１０１  構成データ記憶装置
１０２  データ入力回路
１０３  Ｇｅｎｅｒｉｃ  Ｌｏｇｉｃ
１０４  結果出力回路
１０５  Ｃｏｎｆｉｇｕｒａｔｉｏｎ  Ｃｏｎｔｒｏｌｌｅｒ
１０６  記憶装置
１０７  Ｇｅｎｅｒｉｃ  Ｌｏｇｉｃ
２００〜２２５  キャラクタノード（ｃｈａｒ＿ｎｏｄｅ）
３００〜３２１  メタキャラクタノード（ｍｃｈａｒ＿ｎｏｄｅ）
４００〜４３５  スイッチノード（ｓｎｏｄｅ）
５００〜５２１  マルチプレクサ（ＭＵＸ）
６００〜６０８  Ｆｌｉｐ−Ｆｌｏｐ（レジスタ）
７００〜７０７  Ｃｏｍｐａｒａｔｏｒ（比較器）
８００〜８０７  ＡＮＤゲート
９００〜９０３  ＯＲゲート
１０００〜１０１５  ＬＵＴ（Ｌｏｏｋ−Ｕｐ  Ｔａｂｌｅ）
【図１】
2011141627.tif 000003
【図２】
2011141627.tif 000004
【図３】
2011141627.tif 000005
【図４】
2011141627.tif 000006
【図５】
2011141627.tif 000007
【図６】
2011141627.tif 000008
【図７】
2011141627.tif 000009
【図８ａ】
2011141627.tif 000010
【図８ｂ】
2011141627.tif 000011
【図８ｃ】
2011141627.tif 000012
【図９】
2011141627.tif 000013
【図１０】
2011141627.tif 000014
【図１１】
2011141627.tif 000015
【図１２】
2011141627.tif 000016
【図１３】
2011141627.tif 000017
【図１４】
2011141627.tif 000018
【図１５ａ】
2011141627.tif 000019
【図１５ｂ】
2011141627.tif 000020
【図１５ｃ】
2011141627.tif 000021
【図１５ｄ】
2011141627.tif 000022
【図１５ｅ】
2011141627.tif 000023
【図１５ｆ】
2011141627.tif 000024
【図１５ｇ】
2011141627.tif 000025
【図１５ｈ】
2011141627.tif 000026
【図１６】
2011141627.tif 000027
【図１７】
2011141627.tif 000028
【図１８】
2011141627.tif 000029
【図１９】
2011141627.tif 000030
【図２０】
2011141627.tif 000031
【図２１】
2011141627.tif 000032
【図２２】
2011141627.tif 000033
【図２３】
2011141627.tif 000034
【図２４】
2011141627.tif 000035
【図２５】
2011141627.tif 000036
【図２６】
2011141627.tif 000037
【図２７】
2011141627.tif 000038
【図２８】
2011141627.tif 000039
【図２９】
2011141627.tif 000040
【図３０】
2011141627.tif 000041
【図３１】
2011141627.tif 000042
【図３２】
2011141627.tif 000043
【図３３】
2011141627.tif 000044
【図３４ａ】
2011141627.tif 000045
【図３４ｂ】
2011141627.tif 000046
【図３５】
2011141627.tif 000047
【図３６ａ】
2011141627.tif 000048
【図３６ｂ】
2011141627.tif 000049
【図３７】
2011141627.tif 000050
【図３８ａ】
2011141627.tif 000051
【図３８ｂ】
2011141627.tif 000052
【図３９】
2011141627.tif 000053
【図４０ａ】
2011141627.tif 000054
【図４０ｂ】
2011141627.tif 000055