(57)【特許請求の範囲】
【請求項１】
複数のＯＲ条件の文字列に関する照合をＡＣオートマトンで実行する照合装置であって、
該ＯＲ条件の文字列について、ルートノードから前記文字列に対応するＡＣオートマトンのトライ構造を生成する場合に、特定の文字列の特定文字桁までは一致したがその後に不一致が発生した際、または、特定の文字列がすべて一致した際に、他の文字列の特定の文字桁の文字に対応するノードへ遷移するフェイラ遷移を設定したＡＣオートマトンのトライ構造を生成する第１の生成部と、
前記第１の生成部によって生成されたトライ構造に対して、照合対象である対象文字列の文字として用いられる可能性のある全ての文字に対応するノードを追加ノードとして追加するとともに、追加した追加ノードの前記フェイラ遷移を前記ルートノードに設定し、追加して得られたトライ構造から前記ルートノードを削除する処理を行うことで、ＡＣオートマトンの新たなトライ構造を生成する第２の生成部と、
照合対象である対象文字列の最初の文字を読み出したとき、前記第２の生成部によって生成されたトライ構造の中の、読み出した文字に対応する追加ノードへ遷移し、該対象文字列の次に読み出した文字について、該トライ構造の次の文字桁の文字と照合し、該対象文字列の読み出した文字を照合した結果、遷移先が前記フェイラ遷移に基づいて前記ルートノードに設定されているときに、読み出した文字に対応する追加ノードへ遷移し、該対象文字列の次に読み出した文字について、該トライ構造の次の文字桁の文字と照合する照合部と
を有することを特徴とする照合装置。
【請求項２】
コンピュータに、
複数のＯＲ条件の文字列について、ルートノードから前記文字列に対応するＡＣオートマトンのトライ構造を生成する場合に、特定の文字列の特定文字桁までは一致したがその後に不一致が発生した際、または、特定の文字列がすべて一致した際に、他の文字列の特定の文字桁の文字に対応するノードへ遷移するフェイラ遷移を設定したＡＣオートマトンのトライ構造を生成し、
前記トライ構造を生成する処理によって生成されたトライ構造に対して、照合対象である対象文字列の文字として用いられる可能性のある全ての文字に対応するノードを追加ノードとして追加するとともに、追加した追加ノードの前記フェイラ遷移を前記ルートノードに設定し、追加して得られたトライ構造から前記ルートノードを削除する処理を行うことで、ＡＣオートマトンの新たなトライ構造を生成し、
照合対象である対象文字列の最初の文字を読み出したとき、前記新たなトライ構造を生成する処理によって生成されたトライ構造の中の、読み出した文字に対応する追加ノードへ遷移し、該対象文字列の次に読み出した文字について、該トライ構造の次の文字桁の文字と照合し、該対象文字列の読み出した文字を照合した結果、遷移先が前記フェイラ遷移に基づいて前記ルートノードに設定されているときに、読み出した文字に対応する追加ノードへ遷移し、該対象文字列の次に読み出した文字について、該トライ構造の次の文字桁の文字と照合する
各処理を実行させることを特徴とする照合プログラム。
【請求項３】
コンピュータが、
複数のＯＲ条件の文字列について、ルートノードから前記文字列に対応するＡＣオートマトンのトライ構造を生成する場合に、特定の文字列の特定文字桁までは一致したがその後に不一致が発生した際、または、特定の文字列がすべて一致した際に、他の文字列の特定の文字桁の文字に対応するノードへ遷移するフェイラ遷移を設定したＡＣオートマトンのトライ構造を生成し、
前記トライ構造を生成する処理によって生成されたトライ構造に対して、照合対象である対象文字列の文字として用いられる可能性のある全ての文字に対応するノードを追加ノードとして追加するとともに、追加した追加ノードの前記フェイラ遷移を前記ルートノードに設定し、追加して得られたトライ構造から前記ルートノードを削除する処理を行うことで、ＡＣオートマトンの新たなトライ構造を生成し、
照合対象である対象文字列の最初の文字を読み出したとき、前記新たなトライ構造を生成する処理によって生成されたトライ構造の中の、読み出した文字に対応する追加ノードへ遷移し、該対象文字列の次に読み出した文字について、該トライ構造の次の文字桁の文字と照合し、該対象文字列の読み出した文字を照合した結果、遷移先が前記フェイラ遷移に基づいて前記ルートノードに設定されているときに、読み出した文字に対応する追加ノードへ遷移し、該対象文字列の次に読み出した文字について、該トライ構造の次の文字桁の文字と照合する
各処理を実行することを特徴とする照合方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、照合装置などに関する。
【背景技術】
【０００２】
近年、照合装置のコアエンジンとしてＡＣマシン（Aho-Corasick  Machine）と呼ばれるオートマトンが利用されている。かかるＡＣマシンは、テキストデータ（文字列）が入力された場合に、パターン照合を実行し、照合対象の文字列（キーワードまたはパターンと呼ぶ）の出現位置をテキストデータの中から高速に算出する。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２０１０−２１８１４０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
ここで、ＡＣマシンによるパターン照合の処理では、多くのリソースが使用される。このため、ＣＰＵ（Central  Processing  Unit）でパターン照合の処理が実行されると、他の処理が滞ってしまうことがある。そこで、パターン照合の処理は、別途、ＦＰＧＡ（Field-Programmable  Gate  Array）で実行されている。
【０００５】
ＣＰＵに代えてＦＰＧＡに処理をさせることで、ＣＰＵ自体の負荷は少なくなる反面、ＦＰＧＡの処理性能自体は低いことが多い。このため、ＦＰＧＡによるテキストデータ（文字列）のパターン照合の処理を効率化することが望まれる。そこで、ＦＰＧＡによるテキストデータ（文字列）のパターン照合の処理を並列化することが考えられる。
【０００６】
パターン照合の処理を並列化する場合、ＦＰＧＡのチップ自体は物理的に小さいので、該チップ内に並列処理の数だけ複数のＡＣマシンを用意できない。すなわち、並列処理の数だけ複数のＡＣマシンをＦＰＧＡのチップに複製されようとしても、ＦＰＧＡのチップ内のＲＡＭ（Random  Access  Memory）は、複製される分のＡＣマシンのデータを保持できない。そこで、並列化されたチャネルが、１つのＡＣマシンに対して各文字を入力するようにすることが考えられる。
【０００７】
しかしながら、受ける側のＡＣマシンは１つであるので、並列化されたチャネルから入力された各文字に対応する状態が同じである場合、パターン照合の処理が競合してしまい、並列処理を効率的に行うことができないという問題がある。
【０００８】
開示の技術は、上記に鑑みてなされたものであって、ＡＣマシンを１つにしても、並列処理を効率的に行うことができる照合装置などを提供することを目的とする。
【課題を解決するための手段】
【０００９】
開示の照合装置は、複数のＯＲ条件の文字列に関する照合をＡＣオートマトンで実行する照合装置であって、該ＯＲ条件の文字列について、第１の初期状態ノードから前記文字列に対応するＡＣオートマトンのトライ構造を生成し、生成したトライ構造に、特定の文字列の特定文字桁までは一致したがその後に不一致が発生した際、または、特定の文字列がすべて一致した際に、他の文字列の特定の文字桁の文字に対応するノードへ遷移するフェイラ遷移を設定したＡＣオートマトンのトライ構造を生成する第１の生成部と、前記第１の生成部によって生成されたトライ構造に対して、前記ＯＲ条件の文字列の文字として用いられる可能性のある全ての文字に対応する第２の初期状態ノードを追加するとともに、追加した第２の初期状態ノードの前記フェイラ遷移を前記第１の初期状態ノードに設定し、追加して得られたトライ構造から前記第１の初期状態ノードを削除する処理を行うことで、ＡＣオートマトンの新たなトライ構造を生成する第２の生成部と、照合対象である対象文字列の最初の文字を読み出したとき、前記第２の生成部によって生成されたトライ構造の中の、読み出した文字に対応する第２の初期状態ノードへ遷移し、該対象文字列の次に読み出した文字について、該トライ構造の次の文字桁の文字と照合し、該対象文字列の読み出した文字を照合した結果、前記フェイラ遷移に基づいて前記第１の初期状態ノードへ遷移するときに、読み出した文字に対応する第２の初期状態ノードへ遷移し、該対象文字列の次に読み出した文字について、該トライ構造の次の文字桁の文字と照合する照合部とを有する。
【発明の効果】
【００１０】
本願の開示する照合装置の一つの態様によれば、ＡＣマシンを１つにしても、並列処理を効率的に行うことができるという効果を奏する。
【図面の簡単な説明】
【００１１】
【図１】図１は、従来のＡＣマシンのデータ構造の一例を示す図である。
【図２】図２は、従来の状態定義のデータ構造の一例を示す図である。
【図３】図３は、従来のＡＣマシンを構築する処理手順を示すフローチャートである。
【図４】図４は、従来のパターン集合ΠのトライＴ構築処理の処理手順を示すフローチャートである。
【図５】図５は、従来のパターン登録処理の処理手順を示すフローチャートである。
【図６】図６は、従来のフェイラ遷移追加処理の処理手順を示すフローチャート（１）である。
【図７】図７は、従来のフェイラ遷移追加処理の処理手順を示すフローチャート（２）である。
【図８】図８は、従来のパターン集合Πのトライ構築処理を説明するための図（１）である。
【図９】図９は、従来のパターン集合Πのトライ構築処理を説明するための図（２）である。
【図１０】図１０は、従来のパターン集合Πのトライ構築処理を説明するための図（３）である。
【図１１】図１１は、従来のフェイラ遷移追加処理を説明するための図（１）である。
【図１２】図１２は、従来のフェイラ遷移追加処理を説明するための図（２）である。
【図１３】図１３は、従来のフェイラ遷移追加処理を説明するための図（３）である。
【図１４】図１４は、従来のフェイラ遷移追加処理を説明するための図（４）である。
【図１５】図１５は、従来のフェイラ遷移追加処理を説明するための図（５）である。
【図１６】図１６は、従来のフェイラ遷移追加処理を説明するための図（６）である。
【図１７】図１７は、従来のフェイラ遷移追加処理を説明するための図（７）である。
【図１８】図１８は、従来のフェイラ遷移追加処理を説明するための図（８）である。
【図１９】図１９は、従来のフェイラ遷移追加処理を説明するための図（９）である。
【図２０】図２０は、従来のパターン照合処理の処理手順を示すフローチャートである。
【図２１】図２１は、従来のパターン照合処理を説明するための図（１）である。
【図２２】図２２は、従来のパターン照合処理を説明するための図（２）である。
【図２３】図２３は、従来のパターン照合処理を説明するための図（３）である。
【図２４】図２４は、従来のパターン照合処理を説明するための図（４）である。
【図２５】図２５は、従来のパターン照合処理を説明するための図（５）である。
【図２６】図２６は、従来のパターン照合処理を説明するための図（６）である。
【図２７】図２７は、ＦＰＧＡにおける従来のＡＣマシンを共有した場合の回路構成の一例を示す図である。
【図２８】図２８は、実施例に係る照合装置の概要を説明するための図である。
【図２９】図２９は、実施例に係る照合装置の構成を示す図である。
【図３０】図３０は、実施例に係る状態定義表のデータ構造の一例を示す図である。
【図３１】図３１は、実施例に係る第一ノード追加処理および初期状態ノード削除処理を説明するための図（１）である。
【図３２】図３２は、実施例に係る第一ノード追加処理および初期状態ノード削除処理を説明するための図（２）である。
【図３３】図３３は、実施例に係る第一ノード追加処理および初期状態ノード削除処理を説明するための図（３）である。
【図３４】図３４は、実施例に係る第一ノード追加処理および初期状態ノード削除処理を説明するための図（４）である。
【図３５】図３５は、実施例に係る照合装置の具体例を説明するための図である。
【図３６】図３６は、実施例に係るパターン照合処理を説明するための図（１）である。
【図３７】図３７は、実施例に係るパターン照合処理を説明するための図（２）である。
【図３８】図３８は、実施例に係るパターン照合処理を説明するための図（３）である。
【図３９】図３９は、実施例に係るパターン照合処理を説明するための図（４）である。
【図４０】図４０は、実施例に係るパターン照合処理を説明するための図（５）である。
【図４１】図４１は、実施例に係るパターン照合処理を説明するための図（６）である。
【図４２】図４２は、実施例に係るパターン照合処理を説明するための図（７）である。
【図４３】図４３は、実施例に係る照合装置がＡＣマシンを構築する処理手順を示すフローチャートである。
【図４４】図４４は、実施例に係る第一ノード追加処理および初期状態ノード削除処理の処理手順を示すフローチャートである。
【図４５】図４５は、実施例に係る照合処理の処理手順を示すフローチャートである。
【図４６】図４６は、並列して照合した場合のパターン照合処理を説明するための図（１）である。
【図４７】図４７は、並列して照合した場合のパターン照合処理を説明するための図（２）である。
【図４８】図４８は、並列して照合した場合のパターン照合処理を説明するための図（３）である。
【図４９】図４９は、並列して照合した場合のパターン照合処理を説明するための図（４）である。
【図５０】図５０は、並列して照合した場合のパターン照合処理を説明するための図（５）である。
【図５１】図５１は、並列して照合した場合のパターン照合処理を説明するための図（６）である。
【図５２】図５２は、並列して照合した場合のパターン照合処理を説明するための図（７）である。
【図５３】図５３は、４つの状態定義表に分割した場合のＡＣマシンの回路構成の一例を示す図である。
【図５４】図５４は、照合プログラムを実行するコンピュータの一例を示す図である。
【発明を実施するための形態】
【００１２】
以下に、本願の開示する照合装置、照合プログラムおよび照合方法の実施例を図面に基づいて詳細に説明する。なお、この実施例によりこの発明が限定されるものではない。
【実施例】
【００１３】
まず、本実施例を説明する前に、従来のＡＣマシン（ＡＣオートマトン）について説明する。図１は、従来のＡＣマシンのデータ構造の一例を示す図である。図１に示すＡＣマシンは、テキストデータが入力された場合に、キーワード「ＡＣ、ＢＡ、ＢＢ、ＢＡＡ、ＢＡＣＤ」の位置を算出するＡＣマシンである。
【００１４】
図１に示すように、ＡＣマシンは、複数の状態を有しており、各状態は、初期状態、通常状態、照合状態に分別される。初期状態は、初めにテキストデータと照合される状態であり、通常状態は、２番目以降にテキストデータと照合される状態である。照合状態は、テキストデータが特定のキーワードにヒットした場合に遷移する状態である。図１に示す例では、初期状態は状態２５６であり、通常状態は状態６５、６６であり、照合状態は状態２５７〜２６２である。
【００１５】
ＡＣマシンは、テキストデータの文字を初期状態２５６から順次照合し、通常遷移とフェイラ（Failure）遷移を繰り返すことで、テキストデータに含まれるテキスト（例えば、図１の集合Πに含まれるテキスト）の出現位置を算出する。
【００１６】
ここで、通常遷移は、照合対象となる状態において、テキストデータの比較対象となる文字による遷移先が存在する場合の遷移を示す。例えば、状態６５において、テキストデータの比較対象となる文字がＣの場合には、通常遷移となる。テキストデータの文字がＣの場合には、状態６５から状態２５７に通常遷移する。
【００１７】
一方、通常遷移の条件に該当しない場合には、フェイラ遷移となる。例えば、状態６５において、テキストデータの比較対象となる文字がＣ以外の場合には、フェイラ遷移となる。状態６５においてフェイラ遷移した場合には、遷移先が状態２５６となる。ＡＣマシンでは、各状態に一本ずつフェイラ遷移が存在する。図１で省略されているフェイラ遷移は、全て初期状態２５６に向かっているものとする。
【００１８】
ここで、図１に示したＡＣマシンが有する状態（状態定義）のデータ構造について説明する。図２は、従来の状態定義のデータ構造の一例を示す図である。図２に示すように、この状態定義は、各状態を識別する状態ＩＤと、パターンリストと、通常遷移先と、フェイラ遷移先とを有する。
【００１９】
パターンリストには、状態定義が照合状態の場合に、該当するキーワードが格納される。例えば、状態２５７（状態ＩＤ２５７）の状態定義に含まれるパターンリストは、ＡＣとなる。通常遷移先は、通常遷移先の状態ＩＤを示し、括弧内の文字コードが示す文字を読んだときの次の状態ＩＤを表す。通常遷移先の数は、文字コードの数、ここでは２５６個のエントリ数分存在する。例えば、状態６５（状態ＩＤ６５）の状態定義に含まれるｇ［６７］は状態２５７（状態ＩＤ２５７）を表す。括弧内の６７は、文字「Ｃ」のアスキーコードを示す。フェイラ遷移先は、フェイラ遷移先の状態ＩＤを示す。なお、状態定義が、ＡＣマシンのトライ構造の一例に挙げられる。
【００２０】
次に、従来技術の装置（以下、従来装置；図示略）が、ＡＣマシンを構築する処理手順について説明する。図３は、従来のＡＣマシンを構築する処理手順を示すフローチャートである。図３に示すように、従来装置は、パターン集合Π（照合対象となるキーワードの集合）を取得し（ステップＳ１０）、パターン集合ΠのトライＴ（Π）を構築する（ステップＳ１１）。そして、従来装置は、トライＴ（Π）にフェイラ遷移を追加し、その結果をＡＣマシンα（Π）とする（ステップＳ１２）。そして、従来装置は、ＡＣマシンα（Π）を出力する（ステップＳ１３）。
【００２１】
次に、図３のステップＳ１１に示したパターン集合ΠのトライＴ（Π）を構築する処理について説明する。図４は、従来のパターン集合ΠのトライＴ構築処理の処理手順を示すフローチャートである。図４に示すように、従来装置は、初期状態（id＝Ｎ）を作成し、トライＴ（Π）を初期状態のみで構成されるトライに設定する（ステップＳ２０）。なお、Ｎは、例えば２５６であり、文字コードの最大の値（２５５）より１だけ大きい値であれば良い。
【００２２】
従来装置は、初期状態における通常遷移先を全て初期状態（id＝Ｎ）に設定し（ステップＳ２１）、パターン集合Πにパターンが存在するか否かを判定する（ステップＳ２２）。パターンが存在しない場合には（ステップＳ２２；Ｎｏ）、トライＴ（Π）を出力する（ステップＳ２３）。
【００２３】
一方、パターン集合Πにパターンが存在する場合には（ステップＳ２２；Ｙｅｓ）、従来装置は、パターン集合Πから１つのパターンを取り出し、取り出したパターンをパターンｐに設定する（ステップＳ２４）。そして、従来装置は、設定したパターンｐについて、パターン登録処理を行う（ステップＳ２５）。すなわち、従来装置は、トライＴ（Π）にパターンｐを登録し、登録済みのトライを新たなトライＴ（Π）に設定する。そして、従来装置は、ステップＳ２２に移行する。
【００２４】
次に、図４のステップＳ２５に示したパターン登録処理について説明する。図５は、従来のパターン登録処理の処理手順を示すフローチャートである。図５に示すように、従来装置は、状態ｓをトライＴの初期状態に設定し、変数ｊを文字コード数Ｎ＋１に設定する（ステップＳ３０）。なお、Ｎは、例えば２５６であり、文字コードの最大の値（２５５）より１だけ大きい値であれば良い。そして、従来装置は、パターンｐに次の文字が存在するか否かを判定する（ステップＳ３１）。
【００２５】
パターンｐに次の文字が存在しない場合には（ステップＳ３１；Ｎｏ）、従来装置は、状態ｓのパターンリストPlistに、パターンｐを代入し（ステップＳ３２）、トライＴを出力する（ステップＳ３３）。
【００２６】
一方、パターンｐに次の文字が存在する場合には（ステップＳ３１；Ｙｅｓ）、従来装置は、次の文字をａとし、ａのアスキーコードをcode(a)とする（ステップＳ３４）。そして、従来装置は、状態ｓの通常遷移先g[code(a)]がNullであるか否かを判定する（ステップＳ３５）。
【００２７】
通常遷移先g[code(a)]がNullではない場合には（ステップＳ３５；Ｎｏ）、従来装置は、ステップＳ３９に移行する。一方、通常遷移先g[code(a)]がNullの場合には（ステップＳ３５；Ｙｅｓ）、従来装置は、状態ｓが初期状態であるか否かを判定する（ステップＳ３６）。
【００２８】
状態ｓが初期状態である場合には（ステップＳ３６；Ｙｅｓ）、従来装置は、状態を新規作成し、状態ＩＤをcode(a)に設定し、状態ｓの通常遷移先g[code(a)]をcode(a)に設定し（ステップＳ３７）、ステップＳ３９に移行する。一方、状態ｓが初期状態でない場合には（ステップＳ３６；Ｎｏ）、従来装置は、状態を新規作成し、状態ＩＤを変数ｊの値に設定し、状態ｓの通常遷移先g[code(a)]を変数ｊの値に設定する。そして、従来装置は、変数ｊの値を１加算し（ステップＳ３８）、ステップＳ３９に移行する。
【００２９】
そして、従来装置は、状態ｓに文字ａの通常遷移先g[code(a)]を代入し（ステップＳ３９）、ステップＳ３１に移行する。
【００３０】
次に、図３のステップＳ１２に示したフェイラ遷移追加処理について説明する。図６および図７は、従来のフェイラ遷移追加処理の処理手順を示すフローチャートである。図６に示すように、従来装置は、初期状態から通常遷移先となる状態を判定し、判定した状態をキュー（queue）に登録する（ステップＳ４０）。
【００３１】
そして、従来装置は、キューに登録された状態（状態定義）のフェイラ遷移先に初期状態を登録し（ステップＳ４１）、キューに状態が存在するか否かを判定する（ステップＳ４２）。キューに状態が存在しない場合には（ステップＳ４２；Ｎｏ）、従来装置は、現在のトライＴをＡＣマシンαとして出力する（ステップＳ４３）。
【００３２】
一方、キューに状態が存在する場合には（ステップＳ４２；Ｙｅｓ）、従来装置は、キューの先頭の状態を取り出し、取り出した状態を状態ｓに設定する（ステップＳ４４）。このとき、従来装置は、キューから、取り出した状態を除去する。そして、従来装置は、状態ｓの通常遷移先が全てNullであるか否かを判定する（ステップＳ４５）。状態ｓの通常遷移先が全てNullの場合には（ステップＳ４５；Ｙｅｓ）、従来装置は、ステップＳ４２に移行する。
【００３３】
一方、状態ｓの通常遷移先が全てNullではない場合には（ステップＳ４５；Ｎｏ）、従来装置は、状態ｓにおいて、g[code(a)]≠Nullとなるすべての文字ａを抽出し、抽出した文字ａを集合Ａに格納する（ステップＳ４６）。
【００３４】
続いて、従来装置は、集合Ａに文字が存在するか否かを判定し（ステップＳ４７）、集合Ａに文字が存在しない場合には（ステップＳ４７；Ｎｏ）、ステップＳ４２に移行する。一方、集合Ａに文字が存在する場合には（ステップＳ４７；Ｙｅｓ）、集合Ａから文字ａを一つ取り出し、取り出した文字ａに該当する文字を集合Ａから削除する（ステップＳ４８）。
【００３５】
そして、従来装置は、状態ｓに対する文字ａの通常遷移先next＝g[code(a)]を、キューの最後尾に追加する（ステップＳ４９）。そして、従来装置は、状態ｓからフェイラ遷移を繰り返し、文字ａに対する通常遷移先がNullにならない最初の状態を状態ｆに設定する（ステップＳ５０）。そして、従来装置は、状態ｆに対する文字ａの通常遷移先fnext=g[code(a)]を、状態nextのフェイラ遷移先に設定する（ステップＳ５１）。
【００３６】
さらに、従来装置は、状態nextのフェイラ遷移先の状態にパターンリストが存在する場合に、このパターンリストを状態nextのパターンリストに追加し（ステップＳ５２）、ステップＳ４７に移行する。
【００３７】
次に、図３のステップＳ１１で示したパターン集合ΠのトライＴ構築処理を、具体例を用いて説明する。図８〜図１０は、従来のパターン集合Πのトライ構築処理を説明するための図である。ここでは一例として、パターン集合ΠをΠ＝｛ＡＣ、ＢＡ、ＢＢ、ＢＡＡ、ＢＡＣＤ｝とする。
【００３８】
まず、従来装置は、初期状態（id＝２５６）を作成し、現在の状態を初期状態とする。そして、従来装置は、初期状態の状態定義における全ての通常遷移先を初期状態に設定する（図８、ステップＳ６０）。そして、従来装置は、パターン集合Πからパターン「ＡＣ」を取り出す。従来装置は、文字Ａを選択し、現在の状態が初期状態であるので、選択した文字Ａのアスキーコード（６５）を状態ＩＤとする状態を新規作成する。そして、従来装置は、文字Ａによる初期状態（id＝２５６）の通常遷移先を通常状態（id＝６５）に設定し、現在の状態を通常状態（id＝６５）とする。次に、従来装置は、文字Ｃを選択し、現在の状態が初期状態でないので、「２５７」を状態ＩＤとする状態を新規作成する。そして、従来装置は、文字Ｃによる現在の状態（id＝６５）の通常遷移先を照合状態（id＝２５７）に設定し、照合状態のパターンリストを「ＡＣ」に設定する（図８、ステップＳ６１）。文字Ｃは、パターン「ＡＣ」の最後尾の文字であるため、状態２５７は、照合状態となる。
【００３９】
従来装置は、初期状態（id＝２５６）に戻り、現在の状態を初期状態とする。そして、従来装置は、パターン集合Πからパターン「ＢＡ」を取り出す。従来装置は、文字Ｂを選択し、現在の状態が初期状態であるので、選択した文字Ｂのアスキーコード（６６）を状態ＩＤとする状態を新規作成する。そして、従来装置は、文字Ｂによる初期状態（id＝２５６）の通常遷移先を通常状態（id＝６６）に設定し、現在の状態を通常状態（id＝６６）とする。次に、従来装置は、文字Ａを選択し、現在の状態が初期状態でないので、「２５８」を状態ＩＤとする状態を新規作成する。そして、従来装置は、文字Ａによる現在の状態（id＝６６）の通常遷移先を照合状態（id＝２５８）に設定し、照合状態のパターンリストを「ＢＡ」に設定する（図８、ステップＳ６２）。文字Ａは、パターン「ＢＡ」の最後尾の文字であるため、状態２５８は、照合状態となる。
【００４０】
従来装置は、初期状態（id＝２５６）に戻り、現在の状態を初期状態とする。そして、従来装置は、パターン集合Πからパターン「ＢＢ」を取り出し、文字Ｂを選択する。ここで、文字Ｂによる初期状態（id＝２５６）の通常遷移先は通常状態（id＝６６）であり、既に作成済みであるため、現在の状態を通常状態（id＝６６）に遷移する。また、従来装置は、文字Ｂを選択し、文字Ｂによる通常状態（id＝６６）の通常遷移先を照合状態（id＝２５９）に設定し、パターンリストを「ＢＢ」に設定する（図９、ステップＳ６３）。文字Ｂは、パターン「ＢＢ」の最後尾の文字であるため、状態２５９は、照合状態となる。
【００４１】
従来装置は、初期状態（ｉｄ＝２５６）に戻り、現在の状態を初期状態とする。そして、従来装置は、パターン集合Πからパターン「ＢＡＡ」を取り出し、文字Ｂを選択する。ここで、文字Ｂによる初期状態（id＝２５６）の通常遷移先は、通常状態（id＝６６）であり、既に作成済みであるため、現在の状態を通常状態（id＝６６）に遷移する。また、従来装置は、文字Ａを選択する。ここで、文字Ａによる通常状態（id＝６６）の通常遷移先は、照合状態（id＝２５８）であり、既に作成済みであるため、現在の状態を照合状態（id＝２５８）に設定する。また、従来装置は、文字Ａを選択する。文字Ａによる照合状態（id＝２５８）の通常遷移先を照合状態（id＝２６０）に設定し、パターンリストを「ＢＡＡ」に設定する（図９、ステップＳ６４）。文字Ａは、パターン「ＢＡＡ」の最後尾の文字であるため、状態２６０は、照合状態となる。
【００４２】
従来装置は、初期状態（id＝２５６）に戻り、現在の状態を初期状態とする。そして、従来装置は、パターン集合Πからパターン「ＢＡＣＤ」を取り出し、文字Ｂを選択する。ここで、文字Ｂによる初期状態（id＝２５６）の通常遷移先は、通常状態（id＝６６）であり、既に登録済みであるため、現在の状態を通常状態（id＝６６）に遷移する。また、従来装置は、文字Ａを選択する。ここで、文字Ａによる通常状態（id＝６６）の通常遷移先は、照合状態（id＝２５８）であり、既に作成済みであるため、現在の状態を照合状態（id＝２５８）に設定する。
【００４３】
また、従来装置は、文字Ｃを選択し、文字Ｃによる照合状態（id＝２５８）の通常遷移先を通常状態（id＝２６１）に設定する。また、従来装置は、文字Ｄを選択し、文字Ｄによる通常状態（id＝２６１）の通常遷移先を照合状態（id＝２６２）に設定し、パターンリストを「ＢＡＣＤ」に設定する（図１０、ステップＳ６５）。文字Ｄは、パターン「ＢＡＣＤ」の最後尾の文字であるため、状態２６２は、照合状態となる。ステップＳ６５が終了した段階で、従来装置は、パターン集合Πに含まれる全てのパターンの登録を終了し、トライＴの構築処理が終了する。
【００４４】
次に、図３のステップＳ１２に示したフェイラ遷移追加処理を、具体例を用いて説明する。図１１〜図１９は、従来のフェイラ遷移追加処理を説明するための図である。
【００４５】
図１１に示すように、従来装置は、初期状態（id＝２５６）からの通常遷移先となる状態を判定し、判定した状態をキュー（Queue）に登録し、キューに登録された状態のフェイラ遷移先に初期状態２５６を登録する。ここで、初期状態の通常遷移先は、通常状態６５、６６となるので、キューに６５、６６を登録する。また、通常状態６５、６６のフェイラ遷移先を初期状態２５６に設定する。
【００４６】
次に、従来装置は、キューの先頭の状態６５を取り出し、取り出した状態６５を状態ｓに設定する。従来装置は、状態ｓにおいて、g[code(a)]≠Nullとなる全ての文字ａを抽出し、集合Ａに格納する。この場合は、従来装置は、文字Ｃを抽出し、集合Ａに文字Ｃを格納する。
【００４７】
図１２に示すように、従来装置は、集合Ａから文字Ｃを取り出し、状態ｓ（状態６５）の通常遷移先となる状態２５７（状態next）をキューの最後尾に追加する。従来装置は、状態６５からフェイラ遷移した初期状態２５６に移行し、文字Ｃに対する通常遷移先を判定することで、状態next（状態２５７）のフェイラ遷移先を判定すると、初期状態２５６となる。そして、従来装置は、状態next（状態２５７）のフェイラ遷移先を初期状態２５６に設定する。
【００４８】
図１３に示すように、従来装置は、キューの先頭の状態６６を取り出し、取り出した状態６６を状態ｓに設定する。従来装置は、状態ｓにおいて、g[code(a)]≠Nullとなる全ての文字ａを抽出し、集合Ａに格納する。この場合は、従来装置は、文字Ａ、Ｂを抽出し、集合Ａに文字Ａ、Ｂを格納する。
【００４９】
従来装置は、集合Ａから文字Ａを取り出し、状態ｓ（状態６６）の文字Ａの通常遷移先となる状態２５８（状態next）をキューの最後尾に追加する。従来装置は、状態ｓからフェイラ遷移した初期状態（id＝２５６）に移行し、文字Ａに対する通常遷移先を判定することで、状態next（状態２５８）のフェイラ遷移先を判定すると、状態６５となる。そして、従来装置は、状態next（状態２５８）のフェイラ遷移先を状態６５に設定する。（図１３の状態２５８参照）。
【００５０】
従来装置は、集合Ａから文字Ｂを取り出し、状態ｓ（通常状態６６）の文字Ｂの通常遷移先となる状態２５９（状態next）をキューの最後尾に追加する。従来装置は、状態ｓからフェイラ遷移した初期状態２５６に移行し、文字Ｂに対する通常遷移先を判定することで、状態next（状態２５９）のフェイラ遷移先を判定すると、状態６６となる。そして、従来装置は、状態next（状態２５９）のフェイラ遷移先を通常状態６６に設定する。（図１３の状態２５９参照）。
【００５１】
図１４に示すように、従来装置は、キューの先頭の状態２５７を取り出し、取り出した状態２５７を状態ｓに設定する。従来装置は、状態ｓにおいて、g[code(a)]≠Nullとなる全ての文字ａを抽出し、集合Ａに格納する。状態ｓに通常遷移先は存在しないので、次のステップに移行する。
【００５２】
図１５に示すように、従来装置は、キューの先頭の状態２５８を取り出し、取り出した状態２５８を状態ｓに設定する。従来装置は、状態ｓにおいて、g[code(a)]≠Nullとなる全ての文字ａを抽出し、集合Ａに格納する。この場合は、従来装置は、文字Ａ、Ｃを抽出し、集合Ａに文字Ａ、Ｃを格納する。
【００５３】
従来装置は、集合Ａから文字Ａを取り出し、状態ｓ（照合状態２５８）の文字Ａの通常遷移先となる状態２６０（状態next）をキューの最後尾に追加する。従来装置は、状態ｓからフェイラ遷移した状態６５に移行する。状態６５において、文字Ａに対する通常遷移先はNullであるため、再度フェイラ遷移し、初期状態２５６に移行する。
【００５４】
そして、初期状態２５６において、文字Ａに対する通常遷移先を判定することで、状態next（状態２６０）のフェイラ遷移先を判定すると、状態６５となる。そして、従来装置は、状態next（状態２６０）のフェイラ遷移先を通常状態６５に設定する（図１５の状態２６０参照）。
【００５５】
従来装置は、集合Ａから文字Ｃを取り出し、状態ｓ（照合状態２５８）の文字Ｃの通常遷移先となる状態２６１（状態next）をキューの最後尾に追加する。従来装置は、状態ｓからフェイラ遷移した状態６５に移行し、文字Ｃに対する通常遷移先を判定することで、状態nextのフェイラ遷移先を判定すると、状態２５７となる。そして、従来装置は、状態next（状態２６１）のフェイラ遷移先を照合状態２５７に設定する。
【００５６】
また、従来装置は、状態next（状態２６１）のフェイラ遷移先が照合状態２５７となるため、状態２５７のパターンリストを状態２６１のパターンリストに追加することで、状態２６１を照合状態２６１に設定する（図１５の状態２６１参照）。
【００５７】
図１６に示すように、従来装置は、キューの先頭の状態２５９を取り出し、取り出した状態２５９を状態ｓに設定する。従来装置は、状態ｓにおいて、g[code(a)]≠Nullとなる全ての文字ａを抽出し、集合Ａに格納する。状態ｓに通常遷移先は存在しないので、次のステップに移行する。
【００５８】
図１７に示すように、従来装置は、キューの先頭の状態２６０を取り出し、取り出した状態２６０を状態ｓに設定する。従来装置は、状態ｓにおいて、g[code(a)]≠Nullとなる全ての文字ａを抽出し、集合Ａに格納する。状態ｓに通常遷移先は存在しないので、次のステップに移行する。
【００５９】
図１８に示すように、従来装置は、キューの先頭の状態２６１を取り出し、取り出した状態２６１を状態ｓに設定する。従来装置は、状態ｓにおいて、g[code(a)]≠Nullとなる全ての文字ａを抽出し、集合Ａに格納する。この場合は、従来装置は、文字Ｄを抽出し、集合Ａに文字Ｄを格納する。
【００６０】
従来装置は、集合Ａから文字Ｄを取り出し、状態ｓ（照合状態２６１）の文字Ｄの通常遷移先となる状態２６２（状態next）をキューの最後尾に追加する。従来装置は、状態ｓからフェイラ遷移した状態２５７に移行する。状態２５７において、文字Ｄに対する通常遷移先はNullであるため、再度フェイラ遷移し、初期状態２５６に移行する。
【００６１】
そして、初期状態２５６において、文字Ｄに対する通常遷移先を判定することで、状態next（状態２６２）のフェイラ遷移先を判定すると、初期状態２５６となる。そして、従来装置は、状態next（状態２６２）のフェイラ遷移先を初期状態２５６に設定する（図１８の状態２６２参照）。
【００６２】
図１９に示すように、従来装置は、キューの先頭の状態２６２を取り出し、取り出した状態２６２を状態ｓに設定する。従来装置は、状態ｓにおいて、g[code(a)]≠Nullとなる全ての文字ａを抽出し、集合Ａに格納する。状態ｓに通常遷移先は存在しないので、次のステップに移行する。そして、従来装置は、キューに状態が存在しなくなった場合に、パターン集合ΠのＡＣマシンの構築を完了する。
【００６３】
次に、従来のＡＣマシンを用いたテキストデータのパターン照合処理について説明する。図２０は、従来のパターン照合処理の処理手順を示すフローチャートである。図２０に示すように、従来装置は、状態ｓをＡＣマシンαの初期状態とし（ステップＳ７０）、オフセットｄ＝０に設定し、集合Ｒを空集合に設定する（ステップＳ７１）。
【００６４】
従来装置は、テキストデータＤに（ｄ+１）文字目が存在するか否かを判定し（ステップＳ７２）、（ｄ+１）文字目が存在しない場合には（ステップＳ７２；Ｎｏ）、集合Ｒを出力する（ステップＳ７３）。
【００６５】
一方、テキストデータＤに（ｄ+１）文字目が存在する場合には（ステップＳ７２；Ｙｅｓ）、従来装置は、（ｄ+１）文字目の文字を文字ａに設定し（ステップＳ７４）、ｄ＝ｄ+１とする（ステップＳ７５）。
【００６６】
続いて、従来装置は、状態ｓに文字ａの通常遷移先が存在するか否かを判定する（ステップＳ７６）。通常遷移先が存在する場合には（ステップＳ７６；Ｙｅｓ）、従来装置は、状態ｓのg[code(a)]を状態ｓに代入する（ステップＳ７７）。そして、従来装置は、状態ｓが照合状態の場合に、状態ｓのパターンリストをオフセットｄに対応付けて集合Ｒに登録し（ステップＳ７８）、ステップＳ７２に移行する。
【００６７】
通常遷移先が存在しない場合には（ステップＳ７６；Ｎｏ）、従来装置は、状態ｓのフェイラ遷移先を状態ｓに代入し（ステップＳ７９）。そして、従来装置は、状態ｓが照合状態の場合に、状態ｓのパターンリストをオフセットｄに対応付けて集合Ｒに登録し（ステップＳ８０）、さらに文字ａの存在を判定すべく、ステップＳ７６に移行する。
【００６８】
次に、図２０に示したパターン照合処理を、具体例を用いて説明する。図２１〜図２６は、従来のパターン照合処理を説明するための図である。ここでは一例として、パターン集合ΠをΠ＝｛ＡＣ、ＢＡ、ＢＢ、ＢＡＡ、ＢＡＣＤ｝としたＡＣマシンαを用い、テキストデータＤを「ＣＢＡＡＣ」として説明を行う。
【００６９】
図２１に示すように、従来装置は、状態ｓをＡＣマシンαの初期状態２５６に設定し、集合Ｒを空集合に設定する。
【００７０】
図２２に示すように、従来装置は、テキストデータＤから文字Ｃを読み出し、オフセットをｄ＝１に設定する。状態ｓに文字Ｃによる通常遷移先が存在しないので、従来装置は、状態ｓをフェイラ遷移させ、状態ｓをフェイラ遷移先の初期状態２５６に設定する。
【００７１】
図２３に示すように、従来装置は、テキストデータＤから文字Ｂを読み出し、オフセットをｄ＝２に設定する。状態ｓ（初期状態２５６）において、文字Ｂによる通常遷移先は、状態６６となるので、従来装置は、状態ｓを状態６６に設定する。
【００７２】
図２４に示すように、従来装置は、テキストデータＤから文字Ａを読み出し、オフセットをｄ＝３に設定する。状態ｓ（通常状態６６）において、文字Ａによる通常遷移先は、状態２５８となるので、従来装置は、状態ｓを状態２５８に設定する。状態ｓが照合状態となったので、従来装置は、状態ｓのパターンリスト「ＢＡ」をオフセット「３」に対応付けて集合Ｒに登録する。
【００７３】
図２５に示すように、従来装置は、テキストデータＤから文字Ａを読み出し、オフセットをｄ＝４に設定する。状態ｓ（照合状態２５８）において、文字Ａによる通常遷移先は、状態２６０となるので、従来装置は、状態ｓを状態２６０に設定する。状態ｓが照合状態となったので、従来装置は、状態ｓのパターンリスト「ＢＡＡ」をオフセット「４」に対応付けて集合Ｒに登録する。
【００７４】
図２６に示すように、従来装置は、テキストデータＤから文字Ｃを読み出し、オフセットをｄ＝５に設定する。状態ｓ（照合状態２６０）において、文字Ｃによる通常遷移先は、存在しないので、フェイラ遷移し、状態ｓを状態６５に設定する。状態ｓにおいて、文字Ｃによる通常遷移先は、状態２５７となるので、従来装置は、状態ｓを状態２５７に設定する。状態ｓが照合状態となったので、従来装置は、状態ｓのパターンリスト「ＡＣ」をオフセット「５」に対応付けて集合Ｒに登録する。
【００７５】
従来装置は、図２６に示した集合Ｒを、照合結果として出力する。かかる照合結果を参照すると、テキストデータのオフセット３にキーワード「ＢＡ」が存在し、オフセット４にキーワード「ＢＡＡ」が存在し、オフセット５にキーワード「ＡＣ」が存在することが分かる。
【００７６】
ところで、ＡＣマシンを用いたパターン照合処理は、ＣＰＵの処理負荷を避けるために、例えばＦＰＧＡ（Field-Programmable  Gate  Array）で実行されている。しかし、ＦＰＧＡでは、処理性能がＣＰＵに比べて低いことが多いので、パターン照合処理を効率化することが望まれている。そこで、ＦＰＧＡでは、従来のＡＣマシンを共有化し、テキストデータ（文字列）のパターン照合の処理を並列化している。
【００７７】
図２７は、ＦＰＧＡにおける従来のＡＣマシンを共有した場合の回路構成の一例を示す図である。図２７に示す例では、ＦＰＧＡは、３つのチャネルと１つのＡＣマシンとを有する。ＡＣマシンは、３つのチャネルから入力されるそれぞれの入力文字列の入力文字を状態情報とともに取得する。そして、ＡＣマシンは、各状態の状態定義に基づいて、それぞれの状態情報が示す状態に、取得されたそれぞれの入力文字の通常遷移先が存在するか否かを、並列して判定する。そして、ＡＣマシンは、判定の結果、通常遷移先が存在する場合に、通常遷移先を次の状態として入力元のチャネルに出力し、通常遷移先が存在しない場合に、フェイラ遷移先を次の状態として入力元のチャネルに出力する。
【００７８】
しかし、図２１に示すＡＣマシンをそのまま適用すると、照合開始時の場合、ＡＣマシンは、すべてのチャネルから状態情報として初期状態を取得するので、照合処理が競合してしまう。つまり、同じ状態定義へのアクセスは１チャネルずつしかできないところ、初期状態の状態定義へのアクセスで競合が発生してしまう。また、別の例では、ＡＣマシンは、２つのチャネルからの照合処理でどちらともフェイラ遷移先が初期状態であった場合、次の照合時に２つのチャネルから状態情報として初期状態を取得するので、照合処理が競合してしまう。つまり、初期状態の状態定義へのアクセスで競合が発生してしまう。このように、照合開始時の場合や２つのチャネルからの照合処理でどちらともフェイラ遷移先が初期状態であった場合には、ＡＣマシンは、並列処理を効率的に行うことができない。
【００７９】
そこで、かかる問題を解決するために、以下に実施例に係る照合装置について説明する。
【００８０】
［実施例に係る照合装置の概要］
まず、実施例に係る照合装置の概要について説明する。図２８は、実施例に係る照合装置の概要を説明するための図である。図２８に示すように、照合装置は、初期状態から遷移させる従来のＡＣマシンを構築する。パターン集合Πは、図２８の例では、Π＝｛ｃｅｌｌ、ｉｃｅ｝である。遷移の実線は、通常遷移であり、遷移の破線は、フェイラ遷移である。そして、フェイラ遷移が示されていない状態は、すべて初期状態へのフェイラ遷移を持っている。
【００８１】
照合装置は、従来のＡＣマシンを構築した後、構築した結果生成されたトライ構造に、テキストデータの１文字目の文字として用いられる可能性のある全ての文字に対応する第一ノードを追加する。図２８の例では、１６進数の０ｘ００（１０進数の０）〜０ｘｆｆ（１０進数の２５５）に対応する第一ノードｎ０を追加している。例えば、文字ｃは、１６進数の０ｘ４３（１０進数の６７）に対応する。文字ｅは、１６進数の０ｘ４５（１０進数の６９）に対応する。そして、照合装置は、追加した第一ノードのフェイラ遷移を初期状態に設定する。さらに、照合装置は、追加して得られた状態定義から初期状態を表す初期状態ノードを削除し、新たなトライ構造を生成する。
【００８２】
そして、照合装置は、パターン照合処理において、テキストデータの１文字目を読み出したとき、生成したトライ構造の中の、読み出した１文字目に対応する第一ノードへ遷移する。また、照合装置は、テキストデータの文字を読み出したとき、読み出した文字のトライ構造を用いた照合の結果、初期状態へのフェイラ遷移となる場合、読み出した文字に対応する第一ノードへ遷移する。例えば、照合装置は、テキストデータの１文字目が「ｅ」である場合、照合装置は、テキストデータから読み出した「ｅ」に対応する第一ノードｊ０に遷移する。また、状態ｊ１においてテキストデータの文字「ｉ」を読み出したとき、照合装置は、初期状態へのフェイラ遷移となるので、読み出した文字「ｉ」に対応する第一ノードｊ３へ遷移する。
【００８３】
したがって、実施例に係る照合装置は、ＡＣマシンを共有化してテキストデータのパターン照合の処理を並列化しても、トライ構造について、アクセス頻度が高い初期状態を削除し、アクセスを分散するようにしたので、並列処理を効率的に行うことができる。
【００８４】
［実施例に係る照合装置の構成］
次に、実施例に係る照合装置１００の構成について説明する。図２９は、実施例に係る照合装置の構成を示す図である。図２９に示すように、照合装置１００は、入力部１１０と出力部１２０と入出力制御部１３０と記憶部１４０と制御部１５０とを有する。
【００８５】
入力部１１０は、パターン集合、テキストデータなどを入力し、キーボードやマウス、マイクなどに対応する。出力部１２０は、ＡＣマシンによる照合結果などを出力し、モニタ（もしくはディスプレイ、タッチパネル）に対応する。入出力制御部１３０は、入力部１１０、出力部１２０、記憶部１４０、制御部１５０によるデータの入出力を制御する。
【００８６】
記憶部１４０は、制御部１５０による各種処理に必要なデータおよびプログラムを記憶する。さらに、記憶部１４０は、パターン集合１４０ａおよびＡＣマシン１４０ｂを有する。
【００８７】
パターン集合１４０ａは、テキストデータを照合するキーワードの集合である。実施例では一例として、パターン集合１４０ａを、Π＝｛ＡＣ、ＢＡ、ＢＢ、ＢＡＡ、ＢＡＣＤ｝とする。
【００８８】
ＡＣマシン１４０ｂは、パターン集合１４０ａに基づいて生成されるオートマトンである。例えば、パターン集合Π＝｛ＡＣ、ＢＡ、ＢＢ、ＢＡＡ、ＢＡＣＤ｝に対応するＡＣマシンは、図２８の下図に示したＡＣマシンとなる。ＡＣマシン１４０ｂは、複数の状態定義から構成されている。状態定義は、状態定義表に格納される。なお、状態定義表は、例えば、ＲＡＭ（Random Access Memory）、フラッシュメモリ（flash memory）等の半導体メモリ素子に対応する。
【００８９】
図３０は、実施例に係る状態定義表のデータ構造の一例を示す図である。図３０に示すように、状態定義表２００は、複数の状態定義を記憶する。状態定義は、図２と同様に、各状態を識別する状態ＩＤと、パターンリストと、通常遷移先と、フェイラ遷移先とを有する。状態定義の各内容は、図２と同様であるので、その説明は、省略する。
【００９０】
状態定義表２００は、複数存在する。各状態定義表２００は、状態定義を、所定のグループに分割したグループごとに作成される。１つの例では、状態定義表２００は、１０個の状態定義を１つのグループとして作成されても良いし、２０個の状態定義を１つのグループとして作成されても良い。また、状態定義表２００は、１個の状態定義を１つのグループとして作成されても良い。なお、ＡＣマシン１４０ｂの生成は、ＡＣマシン構築部１５０ａによって行われる。
【００９１】
図２９に戻ると、制御部１５０は、各種の処理手順を規定したプログラムや制御データを格納するための内部メモリを有し、これらによって種々の処理を実行する。さらに、制御部１５０は、ＡＣマシン構築部１５０ａと照合部１５０ｂと照合結果出力部１５０ｃとを有する。なお、例えば、制御部１５０は、ＦＰＧＡ（Field  Programmable  Gate  Array）やＡＳＩＣ（Application  Specific  Integrated  Circuit）などの集積回路である。
【００９２】
ＡＣマシン構築部１５０ａは、パターン集合１４０ａに基づいて、初期状態がないＡＣマシン１４０ｃを作成する。例えば、ＡＣマシン構築部１５０ａは、初期状態がないＡＣマシン１４０ｃを作成する場合に、初めにトライ構築処理を行った後に、フェイラ遷移追加処理を実行する。かかるトライ構築処理およびフェイラ遷移追加処理は、図４〜図７で示した処理と同様であるので、その説明は省略する。また、ＡＣマシン構築部１５０ａは、生成したＡＣマシンに対して、照合対象であるテキストデータの文字として用いられる可能性のある全ての文字に対応するノードを第一ノードとして追加する。また、ＡＣマシン構築部１５０ａは、追加した第一ノードのフェイラ遷移を、初期状態を表す初期状態ノードに設定する。さらに、ＡＣマシン構築部１５０ａは、第一ノードを追加して得られた状態定義表から初期状態ノードを削除する処理を行うことで、初期状態がないＡＣマシン１４０ｃを作成する。ここで、第一ノードは、追加ノードの一例として挙げられる。初期状態ノードは、ルートノードの一例として挙げられる。
【００９３】
［第一ノード追加処理および初期状態ノード削除処理の具体例］
ここで、ＡＣマシン構築部１５０ａが実行する、第一ノードを追加し、初期状態ノードを削除する処理について、図３１〜図３４を参照して、具体的に説明する。図３１〜図３４は、実施例に係る第一ノード追加処理および初期状態ノード削除処理を説明するための図である。なお、パターン集合１４０ａをΠ＝｛ＡＣ、ＢＡ、ＢＢ、ＢＡＡ、ＢＡＣＤ｝とするＡＣマシンが、既に生成されているとする。
【００９４】
まず、図３１に示すように、ＡＣマシン構築部１５０ａは、文字コード０に対応する状態がまだ存在していないので、状態を新規作成し、作成した状態の状態定義表における状態ＩＤを０とし、フェイラ遷移先に初期状態（id＝２５６）を代入する。すなわち、ＡＣマシン構築部１５０ａは、文字コード０に対応する状態を表す状態ノードを第一ノードとして追加する。
【００９５】
次に、図３２に示すように、ＡＣマシン構築部１５０ａは、文字コード１に対応する状態が存在していないので、状態を新規作成し、作成した状態の状態定義における状態ＩＤを１とし、フェイラ遷移先に初期状態（id＝２５６）を代入する。すなわち、ＡＣマシン構築部１５０ａは、文字コード１に対応する状態を表す状態ノードを第一ノードとして追加する。
【００９６】
さらに、図３３に示すように、ＡＣマシン構築部１５０ａは、文字コード２から２５５までについても、文字コード０や１の場合と同様に、文字コードに対応する状態を新規作成する。なお、文字コード６５、６６の場合は、各文字コードに対応する状態が既に存在しているので、ＡＣマシン構築部１５０ａは、次の文字コードの処理に移行するだけとなる。
【００９７】
そして、図３４に示すように、ＡＣマシン構築部１５０ａは、文字コードが文字コードの最大の値（２５５）より１だけ大きい値を示す２５６と一致したので、初期状態を表す初期状態ノードを削除する。このように、ＡＣマシン構築部１５０ａは、初期状態がないＡＣマシンを構築する。
【００９８】
図２９に戻って、照合部１５０ｂは、照合対象であるテキストデータの最初の文字を読み出したとき、初期状態がないＡＣマシン１４０ｂの中の、読み出した文字に対応する第一ノードへ遷移する。そして、照合部１５０ｂは、テキストデータの次に読み出した文字について、ＡＣマシン１４０ｂの次の文字桁の文字と照合する。また、照合部１５０ｂは、テキストデータの読み出した文字を照合した結果、フェイラ遷移に基づいて初期状態へ遷移するときに、読み出した文字に対応する第一ノードへ遷移する。そして、照合部１５０ｂは、テキストデータの次に読み出した文字について、ＡＣマシン１４０ｂの次の文字桁の文字と照合する。また、照合部１５０ｂは、照合結果を出力する。
【００９９】
［照合装置の具体例］
ここで、照合部１５０ｂが実行する照合処理を実現するための照合装置１００の具体例を、図３５を参照して説明する。図３５は、実施例に係る照合装置の具体例を説明するための図である。図３５に示すように、照合装置１００は、３並列処理の場合の回路概要を示す。照合装置１００は、３つのチャネルと初期状態なしのＡＣマシンとを有する。各チャネルは、ビット（ｂｉｔ）、状態情報および入力文字のコードを記憶する。
【０１００】
かかる構成の下、例えば、照合部１５０ｂは、照合対象である入力文字列（テキストデータ）の最初の文字を読み出したとき、またはフェイラ遷移に基づいて初期状態のフェイラ遷移先へ遷移するとき、チャネルによって、ｂｉｔを１に設定する。そして、照合部１５０ｂは、ビットが１のとき、チャネルによって、入力文字列から読み出した文字に対応した状態（第一ノード）を次の状態として状態情報に設定する。そして、照合部１５０ｂは、初期状態なしのＡＣマシンによって、状態情報に設定された状態に、入力文字列の次に読み出した文字（入力文字）の通常遷移先が存在するか否かを判定することで照合処理を実行する。
【０１０１】
一方、照合部１５０ｂは、通常遷移先へ遷移するとき、またはフェイラ遷移に基づいて初期状態以外のフェイラ遷移先へ遷移するとき、チャネルによって、ｂｉｔを０に設定する。そして、照合部１５０ｂは、ビットが０のとき、チャネルによって、初期状態なしＡＣマシンからの遷移結果である次の状態を状態情報に設定する。そして、照合処理部１５０は、初期状態なしのＡＣマシンによって、状態情報に設定された状態に、入力文字列の次に読み出した文字（入力文字）の通常遷移先が存在するか否かを判定することで照合処理を実行する。
【０１０２】
［照合処理の具体例］
ここで、照合部１５０ｂの処理をさらに具体的に説明する。図３６〜図４２は、実施例に係るパターン照合処理を説明するための図である。
【０１０３】
ここでは、図３６に示すように、パターン集合１４０ａをΠ＝｛ＡＣ、ＢＡ、ＢＢ、ＢＡＡ、ＢＡＣＤ｝とする初期状態なしのＡＣマシンが、既に生成されているとする。そして、照合対象となるテキストデータを「ＣＢＡＡＣ」とする。さらに、入力文字のコードを示す入力コード、状態情報、ｂｉｔ、通常遷移先およびフェイラ遷移先は、まだ何も設定されていない状態である。また、集合Ｒは、空集合に設定されている。
【０１０４】
図３７に示すように、照合部１５０ｂは、テキストデータの１文字目（オフセット１）の文字Ｃを読み出し、文字Ｃの文字コード（６７）を入力コードに書き込む。そして、照合部１５０ｂは、読み出しがテキストデータの１文字目であるのでｂｉｔを１に設定する。そして、照合部１５０ｂは、ｂｉｔが１であるので、文字Ｃの文字コード（６７）を状態情報に書き込む。そして、照合部１５０ｂは、状態情報を用いて、ＡＣマシン上の現在の状態を状態６７とする。
【０１０５】
続いて、図３８に示すように、照合部１５０ｂは、テキストデータの２文字目（オフセット２）の文字Ｂを読み出し、文字Ｂの文字コード（６６）を入力コードに書き込む。そして、照合部１５０ｂは、状態情報および入力コードを用いて、現在の状態６７の文字Ｂによる遷移先を判定すると、状態６７の文字Ｂによる通常遷移先がＮＵＬＬでありフェイラ遷移先が初期状態（２５６）であるので、ｂｉｔを１に設定する。そして、照合部１５０ｂは、ｂｉｔが１であるので、読み出した文字Ｂの文字コード（６６）を状態情報に書き込む。そして、照合部１５０ｂは、状態情報を用いて、ＡＣマシン上の現在の状態を状態６６とする。
【０１０６】
続いて、図３９に示すように、照合部１５０ｂは、テキストデータの３文字目（オフセット３）の文字Ａを読み出し、文字Ａの文字コード（６５）を入力コードに書き込む。そして、照合部１５０ｂは、状態情報および入力コードを用いて、現在の状態６６の文字Ａによる遷移先を判定すると、状態６６の文字Ａによる通常遷移先が状態２５８であるので、ｂｉｔを０に設定する。そして、照合部１５０ｂは、ｂｉｔが０であるので、遷移結果である状態２５８を状態情報に書き込む。そして、照合部１５０ｂは、状態２５８が照合状態であるので、状態２５８のパターンリスト（ＢＡ）をオフセット３に対応付けて集合Ｒに追加する。そして、照合部１５０ｂは、状態情報を用いて、ＡＣマシン上の現在の状態を状態２５８とする。
【０１０７】
続いて、図４０に示すように、照合部１５０ｂは、テキストデータの４文字目（オフセット４）の文字Ａを読み出し、文字Ａの文字コード（６５）を入力コードに書き込む。そして、照合部１５０ｂは、状態情報および入力コードを用いて、現在の状態２５８の文字Ａによる遷移先を判定すると、状態２５８の文字Ａによる通常遷移先が状態２６０であるので、ｂｉｔを０に設定する。そして、照合部１５０ｂは、ｂｉｔが０であるので、遷移結果である状態２６０を状態情報に書き込む。そして、照合部１５０ｂは、状態２６０が照合状態であるので、状態２６０のパターンリスト（ＢＡＡ）をオフセット４に対応付けて集合Ｒに追加する。そして、照合部１５０ｂは、状態情報を用いて、ＡＣマシン上の現在の状態を状態２６０とする。
【０１０８】
続いて、図４１に示すように、照合部１５０ｂは、テキストデータの５文字目（オフセット５）の文字Ｃを読み出し、文字Ｃの文字コード（６７）を入力コードに書き込む。そして、照合部１５０ｂは、状態情報および入力コードを用いて、現在の状態２６０の文字Ｃによる遷移先を判定すると、状態２６０の文字Ｃによる通常遷移先がＮＵＬＬでありフェイラ遷移先が状態６５であるので、ｂｉｔを０に設定する。そして、照合部１５０ｂは、ｂｉｔが０であるので、遷移結果である状態６５を状態情報に書き込む。そして、照合部１５０ｂは、状態情報を用いて、ＡＣマシン上の現在の状態を状態６５とする。
【０１０９】
さらに、図４２に示すように、照合部１５０ｂは、状態情報および入力コードを用いて、現在の状態６５の文字Ｃによる遷移先を再度判定すると、状態６５の文字Ｃによる通常遷移先が２５７であるので、ｂｉｔを０に設定する。そして、照合部１５０ｂは、ｂｉｔが０であるので、遷移結果である状態２５７を状態情報に書き込む。そして、照合部１５０ｂは、状態２５７が照合状態であるので、状態２５７のパターンリスト（ＡＣ）をオフセット５に対応付けて集合Ｒに追加する。そして、照合部１５０ｂは、状態情報を用いて、ＡＣマシン上の現在の状態を状態２５７とする。照合部１５０ｂは、テキストデータの最後の文字に対する遷移先を判定した後に、パターン照合処理を終了する。
【０１１０】
［ＡＣマシンを構築する処理手順］
次に、実施例に係る照合装置１００の処理手順について説明する。図４３は、実施例に係る照合装置がＡＣマシンを構築する処理手順を示すフローチャートである。図４３に示すように、ＡＣマシン構築部１５０ａは、パターン集合Π（照合対象となるキーワードの集合）を取得し（ステップＳ１０１）、パターン集合ΠのトライＴ（Π）を構築する（ステップＳ１０２）。そして、ＡＣマシン構築部１５０ａは、トライＴ（Π）にフェイラ遷移を追加し、その結果をＡＣマシンα（Π）とする（ステップＳ１０３）。そして、ＡＣマシン構築部１５０ａは、ＡＣマシンα（Π）に存在しない第一ノードをＡＣマシンα（Π）に追加し、ＡＣマシンα（Π）から初期状態ノードを削除し、その結果をＡＣマシンβ（Π）とする（ステップＳ１０４）。そして、ＡＣマシン構築部１５０ａは、ＡＣマシンβ（Π）を、例えばＲＡＭに書き込む（ステップＳ１０５）。
【０１１１】
なお、図４３のステップＳ１０２に示したパターン集合ΠのトライＴ（Π）を構築する処理は、図４に示した処理と同様であるので、その説明は、省略する。また、図４３のステップＳ１０３に示したフェイラ遷移追加処理は、図６および図７に示した処理と同様であるので、その説明は、省略する。
【０１１２】
［第一ノード追加処理および初期状態ノード削除処理の手順］
次に、図４３のステップＳ１０４に示した第一ノードを追加し、初期状態ノードを削除する処理について説明する。図４４は、実施例に係る第一ノード追加処理および初期状態ノード削除処理の処理手順を示すフローチャートである。図４４に示すように、ＡＣマシン構築部１５０ａは、文字コードｃに０を設定する（ステップＳ２０１）。
【０１１３】
そして、ＡＣマシン構築部１５０ａは、文字コードｃがあらかじめ定められた文字コードのサイズＮと一致しているか否かを判定する（ステップＳ２０２）。ここで、Ｎは、文字コードの最大の値（２５５）より１だけ大きい値であれば良く、例えば２５６である。文字コードｃがＮと一致していないと判定した場合（ステップＳ２０２；Ｎｏ）、ＡＣマシン構築部１５０ａは、ＡＣマシンαの初期状態の通常遷移先g[ｃ]がNullであるか否かを判定する（ステップＳ２０３）。すなわち、ＡＣマシン構築部１５０ａは、初期状態の状態定義に基づいて、文字コードｃに対応する状態が存在しないかどうかを判断する。
【０１１４】
初期状態の通常遷移先g[ｃ]がNullである場合には（ステップＳ２０３；Ｙｅｓ）、ＡＣマシン構築部１５０ａは、ＡＣマシンαに文字コードｃの状態が存在しないと判断し、第一ノードを生成する。すなわち、ＡＣマシン構築部１５０ａは、状態を新規作成し、作成した状態（状態定義）のフェイラ遷移先に初期状態を代入し、状態ＩＤをｃとする（ステップＳ２０４）。そして、ＡＣマシン構築部１５０ａは、ステップＳ２０５に移行する。一方、初期状態の通常遷移先g[ｃ]がNullでない場合には（ステップＳ２０３；Ｎｏ）、ＡＣマシン構築部１５０ａは、ステップＳ２０５に移行する。
【０１１５】
そして、ＡＣマシン構築部１５０ａは、文字コードｃを１加算し（ステップＳ２０５）、ステップＳ２０２に移行する。
【０１１６】
一方、文字コードｃがＮと一致していると判定した場合（ステップＳ２０２；Ｙｅｓ）、ＡＣマシン構築部１５０ａは、ＡＣマシンαに文字コードｃの状態がすべて存在したと判断し、初期状態を削除する（ステップＳ２０６）。そして、ＡＣマシン構築部１５０ａは、完成したＡＣマシンβを出力する（ステップＳ２０７）。
【０１１７】
［照合処理の処理手順］
次に、実施例に係る照合装置が実行する照合処理の処理手順について説明する。図４５は、実施例に係る照合処理の処理手順を示すフローチャートである。図４５に示すように、照合装置１００では、照合部１５０ｂが、オフセットｄ＝１に設定し、集合Ｒを空集合に設定する（ステップＳ３０１）。そして、照合部１５０ｂは、テキストデータＤの１文字目の文字を読み出し、読み出した文字の文字コードを状態ｓ（状態情報）に書き込む（ステップＳ３０２）。すなわち、照合部１５０ｂは、テキストデータＤの１文字目の読み出し時に読み出した文字に対応する第一ノードへ遷移する。
【０１１８】
照合部１５０ｂは、テキストデータＤに（ｄ+１）文字目が存在するか否かを判定し（ステップＳ３０３）、（ｄ+１）文字目が存在しない場合には（ステップＳ３０３；Ｎｏ）、集合Ｒを出力する（ステップＳ３０４）。
【０１１９】
一方、テキストデータＤに（ｄ+１）文字目が存在する場合には（ステップＳ３０３；Ｙｅｓ）、照合部１５０ｂは、テキストデータＤの（ｄ+１）文字目の文字を読み出し、文字ａに設定し（ステップＳ３０５）、ｄ＝ｄ+１とする（ステップＳ３０６）。
【０１２０】
続いて、照合部１５０ｂは、状態ｓの状態定義に基づいて、状態ｓに文字ａの通常遷移先が存在するか否かを判定する（ステップＳ３０７）。通常遷移先が存在する場合には（ステップＳ３０７；Ｙｅｓ）、照合部１５０ｂは、状態ｓの通常遷移先g[code(a)]を状態ｓ（状態情報）に書き込む（ステップＳ３０８）。そして、照合部１５０ｂは、状態ｓが照合状態の場合に、状態ｓのパターンリストをオフセットｄに対応付けて集合Ｒに追加し（ステップＳ３０９）、次の文字を読み出すべく、ステップＳ３０３に移行する。
【０１２１】
通常遷移先が存在しない場合には（ステップＳ３０７；Ｎｏ）、照合部１５０ｂは、フェイラ遷移に遷移すると判断し、状態ｓの状態定義に基づいて、フェイラ遷移先が初期状態であるか否かを判定する（ステップＳ３１０）。フェイラ遷移先が初期状態でない場合には（ステップＳ３１０；Ｎｏ）、照合部１５０ｂは、状態ｓのフェイラ遷移先を状態ｓ（状態情報）に書き込む（ステップＳ３１１）。そして、照合部１５０ｂは、状態ｓが照合状態の場合に、状態ｓのパターンリストをオフセットｄに対応付けて集合Ｒに追加し（ステップＳ３１２）、再度同じ文字ａの遷移を判定すべく、ステップＳ３０７に移行する。
【０１２２】
フェイラ遷移先が初期状態である場合には（ステップＳ３１０；Ｙｅｓ）、照合部１５０ｂは、文字ａの文字コードcode(a)を状態ｓ（状態情報）に書き込む（ステップＳ３１３）。すなわち、照合部１５０ｂは、初期状態を表す初期状態ノードへのフェイラ遷移時に、読み出した文字ａに対応する第一ノードへ遷移する。そして、照合部１５０ｂは、次の文字を読み出すべく、ステップＳ３０９を介してステップＳ３０３に移行する。
【０１２３】
［並列して照合した場合の照合処理の具体例］
次に、照合部１５０ｂがチャネルごとに並列して照合した場合について、具体的に説明する。図４６〜図５２は、並列して照合した場合のパターン照合処理を説明するための図である。
【０１２４】
ここでは、図４６に示すように、パターン集合１４０ａをΠ＝｛ＡＣ、ＢＡ、ＢＢ、ＢＡＡ、ＢＡＣＤ｝とする初期状態なしのＡＣマシンが、既に生成されているとする。この初期状態なしのＡＣマシンには、説明の便宜上、状態ごとに状態定義表が作成されているとする。また、チャネル１（Ｃｈ１）の照合対象となるテキストデータを「ＣＢＡＢＣ」とする。チャネル２（Ｃｈ２）の照合対象となるテキストデータを「ＢＣＡＡＣ」とする。さらに、チャネル毎の入力文字のコードである入力コード、状態情報、ｂｉｔ、通常遷移先およびフェイラ遷移先は、それぞれまだ何も設定されていない状態である。また、チャネル１用の集合Ｒ１、チャネル２用の集合Ｒ２は、それぞれ空集合に設定されている。
【０１２５】
図４７に示すように、Ｃｈ１およびＣｈ２では、照合部１５０ｂが、テキストデータの１文字目（オフセット１）の文字を読み出し、照合処理を実行する。Ｃｈ１では、照合部１５０ｂは、テキストデータの１文字目（オフセット１）の文字Ｃを読み出し、文字Ｃの文字コード（６７）を入力コードに書き込む。そして、照合部１５０ｂは、読み出しがテキストデータの１文字目であるのでｂｉｔを１に設定する。そして、照合部１５０ｂは、ｂｉｔが１であるので、文字Ｃの文字コード（６７）を状態情報に書き込む。そして、照合部１５０ｂは、状態情報を用いて、ＡＣマシン上の現在の状態を状態６７とする。
【０１２６】
一方、Ｃｈ２では、照合部１５０ｂは、テキストデータの１文字目（オフセット１）の文字Ｂを読み出し、文字Ｂの文字コード（６６）を入力コードに書き込む。そして、照合部１５０ｂは、読み出しがテキストデータの１文字目であるのでｂｉｔを１に設定する。そして、照合部１５０ｂは、ｂｉｔが１であるので、文字Ｂの文字コード（６６）を状態情報に書き込む。そして、照合部１５０ｂは、状態情報を用いて、ＡＣマシン上の現在の状態を状態６６とする。
【０１２７】
図４８に示すように、Ｃｈ１およびＣｈ２では、照合部１５０ｂが、テキストデータの２文字目（オフセット２）の文字を読み出し、照合処理を実行する。Ｃｈ１では、照合部１５０ｂは、テキストデータの２文字目（オフセット２）の文字Ｂを読み出し、文字Ｂの文字コード（６６）を入力コードに書き込む。そして、照合部１５０ｂは、状態情報および入力コードを用いて、現在の状態６７の文字Ｂによる遷移先を判定すると、状態６７の文字Ｂによる通常遷移先がＮＵＬＬでありフェイラ遷移先が初期状態（２５６）であるので、ｂｉｔを１に設定する。そして、照合部１５０ｂは、ｂｉｔが１であるので、読み出した文字Ｂの文字コード（６６）を状態情報に書き込む。そして、照合部１５０ｂは、状態情報を用いて、ＡＣマシン上の現在の状態を状態６６とする。
【０１２８】
一方、Ｃｈ２では、照合部１５０ｂは、テキストデータの２文字目（オフセット２）の文字Ｃを読み出し、文字Ｃの文字コード（６７）を入力コードに書き込む。そして、照合部１５０ｂは、状態情報および入力コードを用いて、現在の状態６６の文字Ｃによる遷移先を判定すると、状態６６の文字Ｃによる通常遷移先がＮＵＬＬでありフェイラ遷移先が初期状態（２５６）であるので、ｂｉｔを１に設定する。そして、照合部１５０ｂは、ｂｉｔが１であるので、読み出した文字Ｃの文字コード（６７）を状態情報に書き込む。そして、照合部１５０ｂは、状態情報を用いて、ＡＣマシン上の現在の状態を状態６７とする。
【０１２９】
図４９に示すように、Ｃｈ１およびＣｈ２では、照合部１５０ｂが、テキストデータの３文字目（オフセット３）の文字を読み出し、照合処理を実行する。Ｃｈ１では、照合部１５０ｂは、テキストデータの３文字目（オフセット３）の文字Ａを読み出し、文字Ａの文字コード（６５）を入力コードに書き込む。そして、照合部１５０ｂは、状態情報および入力コードを用いて、現在の状態６６の文字Ａによる遷移先を判定すると、状態６６の文字Ａによる通常遷移先が状態２５８であるので、ｂｉｔを０に設定する。そして、照合部１５０ｂは、ｂｉｔが０であるので、遷移結果である状態２５８を状態情報に書き込む。そして、照合部１５０ｂは、状態２５８が照合状態であるので、状態２５８のパターンリスト（ＢＡ）をオフセット３に対応付けて集合Ｒ１に追加する。そして、照合部１５０ｂは、状態情報を用いて、ＡＣマシン上の現在の状態を状態２５８とする。
【０１３０】
一方、Ｃｈ２では、照合部１５０ｂは、テキストデータの３文字目（オフセット３）の文字Ａを読み出し、文字Ａの文字コード（６５）を入力コードに書き込む。そして、照合部１５０ｂは、状態情報および入力コードを用いて、現在の状態６７の文字Ａによる遷移先を判定すると、状態６７の文字Ａによる通常遷移先がＮＵＬＬでありフェイラ遷移先が初期状態（２５６）であるので、ｂｉｔを１に設定する。そして、照合部１５０ｂは、ｂｉｔが１であるので、読み出した文字Ａの文字コード（６５）を状態情報に書き込む。そして、照合部１５０ｂは、状態情報を用いて、ＡＣマシン上の現在の状態を状態６５とする。
【０１３１】
図５０に示すように、Ｃｈ１およびＣｈ２では、照合部１５０ｂが、テキストデータの４文字目（オフセット４）の文字を読み出し、照合処理を実行する。Ｃｈ１では、照合部１５０ｂは、テキストデータの４文字目（オフセット４）の文字Ｂを読み出し、文字Ｂの文字コード（６６）を入力コードに書き込む。そして、照合部１５０ｂは、状態情報および入力コードを用いて、現在の状態２５８の文字Ｂによる遷移先を判定すると、状態２５８の文字Ｂによる通常遷移先がＮＵＬＬでありフェイラ遷移先が状態６５であるので、ｂｉｔを０に設定する。そして、照合部１５０ｂは、ｂｉｔが０であるので、遷移結果である状態６５を状態情報に書き込む。そして、照合部１５０ｂは、状態情報を用いて、ＡＣマシン上の現在の状態を状態６５とする。
【０１３２】
一方、Ｃｈ２では、照合部１５０ｂは、テキストデータの４文字目（オフセット４）の文字Ａを読み出し、文字Ａの文字コード（６５）を入力コードに書き込む。そして、照合部１５０ｂは、状態情報および入力コードを用いて、現在の状態６５の文字Ａによる遷移先を判定すると、状態６５の文字Ａによる通常遷移先がＮＵＬＬでありフェイラ遷移先が初期状態（２５６）であるので、ｂｉｔを１に設定する。そして、照合部１５０ｂは、ｂｉｔが１であるので、読み出した文字Ａの文字コード（６５）を状態情報に書き込む。そして、照合部１５０ｂは、状態情報を用いて、ＡＣマシン上の現在の状態を状態６５とする。このとき、状態６５の状態定義のアクセスで競合が発生する。
【０１３３】
図５１に示すように、Ｃｈ１では、照合部１５０ｂが、再度同じ４文字目の文字Ｂの照合処理を実行し、Ｃｈ２では、照合部１５０ｂが、テキストデータの５文字目（オフセット５）の文字を読み出し、照合処理を実行する。Ｃｈ１では、照合部１５０ｂは、状態情報および入力コードを用いて、現在の状態６５の文字Ｂによる遷移先を再度判定すると、状態６５の文字Ｂによる通常遷移先がＮＵＬＬでありフェイラ遷移先が初期状態（２５６）であるので、ｂｉｔを１に設定する。そして、照合部１５０ｂは、ｂｉｔが１であるので、既に読み出した文字Ｂの文字コード（６６）を状態情報に書き込む。そして、照合部１５０ｂは、状態情報を用いて、ＡＣマシン上の現在の状態を状態６６とする。
【０１３４】
一方、Ｃｈ２では、照合部１５０ｂは、テキストデータの５文字目（オフセット５）の文字Ｃを読み出し、文字Ｃの文字コード（６７）を入力コードに書き込む。ところが、照合部１５０ｂは、現在の状態６５でＣｈ１と競合しているので、Ｃｈ１の状態６５の処理が終了するまで待つ。
【０１３５】
図５２に示すように、Ｃｈ１では、照合部１５０ｂが、テキストデータの５文字目（オフセット５）の文字を読み出し、照合処理を実行し、Ｃｈ２では、照合部１５０ｂが、状態６５のＣｈ１の処理が終了したので、既に読み出された文字Ｃの照合処理を実行する。Ｃｈ１では、照合部１５０ｂは、テキストデータの５文字目（オフセット５）の文字Ｃを読み出し、文字Ｃの文字コード（６７）を入力コードに書き込む。そして、照合部１５０ｂは、状態情報および入力コードを用いて、現在の状態６６の文字Ｃによる遷移先を判定すると、状態６６の文字Ｃによる通常遷移先がＮＵＬＬでありフェイラ遷移先が初期状態（２５６）であるので、ｂｉｔを１に設定する。そして、照合部１５０ｂは、ｂｉｔが１であるので、読み出した文字Ｃの文字コード（６７）を状態情報に書き込む。そして、照合部１５０ｂは、状態情報を用いて、ＡＣマシン上の現在の状態を状態６７とする。
【０１３６】
一方、Ｃｈ２では、照合部１５０ｂは、状態情報および入力コードを用いて、現在の状態６５の文字Ｃによる遷移先を判定すると、状態６５の文字Ｃによる通常遷移先が状態２５７であるので、ｂｉｔを０に設定する。そして、照合部１５０ｂは、ｂｉｔが０であるので、遷移結果である状態２５７を状態情報に書き込む。そして、照合部１５０ｂは、状態２５７が照合状態であるので、状態２５７のパターンリスト（ＡＣ）をオフセット５に対応付けて集合Ｒ２に追加する。そして、照合部１５０ｂは、状態情報を用いて、ＡＣマシン上の現在の状態を状態２５７とする。テキストデータの最後の文字に対する遷移先を判定した後に、パターン照合処理を終了する。
【０１３７】
このように、照合部１５０ｂは、パターン照合の処理の並列化で、テキストデータの１文字目を読み出した場合、読み出した文字に対応する状態へ遷移するので、その後の状態定義表へのアクセスを分散でき、競合を避けることができる。また、照合部１５０ｂは、パターン照合の処理の並列化で、初期状態へのフェイラ遷移時の場合、読み出した文字に対応する状態へ遷移するので、状態定義表へのアクセスを分散でき、競合を避けることができる。この結果、照合部１５０ｂは、並列処理を効率的に行うことができる。
【０１３８】
例えば、図５１において、Ｃｈ１では、状態６５の文字Ｂによる通常遷移先がＮＵＬＬでありフェイラ遷移先が初期状態（２５６）であるので、読み出した文字Ｂの文字コード（６６）に対応する状態６６に遷移する。図５０において、Ｃｈ２では、状態６５の文字Ａによる通常遷移先がＮＵＬＬでありフェイラ遷移先が初期状態（２５６）であるので、読み出した文字Ａの文字コード（６５）に対応する状態６５に遷移する。フェイラ遷移先が初期状態（２５６）の場合であっても、遷移先がそれぞれ状態６５と状態６６とで異なるので、同じ文字Ｃを照合しても、状態定義表へのアクセスを分散でき、競合を避けることができる（図５２参照）。
【０１３９】
また、図４７において、Ｃｈ１では、テキストデータの１文字目の文字Ｃを読み出したとき、文字Ｃの文字コード（６７）に対応する状態６７へ遷移する。Ｃｈ２では、テキストデータの１文字目の文字Ｂを読み出したとき、文字Ｂの文字コード（６６）に対応する状態６６へ遷移する。テキストデータの１文字目の文字を読み出した場合であっても、遷移先がそれぞれ状態６７と状態６６とで異なるので、文字の照合で、状態定義表へのアクセスを分散でき、競合を避けることができる。
【０１４０】
図２９に戻って、照合結果出力部１５０ｃは、照合部１５０ｂの照合結果を出力部１２０に出力する。例えば、図５２に示したＡＣマシンを用いてテキストデータのパターン照合処理を実行した場合、照合結果出力部１５０ｃは、集合Ｒ１、集合Ｒ２の情報を照合結果として出力する。集合Ｒの情報は、例えばテキストデータに含まれるパターンを、テキストデータ中のパターンの存在位置（オフセット）に対応付けた情報である。
【０１４１】
ところで、状態定義表２００は、状態定義を、所定のグループに分割したグループごとに作成されると説明した。例えば、状態定義表２００は、４つのグループごとに作成されるとしても良い。図５３は、４つの状態定義表に分割した場合のＡＣマシンの回路構成の一例を示す図である。図５３に示すように、ＡＣマシン１４０ｂは、４つの状態定義表２００−１〜４を有する。そして、ＡＣマシン１４０ｂは、３つのチャネル１〜３からそれぞれ状態情報（状態ＩＤ）および入力コードを入力する。そして、ＡＣマシン１４０ｂは、それぞれの状態ＩＤの状態定義が記憶されている状態定義表２００を参照し、それぞれの状態ＩＤの、入力コードが示す文字による遷移先を判定する。そして、ＡＣマシン１４０ｂは、遷移結果を、入力元のチャネルに出力する。これにより、同じ状態定義表へのアクセスは１チャネルずつしかできないところ、４つの状態定義表２００−１〜４を有することにより、３つ以下の状態定義表を有していた場合と比べ、状態定義表へのアクセスの競合を少なくできる。
【０１４２】
［実施例の効果］
上記実施例によれば、照合装置１００は、初期状態ノードからＯＲ条件のパターン文字列に対応するＡＣマシンのトライ構造を生成する場合に、フェイラ遷移を設定したＡＣマシンのトライ構造を生成する。そして、照合装置１００は、生成されたトライ構造に対して、照合対象である対象文字列の文字として用いられる可能性のある全ての文字に対応するノードを第一ノードとして追加する。そして、照合装置１００は、追加した第一ノードのフェイラ遷移を初期状態ノードに設定し、追加して得られたトライ構造から初期状態ノードを削除する処理を行うことで、ＡＣマシンの新たなトライ構造を生成する。さらに、照合装置１００は、照合対象である対象文字列の最初の文字を読み出したとき、トライ構造の中の、読み出した文字に対応する第一ノードへ遷移する。そして、照合装置１００は、該対象文字列の次に読み出した文字について、該トライ構造の次の文字桁の文字と照合する。また、照合装置１００は、該対象文字列の読み出した文字を照合した結果、フェイラ遷移に基づいて初期状態ノードへ遷移するときに、読み出した文字に対応する第一ノードへ遷移する。そして、照合装置１００は、該対象文字列の次に読み出した文字について、該トライ構造の次の文字桁の文字と照合する。かかる構成によれば、照合装置１００によれば、対象文字列の最初の文字の読み出し時に、トライ構造の中の、読み出した文字に対応する第一ノードへ遷移する。また、照合装置１００によれば、初期状態ノードへのフェイラ遷移時に、トライ構造の中の、読み出した文字に対応する第一ノードへ遷移する。このため、照合装置１００は、並列処理を行う場合、トライ構造へのアクセスが分散することになり、並列処理を効率的に行うことができる。
【０１４３】
また、上記実施例によれば、並列処理を行う場合であっても、並列数分のＡＣマシンとしないで１つのＡＣマシンとすることで、ＡＣマシンの大きさを小さくすることができるという効果がある。例えば、トライ構造の一例に挙げられる状態定義を格納するＲＡＭの容量を小さくすることができる。ここで、状態定義を格納するＲＡＭの容量を小さくすることができるという効果について説明する。ここでは、次の遷移先になり得るエントリの数について、上記実施例のようなＡＣマシンが１つである場合と、ＡＣマシンが並列数分ある場合とで比較する。
【０１４４】
前提条件は、以下とする。ＡＣマシンが１つである場合のＡＣマシンは、１バイトごとに処理する方式を採用するとする。これに対し、ＡＣマシンが並列数分ある場合のＡＣマシンは、ＡＣマシンの大きさを小さくする工夫として、ハーフバイト（４ビット）ごとに処理するハーフバイト方式を採用するとする。したがって、ＡＣマシンが１つである場合のＡＣマシンの並列数は１６であるのに対し、ハーフバイト方式では３２となる。また、キーワードの数は５０００とし、１つのキーワード長は２バイトとする。さらに、１ハーフバイト目までのビットパターン（２４種類）、２ハーフバイト目までのビットパターン（２８種類）は、キーワードが５０００個あるので、いずれかのキーワードに前方一致すると仮定する。３ハーフバイト目までのビットパターン（２１２種類）では、６０％がいずれかのキーワードに前方一致すると仮定する。先頭から２バイト目までのビットパターン（２１６種類）は、どれも高々１つのキーワードと前方一致すると仮定する。
【０１４５】
このような前提条件の下、上記実施例のようなＡＣマシンが１つである場合、次の遷移先になり得るエントリの数は、１状態定義に対するエントリの数２５６と第一ノードの数２５６とキーワード数分のノードの数５０００とを用いて、以下のように算出できる。
２５６（エントリ）×（２５６＋５０００）＝１，３４５，５３６
【０１４６】
これに対し、ＡＣマシンが並列数分ある場合、次の遷移先になり得るエントリの数は、並列数３２と１状態定義に対するエントリの数１６（２４）とノードの数とを用いて、算出できる。ノードの数は、初期状態ノードの数１と１ハーフバイト目のノードの数１６（２４）と２ハーフバイト目のノードの数２５６（２８）と３ハーフバイト目のノードの数３０００（２１２×０．６）とキーワード分のノードの数５０００とを加算した値となる。
３２（並列）×１６（エントリ）×（１＋１６＋２５６＋３０００＋５０００）＝４，２３５，７７６
【０１４７】
上記の算出結果から、ＡＣマシンが１つである場合の、次の遷移先になり得るエントリ数は、ＡＣマシンが並列数分ある場合のエントリ数を１とすると、約０．３１７となる。すなわち、ＡＣマシンが１つである場合の方が、ＡＣマシンが並列数分ある場合よりも、必要なエントリ数を約１／３にすることができる。したがって、上記実施例では、必要な状態定義を格納するＲＡＭの容量を小さくすることができるという効果を得ることができる。
【０１４８】
なお、ＡＣマシン構築部１５０ａは、ＦＰＧＡを一例とする制御部１５０に含まれると説明した。しかしながら、ＡＣマシン構築部１５０ａは、これに限定されず、ＣＰＵを一例とする他の制御部に含まれるとしても良い。
【０１４９】
［プログラムなど］
なお、照合装置１００は、既知のパーソナルコンピュータ、ワークステーションなどの情報処理装置に、上記したＡＣマシン構築部１５０ａ、照合部１５０ｂなどの各機能を搭載することによって実現することができる。
【０１５０】
また、図示した各装置の各構成要素は、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的態様は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。例えば、照合部１５０ｂと照合結果出力部１５０ｃとを１個の部として統合しても良い。一方、ＡＣマシン構築部１５０ａを、トライを構築する処理部と、トライにフェイラ遷移を追加する処理部と、初期状態ノードを削除する処理部と、第一ノードを追加する処理部とに分散しても良い。また、ＡＣマシン１４０ｂなどの記憶部を照合装置１００の外部装置としてネットワーク経由で接続するようにしても良い。
【０１５１】
また、上記実施例で説明した各種の処理は、あらかじめ用意されたプログラムをパーソナルコンピュータやワークステーションなどのコンピュータで実行することによって実現することができる。そこで、以下では、図２９に示した照合装置１００と同様の機能を実現する照合プログラムを実行するコンピュータの一例を説明する。図５４は、照合プログラムを実行するコンピュータの一例を示す図である。
【０１５２】
図５４に示すように、コンピュータ２００は、各種演算処理を実行するＣＰＵ２０１およびＦＰＧＡ２０２と、ユーザからのデータの入力を受け付ける入力装置２０３と、ディスプレイ２０４を有する。また、コンピュータ２００は、記憶媒体からプログラム等を読取る読み取り装置２０５と、ネットワークを介して他のコンピュータとの間でデータの授受を行うインタフェース装置２０６とを有する。また、コンピュータ２００は、各種情報を一時記憶するＲＡＭ２０７と、ハードディスク装置２０８を有する。そして、各装置２０１〜２０８は、バス２０９に接続される。
【０１５３】
ハードディスク装置２０８は、ＡＣマシン構築プログラム２０８ａ、照合プログラム２０８ｂを記憶する。ＦＰＧＡ２０２は、各プログラム２０８ａ〜２０８ｂを読み出して、ＲＡＭ２０７に展開する。ＡＣマシン構築プログラム２０８ａは、ＡＣマシン構築プロセス２０７ａとして機能する。照合プログラム２０８ｂは、照合プロセス２０７ｂとして機能する。
【０１５４】
例えば、ＡＣマシン構築プロセス２０７ａは、ＡＣマシン構築部１５０ａに対応する。照合プロセス２０７ｂは、照合部１５０ｂに対応する。
【０１５５】
なお、各プログラム２０８ａ〜２０８ｂについては、必ずしも最初からハードディスク装置２０８に記憶させておかなくてもよい。例えば、コンピュータ２００に挿入されるフレキシブルディスク（ＦＤ）、ＣＤ−ＲＯＭ、ＤＶＤディスク、光磁気ディスク、ＩＣカードなどの「可搬用の物理媒体」に各プログラムを記憶させておく。そして、コンピュータ２００がこれらから各プログラム２０８ａ〜２０８ｂを読み出して実行するようにしても良い。
【符号の説明】
【０１５６】
１００    照合装置
１１０    入力部
１２０    出力部
１３０    入出力制御部
１４０    記憶部
１４０ａ  パターン集合
１４０ｂ  ＡＣマシン
１５０    制御部
１５０ａ  ＡＣマシン構築部
１５０ｂ  照合部
１５０ｃ  照合結果出力部
【図１】
0005810951.tif 000002
【図２】
0005810951.tif 000003
【図３】
0005810951.tif 000004
【図４】
0005810951.tif 000005
【図５】
0005810951.tif 000006
【図６】
0005810951.tif 000007
【図７】
0005810951.tif 000008
【図８】
0005810951.tif 000009
【図９】
0005810951.tif 000010
【図１０】
0005810951.tif 000011
【図１１】
0005810951.tif 000012
【図１２】
0005810951.tif 000013
【図１３】
0005810951.tif 000014
【図１４】
0005810951.tif 000015
【図１５】
0005810951.tif 000016
【図１６】
0005810951.tif 000017
【図１７】
0005810951.tif 000018
【図１８】
0005810951.tif 000019
【図１９】
0005810951.tif 000020
【図２０】
0005810951.tif 000021
【図２１】
0005810951.tif 000022
【図２２】
0005810951.tif 000023
【図２３】
0005810951.tif 000024
【図２４】
0005810951.tif 000025
【図２５】
0005810951.tif 000026
【図２６】
0005810951.tif 000027
【図２７】
0005810951.tif 000028
【図２８】
0005810951.tif 000029
【図２９】
0005810951.tif 000030
【図３０】
0005810951.tif 000031
【図３１】
0005810951.tif 000032
【図３２】
0005810951.tif 000033
【図３３】
0005810951.tif 000034
【図３４】
0005810951.tif 000035
【図３５】
0005810951.tif 000036
【図３６】
0005810951.tif 000037
【図３７】
0005810951.tif 000038
【図３８】
0005810951.tif 000039
【図３９】
0005810951.tif 000040
【図４０】
0005810951.tif 000041
【図４１】
0005810951.tif 000042
【図４２】
0005810951.tif 000043
【図４３】
0005810951.tif 000044
【図４４】
0005810951.tif 000045
【図４５】
0005810951.tif 000046
【図４６】
0005810951.tif 000047
【図４７】
0005810951.tif 000048
【図４８】
0005810951.tif 000049
【図４９】
0005810951.tif 000050
【図５０】
0005810951.tif 000051
【図５１】
0005810951.tif 000052
【図５２】
0005810951.tif 000053
【図５３】
0005810951.tif 000054
【図５４】
0005810951.tif 000055