(57)【要約】【課題】  パターンマッチングをハードウェア処理した際の各種遅延の隠蔽およびスループットの向上を可能とする。【解決手段】  個々のパターンの各文字を関数を用いて振り分けることによって、パターンを複数のパターンに分割し、これまでに入力されたテキストのサフィックスに対するパターンの最長プリフィックスを状態として持つオートマトンを分割パターンについて構成し、１つのパターンから生成された全ての分割パターンに対応するオートマトンの全てが最終状態になったか否かを判定する。【選択図】  図１
2005242672.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（ｉ≦ｌ≦ｉ＋ｊ）と定義される。複数のパターンが存在する場合には、個々のパターンに対するオートマトンを単一のオートマトンとして合成することが可能である。このような方法をＡｈｏ−Ｃｏｒａｓｉｃｋと呼ぶ（例えば、非特許文献２参照）。
【００１２】
図９はＡｈｏ−Ｃｏｒａｓｉｃｋオートマトンを説明するための図であるが、図９は例としてパターンをｃａｂｃとｃｂａｃａの２つとした場合に生成されるオートマトンを示している。なお、いずれの状態においても、アーク上に明示されていない文字が入力された場合は状態０に戻る。次に、そのオートマトンに対して入力テキストの文字列を入力させ、入力された文字と現在のオートマトンの状態とから、オートマトンを次の状態に遷移させるという動作を繰り返す。このとき、オートマトンがパターン全体を表す状態（以下、最終状態）に遷移すると、テキスト中の文字列がパターンと一致したことを表す。図９の例では、状態４と状態８が最終状態である。
【００１３】
図１０は従来のメモリを用いたオートマトンの実現例を示す図であり、図１１は従来のオートマトンの回路展開例を示す図であるが、オートマトンのハードウェア実現に際しては、図１０のように、オートマトンをメモリ上で表現する方法と、図１１のようにオートマトンを直接的に回路化する方法とに分けられる。オートマトンをメモリ上で表現する方法として、新しく入力されたテキストの文字と現在のオートマトンの状態とを入力とし、次に遷移すべき状態を出力とする表が用いられる。しかし、オートマトンを表として実現する場合には、表のエントリ数がテキストの一文字あたりのビット幅に対して指数関数的に増加するという問題がある。
【００１４】
一方、オートマトンをバイナリツリー等を用いて表現することによって、エントリ数を削減する方法もある。しかし、この方法では、テキストの文字が入力されてから次の状態が決定されるまでの遅延が表と比較して大きくなる。この遅延の間、次のテキストの文字に対する照合処理ができないため、スループットが大きく制限される。一方、図１１のオートマトンを直接布線論理化する方法では、オートマトンの状態毎に比較器が必要となる。また、状態間の配線遅延によってスループットが制限される。
【００１５】
本発明は、このような背景に行われたものであって、パターンマッチングをハードウェア処理した際の各種遅延の隠蔽およびスループットの向上を可能とすることができるパターンマッチング装置および方法を提供することを目的とする。
【課題を解決するための手段】
【００１６】
本発明では、従来のオートマトンによるパターンマッチングに対し、以下の点を付加することに特徴がある。
【００１７】
個々のパターンの各文字を関数を用いて振り分けることによって、パターンを複数のパターンに分割し、これまでに入力されたテキストのサフィックスに対するパターンの最長プリフィックスを状態として持つオートマトンを分割パターンについて構成し、１つのパターンから生成された全ての分割パターンに対応するオートマトンの全てが最終状態になったか否かを判定することによって、パターンマッチングを行う。
【００１８】
個々のパターンから分割されたパターンに対応するオートマトン全てを単一のオートマトンとして合成し、パターンマッチングすることができる。
【００１９】
生成されたオートマトンをパイプライン化して実現し、テキストと個々の分割パターンとに対する比較を時分割して行うことによって、単一テキスト中の文字単位でパイプライン処理することができる。
【００２０】
生成されたオートマトンを並列に配置し、テキスト中の文字を個々のオートマトンに振り分けて並列に入力することによって、単一テキスト中の文字単位で並列処理することができる。
【００２１】
すなわち、個々の分割パターンとテキストとの比較を互いに独立に行えるため、それらをパイプラインまたは並列処理することが可能である。すなわち、パターンをｋ個に分割する場合に、テキストもｋ個に分割する。本発明では、これらの分割テキストをそれぞれ独立に個々の分割パターンと比較させ、その結果を統合させている。
【００２２】
この結果、分割パターンと分割テキストとの比較を並列処理することが可能となる。また、オートマトンによる比較処理を複数ステージに細分化し、独立な分割テキストを時分割に処理することによって、オートマトンのパイプライン処理を実現することができる。
【００２３】
以上により、本発明の目的である、テキストを文字単位でパイプラインまたは並列処理することによる、パターンマッチングをハードウェア処理した際の配線遅延またはメモリアクセス遅延といった遅延隠蔽とスループット向上効果が得られる。
【００２４】
すなわち、本発明の第一の観点は、入力文字列であるテキストから複数種類の任意文字列であるパターンを検索するパターンマッチング装置であって、本発明の特徴とするところは、個々のパターンの各文字を関数に従って振り分けることによって個々の一つのパターンを複数のパターンに分割した分割パターンを保持し、これまでに入力されたテキストのサフィックスに対するパターンの最長プリフィックスを状態として持つオートマトンを前記分割パターンについてそれぞれ構成する手段と、一つのパターンから分割された全ての前記分割パターンのそれぞれについて構成されたオートマトンの全てが最終状態になったか否かを判定することによってパターンマッチングを行う手段とを備えたところにある（請求項１）。
【００２５】
さらに、前記オートマトンをパイプライン化して実現し、このパイプライン化された前記オートマトンに対し、テキストと個々の前記分割パターンとの比較を時分割して行うパイプライン処理手段を備えることができる（請求項２）。
【００２６】
あるいは、前記オートマトンを複数並列に配置し、この並列に配置された複数の前記オートマトンに対し、テキスト中の文字を個々のオートマトンに振り分けて並列に入力し、単一テキスト中の文字単位で並列処理する手段を備えることができる（請求項３）。
【００２７】
あるいは、前記オートマトンをパイプライン化して実現すると共に、このパイプライン化して実現したオートマトンを複数並列に配置し、この並列に配置された複数の前記オートマトンに対し、テキスト中の文字を個々のオートマトンに振り分けて並列に入力し、単一テキスト中の文字単位で並列処理すると共に、このパイプライン化された前記オートマトンに対し、前記テキスト中の文字と個々の前記分割パターンとの比較を時分割して行う並列パイプライン処理手段を備えることができる（請求項４）。
【００２８】
さらに、一つのパターンから分割された全ての前記分割パターンのそれぞれについて構成されたオートマトンの全てを単一のオートマトンとして合成する手段を備えることができる（請求項５）。
【００２９】
本発明の第二の観点は、入力文字列であるテキストから複数種類の任意文字列であるパターンを検索するパターンマッチング方法であって、本発明の特徴とするところは、個々のパターンの各文字を関数に従って振り分けることによって個々の一つのパターンを複数のパターンに分割するステップと、これまでに入力されたテキストのサフィックスに対するパターンの最長プリフィックスを状態として持つオートマトンを前記分割するステップにより分割された分割パターンについてそれぞれ構成するステップと、一つのパターンから分割された全ての前記分割パターンのそれぞれについて構成されたオートマトンの全てが最終状態になったか否かを判定することによってパターンマッチングを行うステップとを実行するところにある（請求項６）。
【００３０】
さらに、前記オートマトンをパイプライン化して実現し、このパイプライン化された前記オートマトンに対し、テキストと個々の前記分割パターンとの比較を時分割して行うパイプライン処理ステップを実行することができる（請求項７）。
【００３１】
あるいは、前記オートマトンを複数並列に配置し、この並列に配置された複数の前記オートマトンに対し、テキスト中の文字を個々のオートマトンに振り分けて並列に入力し、単一テキスト中の文字単位で並列処理するステップを実行することができる（請求項８）。
【００３２】
あるいは、前記オートマトンをパイプライン化して実現すると共に、このパイプライン化して実現したオートマトンを複数並列に配置し、この並列に配置された複数の前記オートマトンに対し、テキスト中の文字を個々のオートマトンに振り分けて並列に入力し、単一テキスト中の文字単位で並列処理すると共に、このパイプライン化された前記オートマトンに対し、前記テキスト中の文字と個々の前記分割パターンとの比較を時分割して行う並列パイプライン処理ステップを実行することができる（請求項９）。
【００３３】
さらに、一つのパターンから分割された全ての前記分割パターンのそれぞれについて構成されたオートマトンの全てを単一のオートマトンとして合成するステップを実行することができる（請求項１０）。
【００３４】
本発明の第三の観点は、情報処理装置にインストールすることにより、その情報処理装置に、入力文字列であるテキストから複数種類の任意文字列であるパターンを検索するパターンマッチング装置に相応する機能を実現させるプログラムであって、本発明の特徴とするところは、個々のパターンの各文字を関数に従って振り分けることによって個々の一つのパターンを複数のパターンに分割した分割パターンを保持し、これまでに入力されたテキストのサフィックスに対するパターンの最長プリフィックスを状態として持つオートマトンを前記分割パターンについてそれぞれ構成する機能と、一つのパターンから分割された全ての前記分割パターンのそれぞれについて構成されたオートマトンの全てが最終状態になったか否かを判定することによってパターンマッチングを行う機能とを実現させるところにある（請求項１１）。
【００３５】
さらに、前記オートマトンをパイプライン化して実現し、このパイプライン化された前記オートマトンに対し、テキストと個々の前記分割パターンとの比較を時分割して行うパイプライン処理機能を実現させることができる（請求項１２）。
【００３６】
あるいは、前記オートマトンを複数並列に配置し、この並列に配置された複数の前記オートマトンに対し、テキスト中の文字を個々のオートマトンに振り分けて並列に入力し、単一テキスト中の文字単位で並列処理する機能を実現させることができる（請求項１３）。
【００３７】
あるいは、前記オートマトンをパイプライン化して実現すると共に、このパイプライン化して実現したオートマトンを複数並列に配置し、この並列に配置された複数の前記オートマトンに対し、テキスト中の文字を個々のオートマトンに振り分けて並列に入力し、単一テキスト中の文字単位で並列処理すると共に、このパイプライン化された前記オートマトンに対し、前記テキスト中の文字と個々の前記分割パターンとの比較を時分割して行う並列パイプライン処理機能を実現させることができる（請求項１４）。
【００３８】
さらに、一つのパターンから分割された全ての前記分割パターンのそれぞれについて構成されたオートマトンの全てを単一のオートマトンとして合成する機能を実現させることができる（請求項１５）。
【００３９】
本発明の第四の観点は、本発明のプログラムが記録された前記情報処理装置読取可能な記録媒体である（請求項１６）。本発明のプログラムは本発明の記録媒体に記録されることにより、前記情報処理装置は、この記録媒体を用いて本発明のプログラムをインストールすることができる。あるいは、本発明のプログラムを保持するサーバからネットワークを介して直接前記情報処理装置に本発明のプログラムをインストールすることもできる。
【００４０】
これにより、汎用の情報処理装置を用いて、各種遅延の隠蔽およびスループットの向上を可能とすることができるパターンマッチング装置を実現することができる。
【発明の効果】
【００４１】
本発明によれば、パターンマッチングをハードウェア処理した際の各種遅延の隠蔽およびスループットの向上を可能とすることができる。また、パターンマッチングを汎用の情報処理装置とプログラムとを用いて実現する際にも各種遅延の隠蔽およびスループットの向上を可能とすることができる。
【発明を実施するための最良の形態】
【００４２】
本発明実施例のパターンマッチング装置および方法ならびにプログラムについて図１ないし図８を参照して説明する。図１は分割パターンを用いたパターンマッチング装置の構成図である。図２は分割パターンを用いたオートマトンによって文字単位の並列処理を行う実施例を示す図である。図３はメモリを用いたオートマトンによってパイプライン処理する構成を示す図である。図４は回路展開したオートマトンによってパイプライン処理する構成を示す図である。図５は分割パターンを合成したパターンマッチング装置の構成図である。図６は分割パターンを合成したパターンマッチングの実施例を示す図である。図７はメモリ表現した場合の最終状態判定部を示す図である。図８はオートマトンをメモリ表現した場合の実施例を示す図である。
【００４３】
本発明実施例は、図１に示すように、入力文字列であるテキストから複数種類の任意文字列であるパターンを検索するパターンマッチング装置であって、本発明の特徴とするところは、個々のパターンの各文字を関数に従って振り分けることによって個々の一つのパターンを複数のパターンに分割した分割パターンを保持し、これまでに入力されたテキストのサフィックスに対するパターンの最長プリフィックスを状態として持つオートマトンを前記分割パターンについてそれぞれ構成するオートマトン部１と、一つのパターンから分割された全ての前記分割パターンのそれぞれについて構成されたオートマトンの全てが最終状態になったか否かを判定することによってパターンマッチングを行う最終状態判定部２とを備えたところにある（請求項１）。
【００４４】
さらに、図３に示すように、前記オートマトンをパイプライン化して実現し、このパイプライン化された前記オートマトンに対し、テキストと個々の前記分割パターンとの比較を時分割して行うパイプライン処理手段を備えることができる（請求項２）。
【００４５】
あるいは、図２に示すように、前記オートマトンを複数並列に配置し、この並列に配置された複数の前記オートマトンに対し、テキスト中の文字を個々のオートマトンに振り分けて並列に入力し、単一テキスト中の文字単位で並列処理する手段を備えることができる（請求項３）。
【００４６】
あるいは、図８に示すように、前記オートマトンをパイプライン化して実現すると共に、このパイプライン化して実現したオートマトンを複数並列に配置し、この並列に配置された複数の前記オートマトンに対し、テキスト中の文字を個々のオートマトンに振り分けて並列に入力し、単一テキスト中の文字単位で並列処理すると共に、このパイプライン化された前記オートマトンに対し、前記テキスト中の文字と個々の前記分割パターンとの比較を時分割して行う並列パイプライン処理手段を備えることができる（請求項４）。
【００４７】
さらに、図５に示すように、全ての前記分割パターンのそれぞれについて構成されたオートマトンの全てを単一のオートマトンとして合成する合成済みオートマトン部３を備えることができる（請求項５）。
【００４８】
本実施例の入力文字列であるテキストから複数種類の任意文字列であるパターンを検索するパターンマッチング方法は、個々のパターンの各文字を関数に従って振り分けることによって個々の一つのパターンを複数のパターンに分割するステップと、これまでに入力されたテキストのサフィックスに対するパターンの最長プリフィックスを状態として持つオートマトンを前記分割するステップにより分割された分割パターンについてそれぞれ構成するステップと、一つのパターンから分割された全ての前記分割パターンのそれぞれについて構成されたオートマトンの全てが最終状態になったか否かを判定することによってパターンマッチングを行うステップとを実行することを特徴とする（請求項６）。
【００４９】
さらに、前記オートマトンをパイプライン化して実現し、このパイプライン化された前記オートマトンに対し、テキストと個々の前記分割パターンとの比較を時分割して行うパイプライン処理ステップを実行することができる（請求項７）。
【００５０】
あるいは、前記オートマトンを複数並列に配置し、この並列に配置された複数の前記オートマトンに対し、テキスト中の文字を個々のオートマトンに振り分けて並列に入力し、単一テキスト中の文字単位で並列処理するステップを実行することができる（請求項８）。
【００５１】
あるいは、前記オートマトンをパイプライン化して実現すると共に、このパイプライン化して実現したオートマトンを複数並列に配置し、この並列に配置された複数の前記オートマトンに対し、テキスト中の文字を個々のオートマトンに振り分けて並列に入力し、単一テキスト中の文字単位で並列処理すると共に、このパイプライン化された前記オートマトンに対し、前記テキスト中の文字と個々の前記分割パターンとの比較を時分割して行う並列パイプライン処理ステップを実行することができる（請求項９）。
【００５２】
さらに、全ての前記分割パターンのそれぞれについて構成されたオートマトンの全てを単一のオートマトンとして合成するステップを実行することができる（請求項１０）。
【００５３】
本実施例は、汎用の情報処理装置にインストールすることにより、その情報処理装置に本実施例のパターンマッチング装置に相応する機能を実現させるプログラムとして実現することができる（請求項１１〜１５）。このプログラムは、記録媒体に記録されて情報処理装置にインストールされ（請求項１６）、あるいは通信回線を介して情報処理装置にインストールされることにより当該情報処理装置に、オートマトン部１、最終状態判定部２、合成済みオートマトン部３にそれぞれ相応する機能を実現させることができる。
【００５４】
以下では、本発明実施例をさらに詳細に説明する。本発明では、まず、個々のパターンの各文字を一定の関数に基づいて振り分けることによってパターンを複数のパターンに分割する。関数の具体例として、パターンを先頭から順番に振り分ける場合に、分割前のパターンＰをｐ1ｐ2…ｐmとしてｋ分割すると、その分割パターンＤＰi（ｉ＝１，…，ｋ）はｐiｐi+k…ｐi+(m/k-1)kと表記できる。例えば、パターンａｂａｂｃｄから２つの分割パターンを生成する場合に、分割パターンＤＰ1はａａｃ、分割パターンＤＰ2はｂｂｄとなる。任意の部分テキストｔs+1ｔs+2…ｔs+mがパターンと一致するか否かを判定する場合には、パターンと同様に部分テキストを分割し、個々の分割部分テキストが個々の分割パターンと一致するか否かを判定する。すなわち、ｉ＝１，…，ｋについて以下の式が成り立つか否かを判定する。
【００５５】
ｔs+iｔs+i+k…ｔs+i+(m/k-1)k＝ｐiｐi+k…ｐi+(m/k-1)k
次に、これまでに入力されたテキストのサフィックスに対するパターンの最長プリフィックスを状態として持つオートマトンを分割パターンについて構成する。図１に分割パターンを用いたオートマトンによってパターンマッチングを実施するための構成を示す。オートマトンによる検索では、関数に基づいてテキストｔ1…ｔnをｋ個のテキスト列として振り分ける。
【００５６】
関数の具体例として、テキストの先頭から順番に振り分ける場合には、分割後のテキストＤＴi（ｉ＝１，…，ｋ）はｔiｔi+k…ｔi+(n/k-1)kと表記できる。そして、それぞれの分割テキストＤＴiを、各分割パターンに対応するオートマトンに入力する。
【００５７】
適切なタイミングで全ての分割パターンに対応するオートマトンが最終状態に遷移したか否かを判定することによって、パターン全体と一致したか否かを判定する。また、各オートマトンを並列に動作させることによって、テキストとパターンとのマッチングを文字単位で並列処理することが可能である。
【００５８】
図２はａｂａｂｃｄを分割パターンを用いたオートマトンによって文字単位の並列処理を行う場合を例示している。
【００５９】
さらに並列化に加えて、オートマトンを図３、図４のように、オートマトンの各処理を複数ステージに細分化し、同じオートマトンに対して入力される異なる分割テキストを時分割して入力することによって、テキストとパターンとのマッチングを文字単位でパイプライン処理することができる。
【００６０】
個々の分割パターンと分割テキストとの比較を個別のオートマトンを用いて行う場合に、そのオートマトン数は分割パターン数の二乗に比例する。例えば、図２では２つの分割パターンの比較に対し４つのオートマトンを必要としている。これを、Ａｈｏ−Ｃｏｒａｓｉｃｋに基づいて、オートマトンを合成することによって、オートマトン数を削減した構成を図５に示す。分割パターンを合成した場合には、パターンマッチングに必要なオートマトンの個数は分割パターンの数に比例する。図６はａｂａｂｃｄを分割パターンし、そのオートマトンを合成することによって、パターンマッチングを行う場合を例示している。図２と比較すると必要なオートマトンの個数は半分になっている。
【００６１】
最終状態判定部２は、オートマトンの現在の状態が最終状態であるか否かを判定する。図７はオートマトンをメモリ表現した場合の最終状態判定部２の実装例を示す。オートマトンの状態を入力として、最終状態に遷移しているか否かを示す信号を出力する。一方、オートマトンを回路で表現する場合は、各最終状態を表す状態のレジスタの値を出力するのみでよい。
【００６２】
図８は、オートマトンをメモリ表現し、パターンを４つに分割した場合を示している。図８では、テキストから生成される４つの分割テキストのうち、２つをパイプライン処理している。さらに、オートマトンを２つ並列に配置することによって、２つの文字を並列処理している。回路展開した場合も同様に、各状態を表現する回路を２つのステージに細分化したオートマトンを２つ並列に配置する。そして、図８と同様の方法で、テキストを分割してオートマトンに入力し、各分割パターンが最終状態に遷移したか否かを判定することでパターンマッチングが実施可能である。
【産業上の利用可能性】
【００６３】
本発明によれば、パターンマッチングをハードウェア処理した際の各種遅延の隠蔽およびスループットの向上を可能とすることができるため、効率の高いパターンマッチング処理を行うことができるパターンマッチング装置を実現することができる。また、パターンマッチングを汎用の情報処理装置とプログラムとを用いて実現する際にも各種遅延の隠蔽およびスループットの向上を可能とすることができるため、効率の高いパターンマッチング処理を行うことができるパターンマッチング装置を実現することができる。
【図面の簡単な説明】
【００６４】
【図１】分割パターンを用いたパターンマッチング装置の構成図。
【図２】分割パターンを用いたオートマトンによって文字単位の並列処理を行う実施例を示す図。
【図３】メモリを用いたオートマトンによってパイプライン処理する構成を示す図。
【図４】回路展開したオートマトンによってパイプライン処理する構成を示す図。
【図５】分割パターンを合成したパターンマッチング装置の構成図。
【図６】分割パターンを合成したパターンマッチングの実施例を示す図。
【図７】メモリ表現した場合の最終状態判定部を示す図。
【図８】オートマトンをメモリ表現した場合の実施例を示す図。
【図９】Ａｈｏ−Ｃｏｒａｓｉｃｋに基づいて生成されるオートマトンを示す図。
【図１０】メモリを用いたオートマトンの実現例を示す図。
【図１１】オートマトンの回路展開例を示す図。
【符号の説明】
【００６５】
１  オートマトン部
２  最終状態判定部
３  合成済みオートマトン部
【図１】
2005242672.tif 000003
【図２】
2005242672.tif 000004
【図３】
2005242672.tif 000005
【図４】
2005242672.tif 000006
【図５】
2005242672.tif 000007
【図６】
2005242672.tif 000008
【図７】
2005242672.tif 000009
【図８】
2005242672.tif 000010
【図９】
2005242672.tif 000011
【図１０】
2005242672.tif 000012
【図１１】
2005242672.tif 000013