(57)【要約】【課題】  パターンマッチングをハードウェアで実現する際に、メモリおよび回路規模を削減し、かつスループットの向上を可能とする。【解決手段】  入力されたテキストのサフィックスに対するパターンにハッシュ関数を適用した結果として得られる文字列の最長プリフィックスを状態として持つオートマトンを構成し、そのオートマトンに同一のハッシュ関数をテキストに適用した結果として得られる文字列を入力し、パターンに一致する可能性のある入力文字列と、パターンに一致する可能性のない入力文字列との識別を行う。次に、ハッシュ関数の適用によって生成される複数の独立した文字列単位でパイプライン並列処理する。最後に、ハッシュを適用したオートマトンによって特定される、パターンと一致する可能性のあるテキスト中の文字列とそのテキストに一致する可能性のあるパターンとを正確に照合する。【選択図】  図１
2005242668.tif 000002
【特許請求の範囲】
【請求項１】
入力文字列であるテキストから複数種類の任意文字列であるパターンを検索するパターンマッチング装置において、
これまでに入力されたテキストのサフィックスに対するパターンにハッシュ関数を適用した結果として得られる文字列の最長プリフィックスを状態として持つオートマトンを構成する手段と、
このオートマトンに同一のハッシュ関数をテキストに適用した結果として得られる文字列を入力することによって、パターンに一致する可能性のある部分テキストと、パターンに一致する可能性のない部分テキストとの識別を行う手段と
を備えたことを特徴とするパターンマッチング装置。
【請求項２】
複数文字から一つのハッシュ値を生成するハッシュ関数を用いる請求項１記載のパターンマッチング装置。
【請求項３】
パターンの１文字あたりのビット幅より小さいビット幅を持つハッシュ値を生成するハッシュ関数を用いる請求項１記載のパターンマッチング装置。
【請求項４】
ハッシュ関数の適用によって生成される独立した複数の文字列単位でパイプライン処理を行う手段を備えた請求項１記載のパターンマッチング装置。
【請求項５】
ハッシュ関数の適用によって生成される独立した複数の文字列単位を並列処理する手段を備えた請求項１記載のパターンマッチング装置。
【請求項６】
ハッシュ関数の適用によって生成される独立した複数の文字列単位を並列処理すると共にパイプライン処理を行う手段を備えた請求項１記載のパターンマッチング装置。
【請求項７】
前記一致する可能性のある部分テキストに対し、パターンと完全に一致するか否かを判定する手段を備えた請求項１記載のパターンマッチング装置。
【請求項８】
入力文字列であるテキストから複数種類の任意文字列であるパターンを検索するパターンマッチング方法において、
これまでに入力されたテキストのサフィックスに対するパターンにハッシュ関数を適用した結果として得られる文字列の最長プリフィックスを状態として持つオートマトンを構成するステップと、
このオートマトンに同一のハッシュ関数をテキストに適用した結果として得られる文字列を入力することによって、パターンに一致する可能性のある部分テキストと、パターンに一致する可能性のない部分テキストとの識別を行うステップと
を実行することを特徴とするパターンマッチング方法。
【請求項９】
複数文字から一つのハッシュ値を生成するハッシュ関数を用いる請求項８記載のパターンマッチング方法。
【請求項１０】
パターンの１文字あたりのビット幅より小さいビット幅を持つハッシュ値を生成するハッシュ関数を用いる請求項８記載のパターンマッチング方法。
【請求項１１】
ハッシュ関数の適用によって生成される独立した複数の文字列単位でパイプライン処理を行うステップを実行する請求項８記載のパターンマッチング方法。
【請求項１２】
ハッシュ関数の適用によって生成される独立した複数の文字列単位を並列処理するステップを実行する請求項８記載のパターンマッチング方法。
【請求項１３】
ハッシュ関数の適用によって生成される独立した複数の文字列単位を並列処理すると共にパイプライン処理を行うステップを実行する請求項８記載のパターンマッチング方法。
【請求項１４】
前記一致する可能性のある部分テキストに対し、パターンと完全に一致するか否かを判定するステップを実行する請求項８記載のパターンマッチング方法。
【請求項１５】
情報処理装置にインストールすることにより、その情報処理装置に、
入力文字列であるテキストから複数種類の任意文字列であるパターンを検索するパターンマッチング装置に相応する機能を実現させるプログラムにおいて、
これまでに入力されたテキストのサフィックスに対するパターンにハッシュ関数を適用した結果として得られる文字列の最長プリフィックスを状態として持つオートマトンを構成する機能と、
このオートマトンに同一のハッシュ関数をテキストに適用した結果として得られる文字列を入力することによって、パターンに一致する可能性のある部分テキストと、パターンに一致する可能性のない部分テキストとの識別を行う機能と
を実現させることを特徴とするプログラム。
【請求項１６】
ハッシュ関数の適用によって生成される独立した複数の文字列単位でパイプライン処理を行う機能を実現させる請求項１５記載のプログラム。
【請求項１７】
ハッシュ関数の適用によって生成される独立した複数の文字列単位を並列処理する機能を実現させる請求項１５記載のプログラム。
【請求項１８】
ハッシュ関数の適用によって生成される独立した複数の文字列単位を並列処理すると共にパイプライン処理を行う機能を実現させる請求項１５記載のプログラム。
【請求項１９】
前記一致する可能性のある部分テキストに対し、パターンと完全に一致するか否かを判定する機能を実現させる請求項１５記載のプログラム。
【請求項２０】
請求項１５ないし１９のいずれかに記載のプログラムが記録された前記情報処理装置読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、与えられた入力文字列であるテキストから任意の複数種類の文字列であるパターンを検索するパターンマッチングを行うための手法および装置に関する。
【背景技術】
【０００２】
与えられたテキストから任意の複数種類のパターンを検索するパターンマッチングは、ワープロソフト、データベースの検索等、多様な分野で応用されている。しかし、情報化社会の進展、そしてハードディスクといった記憶装置の大容量化、低コスト化によって、検索対象となる情報が膨大化している。したがって、パターンマッチングを高効率化するため、そのハードウェア化などの試みがなされている。
【０００３】
ここで、パターンマッチングについて定義する。長さｎのテキストＴと、長さｍのテキストＰを仮定する。ここで、パターンとテキストとはそれぞれ、共通した文字集合に属する文字を、テキストの場合はｎ文字、パターンの場合はｍ文字を、左から右に順番に並べることで構成される。すなわち、テキストＴ中の文字をｔiと表すと、テキストＴはｔ1…ｔnと表記できる。同様にパターンＰはｐ1…ｐmと表記できる。パターンマッチングの目的はテキスト中にパターンが存在するか否かを特定することにある。すなわち、ｔs+1…ｔs+m＝ｐ1…ｐmとなる部分テキストを検出することにある。
【０００４】
パターンマッチングの方法として既に多くの手法が提案されている。パターンマッチングの方法は大きく以下の二つに分類できる。
１）テキストとパターンとの文字比較位置が関数的に変化する方法。
【０００５】
この種の方法では、テキストおよびパターンの双方の文字を比較し、それぞれの文字が一致しない場合は、比較中のテキストとパターンとの重なり位置（以下、ウィンドウと呼ぶ）をテキストに対して右方向に移動させ、ウィンドウ中のテキストとパターンとの比較を再開する。このとき、テキストとパターンとの文字比較回数を減少させるには、文字が一致しなかった際にウィンドウを移動させる幅を可能な限り大きくすることが重要となる。この種の代表的な方法として、ＢＭ(Boyer Moore)，Ｒｅｖｅｒｓｅ  Ｆａｃｔｏｒ，ＫＭＰ(Knuth-Morris-Pratt)などがある（例えば、非特許文献１参照）。
２）テキストとパターンとの文字比較位置が一定に変化する方法。
【０００６】
この種の方法では、どのようなテキストおよびパターンを用いても、テキストとパターンとの文字比較回数が常にテキスト長にのみ依存する特徴がある。この種の方法として、オートマトンを用いた方法およびＳｈｉｆｔ
ＯＲアルゴリズムがある。
【０００７】
前者の方法では、一般的に文字比較回数の期待値が後者の方法より優れる。このため、特にソフトウェア上での実現では、前者の方法が広く用いられる。しかし、前者の方法では、複数パターンを同時に検索することができないという問題がある。さらに、そのハードウェア化に際して以下の問題が生じる。
【０００８】
先の入力文字の比較結果に応じてどれだけウィンドウを右方向に移動できるかが決まる。このため、テキスト中の入力文字をパイプライン処理することができない。
【０００９】
テキストとパターンとの文字比較位置が関数的に変化するため、文字比較回数がテキストとパターンとに依存して変化する。このとき文字比較回数の最悪値は後者の方法より多くなる。文字比較回数の変化にともなうパターンマッチングのスループットの変化を吸収するため、入力テキストのバッファ機構が必要となる。バッファの容量を大きくとることによって、バッファが溢れる確率を小さくすることが可能であるが、完全にバッファが溢れないことを保障することは困難点である。また、バッファ中のテキストが枯渇した場合には、パイプラインがストールするなどの問題が生じる。
【非特許文献１】Christian Charrs and ThierryLecroq“Handbook of Exact String Matching Algorithms”、[online]、[平成16年2月10日検索]、インターネット<URL:http://homepage.stts.edu/~aikawa/string.pdf>
【非特許文献２】A.V.Aho and M.J.Corasick.Efficientstring matching:an aid to bibliographic search.Comm.of theACM.18(6):333-340,June 1975.
【発明の開示】
【発明が解決しようとする課題】
【００１０】
従来技術によるパターンマッチングのハードウェア化では、主にオートマトンを用いた手法が用いられる。オートマトンの特徴としてまず、１）複数パターンを同時に検索することが可能であることが挙げられる。さらに、ハードウェア向きである特徴として、２−１）テキストとパターンとの文字比較位置が一定でありテキストをバッファする機構が必要でない。２−２）テキスト中の文字が入力されてから次の文字が入力されるまでの遅延が他の方法と比較して小さい、ことが挙げられる。その一方で、オートマトンによる方法では、メモリおよび論理回路の規模、スループットの点において幾つかの課題が存在する。
【００１１】
オートマトンを用いた手法では、まず、これまでに入力されたテキストのサフィックスに対するパターンの最長プリフィックスを状態として持つオートマトンを構成する。ここで、任意の文字列ｔiｔi+1…ｔi+jのプリフィックスは、ｔiｔi+1…ｔi+l（０≦ｌ≦ｊ）と定義される。一方、任意の文字列ｔiｔi+1…ｔi+jのサフィックスはｔlｔl+1…ｔi+j（ｉ≦ｌ≦ｉ＋ｊ）と定義される。複数のパターンが存在する場合には、個々のパターンに対するオートマトンを単一のオートマトンとして合成することが可能である。このような方法をＡｈｏ−Ｃｏｒａｓｉｃｋと呼ぶ（例えば、非特許文献２参照）。
【００１２】
図１１はＡｈｏ−Ｃｏｒａｓｉｃｋオートマトンを説明するための図であるが、図１１は例としてパターンをｃａｂｃとｃｂａｃａの２つとした場合に生成されるオートマトンを示している。なお、いずれの状態においても、アーク上に明示されていない文字が入力された場合は状態０に戻る。次に、そのオートマトンに対して入力テキストの文字列を入力させ、入力された文字と現在のオートマトンの状態とから、オートマトンを次の状態に遷移させるという動作を繰り返す。このとき、オートマトンがパターン全体を表す状態（以下、最終状態）に遷移すると、テキスト中の文字列がパターンと一致したことを表す。図１１の例では、状態４と状態８が最終状態である。
【００１３】
図１２は従来のメモリを用いたオートマトンの実現例を示す図であり、図１３は従来のオートマトンの回路展開例を示す図であるが、オートマトンのハードウェア実現に際しては、図１２のように、オートマトンをメモリ上で表現する方法と、図１３のようにオートマトンを直接的に回路化する方法とに分けられる。オートマトンをメモリ上で表現する方法として、新しく入力されたテキストの文字と現在のオートマトンの状態とを入力とし、次に遷移すべき状態を出力とする表が用いられる。しかし、オートマトンを表として実現する場合には、表のエントリ数がテキストの一文字あたりのビット幅に対して指数関数的に増加するという問題がある。
【００１４】
一方、オートマトンをバイナリツリー等を用いて表現することによって、エントリ数を削減する方法もある。しかし、この方法では、テキストの文字が入力されてから次の状態が決定されるまでの遅延が表と比較して大きくなる。この遅延の間、次のテキストの文字に対する照合処理ができないため、スループットが大きく制限される。一方、図１３のオートマトンを直接布線論理化する方法では、オートマトンの状態毎に比較器が必要となる。また、状態間の配線遅延によってスループットが制限される。
【００１５】
本発明は、このような背景に行われたものであって、パターンマッチングをハードウェアで実現する際に、メモリおよび回路規模を削減し、かつスループットの向上を可能とすることができるパターンマッチング装置および方法を提供することを目的とする。
【課題を解決するための手段】
【００１６】
本発明では、従来のオートマトンによるパターンマッチングに対して以下の点を付加することを特徴とする。まず、これまでに入力されたテキストのサフィックスに対するパターンにハッシュ関数を適用した結果として得られる文字列の最長プリフィックスを状態として持つオートマトンを構成し、そのオートマトンに同一のハッシュ関数をテキストに適用した結果として得られる文字列を入力することによって、パターンに一致する可能性のある入力文字列と一致する可能性のない入力文字列との識別を行う。
【００１７】
このとき、複数文字から一つのハッシュ値を生成するハッシュ関数を用いることによって、オートマトンの状態数を削減させることができる。また、パターンの１文字あたりのビット幅より小さいビット幅を持つハッシュ値を生成するハッシュ関数を用いることによって、オートマトンに入力される文字の種類を削減させることができる。
【００１８】
次に、ハッシュ関数の適用によって生成される複数の独立した文字列単位でオートマトンによるパターンマッチングをパイプライン化して並列化する（以下では、パイプライン並列処理という）。最後に、ハッシュを適用したオートマトンによって特定される、パターンと一致する可能性のあるテキスト中の文字列とそのテキストに一致する可能性のあるパターンとを正確に照合することによってパターンマッチングを行う。
【００１９】
このように、本発明では、ハッシュ関数をテキストとパターンとの双方に対して適用することによって、ハッシュ関数によって圧縮された空間上でパターンマッチングを行う。これにより、オートマトンの状態数の削減効果および文字の種類の削減効果が得られる。ハッシュ関数がｋ文字からハッシュ値を生成するとすると、ハッシュ関数の適用されたパターンの文字数は１／ｋに減少する。
【００２０】
オートマトンをメモリ表現する場合のメモリのエントリ数、回路表現する場合の回路規模はオートマトンの状態数に比例する。また、ハッシュ値のビット幅をハッシュ適用前のパターンの一文字あたりのビット幅より小さくすることによって、オートマトンに入力される文字の種類を削減させることが可能である。
【００２１】
すなわち、ハッシュ適用前のパターンの一文字あたりのビット幅をω、ハッシュ値のビット幅をｈωとすると、その削減比は２hω／２ωとなる。オートマトンをメモリを用いて表として表現する場合は、そのメモリエントリ数は文字のビット幅に対して指数関数的に増加する。故に、ハッシュ関数の適用により、本発明の目的である、メモリおよび回路規模の削減が可能となる。
【００２２】
さらに、テキストにｋ文字からハッシュ値を生成する関数を適用すると、一つのテキストからｋ個の独立した文字列が生成される。この独立した文字列間はそれぞれ依存することなくパターンマッチングを行うことができる。故に、これらの文字列をパイプライン並列処理することによって、本発明の目的である、パターンマッチングのスループット向上が得られる。
【００２３】
すなわち、本発明の第一の観点は、入力文字列であるテキストから複数種類の任意文字列であるパターンを検索するパターンマッチング装置であって、本発明の特徴とするところは、これまでに入力されたテキストのサフィックスに対するパターンにハッシュ関数を適用した結果として得られる文字列の最長プリフィックスを状態として持つオートマトンを構成する手段と、このオートマトンに同一のハッシュ関数をテキストに適用した結果として得られる文字列を入力することによって、パターンに一致する可能性のある部分テキストと、パターンに一致する可能性のない部分テキストとの識別を行う手段とを備えたところにある（請求項１）。
【００２４】
このときに、複数文字から一つのハッシュ値を生成するハッシュ関数を用いることが望ましい（請求項２）。また、パターンの１文字あたりのビット幅より小さいビット幅を持つハッシュ値を生成するハッシュ関数を用いることが望ましい（請求項３）。
【００２５】
さらに、ハッシュ関数の適用によって生成される独立した複数の文字列単位でパイプライン処理を行う手段を備えることができる（請求項４）。あるいは、ハッシュ関数の適用によって生成される独立した複数の文字列単位を並列処理する手段を備えることができる（請求項５）。あるいは、ハッシュ関数の適用によって生成される独立した複数の文字列単位を並列処理すると共にパイプライン処理を行う手段を備えることができる（請求項６）。
【００２６】
さらに、前記一致する可能性のある部分テキストに対し、パターンと完全に一致するか否かを判定する手段を備えることができる（請求項７）。
【００２７】
本発明の第二の観点は、入力文字列であるテキストから複数種類の任意文字列であるパターンを検索するパターンマッチング方法であって、本発明の特徴とするところは、これまでに入力されたテキストのサフィックスに対するパターンにハッシュ関数を適用した結果として得られる文字列の最長プリフィックスを状態として持つオートマトンを構成するステップと、このオートマトンに同一のハッシュ関数をテキストに適用した結果として得られる文字列を入力することによって、パターンに一致する可能性のある部分テキストと、パターンに一致する可能性のない部分テキストとの識別を行うステップとを実行するところにある（請求項８）。
【００２８】
このときに、複数文字から一つのハッシュ値を生成するハッシュ関数を用いることが望ましい（請求項９）。また、パターンの１文字あたりのビット幅より小さいビット幅を持つハッシュ値を生成するハッシュ関数を用いることが望ましい（請求項１０）。
【００２９】
さらに、ハッシュ関数の適用によって生成される独立した複数の文字列単位でパイプライン処理を行うステップを実行することができる（請求項１１）。あるいは、ハッシュ関数の適用によって生成される独立した複数の文字列単位を並列処理するステップを実行することができる（請求項１２）。あるいは、ハッシュ関数の適用によって生成される独立した複数の文字列単位を並列処理すると共にパイプライン処理を行うステップを実行することができる（請求項１３）。
【００３０】
さらに、前記一致する可能性のある部分テキストに対し、パターンと完全に一致するか否かを判定するステップを実行することができる（請求項１４）。
【００３１】
本発明の第三の観点は、情報処理装置にインストールすることにより、その情報処理装置に、入力文字列であるテキストから複数種類の任意文字列であるパターンを検索するパターンマッチング装置に相応する機能を実現させるプログラムであって、本発明の特徴とするところは、これまでに入力されたテキストのサフィックスに対するパターンにハッシュ関数を適用した結果として得られる文字列の最長プリフィックスを状態として持つオートマトンを構成する機能と、このオートマトンに同一のハッシュ関数をテキストに適用した結果として得られる文字列を入力することによって、パターンに一致する可能性のある部分テキストと、パターンに一致する可能性のない部分テキストとの識別を行う機能とを実現させるところにある（請求項１５）。
【００３２】
さらに、ハッシュ関数の適用によって生成される独立した複数の文字列単位でパイプライン処理を行う機能を実現させることができる（請求項１６）。あるいは、ハッシュ関数の適用によって生成される独立した複数の文字列単位を並列処理する機能を実現させることができる（請求項１７）。あるいは、ハッシュ関数の適用によって生成される独立した複数の文字列単位を並列処理すると共にパイプライン処理を行う機能を実現させることができる（請求項１８）。
【００３３】
さらに、前記一致する可能性のある部分テキストに対し、パターンと完全に一致するか否かを判定する機能を実現させることができる（請求項１９）。
【００３４】
本発明の第四の観点は、本発明のプログラムが記録された前記情報処理装置読取可能な記録媒体である（請求項２０）。本発明のプログラムは本発明の記録媒体に記録されることにより、前記情報処理装置は、この記録媒体を用いて本発明のプログラムをインストールすることができる。あるいは、本発明のプログラムを保持するサーバからネットワークを介して直接前記情報処理装置に本発明のプログラムをインストールすることもできる。
【００３５】
これにより、汎用の情報処理装置を用いて、スループットの向上を可能とすることができるパターンマッチング装置を実現することができる。
【発明の効果】
【００３６】
本発明によれば、パターンマッチングをハードウェアで実現する際に、メモリおよび回路規模を削減し、かつスループットの向上を可能とすることができる。また、パターンマッチングを汎用の情報処理装置とプログラムとを用いて実現する際にもスループットの向上を可能とすることができる。
【発明を実施するための最良の形態】
【００３７】
本発明実施例のパターンマッチング装置を図１を参照して説明する。図１は本実施例のパターンマッチング装置のブロック構成図である。
【００３８】
本実施例の入力文字列であるテキストから複数種類の任意文字列であるパターンを検索するパターンマッチング装置は、図１に示すように、これまでに入力されたテキストのサフィックスに対するパターンにハッシュ関数を適用した結果として得られる文字列の最長プリフィックスを状態として持つオートマトンを構成するハッシュ計算部１およびオートマトン部２と、このオートマトンに同一のハッシュ関数をテキストに適用した結果として得られる文字列を入力することによって、パターンに一致する可能性のある部分テキストと、パターンに一致する可能性のない部分テキストとの識別を行う最終状態判定部３とを備えたことを特徴とする（請求項１）。
【００３９】
このときに、ハッシュ計算部１は、複数文字から一つのハッシュ値を生成するハッシュ関数を用いる（請求項２）。また、ハッシュ計算部１は、パターンの１文字あたりのビット幅より小さいビット幅を持つハッシュ値を生成するハッシュ関数を用いる（請求項３）。
【００４０】
図４は本実施例のハッシュ計算部１の実装例を示す図であるが、図４に示すように、ハッシュ計算部１は、ハッシュ関数の適用によって生成される独立した複数の文字列単位を並列処理する手段を備える（請求項５）。
【００４１】
また、図５は本実施例のメモリ表現した場合のハッシュによるパイプライン化を示す図であり、図６は本実施例の回路展開した場合のハッシュによるパイプライン化を示す図であるが、図５および図６に示すように、ハッシュ計算部１は、ハッシュ関数の適用によって生成される独立した複数の文字列単位でパイプライン処理を行う手段を備えることもできる（請求項４）。
【００４２】
また、図７は本実施例のパイプライン並列処理を行うオートマトンの実装例を示す図であるが、図７に示すように、ハッシュ関数の適用によって生成される独立した複数の文字列単位を並列処理すると共にパイプライン処理を行う手段を備えることもできる（請求項６）。
【００４３】
さらに、図１に示すように、前記一致する可能性のある部分テキストに対し、パターンと完全に一致するか否かを判定する完全一致照合部４を備える（請求項７）。
【００４４】
本実施例の入力文字列であるテキストから複数種類の任意文字列であるパターンを検索するパターンマッチング方法は、図１に示すハッシュ計算部１およびオートマトン部２により、これまでに入力されたテキストのサフィックスに対するパターンにハッシュ関数を適用した結果として得られる文字列の最長プリフィックスを状態として持つオートマトンを構成するステップを実行し、最終状態判定部３により、このオートマトンに同一のハッシュ関数をテキストに適用した結果として得られる文字列を入力することによって、パターンに一致する可能性のある部分テキストと、パターンに一致する可能性のない部分テキストとの識別を行うステップを実行することを特徴とする（請求項８）。
【００４５】
このとき、ハッシュ計算部１は、複数文字から一つのハッシュ値を生成するハッシュ関数を用いる（請求項９）。また、ハッシュ計算部１は、パターンの１文字あたりのビット幅より小さいビット幅を持つハッシュ値を生成するハッシュ関数を用いる（請求項１０）。
【００４６】
図４に示すハッシュ計算部１の実装例により、ハッシュ関数の適用によって生成される独立した複数の文字列単位を並列処理するステップを実行する（請求項１２）。
【００４７】
図５に示すメモリ表現した場合のハッシュによるパイプライン化または図６に示す回路展開した場合のハッシュによるパイプライン化により、ハッシュ関数の適用によって生成される独立した複数の文字列単位でパイプライン処理を行うステップを実行することもできる（請求項１２）。
【００４８】
さらに、図７に示すパイプライン並列処理するオートマトンの実装例により、ハッシュ関数の適用によって生成される独立した複数の文字列単位を並列処理すると共にパイプライン処理を行うステップを実行することもできる（請求項１３）。
【００４９】
さらに、図１に示す完全一致照合部４により、前記一致する可能性のある部分テキストに対し、パターンと完全に一致するか否かを判定するステップを実行する（請求項１４）。
【００５０】
本発明は、汎用の情報処理装置にインストールすることにより、その情報処理装置に本発明のパターンマッチング装置に相応する機能を実現させるプログラムとして実現することができる（請求項１５〜１９）。このプログラムは、記録媒体に記録されて情報処理装置にインストールされ（請求項２０）、あるいは通信回線を介して情報処理装置にインストールされることにより当該情報処理装置に、ハッシュ計算部１、オートマトン部２、最終状態判定部３、完全一致照合部４にそれぞれ相応する機能を実現させることができる。
【００５１】
以下では、本実施例のパターンマッチング装置および方法をさらに詳細に説明する。
【００５２】
本発明の全体構成を図１に示す。本発明では、あらかじめハッシュ関数が適用されたパターンを用いてオートマトンを構成しておく。次に、ハッシュ計算部１で入力テキストに対して同様のハッシュを適用する。そして、オートマトン部２において、ハッシュが適用されたテキストからハッシュ関数が適用されたパターン検索を行う。このとき、オートマトンを複数コピーすることによって、ハッシュの適用によって生じる独立した文字系列を並列に処理することが可能である。
【００５３】
最終状態判定部３において、オートマトンが最終状態に遷移したか否かを監視する。オートマトンが最終状態に遷移した場合には、ハッシュが適用されたテキストから、ハッシュが適用されたパターンが検出されたことを示す。次に、完全一致照合部４において、ハッシュ適用前のテキストとパターンとが完全一致するか否かを判定する。
【００５４】
（ハッシュ計算部およびオートマトン部の実施例）
図２は複数のパターンからハッシュ関数が適用された一つのオートマトンを生成する手順を示す。まず、各パターンに対して、ハッシュ関数を適用する。ｋ文字から一つのハッシュ値を生成するハッシュ関数をＨ（ｘ1，ｘ2，…，ｘk）とする。また、パターンＰiの文字数をｍiとし、そのパターンをｐi,1ｐi,2…ｐi,miと表記する。このとき、ハッシュ関数生成後のパターン中の文字ｈｐi,j（ｊ＝１，…，ｍi／ｋ）はＨ（ｐi,(j-1)k+1，ｐi,(j-1)k+2，…，ｐi,jk）と表現できる。全てのパターンをハッシュを用いて変換した後、Ａｈｏ−Ｃｈｏｒａｓｉｃｋアルゴリズムに従って、各パターンを単一オートマトンとして合成する。
【００５５】
すなわち、図２に示すように、パターンを取得し（Ｓ１）、このパターンからｋ文字を取得し（Ｓ２）、このｋ文字からハッシュ値を生成する（Ｓ３）。取得したｋ文字を生成したハッシュ値で置き換え（Ｓ４）、未処理の文字あるいは未処理のパターンが無くなるまで、ステップＳ１〜Ｓ４を繰り返し実行する（Ｓ５、Ｓ６）。続いて、Ａｈｏ−Ｃｏｒａｓｉｃｋによる合成オートマトンの生成を行う（Ｓ７）。
【００５６】
図３はテキストに対してハッシュを適用するハッシュ計算部１の入出力を示す図である。図３ではｎ文字からなる入力テキストをｔ1ｔ2…ｔnと表現している。またｔ(j-1)k+iｔ(j-1)k+i+1…ｔjk+iにハッシュを適用した結果得られるハッシュ値をｈｔi,jと表記している。このとき、ｈｐ1…ｈｐm/kとの比較は、ハッシュ適用後テキストｈｔi,j…ｈｔi,j+m/kに対して行えばよい。
【００５７】
すなわち、ｉ≠ｉ′ならば、ハッシュ適用後テキストｈｔi,0ｈｔi,1…とｈｔi′,0ｈｔi′,1…とは互いに依存関係がなく、独立した文字列とみなすことができる。すなわち、ｋ文字から一つのハッシュ値を生成するハッシュ関数は、ｋ個の独立したハッシュ適用後文字列を生成する。これらの文字列はパイプライン並列処理することが可能である。
【００５８】
（ハッシュ計算の実装例）
ハッシュ関数の具体例として、それぞれの文字間で排他的論理和をとることによって、８ビット幅の文字４つから４ビットのハッシュ値を生成するハッシュ計算部１の実装例を図４に示す。ハッシュ関数の例としては、他にＣＲＣなどが挙げられる。
【００５９】
また、ハッシュ値のビット幅がパターンの１文字あたりのビット幅より小さくならないハッシュ関数も同様に利用可能である。特に、入力される各文字をなんら変更せずに任意に並べるハッシュ関数を用いる場合は、オートマトンが最終状態に遷移した後の完全一致照合処理を省略できる。
【００６０】
（パイプライン処理の場合）
図５は、メモリを用いてオートマトンを表現する場合において、ハッシュ適用後テキストをパイプライン処理する構成を示している。オートマトンをメモリ表現する場合に、入力文字と現在の状態から状態メモリのアドレスを計算するアドレス計算部１１と、メモリにアクセスするメモリアクセス部１２からなる。これら二つの計算部、さらにはその計算部をパイプライン化してハッシュ適用後テキストを処理することができる。
【００６１】
図６は、回路展開してオートマトンを表現する場合において、ハッシュ適用後文字列をパイプライン処理する構成を示している。図６では、状態間の配線にレジスタＲを配置し、各ハッシュ適用後テキストをパイプライン処理させることによって、配線遅延の隠蔽を行っている。
【００６２】
（パイプライン並列処理の場合）
図７は、パイプライン並列処理の例として、図４で生成される４つのハッシュ適用後テキストｈｔ1,0ｈｔ1,1…，ｈｔ2,0ｈｔ2,1…，ｈｔ3,0ｈｔ3,1…，およびｈｔ4,0ｈｔ4,1…を並列処理すると共にパイプライン処理する回路を示す。図７では、メモリを用いて表現したオートマトンを２つのパイプラインステージに分割したものを２つ並列に並べることによって、４つのハッシュ適用後テキストを処理している。回路展開する場合も同様に、各状態を２つのステージに細分化したオートマトンを２つ並列に並べることによって、同様のパイプライン並列処理が可能である。
【００６３】
（最終状態判定部の実施例）
最終状態判定部３は、オートマトンの現在の状態が最終状態であるか否かを判定する。図８はオートマトンをメモリ表現した場合の最終状態判定部３の実装例を示す。オートマトンの状態を入力として、パターンと一致する可能性があるか否か、すなわち、いずれかのパターンに対応する最終状態に遷移したか否かを示す信号と、それに対応するパターン番号とを出力する。
【００６４】
一方、図９は、オートマトンを回路で表現する場合の最終状態判定部３の実施例を示している。各最終状態を表す状態のレジスタ値の論理積をとることによって、オートマトンが各パターンの最終状態に遷移したか否かを示す信号を出力する。また、パターン番号を出力とするデコーダを用いて一致する可能性のあるパターンの番号を出力する。
【００６５】
（完全一致照合部の実施例）
最後に完全一致照合部４において、ハッシュ空間で一致したパターンと部分テキストが、ハッシュ適用前のパターンとテキストとで完全に一致するか否かの判定を行う。ハッシュ空間で一致しなかったパターンと部分列とを比較する必要がないため、この処理に求められるスループットは非常に小さい。このため、ハードウェアではなく、ソフトウェア上で実現することも可能である。
【００６６】
図１０は、完全一致照合部４の照合手順例を示す。まず最終状態判定部３からの出力にしたがって、対象とするハッシュ適用済み部分テキストが同じくハッシュ適用済みパターンと一致するか否かによって分岐する。一致する可能性がある場合のみ、ハッシュ適用済み部分テキストに対応するテキストと、一致する可能性のあるパターンとの比較を行う。この処理を未処理のテキストがなくなるまで繰り返す。
【００６７】
すなわち、図１０に示すように、ハッシュ適用済みテキストとパターンとが一致したか否かを判定し（Ｓ１１）、一致した場合には、一致する可能性のある部分テキストを取得し（Ｓ１２）、さらに、一致する可能性のあるパターンを取得する（Ｓ１３）。これら取得したテキストとパターンとを比較する（Ｓ１４）。この比較結果に基づき、テキストとパターンとが一致した場合には（Ｓ１５）、パターン検出結果を出力する（Ｓ１６）。この検出されたパターンが未判定のハッシュ適用済みテキストでなければ（Ｓ１７）処理を終了する。また、この検出されたパターンが未判定のハッシュ適用済みテキストならばステップＳ１１へ戻る。
【００６８】
また、ステップＳ１１において、ハッシュ適用済みテキストとパターンとが一致せず、未判定のハッシュ適用済みテキストでなければ処理を終了する。あるいは、ステップＳ１５において、テキストとパターンとが一致せず、未判定のハッシュ適用済みテキストでなければ処理を終了する。
【産業上の利用可能性】
【００６９】
本発明は、パターンマッチングをハードウェア処理した際の、メモリおよび論理回路の必要量の低減および各種遅延の隠蔽とテキスト中の複数文字を並列処理することによってスループットを向上させることができるので、記憶装置の大容量化、低コスト化による検索対象となる情報の膨大化に対応することができる。また、パターンマッチングを汎用の情報処理装置とプログラムとを用いて実現する際にもスループットの向上を可能とすることができ、検索対象となる情報の膨大化に対応することができる。
【図面の簡単な説明】
【００７０】
【図１】本実施例のパターンマッチング装置のブロック構成図。
【図２】本実施例のオートマトンの生成手順を示すフローチャート。
【図３】本実施例のハッシュ計算部の入出力を示す図。
【図４】本実施例のハッシュ計算部の実装例を示す図。
【図５】本実施例のメモリ表現した場合のハッシュによるパイプライン化を示す図。
【図６】本実施例の回路展開した場合のハッシュによるパイプライン化を示す図。
【図７】本実施例のパイプライン並列処理するオートマトンの実装例を示す図。
【図８】本実施例のメモリ表現した場合の最終状態判定部を示す図。
【図９】本実施例の回路展開した場合の最終状態判定部を示す図。
【図１０】本実施例の完全一致照合部の照合手順を示すフローチャート。
【図１１】従来のＡｈｏ−Ｃｏｒａｓｉｃｋオートマトンを説明するための図。
【図１２】従来のメモリを用いたオートマトンの実現例を示す図。
【図１３】従来のオートマトンの回路展開例を示す図。
【符号の説明】
【００７１】
１  ハッシュ計算部
２  オートマトン部
３  最終状態判定部
４  完全一致照合部
１１  アドレス計算部
１２  メモリアクセス部
Ｒ  レジスタ
【図１】
2005242668.tif 000003
【図２】
2005242668.tif 000004
【図３】
2005242668.tif 000005
【図４】
2005242668.tif 000006
【図５】
2005242668.tif 000007
【図６】
2005242668.tif 000008
【図７】
2005242668.tif 000009
【図８】
2005242668.tif 000010
【図９】
2005242668.tif 000011
【図１０】
2005242668.tif 000012
【図１１】
2005242668.tif 000013
【図１２】
2005242668.tif 000014
【図１３】
2005242668.tif 000015