(57)【要約】【課題】  オートマトンを処理する際のメモリ消費量を軽減すること。【解決手段】  少なくとも１つのＮＦＡを集めてＮＦＡのクラスタを生成するクラスタ生成装置１は、演算処理を行う際に用いられる記憶領域としてのメモリと、演算処理を行う演算処理装置とを少なくとも備えるとともに、クラスタ生成装置１は、メモリに読み込まれたＮＦＡ群から構造の共通性を有するＮＦＡ群を集めてＮＦＡのクラスタを生成し、ＮＦＡのクラスタをメモリに書き出すクラスタ生成部１１０を含んで構成されることを特徴とする。また、クラスタ生成装置１は、１つのクラスタに所属する複数のＮＦＡを、１つのＮＦＡに統合してメモリに書き出すＮＦＡ統合部１１５をさらに含めて構成されることを特徴とする。【選択図】      図１
2005135179.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも１つの非決定性有限オートマトンを集めて非決定性有限オートマトンのクラスタを生成するクラスタ生成装置であって、前記クラスタ生成装置は、演算処理を行う際に用いられる記憶領域としてのメモリと、前記演算処理を行う演算処理装置とを少なくとも備え、前記クラスタ生成装置は、前記メモリに読み込まれた非決定性有限オートマトン群から構造の共通性を有する非決定性有限オートマトン群を集めて非決定性有限オートマトンのクラスタを生成し、前記非決定性有限オートマトンのクラスタを前記メモリに書き出すクラスタ生成部を含んで構成されることを特徴とするクラスタ生成装置。
【請求項２】
前記クラスタ生成装置は、前記１つのクラスタに所属する複数の非決定性有限オートマトンを、１つの非決定性有限オートマトンに統合して前記メモリに書き出す非決定性有限オートマトン統合部をさらに含めて構成されることを特徴とする請求項１に記載のクラスタ生成装置。
【請求項３】
非決定性有限オートマトンから決定性有限オートマトンを生成する決定性有限オートマトン生成装置であって、前記決定性有限オートマトン生成装置は、演算処理を行う際に用いられる記憶領域としてのメモリと、前記演算処理を行う演算処理装置とを少なくとも備え、前記決定性有限オートマトン生成装置は、サブセット生成法に従い前記メモリに格納された非決定性有限オートマトンから決定性有限オートマトンを生成する決定性有限オートマトン生成手段と、前記決定性有限オートマトン生成部によって生成された決定性有限オートマトンの状態を構成する非決定性有限オートマトンの状態を前記メモリに格納する際に、任意自己推移則を含む非決定性有限オートマトンの状態を記憶する共有状態記憶部と、任意自己推移則を含まない非決定性有限オートマトンの状態を記憶する排他状態記憶部と、に分離して非決定性有限オートマトンの状態を記憶するとともに、共有状態記憶部に記憶された非決定性有限オートマトンの状態を複数の決定性有限オートマトンの状態の構成要素として共有する手段を有することを特徴とする決定性有限オートマトン生成装置。
【請求項４】
演算処理を行う際に用いられる記憶領域としてのメモリと、前記演算処理を行う演算処理装置とを少なくとも備えるコンピュータを、前記メモリに読み込まれた非決定性有限オートマトン群から構造の共通性を有する非決定性有限オートマトン群を集めて非決定性有限オートマトンのクラスタを生成し、前記非決定性有限オートマトンのクラスタを前記メモリに書き出すクラスタ生成手段として機能させるためのクラスタ生成プログラム。
【請求項５】
演算処理を行う際に用いられる記憶領域としてのメモリと、前記演算処理を行う演算処理装置とを少なくとも備えるコンピュータを、サブセット生成法に従い前記メモリに格納された非決定性有限オートマトンから決定性有限オートマトンを生成する決定性有限オートマトン生成手段と、前記決定性有限オートマトン生成部によって生成された決定性有限オートマトンの状態を構成する非決定性有限オートマトンの状態を前記メモリに格納する際に、任意自己推移則を含む非決定性有限オートマトンの状態を記憶する共有状態記憶部と、任意自己推移則を含まない非決定性有限オートマトンの状態を記憶する排他状態記憶部と、に分離して非決定性有限オートマトンの状態を記憶するとともに、共有状態記憶部に記憶された非決定性有限オートマトンの状態を複数の決定性有限オートマトンの状態の構成要素として共有する手段、として機能させるための決定性有限オートマトン生成プログラム。
【請求項６】
請求項４または請求項５に記載されたプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項７】
少なくとも１つの非決定性有限オートマトンを集めて非決定性有限オートマトンのクラスタを生成するクラスタ生成方法であって、演算処理を行う際に用いられる記憶領域としてのメモリと、前記演算処理を行う演算処理装置とを少なくとも備えるクラスタ生成装置が、前記メモリに読み込まれた非決定性有限オートマトン群から構造の共通性を有する非決定性有限オートマトン群を集めて非決定性有限オートマトンのクラスタを生成する手順と、前記生成された１つのクラスタに所属する複数の非決定性有限オートマトンを、１つの非決定性有限オートマトンに統合して前記メモリに書き出す手順と、を実行することを特徴とするクラスタ生成方法。
【請求項８】
前記クラスタ生成装置は、任意の文字、及び前記クラスタの数を制御するための情報を入力する入力手段を備え、前記非決定性有限オートマトンのクラスタを生成する手順は、前記メモリに読み込まれた全ての非決定性有限オートマトン群を１つのクラスタに所属させ、そのクラスタを前記入力手段を介しての第０文字目の文字列入力がなされた後に生成されたクラスタとみなす処理を１回実行した後、変数ｉを初期値１から１ずつ増加させながら前記クラスタの数を制御するための情報から算出されるｋ回数だけ、クラスタ分割処理を繰り返し行うものとし、前記クラスタ分割処理は、前記入力手段を介しての第ｉ文字目の文字列入力に対して、第ｉ−１文字目までの文字列入力によって生成された各クラスタを２つのクラスタに分割し、分割した第１のクラスタは、第ｉ文字目の文字列の種別に関わらず第ｉ文字目の文字列入力がなされる前の状態から第ｉ文字目の文字列入力がなされた後に同一の状態へ推移する任意自己推移則を有する非決定性有限オートマトンを所属させるとともに、分割した第２のクラスタは、前記第１のクラスタに属さない非決定性有限オートマトンを所属させることを特徴とする請求項７に記載のクラスタ生成方法。（１≦ｋ≦オートマトンが受理する最大長）
【請求項９】
非決定性有限オートマトンから決定性有限オートマトンを生成する決定性有限オートマトン生成方法であって、演算処理を行う際に用いられる記憶領域としてのメモリと、前記演算処理を行う演算処理装置とを少なくとも備える決定性有限オートマトン生成装置は、サブセット生成法に従い前記メモリに格納された非決定性有限オートマトンから決定性有限オートマトンを生成する決定性有限オートマトン生成手順と、前記生成された決定性有限オートマトンの状態を構成する非決定性有限オートマトンの状態を前記メモリに格納する際に、任意自己推移則を含む非決定性有限オートマトンの状態を記憶する共有状態記憶部と、任意自己推移則を含まない非決定性有限オートマトンの状態を記憶する排他状態記憶部と、に分離して非決定性有限オートマトンの状態を記憶するとともに、共有状態記憶部に記憶された非決定性有限オートマトンの状態を複数の決定性有限オートマトンの状態の構成要素として共有する手順、を実行することを特徴とするクラスタ生成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、クラスタ生成装置、クラスタ生成プログラム、および、クラスタ生成方法、ならびに、決定性有限オートマトン生成装置、決定性有限オートマトン生成プログラム、および、決定性有限オートマトン生成方法に関する。
【背景技術】
【０００２】
オートマトンは言語処理の基礎理論であり、利用分野は広い（非特許文献１など）。オートマトンの利用分野の具体例としては、プログラミング言語のパース処理、ＸＭＬ（Extensible Markup Language）文書が与えられた文法(スキーマ)に従うか否かを判定するバリデーション処理、ＸＭＬ文書に対するＸＰａｔｈ（XML Path Language）はＸＳＬＴ（XML Stylesheet Language Transform）式などを用いた検索処理などが挙げられる。例えば、ＸＰａｔｈ式などを用いた検索処理では、ＸＰａｔｈ式で記述された検索条件をオートマトンに変換して、検索対象であるＸＭＬ文書を検索することにより、ＸＭＬ文書のデータ構造を活かした効率の良い検索が実現できる。
【０００３】
従来の決定性有限オートマトン＝ＤＦＡ（Deterministic Finite-state Automaton）の生成手法であるサブセット生成法では、個々のＤＦＡの状態においてそれに対応する全ての非決定性有限オートマトン＝ＮＦＡ（Non-deterministic Finite-state Automaton）の状態群を記録する必要がある（非特許文献１など）。この手法では、特に前記したように複雑なＸＭＬ文書を対象に大量のＸＰａｔｈ式の処理をＤＦＡで実施する場合、大規模なメモリ領域を消費してしまう。一方、ＤＦＡを作成せずにＮＦＡを改良する技術もあるが、その手法では同時に推移可能な状態が複数存在するため、処理性能がＤＦＡを用いる場合と比較して劣化してしまうという問題が挙げられる。なお、ＸＰａｔｈ、ＸＴＬ（XML Transformation Language）で使用される言語であって、入力ＸＭＬ内の変換対象を指定するための言語である（非特許文献２など）。
【非特許文献１】John E. Hopcroft、Ullman、Rotwani、Hopcroft、Jeffrey D. Ullman、Rajeev Motwani著、“Introduction to Automata, Theory, Languages and Computation”、出版社“Addison-Wesley”、ISBN: 0201441241、2nd 版 (2000/11/14)
【非特許文献２】The World Wide Web Consortium (W3C)、"XML Path Language (XPath) Version 1.0"、[online]、［平成１５年１０月２９日検索］、インターネット＜ＵＲＬ：http://www.w3.org/TR/xpath.html＞
【発明の開示】
【発明が解決しようとする課題】
【０００４】
複雑な文法や大量のＸＰａｔｈ式をＤＦＡを用いて処理する場合、ＤＦＡの状態数が増大し、同時にＤＦＡの状態に対応するＮＦＡの状態数が増大するため、オートマトンを格納する記憶領域が逼迫するという問題があった。例えば、複雑なＸＭＬ文書を対象に１０万件のＸＰａｔｈ式を処理するためのＤＦＡを構築した場合、約４５０００個のＤＦＡの状態が必要となり、個々のＤＦＡの状態に対応するＮＦＡの状態数は平均約８０００個、結果としてＤＦＡ全体として１６００ＭＢのメモリ領域を消費するという例が挙げられる。メモリは価格が高価であるため、ＤＦＡのメモリ消費量を軽減することは重要な課題である。
【０００５】
そこで、本発明は、前記した問題を解決し、オートマトンを処理する際のメモリ消費量を軽減することを主な目的とする。
【課題を解決するための手段】
【０００６】
前記課題を解決するため、請求項１に記載のクラスタ生成装置は、少なくとも１つの非決定性有限オートマトンを集めて非決定性有限オートマトンのクラスタを生成するクラスタ生成装置であって、前記クラスタ生成装置は、演算処理を行う際に用いられる記憶領域としてのメモリと、前記演算処理を行う演算処理装置とを少なくとも備え、前記クラスタ生成装置は、前記メモリに読み込まれた非決定性有限オートマトン群から構造の共通性を有する非決定性有限オートマトン群を集めて非決定性有限オートマトンのクラスタを生成し、前記非決定性有限オートマトンのクラスタを前記メモリに書き出すクラスタ生成部を含んで構成されることを特徴とする。
【０００７】
請求項２に記載のクラスタ生成装置は、請求項１に記載のクラスタ生成装置であって、前記クラスタ生成装置は、前記１つのクラスタに所属する複数の非決定性有限オートマトンを、１つの非決定性有限オートマトンに統合して前記メモリに書き出す非決定性有限オートマトン統合部をさらに含めて構成されることを特徴とする。
【０００８】
請求項３に記載の決定性有限オートマトン生成装置は、非決定性有限オートマトンから決定性有限オートマトンを生成する決定性有限オートマトン生成装置であって、前記決定性有限オートマトン生成装置は、演算処理を行う際に用いられる記憶領域としてのメモリと、前記演算処理を行う演算処理装置とを少なくとも備え、前記決定性有限オートマトン生成装置は、サブセット生成法に従い前記メモリに格納された非決定性有限オートマトンから決定性有限オートマトンを生成する決定性有限オートマトン生成手段と、前記決定性有限オートマトン生成部によって生成された決定性有限オートマトンの状態を構成する非決定性有限オートマトンの状態を前記メモリに格納する際に、任意自己推移則を含む非決定性有限オートマトンの状態を記憶する共有状態記憶部と、任意自己推移則を含まない非決定性有限オートマトンの状態を記憶する排他状態記憶部と、に分離して非決定性有限オートマトンの状態を記憶するとともに、共有状態記憶部に記憶された非決定性有限オートマトンの状態を複数の決定性有限オートマトンの状態の構成要素として共有する手段を有することを特徴とする。
【０００９】
請求項４に記載のクラスタ生成プログラムは、演算処理を行う際に用いられる記憶領域としてのメモリと、前記演算処理を行う演算処理装置とを少なくとも備えるコンピュータを、前記メモリに読み込まれた非決定性有限オートマトン群から構造の共通性を有する非決定性有限オートマトン群を集めて非決定性有限オートマトンのクラスタを生成し、前記非決定性有限オートマトンのクラスタを前記メモリに書き出すクラスタ生成手段として機能させることを特徴とする。
【００１０】
請求項５に記載の決定性有限オートマトン生成プログラムは、演算処理を行う際に用いられる記憶領域としてのメモリと、前記演算処理を行う演算処理装置とを少なくとも備えるコンピュータを、サブセット生成法に従い前記メモリに格納された非決定性有限オートマトンから決定性有限オートマトンを生成する決定性有限オートマトン生成手段と、前記決定性有限オートマトン生成部によって生成された決定性有限オートマトンの状態を構成する非決定性有限オートマトンの状態を前記メモリに格納する際に、任意自己推移則を含む非決定性有限オートマトンの状態を記憶する共有状態記憶部と、任意自己推移則を含まない非決定性有限オートマトンの状態を記憶する排他状態記憶部と、に分離して非決定性有限オートマトンの状態を記憶するとともに、共有状態記憶部に記憶された非決定性有限オートマトンの状態を複数の決定性有限オートマトンの状態の構成要素として共有する手段、として機能させることを特徴とする。
【００１１】
請求項７に記載のクラスタ生成方法は、少なくとも１つの非決定性有限オートマトンを集めて非決定性有限オートマトンのクラスタを生成するクラスタ生成方法であって、演算処理を行う際に用いられる記憶領域としてのメモリと、前記演算処理を行う演算処理装置とを少なくとも備えるクラスタ生成装置が、前記メモリに読み込まれた非決定性有限オートマトン群から構造の共通性を有する非決定性有限オートマトン群を集めて非決定性有限オートマトンのクラスタを生成する手順と、前記生成された１つのクラスタに所属する複数の非決定性有限オートマトンを、１つの非決定性有限オートマトンに統合して前記メモリに書き出す手順と、を実行することを特徴とする。
【００１２】
請求項８に記載のクラスタ生成方法は、請求項７に記載のクラスタ生成方法であって、前記クラスタ生成装置は、任意の文字、及び前記クラスタの数を制御するための情報を入力する入力手段を備え、前記非決定性有限オートマトンのクラスタを生成する手順は、前記メモリに読み込まれた全ての非決定性有限オートマトン群を１つのクラスタに所属させ、そのクラスタを前記入力手段を介しての第０文字目の文字列入力がなされた後に生成されたクラスタとみなす処理を１回実行した後、変数ｉを初期値１から１ずつ増加させながら前記クラスタの数を制御するための情報から算出されるｋ回数だけ、クラスタ分割処理を繰り返し行うものとし、前記クラスタ分割処理は、前記入力手段を介しての第ｉ文字目の文字列入力に対して、第ｉ−１文字目までの文字列入力によって生成された各クラスタを２つのクラスタに分割し、分割した第１のクラスタは、第ｉ文字目の文字列の種別に関わらず第ｉ文字目の文字列入力がなされる前の状態から第ｉ文字目の文字列入力がなされた後に同一の状態へ推移する任意自己推移則を有する非決定性有限オートマトンを所属させるとともに、分割した第２のクラスタは、前記第１のクラスタに属さない非決定性有限オートマトンを所属させることを特徴とする（１≦ｋ≦オートマトンが受理する最大長）。
【００１３】
請求項９に記載のクラスタ生成方法は、非決定性有限オートマトンから決定性有限オートマトンを生成する決定性有限オートマトン生成方法であって、演算処理を行う際に用いられる記憶領域としてのメモリと、前記演算処理を行う演算処理装置とを少なくとも備える決定性有限オートマトン生成装置は、サブセット生成法に従い前記メモリに格納された非決定性有限オートマトンから決定性有限オートマトンを生成する決定性有限オートマトン生成手順と、前記生成された決定性有限オートマトンの状態を構成する非決定性有限オートマトンの状態を前記メモリに格納する際に、任意自己推移則を含む非決定性有限オートマトンの状態を記憶する共有状態記憶部と、任意自己推移則を含まない非決定性有限オートマトンの状態を記憶する排他状態記憶部と、に分離して非決定性有限オートマトンの状態を記憶するとともに、共有状態記憶部に記憶された非決定性有限オートマトンの状態を複数の決定性有限オートマトンの状態の構成要素として共有する手順、を実行することを特徴とする。
【００１４】
なお、第１の観点の発明（前記クラスタ生成装置、前記クラスタ生成プログラム、前記クラスタ生成方法）により、任意自己推移則はＤＦＡの状態数に大きく影響することが分かっており（Todd J. Green, Gerome Miklau, Makoto Onizuka, Dan Suciu著“Processing XML Streams with Deterministic Automata.”、ICDT（2003）を参照）、その観点でＮＦＡをクラスタ化することによって、任意自己推移による悪影響を局所化することが可能である。この結果、全体のＤＦＡの状態数を減少させることが可能となる。
【００１５】
また、第２の観点の発明（前記ＤＦＡ生成装置、前記ＤＦＡ生成プログラム、前記ＤＦＡ生成方法）により、ＮＦＡにおける推移則の種類（任意推移則か否か）により推移則を分類し、任意推移側により推移可能なＮＦＡの状態群を他のＤＦＡの状態と共有し、それ以外の推移側により推移可能なＮＦＡの状態群を個々のＤＦＡの状態ごとに排他的に管理する。これにより、個々のＤＦＡの状態が管理するＮＦＡの状態群が使用するメモリ容量を減少させることが可能となる。
【発明の効果】
【００１６】
本発明は、ＤＦＡにおける２つのメモリ消費の要因（ＤＦＡの状態数、個々のＤＦＡの状態が管理するＮＦＡの状態数）を、ＮＦＡ群のクラスタ分割処理、および、ＤＦＡの状態において対応するＮＦＡの状態群の共有により縮小する処理、の２つの処理によってメモリ使用量を軽減することが可能となった。
【発明を実施するための最良の形態】
【００１７】
図１に示すオートマトン処理システムは、メモリ領域を節約して効率的にＮＦＡからＤＦＡを生成する機能を有する。このため、オートマトン処理システムは、ＮＦＡ群からＮＦＡのクラスタを生成するクラスタ生成装置１と、ＮＦＡのクラスタからＤＦＡを生成するＤＦＡ生成装置２と、を含めて構成される。なお、クラスタ生成装置１とＤＦＡ生成装置２との間は、例えばＬＡＮ（Local Area Network）によってデータ通信が可能なように構成されている。以下、各構成要素について、具体的に説明する。
【００１８】
まず、クラスタ生成装置１は、ＮＦＡ群を格納するＮＦＡ記憶部１００と、ＮＦＡ群からＮＦＡのクラスタを生成するクラスタ生成部１１０と、各クラスタに属するＮＦＡ群を各クラスタに対応する１つのＮＦＡに統合するＮＦＡ統合部１１５と、生成されたＮＦＡのクラスタを格納するクラスタ記憶部１２０と、を含めて構成される。
【００１９】
次に、ＤＦＡ生成装置２は、ＮＦＡからＤＦＡを生成するＤＦＡ生成部１３０と、生成されたＤＦＡを格納するＤＦＡ記憶部１４０と、を含めて構成される。なお、ＤＦＡ記憶部１４０は、ＤＦＡの状態を構成するためのＮＦＡの状態のうち、複数のＤＦＡの状態に共有されるＮＦＡの状態を記憶する共有状態記憶部１５０と、共有状態記憶部１５０に格納されないＮＦＡの状態を記憶する排他状態記憶部１６０と、を含めて構成される。
【００２０】
図２に示すデータ構造は、ＤＦＡ記憶部１４０に記憶される状態のデータの格納形式の一例である。ＤＦＡの状態とＮＦＡの状態との対応表であるＤＦＡ状態管理テーブル１８０（図２（Ｂ）参照）の各レコードは、ＤＦＡの状態を特定するＤＦＡ状態ＩＤと、ＤＦＡの状態を構成するための共有状態を参照するための共有状態群参照と、ＤＦＡの状態を構成するための排他ＮＦＡ状態群と、を含めて構成される。そして、共有状態記憶部１５０における共有されるＮＦＡを管理するためのデータベースである共有状態管理テーブル１７０（図２（Ａ）参照）の各レコードは、共有状態を特定する共有状態ＩＤと、共有状態となるＮＦＡ状態群と、の組で構成される。
【００２１】
ここで、図１に示すオートマトン処理システムを実現するためのハードウェア資源について、説明する。オートマトン処理システムを構成する各装置（クラスタ生成装置１、ＤＦＡ生成装置２）は、例えば、ＣＰＵ（Central Processing Unit）、ＲＡＭ（Random-Access Memory）などのメモリを備えたコンピュータとして構成される。具体的には、処理に関する構成要素（クラスタ生成部１１０、ＮＦＡ統合部１１５、ＤＦＡ生成部１３０）は、例えば、ＣＰＵに読み取られて実行されるプログラムとして構成される。また、記憶に関する構成要素（ＮＦＡ記憶部１００、クラスタ記憶部１２０、ＤＦＡ記憶部１４０、共有状態記憶部１５０、排他状態記憶部１６０）は、例えば、ＲＡＭ上の所定のアドレスに対応する記憶領域に相当する。
【００２２】
なお、図１に示すオートマトン処理システムは、２台の筐体（クラスタ生成装置１、ＤＦＡ生成装置２）として構成することとしたが、これはあくまで一例であり、オートマトン処理システムの各構成要素を、何台の筐体が実現するかについては、ＣＰＵの処理能力や、ＲＡＭのメモリ容量に応じて、適宜変更してもよい。例えば、省スペース化のために、クラスタ生成装置１とＤＦＡ生成装置２とを物理的に１台の筐体に収めて構成する、などが挙げられる。
【００２３】
以上、オートマトン処理システムの構成について、説明した。次に、オートマトン処理システムの動作について、クラスタ生成装置１によるＮＦＡからのクラスタの生成処理、および、ＤＦＡ生成装置２によるＮＦＡからのＤＦＡの作成処理、の２段階に分けて説明する。まず、クラスタ生成装置１によるＮＦＡからのクラスタ生成処理の概要について、図３を用いて説明する。なお、図３の左側にクラスタ分類される前のＮＦＡ群を、図３の右側にクラスタ分類された後のＮＦＡ群を、それぞれ示す。
【００２４】
まず、クラスタ生成装置１は、第１文字目に関する処理を行う。つまり、図３の左側に示された６つのＮＦＡから構成されるＮＦＡ群について、第１文字目に任意自己推移則を含むＮＦＡ群と、第１文字目に任意自己推移則を含まないＮＦＡ群と、に分類する。そして、クラスタ生成装置１は、第１文字目に任意自己推移則を含むＮＦＡ群をクラスタＣ１１（図示省略）に所属させ、第１文字目に任意自己推移則を含まないＮＦＡ群をクラスタＣ１２（図示省略）に所属させる。よって、３つのクラスタがＣ１１に所属し、３つのクラスタがＣ１２に所属する。
【００２５】
次に、クラスタ生成装置１は、第２文字目に関する処理を行う。まず、クラスタ生成装置１は、クラスタＣ１１に所属するＮＦＡ群について、第２文字目に任意自己推移則を含むＮＦＡ群をクラスタＣ１に所属させ、第２文字目に任意自己推移則を含まないＮＦＡ群をクラスタＣ２に所属させる。同様に、クラスタ生成装置１は、クラスタＣ１２に所属するＮＦＡ群について、第２文字目に任意自己推移則を含むＮＦＡ群をクラスタＣ３に所属させ、第２文字目に任意自己推移則を含まないＮＦＡ群をクラスタＣ４に所属させる。
【００２６】
以上、第２文字目までを対象とする２回のクラスタ生成処理によって、４つのクラスタ（２×２）が生成された。同様にして、３回のクラスタ生成処理は、８つのクラスタ（２×２×２）を生成する。このようにして、ｋ回のクラスタ生成処理は、２のｋ乗個のクラスタを生成する。よって、クラスタ生成処理の回数に応じて、生成されるクラスタの個数が決定される。なお、クラスタ生成装置１は、クラスタ生成処理の回数を入力パラメータとして、例えば、利用者画面を介して、ユーザからの入力を受け付けるようにする。
【００２７】
以上、クラスタの生成処理の概要について、説明した。次に、クラスタの生成処理の流れについて、図４に沿って説明する。なお、図４は、クラスタ生成装置１を主体とするフローチャートである。
【００２８】
まず、クラスタ生成装置１は、ＮＦＡ記憶部１００からＮＦＡ群を読み込み、リスト変数Ｒへ要素として追加する（Ｓ２００）。この結果、Ｒは、１つの要素が登録されていて、かつ、その要素はＮＦＡ記憶部１００に登録されている全てのＮＦＡ群の情報を有する。次に、クラスタ生成装置１は、クラスタ数の入力を受け付けて、変数Ｎに書き込む（Ｓ２１０）。但し、Ｎは２のｎ（ｎは１以上の整数）乗の数であることとする。そして、クラスタ生成装置１は、１からＬｍａｘまでクラスタ処理を繰り返し行うために、ｌｏｇ２Ｎを演算しその結果を変数Ｌｍａｘに書き込む（Ｓ２２０）。さらに、クラスタ生成装置１は、ループ変数ｉを１に初期化する（Ｓ２３０）。
【００２９】
ここで、クラスタ生成装置１は、ループの終了条件（ｉ＜＝Ｌｍａｘ）を判定する（Ｓ２４０）。まず、判定結果が偽（Ｓ２４０、Ｎ）であれば、クラスタ生成装置１は、クラスタ生成処理を終了したとみなし、個々のクラスタに属するＮＦＡ群を１つのＮＦＡに統合し（Ｓ３２０）、処理を終了させる。
【００３０】
なお、クラスタ生成装置１は、ＮＦＡ統合部１１５を用いて行うＮＦＡ群への統合処理は、以下に示す手続きを、個々のクラスタ毎に実施する。まず、ＮＦＡ統合部１１５は、ＮＦＡの開始状態を作成する。次に、ＮＦＡ統合部１１５は、その開始状態からそのクラスタに属する全てのＮＦＡの開始状態ヘイプシロン推移により推移する推移則群を作成する。さらに、ＮＦＡ統合部１１５は、そのクラスタに属する全てのＮＦＡの状態、推移規則、終了状態を、作成したＮＦＡの状態、推移規則、終了状態に加える。以上に示す手続きにより、クラスタに属する１つ以上のＮＦＡが、１つのＮＦＡに統合される。
【００３１】
一方、判定結果が真（Ｓ２４０、Ｙ）であれば、ループ処理を行う。まず、クラスタ生成装置１は、個々のクラスタ毎にクラスタを再分解するためのループ処理のため、ループ変数ｊを１に初期化し、再分解後のクラスタ群を格納するための変数Ｒ２を空集合に初期化する（Ｓ２５０）。
【００３２】
そして、クラスタ生成装置１は、ループの終了条件（ｊ＜＝Ｒの要素数）、を判定する（Ｓ２６０）。まず、判定結果が偽（Ｓ２６０、Ｎ）であれば、クラスタ生成装置１は、再分解されたクラスタ群をＲに設定する（Ｓ３００）。そして、クラスタ生成装置１は、変数ｉの値をインクリメントする（Ｓ３１０）。さらに、クラスタ生成装置１は、ループの終了条件の判定（Ｓ２４０）に処理を戻す。
【００３３】
一方、判定結果が真（Ｓ２６０、Ｙ）であれば、クラスタ生成装置１は、Ｒのｊ番目の要素(ＮＦＡ群)を取り出しレジスタｑに書き込む（Ｓ２７０）。そして、クラスタ生成装置１は、ｑのＮＦＡ群を２つのクラスタに分解し、結果をＲ２に追加する（Ｓ２８０）。さらに、クラスタ生成装置１は、変数ｊの値をインクリメントする（Ｓ２９０）。そして、クラスタ生成装置１は、ループの終了条件の判定（Ｓ２６０）に処理を戻す。
【００３４】
以上、クラスタの生成処理の流れについて、図４に沿って説明した。さらに、クラスタの生成処理のうち、２つのクラスタに分解する処理（Ｓ２８０）について、図５に沿って具体的に説明する。
【００３５】
まず、クラスタ生成装置１は、２クラスタ処理の結果として得られる２つのクラスタに属するＮＦＡ群を格納するため、変数Ｃ１，Ｃ２を空集合に初期化する（Ｓ３５０）。次に、クラスタ生成装置１は、レジスタｑに書かれている個々のＮＦＡ毎のループ処理のため、ループ変数ｋを１に初期化する（Ｓ３７０）。
【００３６】
ここで、クラスタ生成装置１は、ループの終了条件ｋ＜=ｑに書かれたＮＦＡ数を判定する（Ｓ３８０）。まず、判定結果が偽であれば、クラスタ生成装置１は、ループを抜け、レジスタＲ２にＣ１とＣ２の結果を加え（Ｓ３９０）、２つのクラスタに分解する処理（Ｓ２８０）を終了させる。
【００３７】
一方、判定結果が真であれば、クラスタ生成装置１は、ループ処理を行う。まず、クラスタ生成装置１は、ｑのｋ番目の要素(ＮＦＡ)を取り出し変数ｘに書き込む（Ｓ４００）。
【００３８】
ここで、クラスタ生成装置１は、ｘをＣ１かＣ２かのクラスタに振り分けるための判断を行う（Ｓ４１０）。具体的には、クラスタ生成装置１は、個々のオートマトンｘを対象に、任意自己推移以外の推移則を用いて、ｉ文字分の入力により推移する先のオートマトンの全ての状態において、任意自己推移の有無を判定する。まず、任意自己推移が１つでもあれば、クラスタ生成装置１は、ｘをＣ２に追加する（Ｓ４３０）。一方、任意自己推移がなければ、クラスタ生成装置１は、ｘをＣ１に追加する（Ｓ４２０）。
【００３９】
そして、クラスタ生成装置１は、変数ｋの値をインクリメントし（Ｓ４４０）、処理をＳ３８０に戻す。
【００４０】
以上、クラスタ生成装置１によるＮＦＡからのクラスタ生成処理について、説明した。そして、ＤＦＡ生成装置２によるＮＦＡのクラスタからのＤＦＡの作成処理の概要について、図５に沿って説明する。
【００４１】
図６は、ＮＦＡからＤＦＡを生成する処理を説明する図である。図６は、左側にＮＦＡを示し、右側にＮＦＡから生成されるＤＦＡを示している。さらに、生成されたＤＦＡを表現する情報を、図６の上部に示す。まず、ＤＦＡ生成装置２は、ＮＦＡを構成する７つの状態（Ｓ０〜Ｓ６）について、任意自己推移の有無を確認する。図では、３つの状態（Ｓ１、Ｓ３、Ｓ５）が、任意自己推移を有している。
【００４２】
次に、ＤＦＡ生成装置２は、任意自己推移を有しているＮＦＡの状態を、共有状態として共有状態記憶部１５０に記録する。ここで、記録された共有状態には、共有状態の識別子として、共有状態ＩＤが付される。さらに、ＤＦＡ生成装置２は、共有状態｛Ｓ１、Ｓ３、Ｓ５｝と、ＮＦＡを構成する７つの状態のうち、共有状態には選出されなかった状態｛Ｓ０、Ｓ２、Ｓ４、Ｓ６｝とを用いて、ＤＦＡの状態を作成する。作成されたＤＦＡの状態には、それぞれ識別子となるＤＦＡ状態ＩＤ（ｄ０〜ｄ４）が、付される。
【００４３】
以上、ＤＦＡの作成処理の概要について、説明した。次に、ＤＦＡの作成処理の動作について、図７に沿って説明する。
【００４４】
まず、ＤＦＡ生成装置２は、ＮＦＡを読み込んで、変数Ｑに書き込む（Ｓ５００）。ここで、ＤＦＡ生成装置２は、ＮＦＡをクラスタ生成装置１のクラスタ記憶部１２０より読み込んでもよいし、別装置から新たに読み込んでも良い。次に、ＤＦＡ生成装置２は、ＤＦＡの開始状態ｄ０を作成し、ｄ０に対応する行を排他状態記憶部１６０に挿入する（Ｓ５１０）。
【００４５】
そして、ＤＦＡ生成装置２は、レジスタｄにｄ０を書き込む（Ｓ５２０）。この際、任意自己推移則を用いてｄの排他ＮＦＡ状態群からイプシロン推移可能な状態群を共有状態記憶部１５０に書き込み、そのＩＤを排他状態記憶部１６０の共有状態群参照に追加する。またイプシロン推移により、任意自己推移以外の推移則を用いて、ｄ０の排他ＮＦＡ状態群から推移可能な状態群を排他ＮＦＡ状態群に書き込む。
【００４６】
さらに、ＤＦＡ生成装置２は、レジスタｄから推移可能なＤＦＡの状態を再帰的に生成する（Ｓ５３０）。以上により、ＤＦＡの作成処理の動作について、説明した。ここで、再帰的な生成の生成処理（Ｓ５３０）について、図８に沿って、具体的に説明する。
【００４７】
まず、ＤＦＡ生成装置２は、レジスタｄに記録されたＤＦＡの状態の排他ＮＦＡ状態群から可能な推移則群を収集し、推移を生じさせる入力文字群を変数Ｅに書き込み、文字群の件数をｃに書き込む（Ｓ６１０）。次に、ＤＦＡ生成装置２は、変数Ｅに属する個々の入力文字ごとに繰り返し処理を行うために、変数ｉを１に初期化する（Ｓ６２０）。ここで、ＤＦＡ生成装置２は、ループの終了条件ｉ＜＝ｃを判定する（Ｓ６３０）。
【００４８】
もし、判定結果が真であれば、ＤＦＡ生成装置２は、ループ処理を行う。つまり、ＤＦＡ生成装置２は、変数Ｅのｉ番目の要素を取り出し、変数ｅに書き込む（Ｓ６４０）。次に、ＤＦＡ生成装置２は、ＤＦＡの状態ｄ１を作成し、ｄ１に対応する行を排他状態記憶部１６０に書き込む（Ｓ６５０）。そして、ＤＦＡ生成装置２は、変数ｉの値をインクリメントする（Ｓ６６０）。さらに、ＤＦＡ生成装置２は、処理をＳ６３０に戻す。
【００４９】
一方、判定結果が偽であれば、ＤＦＡ生成装置２は、ループ処理を抜ける。そして、ＤＦＡ生成装置２は、新たに生成された個々のＤＦＡの状態をレジスタｄに記録する（Ｓ６７０）。次に、ＤＦＡ生成装置２は、図８の状態推移処理を再帰的に呼び出す。さらに、ＤＦＡ生成装置２は、推移処理がなされていないＤＦＡの状態が無いかどうかを判定する（Ｓ６８０）。判定結果が真であれば、ＤＦＡ生成装置２は、Ｓ６７０に処理を戻し、判定結果が偽であれば、図８の状態推移処理を終了する。
【００５０】
なお、ＤＦＡ生成装置２は、排他状態記憶部１６０に書き込む（Ｓ６５０）際に、ｄ１の排他状態記憶部１６０の共有状態群参照へ、レジスタｄの排他状態記憶部１６０の共有状態群参照の値をコピーする。変数ｅを入力とし、任意自己推移則を用いて、レジスタｄの排他ＮＦＡ状態群から推移可能な状態群を共有状態記憶部１５０に書き込み（但し、もし同じ組み合わせの状態群が既に登録されていれば、それを利用する）、そのＩＤを排他状態記憶部１６０の共有状態群参照に追加する。また変数ｅを入力とし、任意自己推移以外の推移則を用いて、ｄ０の排他非ＤＦＡ状態群から推移可能な状態群を排他ＮＦＡ状態群に書き込む。このとき、ｄ０の共有状態群と同じ組み合わせの共有状態群であり、且つｄ０の排他状態群と同じ組み合わせの排他状態群であるようなＤＦＡの状態が既に排他状態記憶部１６０のデータ部に登録されている場合は、推移先としてそれを利用してｄ０を削除する。
【００５１】
以上、図８の状態推移処理について、説明した。ここで、ＮＦＡからＤＦＡを生成する処理について、図６を用いて、補足説明する。
【００５２】
図７のＳ５１０の処理により、ＤＦＡｄ０が生成される。次のＳ５３０のサブルーチン処理の内部処理Ｓ６１０により変数Ｅ=[ａ，ｂ，ｃ，ｏｔｈｅｒ]，ｃ=４という処理を行う。但し、ｏｔｈｅｒは列挙された文字以外という意味であり、この場合はａ，ｂ，ｃ以外の文字ということを意味する。Ｓ６２０〜Ｓ６６０のループ処理により、Ｅに属する個々の文字に対してＤＦＡの状態が生成され、ｄ１，ｄ２，ｄ３，ｄ４の状態群を生成する。そしてＳ６７０により生成された個々のｄ１，ｄ２，ｄ３，ｄ４に対して、Ｓ６１０が適用され、各状態からの推移処理が行われる。ｄ１，ｄ２，ｄ３，ｄ４のどのケースにおいても、結果的にＳ６５０で推移先の状態が既に生成済みであることが判断されるため、図６の右側に示されるように既存の状態への推移が矢印によって示されている。
【００５３】
以上、説明した２つの観点の発明は、メモリ使用量の節約に有効である。実際に、複雑なＸＭＬ文書を対象に１０万件のＸＰａｔｈ式を処理するためのＤＦＡを構築した場合、従来の手法では、約４５０００個のＤＦＡの状態が必要となり、個々のＤＦＡの状態に対応するＮＦＡの状態数は平均約８０００個、結果としてＤＦＡ全体として１６００ＭＢのメモリ領域を消費した。そこで、前記の２つの観点の発明を適用したところ(８分割クラスタ)、ＤＦＡ全体のメモリ消費量は、４００ＭＢに削減することができた。
【００５４】
以上説明した本発明は、前記した実施例に限定されることなく、その技術思想の及ぶ範囲で様々な形態として実施することができる。
【図面の簡単な説明】
【００５５】
【図１】本発明の一実施形態に関するオートマトン処理システムの構成図である。
【図２】本発明の一実施形態に関するＤＦＡの状態を管理するための構成図である。
【図３】本発明の一実施形態に関するクラスタ生成装置におけるクラスタ生成を説明する図である。
【図４】本発明の一実施形態に関するクラスタ生成装置におけるクラスタ生成処理を示すフローチャートである。
【図５】本発明の一実施形態に関するクラスタ生成装置におけるクラスタ生成処理の詳細を示すフローチャートである。
【図６】本発明の一実施形態に関するＤＦＡ生成装置におけるＤＦＡ生成を説明する図である。
【図７】本発明の一実施形態に関するＤＦＡ生成装置におけるＤＦＡ生成処理を示すフローチャートである。
【図８】本発明の一実施形態に関するＤＦＡ生成装置におけるサブモジュール状態推移処理のフローチャートである。
【符号の説明】
【００５６】
１      クラスタ生成装置
２      ＤＦＡ（決定性有限オートマトン）生成装置
１００  ＮＦＡ（非決定性有限オートマトン）記憶部
１１０  クラスタ生成部
１１５  ＮＦＡ（非決定性有限オートマトン）統合部
１２０  クラスタ記憶部
１３０  ＤＦＡ（決定性有限オートマトン）生成部
１４０  ＤＦＡ（決定性有限オートマトン）記憶部
１５０  共有状態記憶部
１６０  排他状態記憶部
【図１】
2005135179.tif 000003
【図２】
2005135179.tif 000004
【図３】
2005135179.tif 000005
【図４】
2005135179.tif 000006
【図５】
2005135179.tif 000007
【図６】
2005135179.tif 000008
【図７】
2005135179.tif 000009
【図８】
2005135179.tif 000010