(57)【要約】  任意または未知のシステムまたはアプリケーションから異種ログを取り込むことと、一意的なログメッセージのそれぞれについて１つのパターンを生成することと、類似性メトリクスに基づいてパターンをグループ化することによってパターン階層ツリーを構築し、それぞれのグループについてそのグループを構成する全てのパターンを結合することによって１つのパターンを生成することと、パターン階層ツリーからパターンのセットを選択することとによって、任意または未知のシステムまたはアプリケーションからのログを構文解析するシステムおよび方法を開示する。
2019502196.tif 000002
【特許請求の範囲】
【請求項１】
任意または未知のシステムまたはアプリケーションからのログを構文解析する方法であって、
前記任意または未知のシステムまたはアプリケーションから異種ログを取り込むことと、
一意的なログメッセージのそれぞれについて１つのパターンを生成することと、
類似性メトリクスに基づいてパターンをグループ化することによってパターン階層ツリーを構築し、それぞれのグループについて、そのグループを構成する全てのパターンを結合することによって１つのパターンを生成することと、
前記パターン階層ツリーからパターンのセットを選択することとを含む、方法。
【請求項２】
ログが、１つまたは複数のフィールドを有する非構造化テキストコンテンツを含む、請求項１に記載の方法。それらは、タイムスタンプも含む可能性がある。
【請求項３】
前記パターンツリーが、ワイルドカードがないリーフレベルのパターンを含む、請求項１に記載の方法。
【請求項４】
前記パターンツリーが、ワイルドカードがある、またはワイルドカードがない、上位レベルのパターンを含む、請求項１に記載の方法。
【請求項５】
トークン化を実行して、意味論的に意味のあるトークンをログから生成することを含む、請求項１に記載の方法。
【請求項６】
区切り文字のセットに基づいて各入来ログを分割し、日付、時間、インターネットアドレスを含む既定のデータタイプのセットを検出することと、フィールドをデータタイプで置換することとを含む、請求項１に記載の方法。
【請求項７】
全ての一意的なコンパクトシグネチャについて指標を維持することによって、コンパクトシグネチャの一意性を決定することを含む、請求項１に記載の方法。
【請求項８】
各指標入力が、コンパクトシグネチャを鍵として含み、関連するメタデータを値として含み、メタデータが、ログトークンおよびカウンタを含み、前記方法が、前記トークンからログのパターンを生成することを含む、請求項７に記載の方法。
【請求項９】
処理対象の新たなログのそれぞれについて、前記新たなログを代表ログのセットと比較することと、所定値以下の前記新たなログまでの類似性距離を有する１つの代表ログを決定することとを含む、請求項１に記載の方法。
【請求項１０】
前記類似性距離が前記所定値を超える場合にアーリーアバンダニングを実行することを含む、請求項９に記載の方法。
【請求項１１】
【数１】
2019502196.tif 000007
を決定することを含み、
ここで、Ｐｉが、ログＰのｉ番目のトークンであり、ｌｅｎ（Ｐ）が、ログＰのトークン数であり、Ｑｉが、ログＱのｉ番目のトークンであり、ｌｅｎ（Ｑ）が、ログＱのトークン数であり、ｋ１が、調整可能なパラメータであり、デフォルト距離関数ではｋ１＝１である、請求項１に記載の方法。
【請求項１２】
２つのログを、前記２つのログの最良のアラインメントを決定することによってマージすることを含む、請求項１に記載の方法。
【請求項１３】
前記パターン階層ツリーが、クラスタ化およびパターン認識を使用して作成される、請求項１に記載の方法。
【請求項１４】
【数２】
2019502196.tif 000008
を決定することを含み、
ここで、Ｓｉｚｅｉが、クラスタｉのログ数であり、ＷＣｉ、Ｖａｒｉ、およびＦＶｉが、それぞれクラスタｉのパターン中のワイルドカードの数、変数トークンの数、固定値トークンの数であり、ａ１、ａ２、およびａ３が、調整可能なパラメータである、請求項１に記載の方法。
【請求項１５】
コスト推定式を適用して、ユーザの好みに基づいてパターンのセットを選択することを含む、請求項１に記載の方法。
【請求項１６】
最終的なパターンのセットとして、ワイルドカードのない最小数のパターンを選択することを含む、請求項１に記載の方法。
【請求項１７】
最終的なパターンとして、パターン数についてのユーザの上限に合致するパターンのセットを選択することを含む、請求項１に記載の方法。
【請求項１８】
全てのログが正しく構文解析されるように、設定された異種ログから正規表現のセットを生成することを含む、請求項１に記載の方法。
【請求項１９】
プロセッサと、
前記プロセッサにデータを提供する、モノのインターネット（ＩｏＴ）のセンサと、
前記プロセッサによって実行されて
任意または未知のシステムまたはアプリケーションから異種ログを取り込み、
一意的なログメッセージのそれぞれについて１つのパターンを生成し、
類似性メトリクスに基づいてパターンをグループ化することによってパターン階層ツリーを構築し、それぞれのグループについてそのグループを構成する全てのパターンを結合することによって１つのパターンを生成し、
前記パターンツリーからパターンのセットを選択する、
コンピュータ可読コードとを含む、システム。
【請求項２０】
全てのログが正しく構文解析されるように、設定された異種ログから正規表現のセットを生成するコードを含む、請求項１９に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本願は、参照によりその内容を本明細書に組み込む、２０１５年１１月１７日出願の仮出願第６２２５６２１２号の優先権を主張するものである。
【０００２】
本発明は、アプリケーション、センサ、または器具のログ解析を行うシステムに関する。
【背景技術】
【０００３】
人間は、自然言語を介してコミュニケーションを取り、機械は、ログメッセージを通して人間および他のデバイスとコミュニケーションを取る。多数のログメッセージが、ソーシャルネットワーク、銀行業務システム、健康管理システム、スマートシティ、ＩｏＴデバイスなどによって毎日生成されている。管理者は、将来の出来事を予測する、異常を検出する、または性能上の問題をデバッグするために、これらのログメッセージを解析することに関心がある。ログを解析するためには、ユーザは、まず、そのログを構文解析して、その内容を理解する必要がある。ログを構文解析する１つの従来の方法は、いくつかの正規表現（ｒｅｇｕｌａｒ  ｅｘｐｒｅｓｓｉｏｎ：ｒｅｇｅｘ）を手作業で作り出すことである。ログは様々なフォーマットを有するので、これは現実には困難である。どれだけの数の独自フォーマットがログに存在するのかは、これまで分かっていない。さらに、ウェブサーバおよびＩｏＴデバイスは、毎日数百万のログを生成する。この速度についていくためには、ログパーサは、何百万ものログを数時間で処理することができなければならない。
【０００４】
従来のシステムは、システムのユーザによって様々なパラメータが設定される必要がある。これらのパラメータの最良の値をユーザが全く知らないこともあるので、これは困難である。さらに、ユーザがこれらのパラメータについて一部の値を設定して、ログ解析器全体を実行させた場合には、ユーザは、最終的なパターンセットに満足できないこともある。このような状況でユーザが有する唯一の選択肢は、それらのパラメータについて異なる値を設定して、パイプライン全体を再度実行させることである。さらに、従来のシステムの低い性能により、各回の実行に長い時間がかかり、したがって、この観点から活用性に柔軟性が得られない。
【発明の概要】
【０００５】
任意または未知のシステムまたはアプリケーションから異種ログを取り込むことと、一意的なログメッセージのそれぞれについて１つのパターンを生成することと、類似性（ｓｉｍｉｌａｒｉｔｙ）メトリクスに基づいてパターンをグループ化することによってパターン階層ツリーを構築し、それぞれのグループについてそのグループを構成する全てのパターンを結合することによって１つのパターンを生成することと、パターン階層ツリーからパターンのセットを選択することとによって、任意または未知のシステムまたはアプリケーションからのログを構文解析するシステムおよび方法を開示する。
【０００６】
このシステムの利点は、以下のうちの１つまたは複数を含む可能性がある。このシステムは、ユーザからのいかなる入力パラメータも必要としない。コンピュータプログラムによって生成されるログ用に特に設計された、高速かつメモリ効率の高いクラスタ化プロセスが提供される。コンピュータプログラムによって生成されるログ用に特に設計された、高速なパターン認識プロセスが提供される。反復プロセスは、クラスタ化アルゴリズムとパターン認識アルゴリズムを組み合わせ、パターンの階層を生成する。この階層から、ユーザは、自分の特定のユースケースに合致するパターンのセットを選択することができる。このシステムは、今日のデバイスによって生成される異種ログソースの異常を自動的に検出する。このシステムは、センサ、コンピュータソフトウェア、またはモノのインターネット（Ｉｎｔｅｒｎｅｔ−ｏｆ  ｔｈｉｎｇｓ）によって生成されるログを処理することができる。このシステムは、いかなる人間の入力または以前の共通パターン基準も必要としない。このシステムは、完全に自動化されており、教師なし機械学習アルゴリズムに依拠して、システム中の任意の異常をユーザに警告する。監視して警告をトリガすることが、大量生産ソフトウェアにおいて問題を迅速に捕捉するための不可欠な「先制攻撃」機構である。さらに、できる限り早く症状の位置を突き止め、その潜在的な原因を突き止めることが重要である。このシステムは、データ解析およびモデルにプラグインすることができ、最新の機械学習技術を使用して、警告を出し、その潜在的な原因を知らせることができるプラットフォームを提供する。このシステムは、構造について事前に知らなくても任意の非修飾ログに対して動作することができる。
【図面の簡単な説明】
【０００７】
【図１】図１は、例示的なパターン発見プロセスを示す図である。
【図２】図２は、例示的な精密パターン生成プロセスの詳細を示す図である。
【図３】図３は、どのようにしてプロセスがログメッセージをトークン化する（ｔｏｋｅｎｉｚｅ）かを示す図である。
【図４】図４は、例示的なパターンツリー構築プロセスの詳細を示す図である。
【図５】図５は、２つのパターンの例示的なマージを示す図である。
【図６】図６は、クラスタ化およびパターン認識を含む反復プロセスを示す図である。
【図７】図７は、例示的なパターンツリーを示す図である。
【図８】図８は、パターン選択プロセスの詳細を示す図である。
【図９】図９は、システムを実行するハードウェアを示す例示的なブロック図である。
【発明を実施するための形態】
【０００８】
図１は、例示的なパターン発見プロセスを示す図である。システムは、全てのログを正しく構文解析することができるように、設定された異種ログから正規表現のセットを効率的に生成するという問題に対処する。本発明では、各正規表現を「パターン」と表現する。
【０００９】
図１を参照すると、１０１で、システムは、異種ログ収集を実行する。このステップでは、任意／未知のシステムまたはアプリケーションから異種ログを取る。ログは、１つまたは複数のフィールドを有する非構造化テキストコンテンツを含む。ログは、タイムスタンプを含むこともある。次に、１０２で、精密パターン生成が行われる。このステップでは、一意的なログメッセージのそれぞれについて１つのパターンを生成する。１０３で、このプロセスは、パターン階層ツリーを構築する。このステップでは、１０２のパターンを類似性メトリクスに基づいてグループ化し、それぞれのグループについて、そのグループを構成する全てのパターンを結合することによって、１つのパターンを生成する。このステップは、小さな類似性距離しきい値から開始して、このしきい値を次第に大きくしていき、複数のパターンをマージすることができるようにする。このステップでは、それぞれの類似性距離しきい値について、パターンのセットを生成し、このパターンのセットを後にマージして、より少ない数のパターンを生成する。このステップは、残りのパターンが１つだけになると終了する。このようにして、このステップでは、パターンツリーを作成する。このツリーでは、リーフレベルは、全ての精密なパターンを含むが、ルートレベルは、１つのパターンしか含まない。全ての中間レベルは、それより下位のレベルの複数のパターンを類似性距離に基づいてマージすることによって構築されたパターンを含む。
【００１０】
次に、１０４で、システムは、パターン選択を実行する。このステップでは、１０３で生成されたパターンツリーから、パターンのセットが選択される。このパターンツリーでは、リーフレベルパターンは、いかなるワイルドカードも含まないが、より上位レベルのパターンは、ワイルドカードを含むことがある。通常は、ワイルドカードは、ログを処理するときに、ある程度の計算オーバヘッドを生じる。さらに、通常は、計算オーバヘッドが減少するので、パターンの数は少ない方がよい。ワイルドカートとパターン数の間に計算オーバヘッドに関する兼ね合いがあることは明らかである。ステップ１０４で、ユーザは、所定の要件を満たすパターンのセットを選択することができる。
【００１１】
この図１のシステムは、完全に新しい手法により、スケーラビリティおよび柔軟性の問題の両方に対処するものである。このシステムは、多くのメモリを消費することなく、はるかに多くのログを短時間で処理し、最終的なパターンのセットにユーザが満足できない場合にも、ユーザは、システム全体を再度実行させる必要がない。さらに、このシステムは、パターンを生成するために、いかなるパラメータも必要としない。
【００１２】
このシステムは、コンピューティングデバイスによって生成されるログの特殊な性質を活用する。このシステムは、ログが、物語の本のような無作為なセンテンスではないものと仮定している。ログは、コンピュータプログラムによって生成される。ログを生成する各アプリケーションソースコードには、いくつかの特定のコード行がある。したがって、それらは全て、特定のフォーマットのセットによって生成される。これは、ソースコード中の同じフォーマットによって生成される全てのログが、互いに非常に類似しているということを意味している。ログの最良のクラスタ化とは、あるパターンに対応する全てのログを同じクラスタに入れることであると仮定すれば、あるクラスタ内の全てのログの間の類似性距離は、複数のクラスタにまたがるログ間の距離と比較して非常に小さい。したがって、空間内に非常に密なクラスタがある。このログの性質は、発明者等が単純かつ効率的なクラスタ化およびパターン認識のプロセスを設計する助けとなる。
【００１３】
図２は、例示的な精密パターン生成プロセスの詳細を示す図である。２０１で、ログトークン化が行われる。（１０１の）任意の異種ログを取り、意味論的に意味のあるトークンをログから生成するためにトークン化が処理される。このプロセスでは、区切り文字（すなわちスペース、カンマなど）のセットに基づいて、各入来ログを分割する。このプロセスでは、次いで、日付、時間、ＩＰ、および数字など既定のデータタイプのセットを検出し、これらのフィールドの実際の値をフィールド名で置換する。例えば、このシステムは、２０１４−０７−０９を「日付」で置換し、１９２．１６８．３２．１０を「ＩＰ」で置換し、「１２５２３」を「数字」で置換する。特定のタイプの実際の内容をユーザが気にすることもあるので、この規定タイプのセットは、ユーザの要件に基づいて変更することができる。図３は、このプロセスがどのようにして長いメッセージをトークン化するかを示す図である。
【００１４】
２０２で、このプロセスは、ログの２０１で得られた全てのトークンを結合して１つの語にし、一意的な語のそれぞれについて一意的な数値を生成する関数を適用することによって、そのログのコンパクトシグネチャ（ｃｏｍｐａｃｔ−ｓｉｇｎａｔｕｒｅ）を生成する。２０３で、このプロセスは、コンパクトシグネチャの一意性を決定する。このプロセスは、全ての一意的なコンパクトシグネチャについて指標を維持する。それぞれの指標入力は、コンパクトシグネチャを「鍵」として含み、それに関連するメタデータを「値」として含む。メタデータは、ログトークン、およびカウンタを含む。後に、このプロセスは、これらのトークンからログのパターンを生成する。それぞれの入来ログについて、システムは、そのコンパクトシグネチャを使用してこの指標を参照する。一致が見られた場合には、それは、この入来ログをカバーするログをシステムが既に発見していることを意味しているので、プロセスは、このログを廃棄し、カウンタを１増やす。そうでない場合には、システムは、関連するトークンとともにこのコンパクトシグネチャを指標に記憶し、カウンタ値を１に設定する。精密パターンを生成するためのメモリ要件は、この指標を記憶するために必要とされる空間である。さらに、指標のサイズは、処理されるログの総数に依存するのではなく、コンパクトシグネチャの一意数に依存する。
【００１５】
図４は、例示的なパターンツリー構築プロセスの詳細を示す図である。３０１で、このプロセスは、２０３で生成された全ての一意的なコンパクトシグネチャのクラスタを、それらのログトークンを使用して構築する。ログトークンの各セットは、特定のログを表している。以下、「ログ」は、２０１で生成された対応するトークンを意味するものとする。同じフォーマットによって生成されたログは、非常に小さい類似性距離（多くの場合はゼロ）を有し、異なるフォーマットによって生成されたログは、通常は、それよりも大きな距離を有する。この性質により、非常に高速かつメモリ効率の高いクラスタ化方法が可能になる。
【００１６】
次に、３０１．ａで、このプロセスは、密なクラスタを発見する。このプロセスは、最初のログから開始して、最後のログに到達し、全ての密なクラスタがこのプロセス中に作成されることになるまで、全てのログを１つ１つ処理する。処理対象の新たなログのそれぞれについて、このプロセスは、その新たなログを代表ログのセットと比較し、その新たなログまでの距離がＭａｘＤｉｓｔ以下である１つの代表ログを発見する。ＭａｘＤｉｓｔは、内部パラメータである。ＭａｘＤｉｓｔは、最初は非常に小さな値（すなわち０．００００００１）に設定される。距離推定式については、ステップ３０１．ｄで説明する。代表が発見されない場合には、それは、処理中のログが、それまでに見つかったいずれのクラスタにも類似していないことを意味しており、プロセスは、新たなクラスタを作成する必要がある。プロセスは、新たなクラスタを作成し、このログをこの新たなクラスタの代表として設定し、メンバリストを作成して新たなログをこのメンバリストに追加し、この新たなクラスタのカウンタ値を新たなログのカウンタ値（１０３から）に設定する。代表が発見された場合には、新たなログは、そのメンバリストに追加され、新たなログのカウンタ値（１０３から）が、クラスタの現在のカウンタ値に追加される。
【００１７】
３０１．ｂで、このプロセスは、アーリーアバンダニング（Ｅａｒｌｙ  Ａｂａｎｄｏｎｉｎｇ）技術を使用して速度を改善することができる。３０１．ａは高速であるが、追加の速度向上技術により、これをさらに速めることができる。アーリーアバンダニングは、ユークリッド距離の下での類似性探索の速度を向上させるための有用な技術である。密なクラスタを発見するために、このプロセスは、新たなログと代表ログとの間の距離をＭａｘＤｉｓｔと比較して、新たなログをそのクラスタに入れることができるかどうかを調べる。２つのログの間の距離は、ユークリッド距離と同様に計算されるので、アーリーアバンダニング技術が適用される。２つの所与のログをトークンごとに比較することにより、距離が既にしきい値を超えていることをプロセスが検出した場合には、それら２つのログは互いにＭａｘＤｉｓｔの半径内にないので、その距離を計算する必要は全くない。ログ内のトークンの数が多数になる可能性もあるので、この技術は、不要な計算をかなり回避する助けになる。
【００１８】
３０１．ｃで、このプロセスは、ログ距離決定を実行する。２つのログＰとＱの間の距離は、以下の数式によって決定される。
【００１９】
【数１】
2019502196.tif 000003
【００２０】
ここで、Ｐｉは、ログＰのｉ番目のトークンであり、ｌｅｎ（Ｐ）は、ログＰのトークン数であり、Ｑｉは、ログＱのｉ番目のトークンであり、ｌｅｎ（Ｑ）は、ログＱのトークン数である。ｋ１は、調整可能なパラメータである。デフォルトのｋ１は１に設定されるが、この値はユーザの要件に応じて変更することができる。
【００２１】
３０１で、高速ログパターン認識が実行される。このプロセスは、ステップ３０１でログをクラスタ化した後で、各クラスタのパターンを生成する。３０１．ｄで、このプロセスは、マージ方法を適用する。２つのログがマージされるものとすると、このプロセスは、それらの最良のアラインメントを発見する。２つのログの最良のアラインメントとは、マージ後に最小数のワイルドカードおよび変数を生成するアラインメントである。アラインメントプロセスでは、各ログのトークン同士の間にいくつかのギャップが挿入されることがある。このアラインメントアルゴリズムは、これらのギャップを挿入した後で２つのログの長さが確実に等しくなるようにする。同じ長さを有する２つのログが発見されたら、この方法は、それらをトークンごとに処理して、出力を生成する。一例を、図５に示す。この図は、２つのパターンの例示的なマージを示す図である。当業者なら、２つのシーケンスをアラインメントする様々な方法を使用することができ、そのうちの１つは、Ｏ（１１．１２）時間ステップで長さ１１および１２を有する２つのシーケンスをアラインメントすることができるスミスウォーターマン（Ｓｍｉｔｈ−Ｗａｔｅｒｍａｎ）法である。したがって、マージ関数の時間計算量（ｔｉｍｅ  ｃｏｍｐｌｅｘｉｔｙ）もＯ（１１．１２）である。
【００２２】
【数２】
2019502196.tif 000004
【００２３】
ＵＰＧＭＡは非常に大きな時間計算量を有するので、この方法は、ＵＰＧＭＡよりよい。その理由は、ＵＰＧＭＡは、ログをマージする最良の順序を発見し、その特定の順序に従って最終的なパターンを作成しようとするからである。発明者等の高速かつ効率的なクラスタ化方法は、各密なクラスタ内のログが互いに非常に類似していることを保証するので、パターンを作成するためにそれらのログをマージする順序は、全く問題にならない。パターンを発見するためには、システムは、最初のログから開始して、その最初のログを２番目のログとマージし、次いで、その結果得られたものを３番目のログとマージし、これが最後のログまで繰り返される。このマージが逆の順序、または任意の順序で行われても、同じ結果を得ることができる。この方法では最良の順序を発見する必要がないので、ＵＰＧＭＡよりはるかに高速になる。
【００２４】
３０２で、このプロエスは、パターン階層ツリーを構築する。階層を作成するために、このシステムは、高速かつ効率的なクラスタ化（３０１）、および高速パターン認識（３０２）の両方を反復して使用する。図６は、この反復プロセスを示す図である。クラスタ化方法は、所与のログのセットに対して、非常に小さいＭａｘＤｉｓｔ（すなわち０．００００００１）で適用される。このクラスタ化の出力は、各クラスタがログを１つしか含まない密なクラスタのセットである。各クラスタにログが１つしかないので、マージステップは不要であり、ログ自体がパターンとして働くことができる。これらのパターンは、パターン階層ツリーのリーフ（最下層レベル）である。リーフレベルは、精密パターンに対応している。階層のその他のレベルを生成するためには、クラスタ化方法のＭａｘＤｉｓｔパラメータが、内部パラメータであるしきい値αだけ増大され、これが、ＭａｘＤｉｓｔの以前の値で生成されたパターンに対して実行される。換言すれば、（より大きなＭａｘＤｉｓｔを使用することによって）より緩和されたバージョンのクラスタ化方法が、新たなクラスタを生成することになるパターンに対して適用される。αのデフォルト値は、０．３に設定されるが、この値は、ユーザの好みに応じて変更することができる。クラスタ化された全てのパターンに対してパターン認識が実行されて、より一般的なパターンを発見する。これらの新たなパターンのセットは、新たなレベルとして階層に追加されることになる。反復する度に、新たなレベルが階層に追加される。これは、パターン階層を構築するボトムアップ方法である。階層の上に行くほど、発見されるパターンが少なくなり、それらのパターンは、低いレベルのパターンより一般的である。この構造は、ツリーのどのレベルでも所望のパターンのセットとして選択できる柔軟性を提供する。図７は、例示的なパターンツリーを示す図である。
【００２５】
図８は、パターン選択プロセスの詳細を示す図である。４０１で、（１０３から）ログのセットについてパターンの階層が与えられると、ユーザは、特定の性質を有するレベルに関心を持つことがある。ユーザによっては、最小数のパターンを得ることを優先することもあるし、ユーザによっては、非常に精密なパターンを得ることに関心を持ち、パターンの数は気にしないこともある。レベルを選択するためにユーザが使用することができる基準としては、多数の異なる基準があるが、階層のあるレベルのコストを計算する一般式は、以下の通りである。
【００２６】
【数３】
2019502196.tif 000005
【００２７】
ここで、Ｓｉｚｅｉは、クラスタｉのログ数であり、ＷＣｉ、Ｖａｒｉ、およびＦＶｉは、それぞれクラスタｉのパターン中のワイルドカードの数、変数トークンの数、固定値トークンの数であり、ａ１、ａ２、およびａ３は、ユーザの要件を満たすように設定することができる調整可能なパラメータである。
【００２８】
表１は、図７のパターンのコスト推定の一例を示している。
【００２９】
【表１】
2019502196.tif 000006
【００３０】
４０２で、ユーザが好みを有していない場合には、このプロセスは、デフォルトで、ａ１＝１、ａ２＝０、およびａ３＝０と設定して、最小数のパターンを有する、ワイルドカードを有していないレベルが最終的なパターンのセットとして選択されるようにする。例えば、図７で表１を使用した場合には、レベル２は、ワイルドカードのない２つのパターンを有するので、レベル２のこれら２つのパターンが、最終的なパターンのセットとして選択される。ユーザは、予想されるパターンの最大数を指定することによって、自分の好みを与えることもできる。この場合には、プロセスは、その予想パターン数を超えずに最小数のワイルドカードを含むレベルを選択する。例えば、ユーザが、最大で４つのパターンまで生成するように指定することがある。この場合には、プロセスは、レベル２がユーザのパターン上限の４を超えずに最小数のパターンを生成することになると表１が示しているように、図７のレベル２の２つのパターンを選択する。このパターンツリーから、ユーザは、任意の特定のレベルを選択することもできる。例えば、ユーザが、レベル１を選択したいと思うこともある。この場合には、レベル１の４つのパターンが、最終的なパターンセットとして選択されることになる。
【００３１】
同じ番号が同じまたは類似の要素を表している図面を参照し、まずは図９を参照すると、本発明の原理が適用され得る例示的な処理システム１００を示すブロック図が、本発明の原理の実施形態に従って示されている。処理システム１００は、システムバス１０２を介して他の構成要素に動作可能に結合された少なくとも１つのプロセッサ（ＣＰＵ）１０４を含む。キャッシュ１０６、読取り専用メモリ（ＲＯＭ）１０８、ランダムアクセスメモリ（ＲＡＭ）１１０、入出力（Ｉ／Ｏ）アダプタ１２０、音声アダプタ１３０、ネットワークアダプタ１４０、ユーザインタフェースアダプタ１５０、およびディスプレイアダプタ１６０が、システムバス１０２に動作可能に結合されている。
【００３２】
第１の記憶デバイス１２２および第２の記憶デバイス１２４は、Ｉ／Ｏアダプタ１２０によってシステムバス１０２に動作可能に結合されている。記憶デバイス１２２および１２４は、ディスク記憶デバイス（例えば磁気または光ディスク記憶デバイス）および固体磁気デバイスなどのうちのいずれであってもよい。記憶デバイス１２２と１２４は、同じタイプの記憶デバイスであってもよいし、異なるタイプの記憶デバイスであってもよい。
【００３３】
スピーカ１３２は、音声アダプタ１３０によってシステムバス１０２に動作可能に結合されている。トランシーバ１４２は、ネットワークアダプタ１４０によってシステムバス１０２に動作可能に結合されている。表示デバイス１６２は、ディスプレイアダプタ１６０によってシステムバス１０２に動作可能に結合されている。第１のユーザ入力デバイス１５２、第２のユーザ入力デバイス１５４、および第３のユーザ入力デバイス１５６は、ユーザインタフェースアダプタ１５０によってシステムバス１０２に動作可能に結合されている。ユーザ入力デバイス１５２、１５４および１５６は、キーボード、マウス、キーパッド、画像取込みデバイス、動作感知デバイス、マイクロフォン、および上記のデバイスのうちの少なくとも２つの機能を組み込んだデバイスなどのうちのいずれかとすることができる。もちろん、本発明の原理の趣旨を維持したままで、その他のタイプの入力デバイスも使用される可能性がある。ユーザ入力デバイス１５２、１５４および１５６は、同じタイプのユーザ入力デバイスであってもよいし、異なるタイプのユーザ入力デバイスであってもよい。ユーザ入力デバイス１５２、１５４および１５６は、システム１００に情報を入力し、システム１００から情報を出力するために使用される。
【００３４】
もちろん、処理システム１００は、当業者なら容易に思いつくように、他の要素（図示せず）を含むこともできるし、特定の要素を省略することもできる。例えば、当業者なら容易に理解するように、処理システム１００の個々の実施態様に応じて、様々な他の入力デバイスおよび／または出力デバイスが、処理システム１００に含まれる可能性がある。例えば、様々なタイプの無線および／または有線の入力および／または出力デバイスが使用される可能性がある。さらに、当業者なら容易に理解するように、追加のプロセッサ、制御装置、およびメモリなども、様々な構成で利用される可能性がある。処理システム１００の上記およびその他の変形形態は、本明細書に与えられる本発明の原理の教示があれば、当業者なら容易に思いつく。
【００３５】
本明細書に記載される実施形態は、全体がハードウェアであってもよいし、あるいは、ハードウェア要素と、これらに限定されるわけではないが、ファームウェア、常駐ソフトウェア、マイクロコードを含むソフトウェア要素とを両方含んでいてもよいことを理解されたい。
【００３６】
実施形態は、コンピュータまたは任意の命令実行システムによって使用される、あるいはそれと関連付けて使用されるプログラムコードを提供するコンピュータ使用可能またはコンピュータ可読媒体からアクセス可能なコンピュータプログラム製品を含む可能性がある。コンピュータ使用可能またはコンピュータ可読媒体は、命令実行システム、装置またはデバイスによって使用される、あるいはそれと関連付けて使用されるプログラムを記憶、通信、伝搬または移送する任意の装置を含む可能性がある。この媒体は、磁気、光、電子、電磁気、赤外線または半導体システム（または装置もしくはデバイス）、あるいは伝搬媒体とすることができる。この媒体は、半導体または固体メモリ、磁気テープ、取外し可能コンピュータディスケット、ランダムアクセスメモリ（ＲＡＭ）、読取り専用メモリ（ＲＯＭ）、固い磁気ディスク、光ディスクなどのコンピュータ可読記憶媒体を含む可能性がある。
【００３７】
プログラムコードを記憶および／または実行するのに適したデータ処理システムは、システムバスを介して直接または間接的にメモリ要素に結合されている、例えばハードウェアプロセッサなどの、少なくとも１つのプロセッサを含むことがある。メモリ要素は、プログラムコードの実際の実行中に利用されるローカルメモリ、大容量記憶装置、および実行中に大容量記憶装置からコードが取り出される回数を減らすために少なくとも一部のプログラムコードの一時的記憶域を提供するキャッシュメモリを含む可能性がある。入出力またはＩ／Ｏデバイス（これらに限定されるわけではないが、キーボード、ディスプレイ、ポインティングデバイスなど）は、直接システムに結合されていることもあるし、あるいは間にＩ／Ｏ制御装置を介してシステムに結合されていることがある。
【００３８】
以上の説明は、あらゆる点で限定的なものではなく例証および例示的なものとして理解されたい。本明細書に開示される本発明の範囲は、上記の詳細な説明によって決定されるのではなく、特許法で許される最も広い意味で解釈される特許請求の範囲によって決定される。本明細書に示され説明される実施形態は、本発明の原理の単なる例示に過ぎないこと、ならびに当業者なら、本発明の範囲および趣旨を逸脱することなく様々な修正を実施することができることを理解されたい。当業者なら、本発明の範囲および趣旨を逸脱することなく、様々な他の特徴の組合せを実施することもできる。
【図１】
2019502196.tif 000009
【図２】
2019502196.tif 000010
【図３】
2019502196.tif 000011
【図４】
2019502196.tif 000012
【図５】
2019502196.tif 000013
【図６】
2019502196.tif 000014
【図７】
2019502196.tif 000015
【図８】
2019502196.tif 000016
【図９】
2019502196.tif 000017
【国際調査報告】
2019502196.tif 000018
2019502196.tif 000019