【手続補正書】
【提出日】平成26年10月17日(2014.10.17)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
１つまたは複数のプロセッサおよびシステム・メモリを含むコンピュータ・システムにおいて、有向非循環グラフで１つまたは複数の正規表現を表現する方法であって、
第１の正規表現から分解された１つまたは複数のキーワード・グラフにアクセスする動作であって、１つまたは複数のキーワード・グラフの各々はルート・ノード、１つまたは複数の中間ノード、および葉ノードを有し、前記１つまたは複数の中間ノードの各々および前記葉ノードが、前記第１の正規表現に部分的にマッチする文字パターンを特定し、前記ルート・ノードおよび前記１つまたは複数の中間ノードの各々は単一の対応する子ノードを有し、前記中間ノードの１つは前記葉ノードを前記対応する子ノードとして有し、各前記葉ノードは前記第１の正規表現のマッチ状態としてラベルが付される、動作と、
第２の正規表現の少なくとも一部を表現する第２のグラフにアクセスする動作であって、前記第２のグラフはルート・ノード、１つまたは複数の中間ノード、および１つまたは複数の葉ノードを有し、前記１つまたは複数の中間ノードおよび前記１つまたは複数の葉ノードの各々が、前記第２の正規表現に部分的にマッチする文字パターンを特定する、動作と、
前記１つまたは複数のキーワード・グラフおよび前記第２のグラフを、前記第１の正規表現および前記第２の正規表現の両方を集合的に表現する有向非循環グラフにマージする動作であって、
少なくとも部分的に重複する文字パターンを有する、前記１つまたは複数のキーワード・グラフおよび前記第２のグラフ内の任意の同様に配置された中間ノードを特定する動作と、
同様に配置され、部分的にのみ重複する文字パターンを有する、前記選択されたキーワード・グラフ内の任意の特定された中間ノードおよび前記第２のグラフ内の任意の特定の中間ノードに対して、
前記部分的に重複する文字パターンを排除するために、前記特定された中間ノードのうちの少なくとも１つの中間ノードの文字パターンを変更する動作と、
前記特定された中間ノードのうちの前記少なくとも１つの中間ノードの前記文字パターンの変更に対して補償をするために、前記キーワード・グラフと前記第２のグラフとの間にエッジを追加する動作と、
同様に配置され、完全に重複する文字パターンを有する、キーワード・グラフ内の任意の特定された中間ノードおよび前記第２のグラフ内の特定された中間ノードに対して、
前記キーワード・グラフ内の中間ノードおよび前記第２のグラフ内の中間ノードを前記完全に重複する文字パターンを表現する単一のノードへと結合することにより、前記キーワード・グラフおよび前記第２のグラフを結合する動作と
を含む、動作と
を含むことを特徴とする方法。
【請求項２】
少なくとも部分的に重複する文字パターンを有する、前記選択されたキーワード・グラフおよび前記第２のグラフ内の任意の同様に配置された中間ノードを特定する前記動作は、完全に重複する、前記選択されたキーワード・グラフ内の中間ノードおよび前記第２のグラフ内の中間ノードを特定する動作を含むことを特徴とする請求項１に記載の方法。
【請求項３】
少なくとも部分的に重複する文字パターンを有する、前記選択されたキーワード・グラフおよび前記第２のグラフ内の任意の同様に配置された中間ノードを特定する前記動作は、部分的に重複する、前記選択されたキーワード・グラフ内の中間ノードおよび前記第２のグラフ内の中間ノードを特定する動作を含むことを特徴とする請求項１に記載の方法。
【請求項４】
前記第１の正規表現を表現する第１のグラフにアクセスする動作と、
前記第１のグラフを前記１つまたは複数のキーワード・グラフへと分解する動作と
をさらに含むことを特徴とする請求項１に記載の方法。
【請求項５】
前記１つまたは複数のキーワード・グラフのうちの各々のキーワード・グラフの前記葉ノードを、前記第１の正規表現に対するマッチ状態としてラベル付けする動作をさらに含むことを特徴とする請求項４に記載の方法。
【請求項６】
前記第２のグラフ内の各終端ノードを前記第２の正規表現に対するマッチ状態としてラベル付けする動作をさらに含み、前記終端ノードは前記１つまたは複数の中間ノートおよび前記１つまたは複数の葉ノードの中から選択されることを特徴とする請求項１に記載の方法。
【請求項７】
前記有向非循環グラフをテキストの一部に対して状態機械として実行して、前記テキストの一部が、前記第１の正規表現および前記第２の正規表現のうちの１つまたは複数にマッチするかどうかを判定する動作をさらに含むことを特徴とする請求項１に記載の方法。
【請求項８】
前記第２のグラフは前記第２の正規表現から分解されたキーワード・グラフであることを特徴とする請求項１に記載の方法。
【請求項９】
コンピュータ・システムで使用するためのコンピュータ・プログラム製品であって、前記コンピュータ・プログラム製品は、有向非循環グラフで１つまたは複数の正規表現を表現するための方法を実装するものであり、前記コンピュータ・プログラム製品は、コンピュータ実行可能命令を格納した１つまたは複数のコンピュータ・ハードウェア記憶装置を備え、当該コンピュータ実行可能命令は、プロセッサで実行されると、前記コンピュータ・システムに、
第１の正規表現から分解された１つまたは複数のキーワード・グラフにアクセスするステップであって、前記１つまたは複数のキーワード・グラフの各々はルート・ノード、１つまたは複数の中間ノード、および葉ノードを有し、前記１つまたは複数の中間ノードの各々および前記葉ノードが、前記第１の正規表現に部分的にマッチする文字パターンを特定し、前記ルート・ノードおよび前記１つまたは複数の中間ノードの各々は単一の対応する子ノードを有し、前記中間ノードの１つは前記葉ノードを前記対応する子ノードとして有し、各前記葉ノードは前記第１の正規表現のマッチ状態としてラベルが付される、ステップと、
第２の正規表現を表現する第２のグラフにアクセスするステップであって、前記第２のグラフはルート・ノード、１つまたは複数の中間ノード、および１つまたは複数の葉ノードを有し、前記１つまたは複数の中間ノードおよび前記１つまたは複数の葉ノードの各々が、前記第２の正規表現に部分的にマッチする文字パターンを特定する、ステップと、
前記１つまたは複数のキーワード・グラフおよび前記第２のグラフを、前記第１の正規表現および前記第２の正規表現の両方を集合的に表現する有向非循環グラフにマージするステップであって、
少なくとも部分的に重複する文字パターンを有する、前記１つまたは複数のキーワード・グラフおよび前記第２のグラフ内の任意の同様に配置された中間ノードを特定するステップと、
同様に配置され、部分的にのみ重複する文字パターンを有する、キーワード・グラフ内の任意の特定された中間ノードおよび前記第２のグラフ内の任意の特定された中間ノードに対して、
前記部分的に重複する文字パターンを排除するために、前記特定された中間ノードのうちの少なくとも１つの中間ノードの文字パターンを変更するステップと、
前記特定された中間ノードのうちの前記少なくとも１つの中間ノードの前記文字パターンの変更に対して補償をするために、前記キーワード・グラフと前記第２のグラフとの間にエッジを追加するステップと、
同様に配置され、完全に重複する文字パターンを有する、キーワード・グラフ内の任意の特定された中間ノードおよび前記第２のグラフ内の特定された中間ノードに対して、
前記キーワード・グラフ内の中間ノードおよび前記第２のグラフ内の中間ノードを前記完全に重複する文字パターンを表現する単一のノードへと結合することにより、前記キーワード・グラフおよび前記第２のグラフを結合するステップと
を含む、ステップと、
を含む前記方法を実施させることを特徴とするコンピュータ・プログラム製品。
【請求項１０】
実行されると、前記コンピュータ・システムに、少なくとも部分的に重複する文字パターンを有する、前記１つまたは複数のキーワード・グラフおよび前記第２のグラフ内の任意の同様に配置された中間ノードを特定させるコンピューター実行可能命令は、実行されると、前記コンピュータ・システムに、完全に重複する、キーワード・グラフ内の中間ノードおよび前記第２のグラフ内の中間ノードを特定させるコンピュータ実行可能命令を含むことを特徴とする請求項９に記載のコンピュータ・プログラム製品。
【請求項１１】
実行されると、前記コンピュータ・システムに、少なくとも部分的に重複する文字パターンを有する、前記１つまたは複数のキーワード・グラフおよび前記第２のグラフ内の任意の同様に配置された中間ノードを特定させるコンピューター実行可能命令は、実行されると、前記コンピュータ・システムに、部分的に重複する、キーワード・グラフ内の中間ノードおよび前記第２のグラフ内の中間ノードを特定させるコンピュータ実行可能命令を含むことを特徴とする請求項９に記載のコンピュータ・プログラム製品。
【請求項１２】
実行されると、前記コンピュータ・システムに、前記１つまたは複数のキーワード・グラフのうちの各々のキーワード・グラフの前記葉ノードを、前記第１の正規表現に対するマッチ状態としてラベル付けさせるコンピュータ実行可能命令をさらに含むことを特徴とする請求項９に記載のコンピュータ・プログラム製品。
【請求項１３】
実行されると、前記コンピュータ・システムに、前記第２のグラフ内の各終端ノードを前記第２の正規表現に対するマッチ状態としてラベル付けさせるコンピュータ実行可能命令をさらに含むことを特徴とする請求項９に記載のコンピュータ・プログラム製品。
【請求項１４】
コンピュータ・システムであって、
１つまたは複数のプロセッサと、
システム・メモリと
を備え、前記システム・メモリは、前記１つまたは複数のプロセッサで実行されると、前記コンピュータ・システムに、有向非循環グラフで１つまたは複数の正規表現を表現する方法を実行させるコンピュータ実行可能命令を格納し、前記方法は、、
第１の正規表現から分解された１つまたは複数のキーワード・グラフにアクセスする動作であって、１つまたは複数のキーワード・グラフの各々はルート・ノード、１つまたは複数の中間ノード、および葉ノードを有し、前記１つまたは複数の中間ノードの各々および前記葉ノードが、前記第１の正規表現に部分的にマッチする文字パターンを特定し、前記ルート・ノードおよび前記１つまたは複数の中間ノードの各々は単一の対応する子ノードを有し、前記中間ノードの１つは前記葉ノードを前記対応する子ノードとして有し、各前記葉ノードは前記第１の正規表現のマッチ状態としてラベルが付される、動作と、
第２の正規表現を表現する第２のグラフにアクセスする動作であって、前記第２のグラフはルート・ノード、１つまたは複数の中間ノード、および１つまたは複数の葉ノードを有し、前記１つまたは複数の中間ノードおよび前記１つまたは複数の葉ノードの各々が、前記第２の正規表現に部分的にマッチする文字パターンを特定し、前記第２のグラフは前記第２の正規表現のマッチ状態としてラベルが付された１つまたは複数の終端ノードを有する、動作と、
前記１つまたは複数のキーワード・グラフおよび前記第２のグラフを、前記第１の正規表現および前記第２の正規表現の両方を集合的に表現する有向非循環グラフにマージする動作であって、
少なくとも部分的に重複する文字パターンを有する、前記１つまたは複数のキーワード・グラフおよび前記第２のグラフ内の任意の同様に配置された中間ノードを特定する動作と、
同様に配置され、部分的にのみ重複する文字パターンを有する、キーワード・グラフ内の任意の特定された中間ノードおよび前記第２のグラフ内の任意の特定された中間ノードに対して、
前記特定された中間ノードのうちの少なくとも１つの中間ノードの前記文字パターンを変更して前記部分的に重複する文字パターンを削除する動作と、
前記キーワード・グラフと前記第２のグラフとの間にエッジを追加して、前記特定された中間ノードのうちの前記少なくとも１つの中間ノードの前記文字パターンの変更を補償する動作と、
同様に配置され、完全に重複する文字パターンを有する、キーワード・グラフ内の任意の特定された中間ノードおよび前記第２のグラフ内の任意の特定された中間ノードに対して、
前記キーワード・グラフ内の前記中間ノードおよび前記第２のグラフ内の前記中間ノードを前記完全に重複する文字パターンを表現する単一のノードへと結合することによって、前記キーワード・グラフおよび前記第２のグラフを結合する動作と、
を含む、動作と、
を含むことを特徴とするコンピュータ・システム。