"1つまたは複数のプロセッサおよびシステムメモリを含むコンピュータシステムにおいて、有向非循環グラフで1つまたは複数の正規表現を表現する方法であって、第1の正規表現から分解された1つまたは複数のキーワードグラフにアクセスする動作であって、1つまたは複数のキーワードグラフの各々は1つのルートノード、1つまたは複数の中間ノード、および1つの葉ノードを有し、前記1つまたは複数の中間ノードの各々および前記葉ノードが、前記第1の正規表現に部分的にマッチする文字パターンを特定し、前記ルートノードおよび前記1つまたは複数の中間ノードの各々は単一の子ノードを有し、前記中間ノードの1つは前記葉ノードを子ノードとして有し、各前記葉ノードは前記第1の正規表現のマッチ状態としてラベルが付される、動作と、第2の正規表現の少なくとも一部を表現する第2のグラフにアクセスする動作であって、前記第2のグラフは1つのルートノード、1つまたは複数の中間ノード、および1つまたは複数の葉ノードを有し、前記1つまたは複数の中間ノードおよび前記1つまたは複数の葉ノードの各々が、前記第2の正規表現に部分的にマッチする文字パターンを特定する、動作と、前記1つまたは複数のキーワードグラフおよび前記第2のグラフを、前記第1の正規表現および前記第2の正規表現の両方を集合的に表現する有向非循環グラフにマージする動作であって、前記1つまたは複数のキーワードグラフごとに、前記キーワードグラフを独立に選択する動作と、少なくとも部分的に重複する文字パターンを有する、前記選択されたキーワードグラフおよび前記第2のグラフ内の任意の同様に配置された中間ノードを特定する動作と、同様に配置され、部分的に重複する文字パターンを有する、前記選択されたキーワードグラフ内の任意の特定された中間ノードおよび前記第2のグラフ内の任意の特定の中間ノードに対して、前記選択されたキーワードグラフおよび前記第2のグラフを前記特定された中間ノードでマージして、前記選択されたキーワードグラフおよび前記第2のグラフの等価なマッチ状態を前記有向非循環グラフで表現する動作であって、前記マージにより、前記キーワードグラフが前記第2のグラフの一部となるようにする、動作とを含む、動作と、を含むことを特徴とする方法。少なくとも部分的に重複する文字パターンを有する、前記選択されたキーワードグラフおよび前記第2のグラフ内の任意の同様に配置された中間ノードを特定する前記動作は、完全に重複する、前記選択されたキーワードグラフ内の中間ノードおよび前記第2のグラフ内の中間ノードを特定する動作を含むことを特徴とする請求項1に記載の方法。前記選択されたキーワードグラフおよび前記第2のグラフを前記特定された中間ノードでマージすることは、前記選択されたキーワードグラフ内の前記中間ノードおよび前記第2のグラフ内の前記中間ノードを、前記完全に重複する文字パターンを表現する単一のノードへと結合する動作を含むことを特徴とする請求項2に記載の方法。少なくとも部分的に重複する文字パターンを有する、前記選択されたキーワードグラフおよび前記第2のグラフ内の任意の同様に配置された中間ノードを特定する前記動作は、部分的に重複する、前記選択されたキーワードグラフ内の中間ノードおよび前記第2のグラフ内の中間ノードを特定する動作を含むことを特徴とする請求項1に記載の方法。前記選択されたキーワードグラフおよび前記第2のグラフを前記特定された中間ノードでマージすることは、少なくとも1つの前記特定された中間ノードの前記文字パターンを変更して前記部分的に重複する文字パターンを排除する動作を含むことを特徴とする請求項4に記載の方法。前記選択されたキーワードグラフおよび前記第2のグラフを前記特定された中間ノードでマージすることは、前記選択されたキーワードグラフと前記第2のグラフとの間にエッジを追加して、前記少なくとも1つの前記特定された中間ノードの前記文字パターンの変更を補償する動作を含むことを特徴とする請求項4に記載の方法。コンピュータシステムで使用するためのコンピュータプログラム製品であって、前記コンピュータプログラム製品は、有向非循環グラフで1つまたは複数の正規表現を表現するための方法を実装するものであり、前記コンピュータプログラム製品は、コンピュータ実行可能命令を格納した1つまたは複数のコンピュータ記憶装置を備え、当該コンピュータ実行可能命令は、プロセッサで実行されると、前記コンピュータシステムに、第1の正規表現から分解された1つまたは複数のキーワードグラフにアクセスするステップであって、前記1つまたは複数のキーワードグラフの各々は1つのルートノード、1つまたは複数の中間ノード、および1つの葉ノードを有し、前記1つまたは複数の中間ノードの各々および前記葉ノードが、前記第1の正規表現に部分的にマッチする文字パターンを特定し、前記ルートノードおよび前記1つまたは複数の中間ノードの各々は単一の子ノードを有し、前記中間ノードの1つは前記葉ノードを子ノードとして有し、各前記葉ノードは前記第1の正規表現のマッチ状態としてラベルが付される、ステップと、第2の正規表現を表現する第2のグラフにアクセスするステップであって、前記第2のグラフは1つのルートノード、1つまたは複数の中間ノード、および1つまたは複数の葉ノードを有し、前記1つまたは複数の中間ノードおよび前記1つまたは複数の葉ノードの各々が、前記第2の正規表現に部分的にマッチする文字パターンを特定する、ステップと、前記1つまたは複数のキーワードグラフおよび前記第2のグラフを、前記第1の正規表現および前記第2の正規表現の両方を集合的に表現する有向非循環グラフにマージするステップであって、少なくとも部分的に重複する文字パターンを有する、前記1つまたは複数のキーワードグラフおよび前記第2のグラフ内の任意の同様に配置された中間ノードを特定するステップと、同様に配置され、部分的に重複する文字パターンを有する、前記キーワードグラフ内の任意の特定された中間ノードおよび前記第2のグラフ内の任意の特定された中間ノードに対して、前記キーワードグラフおよび前記第2のグラフを前記特定された中間ノードでマージして、前記キーワードグラフおよび前記第2のグラフ内で表現された等価なマッチ状態を前記有向非循環グラフで表現するステップとを含む、ステップと、を含む前記方法を実施させることを特徴とするコンピュータプログラム製品。実行されると、前記コンピュータシステムに、前記1つまたは複数のキーワードグラフの各々の前記葉ノードに前記第1の正規表現のマッチ状態としてラベルを付させるコンピュータ実行可能命令をさらに含むことを特徴とする請求項7に記載のコンピュータプログラム製品。実行されると、前記コンピュータシステムに、前記第2のグラフ内の各終端ノードに前記第2の正規表現のマッチ状態としてラベルを付させるコンピュータ実行可能命令をさらに含むことを特徴とする請求項7に記載のコンピュータプログラム製品。1つまたは複数のプロセッサおよびシステムメモリを含むコンピュータシステムにおいて、有向非循環グラフで1つまたは複数の正規表現を表現する方法であって、第1の正規表現から分解された1つまたは複数のキーワードグラフにアクセスする動作であって、1つまたは複数のキーワードグラフの各々は1つのルートノード、1つまたは複数の中間ノード、および1つの葉ノードを有し、前記1つまたは複数の中間ノードの各々および前記葉ノードが、前記第1の正規表現に部分的にマッチする文字パターンを特定し、前記ルートノードおよび前記1つまたは複数の中間ノードの各々は単一の子ノードを有し、前記中間ノードの1つは前記葉ノードを子ノードとして有し、各前記葉ノードは前記第1の正規表現のマッチ状態としてラベルが付される、動作と、第2の正規表現を表現する第2のグラフにアクセスする動作であって、前記第2のグラフは1つのルートノード、1つまたは複数の中間ノード、および1つまたは複数の葉ノードを有し、前記1つまたは複数の中間ノードおよび前記1つまたは複数の葉ノードの各々が、前記第2の正規表現に部分的にマッチする文字パターンを特定し、前記第2のグラフは前記第2の正規表現のマッチ状態としてラベルが付された1つまたは複数の終端ノードを有する、動作と、前記1つまたは複数のキーワードグラフおよび前記第2のグラフを、前記第1の正規表現および前記第2の正規表現の両方を集合的に表現する有向非循環グラフにマージする動作であって、少なくとも部分的に重複する文字パターンを有する、前記1つまたは複数のキーワードグラフおよび前記第2のグラフ内の任意の同様に配置された中間ノードを特定する動作と、同様に配置され、部分的に重複する文字パターンを有する、前記キーワードグラフ内の任意の特定された中間ノードおよび前記第2のグラフ内の任意の特定された中間ノードに対して、少なくとも1つの前記特定された中間ノードの前記文字パターンを変更して前記部分的に重複する文字パターンを削除する動作と、前記キーワードグラフと前記第2のグラフとの間にエッジを追加して、前記少なくとも1つの前記特定された中間ノードの前記文字パターンの変更を補償する動作と、同様に配置され、完全に重複する文字パターンを有する、前記キーワードグラフ内の任意の特定された中間ノードおよび前記第2のグラフ内の任意の特定された中間ノードに対して、前記キーワードグラフおよび前記第2のグラフを、前記キーワードグラフ内の前記中間ノードおよび前記第2のグラフ内の前記中間ノードを前記完全に重複する文字パターンを表現する単一のノードへと結合することによって結合する動作と、を含む、動作と、を含むことを特徴とする方法。本発明は、正規表現を分解しマージするための方法、システム、およびコンピュータプログラム製品に関する。1つまたは複数のキーワードグラフにアクセスする。1つまたは複数のキーワードグラフは第1の正規表現を分解したものである。1つまたは複数のキーワードグラフの各々は、1つのルートノード、1つまたは複数の中間ノード、および1つの葉ノードを有する。1つまたは複数の中間ノードの各々および葉ノードが、第1の正規表現に部分的にマッチする文字パターンを特定する。ルートノードおよび1つまたは複数の中間ノードの各々は、単一の子ノードを有する。中間ノードの1つは、葉ノードを子ノードとして有する。各葉ノードは、第1の正規表現のマッチ状態としてラベルが付される。第2のグラフにアクセスする。第2のグラフは、第2の正規表現を表現する。第2のグラフは、1つのルートノード、1つまたは複数の中間ノード、および1つまたは複数の葉ノードを有する。1つまたは複数の中間ノードおよび1つまたは複数の葉ノードの各々が、第2の正規表現に部分的にマッチする文字パターンを特定する。第2のグラフは、第2の正規表現のマッチ状態としてラベルが付された1つまたは複数の終端ノードを有する。1つまたは複数のキーワードグラフおよび第2のグラフを、第1の正規表現および第2の正規表現の両方を集合的に表現する有向非循環グラフにマージする。マージには、少なくとも部分的に重複する文字パターンを有する、1つまたは複数のキーワードグラフおよび第2のグラフ内の任意の同様に配置された中間ノードを特定することを含む。部分的に重複する文字パターンを有する任意の特定された中間ノードに対して、少なくとも1つの特定された中間ノードの文字パターンを変更して、部分的に重複する文字パターンを排除する。キーワードグラフと第2のグラフとの間にエッジを追加して、少なくとも1つの特定された中間ノードの文字パターンの変更に対して補償する。完全に重複する文字パターンを有する任意の特定された中間ノードに対して、キーワードグラフ内の中間ノードおよび第2のグラフ内の中間ノードを、完全に重複する文字パターンを表現する単一のノードへと結合する。本発明の諸実施形態が、特殊目的または汎用目的のコンピュータを備えるかまたは利用してもよい。当該コンピュータには、下記でさらに詳細に論ずるように、例えば1つまたは複数のプロセッサおよびシステムメモリのようなコンピュータハードウェアが含まれる。本発明の範囲内の諸実施形態はまた、コンピュータ実行可能命令および/またはデータ構造を伝送または格納するための物理的なおよび他のコンピュータ読取可能媒体を備える。かかるコンピュータ読取可能媒体は、汎用目的または特殊目的のコンピュータシステムがアクセスできる任意の利用可能な媒体であってよい。コンピュータ実行可能命令を格納するコンピュータ読取可能媒体は、コンピュータ記憶媒体装置である。コンピュータ実行可能命令を伝送するコンピュータ読取可能媒体は、送信媒体である。したがって、限定ではなく例として、本発明の諸実施形態は、少なくとも2つの明らかに相違なる種類のコンピュータ読取可能媒体、即ち、コンピュータ記憶媒体装置および送信媒体を備えることができる。コンピュータ記憶媒体装置には、RAM、ROM、EEPROM、CD-ROMもしくは他の光ディスク記憶装置、磁気ディスク記憶装置もしくは他の磁気記憶装置、または、コンピュータ実行可能命令またはデータ構造の形で所望のプログラムコード手段を格納するのに使用でき、汎用目的または特殊目的のコンピュータがアクセスできる他の任意の媒体が含まれる。ネットワークは、コンピュータシステムおよび/またはモジュールおよび/または他の電子装置間で電子データの送信を可能とする1つまたは複数のデータリンクとして定義される。情報がネットワークまたは別の通信接続ハードワイヤード、無線、またはハードワイヤードもしくは無線の組合せのいずれかを介してコンピュータに転送または提供されるとき、当該コンピュータは当該接続を正しく送信媒体とみなす。送信媒体には、コンピュータ実行可能命令またはデータ構造の形で所望のプログラムコード手段を伝送するのに使用でき汎用目的または特殊目的のコンピュータがアクセスできる、ネットワークおよび/またはデータリンクを含めることができる。上記を組み合わせたものも、コンピュータ読取可能媒体の範囲に含まれるべきである。さらに、様々なコンピュータシステムのコンポーネントに到達すると、コンピュータ実行可能命令またはデータ構造の形のプログラムコード手段を送信媒体からコンピュータ記憶媒体装置に自動的に転送することができる逆も可能。例えば、ネットワークまたはデータリンクを介して受信したコンピュータ実行可能命令またはデータ構造を、ネットワークインタフェースモジュール例えば、NIC内のRAMにバッファし、最終的にコンピュータシステムのRAMおよび/またはコンピュータシステムにある揮発性の低いコンピュータ記憶媒体装置に転送することができる。したがって、コンピュータ記憶媒体装置を、追加的にまたは主に送信媒体を利用するコンピュータシステムのコンポーネントに含めることができることは理解されよう。コンピュータ実行可能命令は、例えば、プロセッサで実行されたときに汎用目的のコンピュータ、特殊目的のコンピュータ、または特殊目的の処理装置に一定の機能または機能群を実行させる命令およびデータを備える。コンピュータ実行可能命令は、例えばバイナリ、アセンブリ言語のような中間形式の命令、または、ソースコードであってもよい。本発明を構造的特徴および/または方法論的動作に固有な言葉で説明したが、添付の特許請求の範囲で定義した本発明は必ずしも説明した特徴または上述の動作に限定されないことは理解されよう。むしろ、説明した特徴および動作は諸請求項を実装する例示的な形態として開示されている。本発明を多種類のコンピュータシステム構成を有するネットワークコンピューティング環境で実践してもよいことは、当業者には理解されよう。当該構成には、パーソナルコンピュータ、デスクトップコンピュータ、ラップトップコンピュータ、メッセージプロセッサ、ハンドヘルド装置、マルチプロセッサシステム、マイクロプロセッサベースのまたはプログラム可能な家庭用電化製品、ネットワークPC、ミニコンピュータ、メインフレームコンピュータ、携帯電話、PDA、ページャ、ルータ、スイッチ、等が含まれる。本発明を分散システム環境で実践してもよい。この場合、ローカルおよびリモートのコンピュータシステムが、ハードワイヤードのデータリンク、無線データリンクによって、またはハードワイヤードのデータリンクおよび無線データリンクの組合せによってネットワークを介して接続され、両方ともタスクを実施する。分散システム環境では、プログラムモジュールをローカルおよびリモートの両方のメモリ記憶装置に配置してもよい。本明細書および添付の特許請求の範囲においては、正規表現とは、例えば特定の文字、単語、または文字パターンのようなテキスト文字列にマッチするよう用いられる構造体である。幾つかの実施形態では、正規表現は有限のアルファベットを有する。正規表現は、正規表現プロセッサにより解釈できる形式言語で記述することができる。正規表現プロセッサは、構文解析器生成器としての役割を果たすか、または、テキストを調べて所与の正規表現にマッチするテキストの部分を特定する。一般に、グラフを用いて正規表現およびそのマッチ状態を表現することができる。例えば、図2を簡単に参照すると、グラフ201が正規表現\d\d|ab|cを表現している。同様に、図4を簡単に参照すると、グラフ401が正規表現[a,b,c]x|\dcd|[1,3,5][a,c,d]|eaを表現している。グラフを、入力テキストで状態機械を実行することにより実行することができ、これによりグラフの並列化が可能になる。図1は、正規表現の分解およびマージを容易にする例示的なコンピュータアーキテクチャ100を示す。図1を参照すると、コンピュータアーキテクチャ100は、分解モジュール101、ラベリングモジュール102、およびマージモジュール141を備える。図示したコンポーネントの各々を、例えばLANLocalAreaNetwork、WANWideAreaNetwork、およびインターネットのようなネットワークまたはその一部を介して互いに接続することができる。したがって、図示したコメントならびに他の任意の接続されたコンピュータシステムおよびそのコンポーネントが、ネットワークを介してメッセージ関連データ例えば、IPInternetProtocolデータグラム、および、TCPTransmissionControlProtocol、HTTPHypertextTransferProtocol、SMTPSimpleMailTransferProtocol、等のような、IPデータグラムを利用する他の上位層プロトコルを作成し交換することができる。一般に、分解を用いて、正規表現を表現する1組の単純なグラフを、当該正規表現を表現するより複雑なグラフから生成することができる。したがって、分解モジュール101は、例えば正規表現を表現するグラフのようなグラフを、対応する複数のキーワードグラフに分解するように構成される。分解モジュール101は、基本的には、より複雑な正規表現の選択的な部分disjunctiveportionを除去して、当該より複雑な正規表現を複数のより単純な正規表現に分解することができる。各キーワードグラフの葉ノードは、より複雑なグラフの最終状態当該より複雑なグラフ内の中間ノードまたは葉ノードにおけるものであってもよいを表現する。分解モジュール101は、ラベル付きグラフまたはラベルなしグラフを分解することができる。ラベリングモジュール102は、グラフまたはキーワードグラフのノードにラベルを付して、表現された正規表現のマッチ状態を示すように構成される。ラベリングモジュール102は、分解の前または後で、ノードにラベルを付すことができる。再度図2を参照すると、図2は、正規表現を表現するグラフを分解する例を示す。図示したように、分解モジュール101はグラフ201を入力として受け取る。グラフ201には、正規表現\d\d|ab|cのマッチ状態を示すために予めラベルを付してある斜線の網掛けで表す。分解モジュール101は、グラフ201を分解してキーワードグラフ202を出力する。グラフ201内のラベルはキーワードグラフ202に受け継がれる。したがって、テキストをグラフ201、または、キーワードグラフ202の何れかと比較これらに対して実行すると、任意のマッチが\d\d|ab|cに対するマッチとして示される。再度図4を参照すると、図4は、正規表現を表現するグラフを分解する別の例を示す。図示したように、分解モジュール101はグラフ401を入力として受け取る。グラフ401には、正規表現[a,b,c]x|\dcd|[1,3,5][a,c,d]|eaのマッチ状態を示すために予めラベルを付してある斜線の網掛けで表す。分解モジュール101は、グラフ401を分解してキーワードグラフ402を出力する。グラフ401内のラベルはキーワードグラフ402に受け継がれる。したがって、テキストをグラフ401、または、キーワードグラフ402の何れかと比較これらに対して実行すると、任意のマッチが[a,b,c]x|\dcd|[1,3,5][a,c,d]|eaに対するマッチとして示される。幾つかの実施形態では、グラフは以下のアルゴリズムに従ってキーワードグラフに分解される。ルートノードから開始する。ルートノードの全ての子ノードを特定する。これらのノードごとに、a.当該ノードこれをprefix.iと称するより上の親ノードをコピーする。b.当該ノードおよびその部分木をprefix.iの子として追加する。c.現在のノードのルートノードとしての使用を除き、2から再度実行する。当該アルゴリズムにより、当該グラフを表現するキーワードグラフの集合例えば、DAGを生成することができる。各キーワードグラフは、葉ノードである単一の終端ノードを有する。各グラフにおいて、各ノードは単一の子ノードを有する。一般に、マージを使用して、正規表現の集合を表現する単一の有向非循環グラフDAGを生成することができる。したがって、マージモジュール101は、2つのグラフを入力として受け取って、当該2つのグラフを、2つの入力グラフのマッチ状態を集合的に表現する単一のDAGにマージするように構成される。処理の冗長性を排除するために、マージモジュール101は、2つの入力グラフ内の同様に配置されたノードにある重複する文字パターンを、単一のDAG内の単一のノードへと結合することができる。文字パターンが部分的に重複するとき、マージモジュール101は一方の入力グラフ内のノードにある当該文字パターンを変更することができる。マージモジュール101は次いで、当該ノードともう一方の入力グラフ内の対応するノードとの間に追加のエッジを加えることにより、補償することができる。追加のエッジを加えることで、2つの入力グラフと単一のDAGとの間のマッチ状態における等価性が促進される。幾つかの実施形態では、マージモジュール141が2つのキーワードグラフを単一のDAGにマージする。他の諸実施形態では、マージモジュール141はキーワードグラフおよび別のグラフを単一のDAGにマージする。マージモジュール141の機能を必要に応じて再利用して、数組の大規模なグラフを共にマージすることができる。図3を参照すると、マージモジュール141はキーワードグラフ301例えば、別のグラフから前もって分解したものおよびグラフ302を有向非循環グラフ304にマージする。マージモジュール141はグラフ302およびキーワードグラフ301Aを入力として利用する。マージモジュール141はグラフ302およびキーワードグラフ301Aを中間グラフ303にマージする。続いて、マージモジュール141は中間グラフ330およびキーワードグラフ301Bを利用する。マージモジュール141は中間グラフ303およびキーワードグラフ301Bを有向非循環グラフ304にマージする。文字パターンのノード312および313が重複するので、ノード312および313は有向非循環グラフ304内の単一のノード314にマージされる。異なる斜線の罫線で示されたラベルは、マージ処理にわたって保持される。したがって、終端ノードはマッチした正規表現を示す。ノード316および317は、正規表現\d\d|umノード316および317がそこから分解された正規表現に対するマッチを示し、ノード318は、正規表現unに対するマッチを示す。図3で示したように、マージモジュール141への入力は外部にある。他の実施形態では、マージモジュール141は1組のグラフを入力として受け取ってDAGを出力する。処理の最中は、中間グラフがマージモジュール141内部で保持され処理される。図示したように、マージモジュール141は位置検出器142、重複検出器143、および重複補償器144を備える。マージ位置にある間は、位置検出器142は、別のグラフにおいて同様に配置されたノードを特定するように構成される。同様に配置されたノードを、ルートノードからの距離に基づいて特定することができる。例えば、図3では、ノード312および313が同様に配置されている。マージの最中は、重複検出器143は、別のノードの文字パターンが少なくとも部分的に重複するかどうかを検出するように構成されている。例えば、文字パターン[1,3,5]は文字パターン\dに部分的にマッチする。他方、文字パターン[a,b,c]および文字パターン[a,b,c]は完全に重複している。マージの最中は、重複補償器144は、部分的に重複する文字パターンを有するノードが単一のノードにマージされるときに補償するように構成されている。補償には、マージされている入力グラフ間にエッジを追加することを含むことができる。追加のエッジにより、入力グラフのマッチ状態と結果のDAGのマッチ状態との間の等価性が促進される。図5は、異なる正規表現を表現するグラフをマージする別の例を示す。キーワードグラフ501およびグラフ502を、入力として例えば、マージモジュール141で受け取ることができる。位置検出器142は、ノード511およびノード512がそれぞれキーワードグラフ501およびグラフ502の中で同様に配置されていることを検出することができる。重複検出器143は、部分的に重複するパターン503または共通エッジを特定することができる。即ち、文字パターン\dは文字パターン[2,3]と部分的に重複する。重複補償器144は、ノード511の文字パターンを\d-[2,3]に変更することによって、この部分的な重複を削除共通エッジを削除することができる。重複補償器はまた、ノード512からノード513へエッジ514を追加することができる。マージモジュール114は次いで、ルートノードを結合して、変更したキーワードグラフ501をグラフ502に追加することができる。重複補償により、マージすべきグラフが、依然として等価なマッチ状態を表現することが可能になる。例えば、テキスト文字列2cdは、比較がノード512で行われてノード511が回避されている場合でも、依然としてキーワードグラフ501にマッチする。図示したように、終端ノード内部の異なる罫線が、それぞれキーワードグラフ501およびグラフ502のマッチ状態を示す。幾つかの実施形態では、グラフは以下のアルゴリズムに従ってマージされる。ルートノードのみを有する空のDAGを作成し、これにFinal.DAGとしてラベルを付す。集合内のDAGi.DAGごとに、以下を行う。a.i.ノードをi.DAGのルートノードに設定する。b.final.ノードをFinal.DAGのルートノードに設定する。c.final.ノードが厳密に同一のエッジを有する限り、i.ノードからfinal.ノードまで繰り返す。d.i.ノードのエッジがfinal.ノードのエッジのスーパーセットである場合は、i.i.ノードとfinal.ノードとの間の共通でない文字を表現するエッジを追加する。このエッジはi.ノードの子を指す。ii.共通のエッジ、ノードごとに1.final.ノードおよびi.ノードが厳密に同一のエッジを有する限り、それらについて繰り返す。2.終端ノードに到達した場合は、それにi.DAGの終端としてラベルを付す。3.そうでない場合は、final.ノードからi.ノードの子へのエッジを追加する。e.final.ノードのエッジがi.ノードのエッジのスーパーセットである場合は、i.i.ノードとfinal.ノードとの間の共通でない文字を表現するエッジを追加する。このエッジはfinal.ノードの子を指す。ii.共通のエッジ、ノードごとに1.final.ノードおよびi.ノードが厳密に同一のエッジを有する限り、それらについて繰り返す。2.終端ノードに到達した場合は、それにfinal.DAGの終端としてラベルを付す。3.そうでない場合は、i.ノードからfinal.ノードの子へのエッジを追加する。図6A、図6Bは、正規表現を分解しマージするための例示的な方法600の流れ図を示す。方法600を、コンピュータアーキテクチャ100のコンポーネントおよびデータに関して、かつ、図3および図5を一部参照して、説明する。方法600は、第1の正規表現を表現するグラフにアクセスする動作を含む動作601。例えば、分解モジュール101は、正規表現111を表現するグラフ112にアクセスすることができる。方法600は、グラフを1つまたは複数のキーワードグラフに分解する動作を含む。1つまたは複数のキーワードグラフの各々は、1つのルートノード、1つまたは複数の中間ノード、および1つの葉ノードを有し、1つまたは複数の中間ノードの各々および葉ノードは、第1の正規表現に部分的にマッチする文字パターンを特定し、ルートノードおよび1つまたは複数の中間ノードの各々は、単一の子ノードを有し、中間ノードの1つは、葉ノードを子ノードとして有する動作602。例えば、分解モジュール101は、グラフ112をキーワードグラフ113例えば、113A、113B、113C、等に分解することができる。方法600は、1つまたは複数のキーワードグラフの各々の葉ノードに、第1の正規表現のマッチ状態としてラベルを付す動作を含む動作603。例えば、ラベリングモジュール102は、キーワードグラフ113の葉ノードにラベルを付して、ラベル付きのキーワードグラフ113AL、113BL、113BL、等を生成することができる。方法600は、第2の正規表現を表現する第2のグラフにアクセスする動作を含む。第2のグラフは、1つのルートノード、1つまたは複数の中間ノード、および1つまたは複数の葉ノードを有し、1つまたは複数の中間ノードおよび1つまたは複数の葉ノードの各々は、第2の正規表現に部分的にマッチする文字パターンを特定する動作604。例えば、ラベリングモジュール102は、正規表現121を表現するグラフ123にアクセスすることができる。方法600は、第2のグラフ内の1つまたは複数の終端ノードに、第2の正規表現のマッチ状態としてラベルを付す動作を含む動作605。例えば、ラベリングモジュール102は、グラフ123の終端ノードにラベルを付して、ラベル付きのグラフ123Lを生成することができる。方法600は、1つまたは複数のキーワードグラフおよび第2のグラフを、第1の正規表現および第2の正規表現の両方を集合的に表現する有向非循環グラフにマージする動作を含む動作606。例えば、マージモジュール141は、ラベル付きキーワードグラフ113Lおよびラベル付きグラフ123Lを有向非循環グラフ134にマージすることができる。有向非循環グラフ134は、正規表現111および正規表現121を集合的に表現する。動作606は、少なくとも部分的に重複する文字パターンを有する、1つまたは複数のキーワードグラフおよび第2のグラフ内の任意の同様に配置された中間ノードを特定する動作の動作を含む動作607。例えば、位置検出器142は、もう1つのラベル付きキーワードグラフ113Lおよびラベル付きグラフ123L内の同様に配置された中間ノードを特定することができる。同様に配置されたノードは、そのルートノードから等距離のノードであることができる。例えば、図3を参照すると、ノード312および313は同様に配置されている両方とも、その対応するルートノードから1つのエッジのところにある。同様に、図5では、ノード511および512が同様に配置されている。ノード513および514も図5において同様に配置されている。同様に配置された中間ノードにおいて、重複検出器143は、ノードが少なくとも部分的に重複する文字パターンを有する場合を検出することができる。図3では、ノード312および313は完全に重複している。図5では、ノード511および512が部分的に重複し、ノード513および514は重複していない。同様に配置され、部分的に重複する文字パターンを有する、キーワードグラフ内の任意の特定された中間ノードおよび第2のグラフ内の任意の特定された中間ノードに対して、動作606は、少なくとも1つの特定された中間ノードの文字パターンを変更して、部分的に重複する文字パターンを排除する動作を含む動作608。例えば、重複補償器144は、中間ノードにおける文字パターンを変更して別のノードとの部分的な重複を排除することができる。図5を参照すると、ノード511にある文字パターン\dを[0,1,4,5,6,7,8,9]と等価である\d-[2,3]に変更してノード512との部分的な重複を排除することができる。同様に配置され、部分的に重複する文字パターンを有する、キーワードグラフ内の任意の特定された中間ノードおよび第2のグラフ内の任意の特定された中間ノードに対して、動作606は、キーワードグラフと第2のグラフとの間にエッジを追加して、少なくとも1つの特定された中間ノードの文字パターンの変更を補償する動作を含む動作609。例えば、重複補償器144は、変更されていないノードから変更されたノードより下のノードへエッジを追加して、変更されたノードの文字パターンの変更を補償することができる。図5を参照すると、エッジ514をノード512からノード513に追加して、ノード511の文字パターンの変更を補償することができる。同様に配置され、完全に重複する文字パターンを有する、キーワードグラフ内の任意の特定された中間ノードおよび第2のグラフ内の任意の特定された中間ノードに対して、動作606は、キーワードグラフおよび第2のグラフを、キーワードグラフ内の中間ノードおよび第2のグラフ内の中間ノードを完全に重複する文字パターンを表現する単一のノードへと結合することによって結合する動作を含む動作610。例えば、重複補償器144は、ラベル付きのキーワードグラフ113Lの中間ノードおよびラベル付きのグラフ123Lの中間ノードを結合することができる。図3を参照すると、ノード312およびノード313をノード314に結合することができる。DAGの作成に続いて、DAGを状態機械上でテキストの一部に対して実行して、テキストの一部がDAGで表現した任意の正規表現にマッチするかどうかを判定することができる。幾つかの実施形態では、マージグラフを正規表現の他のパスと結合して、拡張正規表現構文例えば、、、または数字集合を容易にする。例えば、DAGを構築して正規表現を表現するとき、正規表現の全体をDAGによって表現できないこともありうる。例えば、正規表現は、:のような文字、または入れ子の演算子を含みうる。さらに複雑な状態機械を構築してこれらの種類の演算子を扱うことができる。別の代替手段は、実際の正規表現とモノリシックなDAGを含む複数のテキストプロセッサを作成することである。次いで以下のアルゴリズムを使用して正規表現をマージすることができる。即ち、正規表現を、複雑なDAGとして表現できるコンポーネントおよび複雑なDAGとして表現できないコンポーネントに分解する。a.123\d\d\d5.3\d\d\d\dを考える。b.これにより、以下のコンポーネントを生成することができる。即ち、i.DAG:123\d\d\d|\d\d\d\dii.正規表現:5.3正規表現および単一のDAGに対して全てのテキストプロセッサを実行する。これらのテキストプロセッサが見つかったテキスト内の位置DAG/Regexにより保証されるように、既にソートされているを収集する。元の正規表現を、DAGおよびその正規表現の結果に基づいて再構築し、それが発見されたかどうかを判定する。ステップ3の結果がヒープ集合例えば、フィボナッチヒープに格納されている場合は、このステップはOnで束縛される。したがって、生成されたDAGを正規表現エンジンとともに使用して、正規表現のアルファベット全体について結果を生成することができる。マルチパスのアプローチにより、インプレースの後方トラッキングまたは前方トラッキングのない先読みまたは後読みの正規表現を実行することができ、これによりシステムの複雑度を軽減し、性能を支援する。したがって、本発明の諸実施形態では、正規表現を複数の単純なキーワードグラフに分解し、これらのキーワードグラフを単純かつ効率的にマージし、簡略化された正規表現のアルファベットを実行できる有向非循環グラフDAGを生成する。これらの正規表現のDAGの幾つかを共にマージして、正規表現の集合全体を表現する単一のDAGを生成することができる。他のテキスト処理アルゴリズムおよびヒープ集合に従うDAGを、マルチパスのアプローチで結合して正規表現のアルファベットを拡張することができる。本発明を、その趣旨または本質的な特徴から逸脱しない他の特定の形で具体化してもよい。説明した諸実施形態は、全ての点において限定ではなく例として考えるべきである。したがって、本発明の範囲は、以上の記載ではなく添付の特許請求の範囲により示される。特許請求の範囲の意味および均等の範囲にある全ての変更は、その範囲に含まれるべきである。"