(57)【要約】  回路化されたＮＦＡ（Non-deterministic  Finite  Automaton）から出力されるＮ個（Ｎは自然数）のパターン検出信号の値の組み合わせの各々について、Ｎ個のパターン検出信号のうち有効となるパターン検出信号に対応するパターンを示す識別子と、その組み合わせの区切りを示すフラグとを、組み合わせに応じて設定されるアドレスにそれぞれ格納するメモリと、回路化されたＮＦＡから出力されたパターン検出信号の値の組み合わせを用いて、該パターン検出信号の値の組み合わせに対応するメモリのアドレスを求めるアドレス生成部と、フラグが特定の値になるまで、アドレス生成部にて求められたアドレスをインクリメントしていきながら当該アドレスに格納された識別子及びフラグをメモリから連続的に読み出す読み出し制御部とを有する。
2008084594.tif 000002
【特許請求の範囲】
【請求項１】
回路化されたＮＦＡ（Non-deterministic  Finite  Automaton）から出力されるＮ個（Ｎは自然数）のパターン検出信号の値の組み合わせの各々について、前記Ｎ個のパターン検出信号のうち有効となるパターン検出信号に対応するパターンを示す識別子と、前記組み合わせの区切りを示すフラグとを、前記組み合わせに応じて設定されるアドレスにそれぞれ格納するメモリと、
前記回路化されたＮＦＡから出力されたパターン検出信号の値の組み合わせを用いて、該パターン検出信号の値の組み合わせに対応する前記メモリのアドレスを求めるアドレス生成部と、
前記フラグが特定の値になるまで、前記アドレス生成部にて求められたアドレスをインクリメントしていきながら当該アドレスに格納された前記識別子及び前記フラグを前記メモリから連続的に読み出す読み出し制御部とを有するパターンマッチング装置。
【請求項２】
請求項１に記載のパターンマッチング装置において、
前記アドレス生成部は、前記回路化されたＮＦＡから出力されたパターン検出信号の値の組み合わせを用いて、該パターン検出信号の値の組み合わせに対応する前記メモリのアドレスを求める際に、前記パターン検出信号の出現し得ない値の組み合わせを冗長入力として扱うパターンマッチング装置。
【請求項３】
回路化されたＮＦＡ（Non-deterministic  Finite  Automaton）から出力されるＮ個（Ｎは自然数）のパターン検出信号の値の組み合わせの各々について、前記Ｎ個のパターン検出信号のうち有効となるパターン検出信号に対応するパターンを示す識別子と、前記組み合わせの区切りを示すフラグとを、前記組み合わせに応じて設定されるアドレスにそれぞれメモリに格納する第１の処理と、
前記回路化されたＮＦＡから出力されたパターン検出信号の値の組み合わせを用いて、該パターン検出信号の値の組み合わせに対応する前記メモリのアドレスを求める第２の処理と、
前記フラグが特定の値になるまで、前記第２の処理にて求められたアドレスをインクリメントしていきながら当該アドレスに格納された前記識別子及び前記フラグを前記メモリから連続的に読み出す第３の処理とを有するパターンマッチング方法。
【請求項４】
請求項３に記載のパターンマッチング方法において、
前記第２の処理は、前記回路化されたＮＦＡから出力されたパターン検出信号の値の組み合わせを用いて、該パターン検出信号の値の組み合わせに対応する前記メモリのアドレスを求める際に、前記パターン検出信号の出現し得ない値の組み合わせを冗長入力として扱うパターンマッチング方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、入力されたデータの中に特定のパターンが存在するか否かを判定するパターンマッチング装置及び方法に関する。
【背景技術】
【０００２】
入力されたデータの中に特定のパターンが存在するか否かを判定するパターンマッチングは、情報処理分野における要素技術であり、その用途は多岐にわたる。例えば、ワードプロセッサでのテキスト検索、バイオテクノロジーにおけるＤＮＡ解析、電子メールなどに潜むコンピュータウィルスの検知、等である。【０００３】
パターンマッチングの実現手段の１つとして、有限オートマトン（別名：有限状態機械、有限ステートマシン）を利用する方法がある。【０００４】
パターンマッチングのための有限オートマトンは、パターンあるいはパターンの集合から作成される。【０００５】
例として、３種類のパターン“ＡＢＣ”，“ＣＡＢ”，“ＡＢＣＤ”を受理するＮＦＡ（Non-deterministic  Finite  Automaton：非決定性有限オートマトン）及びＤＦＡ（Deterministic  Finite  Automaton：決定性有限オートマトン）について説明する。【０００６】
図１は、ＮＦＡの一例を示す図である。また、図２は、ＤＦＡの一例を示す図である。なお、ＮＦＡとＤＦＡの違いについては後述する。【０００７】
パターンマッチングのための有限オートマトンは、初期状態から開始し、入力された文字に対応する枝を経由して次の状態へ遷移する。そして、パターンの最終文字に対応する状態（図中では二重円で囲まれた状態）に到達したら、そのパターンを検出したとみなす。【０００８】
上記の動作を、テキストの先頭から末尾までの全ての文字について繰り返し実施する。【０００９】
有限オートマトンの表現形式として、ＮＦＡとＤＦＡの２種類が存在する。【００１０】
ＤＦＡは、決定性という単語が示すように、現在の状態と入力が決まると、次の状態が一意に定まる有限オートマトンである。一方、ＮＦＡは、次の状態が一意に定まらない有限オートマトンである。【００１１】
例えば、図１に示したＮＦＡの状態“０”に着目すると、入力された文字“Ａ”に対応する遷移先は状態“０”、状態“１”、状態“２”の３つが存在する。【００１２】
逐次処理コンピュータ上でＮＦＡを動作させる場合、ある状態からの遷移先が複数存在するとき、その状態をスタックに積んでから、複数の遷移先のうち１つを選んで状態遷移する。そして、状態遷移できなくなるかテキストの末尾に達するまでＮＦＡを辿る。【００１３】
その後、スタックから状態を１つ取り出して、その状態へ復帰し、前回と異なる遷移先を選択して状態遷移する。【００１４】
上記の動作をスタックが空になるまで繰り返す。【００１５】
このように、逐次処理コンピュータ上でＮＦＡを動作させる場合、過去の状態に戻って状態遷移を再開する行為、すなわち、バックトラック（Backtracking）が発生する。このバックトラックの影響により、ＮＦＡに基づく検索の速度はＤＦＡよりも劣る。【００１６】
一方、ＤＦＡに含まれる状態の数と状態遷移の数（枝の本数）は、ＮＦＡよりも多くなる傾向がある。そのため、ＤＦＡを格納するためのメモリの量はＮＦＡの場合よりも多くなる。また、ＤＦＡの作成には多くの計算量を必要とすることが知られている。【００１７】
上述のように、ＮＦＡの唯一の欠点は、バックトラックによる検索速度の低下である。バックトラックは、逐次処理コンピュータにおいて複数の遷移先を同時に探索できないという制約に起因して発生する。すなわち、バックトラックを抑制するには並列処理が求められる。【００１８】
そこで、ＮＦＡをフリップフロップと各種ゲート（ＡＮＤやＯＲ）との組み合わせで表現して、それらを回路としてＬＳＩ等のデバイスに埋め込み、その回路を利用してパターンマッチングする方法が、著者：R.  Sidhu  and  V.  K.  Prasanna、題目：Fast  Regular  Expression  Matching  using  FPGAs、出典：Field-Programmable  Custom  Computing  Machines  (FCCM),  Rohnert  Park,  CA,  USA,  Apr.  2001の文献に提案されている。【００１９】
このようにＮＦＡを回路化することにより、ＮＦＡの欠点であるバックトラックを解消できる。その理由は、回路においては全てのフリップフロップとゲートは並列に動作可能であるからである。【００２０】
図３は、入力されるパターンの一例を示す図である。また、図４は、図３に示したパターンを受理するＮＦＡを示す図である。また、図５は、図４に示したＮＦＡをフリップフロップとゲートとで表現した回路図の一例を示す図である。【００２１】
図３に示す３つのパターン“ＡＢ＊Ｃ”，“Ａ［Ｂ｜Ｃ］”，”ＣＡＢ”には、正規表現が含まれる。正規表現とはパターンを簡潔に表現するための表現法である。【００２２】
第１のパターン“ＡＢ＊Ｃ”に含まれる“Ｂ＊”は０個以上のＢの連続を表す。従って、第１のパターンは、テキスト“ＡＣ”，“ＡＢＣ”，“ＡＢＢＣ”，…にマッチする。【００２３】
第２のパターン“Ａ［Ｂ｜Ｃ］”に含まれる“［Ｂ｜Ｃ］”はＢまたはＣを表す。従って、第２のパターンは、テキスト“ＡＢ”，“ＡＣ”にマッチする。【００２４】
図５に示すように、ＮＦＡ回路１０の入力は、検索対象のテキスト２０の構成要素である文字２２である。テキスト２０は、その先頭の文字から順に１文字ずつ、文字２２としてＮＦＡ回路１０に与えられる。【００２５】
ＮＦＡ回路１０は、Ｘ番目のパターンを検出するたびに、パターン検出信号３０−Ｘ（１≦Ｘ≦３）を１にする。一方、それ以外のパターン検出信号３０−１〜３０−３を０にする。なお、ＮＦＡの非決定性によりパターン検出信号３０−１〜３０−３のうち２つ以上が、同時に１になる場合もある。【００２６】
図４に示したＮＦＡの回路化は、状態の回路化ステップと状態遷移の回路化ステップを経て行われる。【００２７】
状態の回路化ステップでは、ＮＦＡの中の１つの状態を１つのフリップフロップで置き換える。状態が有効であるとき、対応するフリップフロップの出力値が１になる。【００２８】
状態遷移の回路化ステップでは、遷移条件となる文字（＝ＮＦＡの枝に付与されている文字）と文字２２とを比較する比較器を配置する。比較器は、両者が一致していれば１を出力する。【００２９】
比較器の出力と、遷移元のフリップフロップの出力との論理積（ＡＮＤ）をとり、その論理積を、遷移先のフリップフロップの入力とする。また、複数の状態から１つの状態への遷移が存在する場合は、複数の遷移元からの論理積の論理和（ＯＲ）をとり、その論理和を遷移先のフリップフロップの入力とする。【００３０】
回路化されたＮＦＡを利用するパターンマッチング方法は、所望のパターンを検索するための専用回路を構成するので、検索速度が極めて高速であるという利点を有する。【００３１】
しかしながら、回路化されたＮＦＡを利用するパターンマッチング方法は、多数のパターンが存在している場合、テキストにマッチしたパターンを識別することが困難であるという問題点がある。【００３２】
以下に、この問題点について詳細に説明する。【００３３】
最も単純なパターン識別方法は、図５に示したＮＦＡ回路１０が出力するパターン検出信号３０−１〜３０−Ｎの値を個別に調べることである。ここで、Ｎはパターンの個数である。【００３４】
パターン検出信号３０−Ｘ（１≦Ｘ≦Ｎ）の値が１であれば、Ｘ番目のパターンが検出されたことになる。この方法では、例えばパターンの個数が１００００であるとき、１００００本のパターン検出信号３０−１〜３０−１００００の値を全て検査する回路を設ける必要がある。従って、この方法は、パターンの個数が多いとき、ゲート規模・配線量・動作速度の点で実現性に乏しいと言える。【００３５】
そこで、より洗練された別のパターン識別方法としてプライオリティ・エンコーダを用いる従来法が、著者：小野  正人（筑波大学システム情報工学研究科）、他、題目：NIDSにおけるNFAパターンマッチング回路の設計と試作、出典：電子情報通信学会  信学技報  CPSY2004-17の文献に記載されている。【００３６】
プライオリティ・エンコーダとは、入力されたビット列を数値にエンコードする回路である。一般的には、入力されたＮビットは０以上（Ｎ−１）以下の数値に変換され、エンコード後の数値はｌｏｇ２（Ｎ）ビットで表現される。【００３７】
入力されたビット列において同時に複数のビットが１になった場合でも出力値を確定させるために、各ビットに優先度が付与される。優先度の高いビットが１であった場合、それよりも優先度が低いビットは無視される。【００３８】
パターンに正規表現が含まれなければ、プライオリティ・エンコーダを用いてパターン検出信号３０−１〜３０−Ｎのビット列を数値にエンコードし、エンコード後の数値を参照してテキストに含まれるパターンの種類を識別できる。【００３９】
例えば、Ｎ＝８１９２であるとき、エンコード後の数値は０〜８１９１となり、１３ビットで表現される（ｌｏｇ２（８１９２）＝１３）。【００４０】
すなわち、８１９２本のパターン検出信号３０−１〜３０−８１９２を直接参照する必要はなくなり、回路規模が削減される。【００４１】
しかし、プライオリティ・エンコーダを用いる従来法では、パターンに正規表現が含まれる場合、パターンの種類を常に識別できるとは限らない。【００４２】
以下に、この理由について具体例を用いて説明する。【００４３】
前述のとおり、プライオリティ・エンコーダを使用する際には、入力される各ビットに優先順位を定義しなければならない。言い換えれば、各ビットに優先順位を一意に定義できなければ、エンコード後の数値を参照してテキストに含まれるパターンの種類を正確に識別できない。【００４４】
図６は、図５に示したＮＦＡ回路１０が出力するパターン検出信号３０−１〜３０−３の値の組み合わせを示す図である。【００４５】
図６に示した入力表１５のパターン検出信号３０−１とパターン検出信号３０−２の列に着目すると、それらの値の組み合わせは００，０１，１０，１１の４通りである。これの意味するところは、パターン検出信号３０−１とパターン検出信号３０−２の値が、それぞれ単独で１になる場合もあり、かつ、両方とも１になる場合もある、ということである。【００４６】
つまり、パターン検出信号３０−１とパターン検出信号３０−２は従属関係を満たしていないため、それらの間の優先順位を確定できないことが分かる。【００４７】
以上説明したように、回路化されたＮＦＡを利用するパターンマッチング方法において、パターンに正規表現が含まれる場合、テキストにマッチしたパターンを識別する実用的な方法は確立されていなかった。
【発明の開示】
【００４８】
本発明は、上述したような従来の技術が有する問題点に鑑みてなされたものであって、テキストにマッチしたパターンの種類を全て識別可能なパターンマッチング装置及び方法を提供することを目的とする。
【００４９】
上記目的を達成するために本発明は、
回路化されたＮＦＡ（Non-deterministic  Finite  Automaton）から出力されるＮ個（Ｎは自然数）のパターン検出信号の値の組み合わせの各々について、前記Ｎ個のパターン検出信号のうち有効となるパターン検出信号に対応するパターンを示す識別子と、前記組み合わせの区切りを示すフラグとを、前記組み合わせに応じて設定されるアドレスにそれぞれ格納するメモリと、
前記回路化されたＮＦＡから出力されたパターン検出信号の値の組み合わせを用いて、該パターン検出信号の値の組み合わせに対応する前記メモリのアドレスを求めるアドレス生成部と、
前記フラグが特定の値になるまで、前記アドレス生成部にて求められたアドレスをインクリメントしていきながら当該アドレスに格納された前記識別子及び前記フラグを前記メモリから連続的に読み出す読み出し制御部とを有する。
【００５０】
上記のように構成された本発明においては、回路化されたＮＦＡから出力されるＮ個のパターン検出信号の値の組み合わせの各々について、Ｎ個のパターン検出信号のうち有効となるパターン検出信号に対応するパターンを示す識別子と、Ｎ個のパターン検出信号の値の組み合わせの区切りを示すフラグとが、メモリのうち組み合わせに応じて設定されるアドレスにそれぞれ格納される。その後、回路化されたＮＦＡからパターン検出信号の値が出力されると、アドレス生成部において、その組み合わせを用いてパターン検出信号の値の組み合わせに対応するメモリのアドレスが求められ、読み出し制御部において、メモリから読み出されるフラグが特定の値になるまで、アドレス生成部にて求められたアドレスをインクリメントしていきながらそのアドレスに格納された識別子及びフラグがメモリから連続的に読み出される。
【００５１】
本発明においては、回路化されたＮＦＡから出力されるＮ個のパターン検出信号の値の組み合わせの各々について、Ｎ個のパターン検出信号のうち有効となるパターン検出信号に対応するパターンを示す識別子と、Ｎ個のパターン検出信号の値の組み合わせの区切りを示すフラグとを、組み合わせに応じて設定されるアドレスにそれぞれ格納するメモリと、回路化されたＮＦＡから出力されたパターン検出信号の値の組み合わせを用いて、該パターン検出信号の値の組み合わせに対応するメモリのアドレスを求めるアドレス生成部と、フラグが特定の値になるまで、アドレス生成部にて求められたアドレスをインクリメントしていきながら当該アドレスに格納された識別子及びフラグをメモリから連続的に読み出す読み出し制御部とを有する構成としたため、テキストにマッチしたパターンの種類を識別することができる。
【図面の簡単な説明】
【００５２】
【図１】ＮＦＡの一例を示す図である。
【００５３】
【図２】ＤＦＡの一例を示す図である。
【００５４】
【図３】入力されるパターンの一例を示す図である。
【００５５】
【図４】図３に示したパターンを受理するＮＦＡを示す図である。
【００５６】
【図５】図４に示したＮＦＡをフリップフロップとゲートとで表現した回路図の一例を示す図である。
【００５７】
【図６】図５に示したＮＦＡ回路が出力するパターン検出信号の値の組み合わせを示す図である。
【００５８】
【図７】本発明のパターンマッチング装置の実施の一形態を示すブロック図である。
【００５９】
【図８】図７に示したＮＦＡ回路、アドレス生成部、パターンＩＤメモリの内容、終端フラグメモリの内容を求める方法を説明するためのフローチャートである。
【００６０】
【図９】図４に示したＮＦＡから変換されたＤＦＡを示す図である。
【００６１】
【図１０】図７に示したパターンＩＤメモリ、終端フラグメモリ及びインデックスの内容を、図に示した３つのパターンに対応する入力表から作成する様子を示す図である。
【００６２】
【図１１】図８のフローチャートのステップＳ１０２をプログラム的に表現した詳細なアルゴリズムを示す図である。
【００６３】
【図１２】図７に示したアドレス生成部の真理値表が入力表とインデックスとから構成されることを示す図である。
【００６４】
【図１３】図１２に示した真理値表を満足するアドレス生成部の回路図の一例を示す図である。
【００６５】
【図１４】図７に示したパターンマッチング装置の内部の信号の変化を時系列で示すタイムチャートの一例である。
【００６６】
【図１５】図７に示した読み出し制御部の動作を示すフローチャートである。
【発明を実施するための最良の形態】
【００６７】
以下に、本発明の実施の形態について図面を参照して説明する。なお、本発明では、パターンマッチングの対象となるデータを「テキスト」と呼ぶ。また、テキスト及びパターンは、１つ以上の「文字」の並びから構成されるものとする。文字は、人間が認識可能なものに限定されず、単なる数値（バイナリ）でもよい。【００６８】
図７は、本発明のパターンマッチング装置の実施の一形態を示すブロック図である。【００６９】
本形態におけるパターンマッチング装置１は図７に示すように、ＮＦＡ回路１０と、アドレス生成部１１と、読み出し制御部１２と、パターンＩＤメモリ１３と、終端フラグメモリ１４とから構成されている。そして、テキスト２０を入力とし、テキスト２０の中でパターンを発見するたびに、そのパターンに付随する識別子であるパターンＩＤ２１を出力する。テキスト２０は、その先頭の文字から順に１文字ずつ、文字２２としてパターンマッチング装置１に与えられる。【００７０】
ＮＦＡ回路１０は、図５に示したように、背景技術で述べた方法を用いて回路化されたＮＦＡである。例えば、著者：R.  Sidhu  and  V.  K.  Prasanna、題目：Fast  Regular  Expression  Matching  using  FPGAs、出典：Field-Programmable  Custom  Computing  Machines  (FCCM),  Rohnert  Park,  CA,  USA,  Apr.  2001の文献に記載された方法を用いて回路化されたものである。ＮＦＡ回路１０の入力は、テキスト２０の構成要素である文字２２である。ＮＦＡ回路１０は、Ｘ番目のパターンを検出するたびに、パターン検出信号３０−Ｘ（１≦Ｘ≦Ｎ）を１にし、それ以外のパターン検出信号３０−１〜３０−Ｎを０にする。ここで、Ｎは、パターンの個数であり、自然数である。なお、ＮＦＡの非決定性によりパターン検出信号３０−１〜３０−Ｎのうち２つ以上が、同時に１になる場合もある。【００７１】
アドレス生成部１１は、パターン検出信号３０−１〜３０−Ｎの値の組み合わせに対応する開始アドレス３１を算出する。開始アドレス３１は、パターンＩＤメモリ１３と終端フラグメモリ１４において、読み出しを開始するアドレスである。アドレス生成部１１は、パターンに依存し、後述の方法によりパターンから設計される。【００７２】
読み出し制御部１２は、アドレス生成部１１から開始アドレス３１を受け取り、パターンＩＤメモリ１３と終端フラグメモリ１４へ与えるアドレス３２を生成する。そして、終端フラグメモリ１４から読み出された終端フラグ３３が１になるまで、アドレス３２をインクリメントする。なお、終端フラグ３３は、パターン検出信号３０−１〜３０−Ｎの組み合わせの区切りを示すフラグとなる。【００７３】
パターンＩＤメモリ１３は、読み出し制御部１２の制御によって、アドレス３２に対応するメモリの内容が読み出され、パターンＩＤ２１として出力する。【００７４】
終端フラグメモリ１４は、読み出し制御部１２の制御によって、アドレス３２に対応するメモリの内容が読み出され、終端フラグ３３として出力する。【００７５】
パターンＩＤメモリ１３及び終端フラグメモリ１４の内容はパターンに依存し、後述の方法によりパターンから作成される。【００７６】
なお、本形態では、パターンＩＤメモリ１３と終端フラグメモリ１４とを個別に扱っているが、これらを物理的に同一のメモリに収容しても差し支えない。【００７７】
以下に、上述したＮＦＡ回路１０、アドレス生成部１１、パターンＩＤメモリ１３の内容、終端フラグメモリ１４の内容それぞれを、パターンから設計・決定する方法についてフローチャートを参照して説明する。【００７８】
図８は、図７に示したＮＦＡ回路１０、アドレス生成部１１、パターンＩＤメモリ１３の内容、終端フラグメモリ１４の内容を求める方法を説明するためのフローチャートである。【００７９】
まず、ステップＳ１００において、パターンからＮＦＡ回路１０を設計する。この設計手法は公知のものであり、背景技術にて説明済みである。【００８０】
次に、ステップＳ１０１において、パターン検出信号３０−１〜３０−Ｎの、出現しうる値の組み合わせが全て列挙された入力表１５を作成する。パターン検出信号３０−１〜３０−Ｎは、それぞれ０か１かの２値をとるため、最大で「２のＮ乗」個の組み合わせを持つ。【００８１】
しかし、「２のＮ乗」個の組み合わせの全てが実際に出現するとは限らない。出現しうるパターン検出信号３０−１〜３０−Ｎの組み合わせは、パターンによって一意に決まる。組み合わせを求めるための好適な方法は、ステップＳ１００で求めたＮＦＡを、ＤＦＡに変換することである。部分集合構成（Subset  Construction）法などの公知のアルゴリズムにより、ＮＦＡをＤＦＡに変換できる。【００８２】
図９は、図４に示したＮＦＡから変換されたＤＦＡを示す図である。【００８３】
図９中の楕円はＤＦＡ状態を表し、楕円に含まれる１つ以上の数字はそれぞれＮＦＡ状態の番号を示している。つまり、ＤＦＡの各状態は、ＮＦＡ状態の１つ以上の集合になっている。【００８４】
例えば、図９のＤＦＡ状態｛０，１，２｝は、ＮＦＡ状態“０”と“１”と“２”が同時に有効になっており、その他のＮＦＡ状態が無効になっている状態を意味する。従って、ＤＦＡ状態｛０，１，２｝に遷移したとき、ＮＦＡ回路１０においては、
・ＮＦＡ状態“１”に対応するパターン検出信号３０−１の値＝１
・ＮＦＡ状態“２”に対応するパターン検出信号３０−２の値＝１
・ＮＦＡ状態“３”に対応するパターン検出信号３０−３の値＝０
になる。【００８５】
すなわち、各ＤＦＡ状態は、パターン検出信号３０−１〜３０−Ｎの値の組み合わせの１つに対応する。【００８６】
ゆえに、ＤＦＡを求めることにより、パターン検出信号３０−１〜３０−Ｎの値の組み合わせを全て得ることができる。【００８７】
入力表１５は、パターン検出信号３０−１〜３０−Ｎの値の全ての組み合わせが行単位に配列された表である。値が全て０のパターン検出信号３０−１〜３０−Ｎに対応する行は、入力表１５の第１行に配置される。入力表１５の２行目以降については順不同である。【００８８】
図１０は、図７に示したパターンＩＤメモリ１３、終端フラグメモリ１４及びインデックスの内容を、図３に示した３つのパターンに対応する入力表から作成する様子を示す図である。【００８９】
ステップＳ１０２において、入力表１５を元にして、パターンＩＤメモリ１３の内容、終端フラグメモリ１４の内容、インデックス１６をそれぞれ作成する。【００９０】
インデックス１６は、図８に示すフローチャートにおいて計算途中に作成されるテンポラリな１次元配列であって、パターンマッチング装置１の構成要素ではない。インデックス１６は、Ｍ個のセルを持ち、各セルにはパターンＩＤメモリ１３と終端フラグメモリ１４のアドレスが格納される。ここでＭは、入力表１５の行数、すなわち、パターン検出信号３０−１〜３０−Ｎの値の組み合わせの数である。【００９１】
図１１は、図８のフローチャートのステップＳ１０２をプログラム的に表現した詳細なアルゴリズムを示す図である。【００９２】
アルゴリズムＡ１０２に登場する変数の意味は、下記の通りである。
・ｉｎｄｅｘ［Ｘ］（０≦Ｘ＜Ｍ）…インデックス１６の（Ｘ＋１）番目のセルの値
・ｉｎｐｕｔ［Ｘ］［Ｙ］（０≦Ｘ＜Ｍ、０≦Ｙ＜Ｎ）…入力表１５の（Ｘ＋１）行目（Ｙ＋１）桁目のセルの値
・ｐａｔｔｅｒｎ＿ｉｄ［Ｘ］（Ｘ≧０）…パターンＩＤメモリ１３のアドレス”Ｘ”の内容
・ｔｅｒｍｉｎａｔｉｏｎ＿ｆｌａｇ［Ｘ］（Ｘ≧０）…終端フラグメモリ１４のアドレス”Ｘ”の内容
アルゴリズムＡ１０２を文章で表現すると、次のようになる。【００９３】
入力表１５の各行について、パターン検出信号３０−Ｘ（１≦Ｘ≦Ｎ）に対応するセルの値が１であれば、Ｘ番目のパターンのＩＤをパターンＩＤメモリ１３に追記する。【００９４】
また、そのセルが、値が１である最後のセルであれば、終端フラグメモリ１４に１を追記し、そうでなければ０を追記する。【００９５】
上記の処理を、入力表１５の第１行から最終行まで順に実行する。【００９６】
パターンＩＤメモリ１３及び終端フラグメモリ１４への書き込みはアドレス“１”から開始される。すなわち、パターンＩＤメモリ１３及び終端フラグメモリ１４のアドレス“０”の内容は不定である。【００９７】
また、入力表１５のＸ行目（１≦Ｘ≦Ｎ）の処理において、パターンＩＤメモリ１３及び終端フラグメモリ１４に初めて値を書き込んだとき、その書き込んだアドレスをインデックス１６のＸ番目のセルに代入する。【００９８】
このようにして、図１０に示すように、パターンＩＤメモリ１３及び終端フラグメモリ１４には、ＮＦＡ回路１０から出力されるパターン検出信号３０−１〜３０−Ｎの値の組み合わせの各々について、パターン検出信号３０−１〜３０−Ｎのうち有効となるパターン検出信号に対応するパターンを示すパターンＩＤと、その組み合わせの区切りとなる終端を示す終端フラグとが、組み合わせに応じて設定されるアドレスにそれぞれ格納される。【００９９】
次に、ステップＳ１０３において、入力表１５とインデックス１６とから真理値表１７を作成する。論理回路における真理値表とは、入力値とそれに対応した出力値を表形式で表したものである。【０１００】
図１２は、図７に示したアドレス生成部１１の真理値表が入力表とインデックスとから構成されることを示す図である。【０１０１】
図１２に示すように、真理値表１７の入力はパターン検出信号３０−１〜３０−Ｎであり、出力は開始アドレス３１である。また、真理値表１７の入力値の組み合わせは入力表１５であり、それに対応する出力値はインデックス１６である。【０１０２】
さらに、入力表１５に定義されていない入力値の組み合わせ、すなわち、パターン検出信号の出現し得ない値の組み合わせを、冗長入力として扱う。冗長入力に対応する出力値を、任意（Don't  care）とする。【０１０３】
例として、図１０に示した入力表１５とインデックス１６から作成された真理値表１７を図１２の下部に示す。【０１０４】
次に、ステップＳ１０４において、真理値表１７からアドレス生成部１１を設計する。アドレス生成部１１は、真理値表１７を満足する論理回路である。【０１０５】
図１３は、図１２に示した真理値表１７を満足するアドレス生成部１１の回路図の一例を示す図である。【０１０６】
一般的に、真理値表から論理回路を設計するには、真理値表を論理圧縮して簡略化された論理式を導出する手順を踏む。特に、真理値表１７には冗長入力が存在するため、論理圧縮によってコンパクトな論理回路を得られやすい。【０１０７】
このように、開始アドレス３１をパターン検出信号の値の組み合わせから求める際に、パターン検出信号の出現し得ない値の組み合わせを冗長入力として扱うことにより、アドレスを求める回路の規模を小さくすることができる。【０１０８】
論理圧縮に関する公知の方法としては、カルノー（Karnaugh）図、クワイン（Quine）法、クワイン−マクラスキー（Quine-McCluskey）法が代表的である。これらはデジタル電子回路設計の基本であって本分野における一般知識であるため、それらの説明は割愛する。【０１０９】
以下に、図７に示したパターンマッチング装置１の動作について、具体例を挙げて詳細に説明する。【０１１０】
本例では、図３に示した３つのパターン“ＡＢ＊Ｃ”，“Ａ［Ｂ｜Ｃ］”，“ＣＡＢ”を使用する。また、テキスト２０は、４文字からなる文字列“ＡＣＡＢ”であると仮定する。すなわち、文字２２として“Ａ”，“Ｃ”，“Ａ”，“Ｂ”がパターンマッチング装置１に順次与えられる。【０１１１】
上述した実施の形態における方法により、それら３つのパターンに対応するＮＦＡ回路１０、アドレス生成部１１、パターンＩＤメモリ１３及び終端フラグメモリ１４の内容は、それぞれ図５、図１３及び図１０のように作成される。【０１１２】
以下に、パターンマッチング装置１が、パターンをテキスト２０の中で検出するたびに、そのパターンに付随するパターンＩＤを出力する動作について説明する。【０１１３】
図１４は、図７に示したパターンマッチング装置１の内部の信号の変化を時系列で示すタイムチャートの一例であり、本例における、パターン検出信号３０−１〜３０−３、開始アドレス３１、アドレス３２、終端フラグ３３、パターンＩＤ２１、のそれぞれの値を時系列順に記している。【０１１４】
まず、テキスト２０の１文字目の“Ａ”がパターンマッチング装置１に入力されたときの動作を説明する。【０１１５】
文字２２として“Ａ”が図５に示したＮＦＡ回路１０に与えられると、ＮＦＡ回路１０はパターン検出信号３０−１〜３０−３を出力し、それらの値は全て０になる。【０１１６】
パターン検出信号３０−１〜３０−３はアドレス生成部１１へ入力され、開始アドレス３２として０が出力される。開始アドレス３２は読み出し制御部１２に与えられる。【０１１７】
ここで、読み出し制御部１２の動作を説明する。【０１１８】
図１５は、図７に示した読み出し制御部１２の動作を示すフローチャートである。【０１１９】
まず、ステップＳ２００において、アドレス生成部１１から開始アドレス３１を取得する。【０１２０】
次に、ステップＳ２０１において、開始アドレス３１の値が０であるか否かを判定し、０であればステップＳ２００に戻る。０以外であれば、ステップＳ２０２において、取得した開始アドレス３１をアドレス３２に代入する。【０１２１】
ステップＳ２０２とステップＳ２０３の間において、パターンＩＤメモリ１３及び終端フラグメモリ１４は、読み出し制御部１２の制御によって、アドレス３２に対応するメモリの内容を読み出し、パターンＩＤ２１、終端フラグ３３として、それぞれ出力する。【０１２２】
ステップＳ２０３において、読み出し制御部１２は、読み出された終端フラグ３３を受け取る。【０１２３】
その後、ステップＳ２０４において、終端フラグ３３の値が１であるか否かを判定し、１であればステップＳ２００に戻る。また、１以外であれば、ステップＳ２０５において、アドレス３２の内容を１だけ増加させてから、ステップＳ２０３に戻る。【０１２４】
パターンマッチング装置１の動作の説明に復帰する。【０１２５】
前述のように、文字２２として“Ａ”が入力された時点では、開始アドレス３２の値は０である。【０１２６】
このとき、読み出し制御部１２では、図１５に示したステップＳ２０１の条件が成立して即座にステップＳ２００に戻り、テキスト２０の１文字目に対応する処理は終了する。【０１２７】
この時点ではパターンは検出されず、パターンＩＤ２１は出力されない。【０１２８】
引き続き、テキスト２０の２文字目の“Ｃ”がパターンマッチング装置１に入力されたときの動作を説明する。【０１２９】
文字２２として”Ｃ”が図５に示したＮＦＡ回路１０に与えられると、パターン検出信号３０−１〜３０−３の値は順に１，１，０になる。【０１３０】
このとき、アドレス生成部１１は、開始アドレス３２として２を出力する。【０１３１】
読み出し制御部１２では、開始アドレス３２の値が０以外であるため、図１５に示したステップＳ２０１の条件は成立せずにステップＳ２０２へ進み、開始アドレス３１の値、すなわち２がアドレス３２に代入される。【０１３２】
図１０を参照すると、パターンＩＤメモリ１３のアドレス“２”に対応するメモリの内容は第１のパターンのＩＤであるから、パターンＩＤ２１として第１のパターンのＩＤが出力される。【０１３３】
また、終端フラグメモリ１４のアドレス“２”に対応するメモリの内容は０であるから、終端フラグ３３の値は０になる。終端フラグ３３の値は０であるため、図１５に示したステップＳ２０４の条件は成立せず、ステップＳ２０５へ進み、アドレス３２に１を加算して３とする。【０１３４】
前回と同様に、図１０を参照すると、パターンＩＤメモリ１３のアドレス“３”に対応するメモリの内容は第２のパターンのＩＤであるから、パターンＩＤ２１として第２のパターンのＩＤが出力される。【０１３５】
また、終端フラグメモリ１４のアドレス“３”に対応するメモリの内容は１であるから、終端フラグ３３の値は１になる。終端フラグ３３の値は０でないため、ステップＳ２０４の条件が成立し、ステップＳ２００に戻り、テキスト２０の２文字目に対応する処理は終了する。【０１３６】
テキスト２０の３文字目のＡ及び４文字目のＢがパターンマッチング装置１に入力された際の動作は上記と同様である。【０１３７】
以上、実施例を参照して本願発明を説明したが、本願発明は上記実施例に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。【０１３８】
この出願は、２００７年１月１２日に出願された日本出願特願２００７−００４４５８を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【図１】
2008084594.tif 000003
【図２】
2008084594.tif 000004
【図３】
2008084594.tif 000005
【図４】
2008084594.tif 000006
【図５】
2008084594.tif 000007
【図６】
2008084594.tif 000008
【図７】
2008084594.tif 000009
【図８】
2008084594.tif 000010
【図９】
2008084594.tif 000011
【図１０】
2008084594.tif 000012
【図１１】
2008084594.tif 000013
【図１２】
2008084594.tif 000014
【図１３】
2008084594.tif 000015
【図１４】
2008084594.tif 000016
【図１５】
2008084594.tif 000017
【国際調査報告】
2008084594.tif 000018
2008084594.tif 000019