(57)【特許請求の範囲】
【請求項１】
ログメッセージのフォーマットを推定する方法であって、コンピュータが、
第１のログメッセージを所定のキャラクタの前後で分割して、当該分割した各部分をノードとし、当該ノードそれぞれを前記第１のログメッセージの先頭から順に並べて第１の有向グラフ構造を作成するステップと、
第２のログメッセージを前記所定のキャラクタの前後で分割して、当該分割した各部分をノードとし、当該ノードそれぞれを前記第２のログメッセージの先頭から順に並べて第２の有向グラフ構造を作成するステップと、
前記第１の有向グラフ構造中のノードと前記第２の有向グラフ構造中のノードとを比較して、前記第１の有向グラフ構造中のノードと前記第２の有向グラフ構造中のノードとの間で文字列が一致するノード以外のノードを検出するステップと、
前記検出したノードのうち、前記第２の有向グラフ構造中の前記検出したノードを、前記第１の有向グラフ構造に第１の分岐ノードとして追加するステップと、
前記第１の分岐ノードが追加された第１の有向グラフ構造に基づいて、前記フォーマットを推定するステップであって、前記フォーマットが、前記文字列が一致するノードに関連付けられた第１の部分、及び、前記第１の有向グラフ構造中の前記検出したノードと前記第２の有向グラフ構造中の前記検出したノードとの間で文字列の出現傾向が類似するノードに関連付けられた第２の部分、並びに任意的に、前記文字列の出現傾向が類似する前記ノード以外のノードに関連付けられた第３の部分を含む、前記推定するステップと
を実行することを含む、前記方法。
【請求項２】
前記コンピュータが、
前記第２の有向グラフ構造を作成するステップ、前記検出するステップ、及び前記追加するステップを繰り返すステップ
をさらに実行することを含む、請求項１に記載の方法。
【請求項３】
前記推定するステップが、前記繰り返しが所定回数行われた後における前記追加するステップで作成された有向グラフ構造に基づいて行われる、請求項２に記載の方法。
【請求項４】
前記コンピュータが、
前記第１の分岐ノードが追加された第１の有向グラフ構造において、前記文字列の出現傾向が類似する前記ノードを一つのノードに統合するステップ
をさらに実行するステップを含み、
前記推定するステップが、前記文字列の出現傾向が類似する前記ノードが一つのノードに統合された第１の有向グラフ構造に基づいて行われる、
請求項１〜３のいずれか一項に記載の方法。
【請求項５】
前記文字列の出現傾向が類似することが、
文字種別が類似する文字列が所定の割合以上であること、
文字長さが所定の長さ以上であること、
文字の編集距離が近いこと、又は、
それらの少なくとも２つの組み合わせ
に基づいて判断される、請求項４に記載の方法。
【請求項６】
前記コンピュータが、
前記第２の有向グラフ構造を作成するステップ、前記検出するステップ、前記追加するステップ、及び前記統合するステップを繰り返すステップ
をさらに実行することを含む、請求項４又は５に記載の方法。
【請求項７】
前記推定するステップが、前記繰り返しが所定回数行われた後における前記統合するステップで作成された有向グラフ構造に基づいて行われる、請求項６に記載の方法。
【請求項８】
前記分岐ノードが追加された第１の有向グラフ構造が、前記文字列が一致する２つのノードと、前記第１の有向グラフ構造中の前記検出した少なくとも１つのノード及び前記第２の有向グラフ構造中の前記検出した少なくとも１つのノードとからなる閉路を有し、前記第１の有向グラフ構造中の前記検出した少なくとも１つのノード及び前記第２の有向グラフ構造中の前記検出した少なくとも１つのノードが、前記文字列が一致する前記２つのノード間にある、請求項４〜７のいずれか一項に記載の方法。
【請求項９】
前記検出するステップが、前記閉路が複数形成されている場合に、
前記文字列の出現傾向が類似することを前記複数の閉路のうちの小さい閉路から再帰的に判定するステップ
をさらに含む、請求項８に記載の方法。
【請求項１０】
前記コンピュータが、
前記文字列の出現傾向が類似する前記ノードが一つのノードに統合された第１の有向グラフ構造をオートマトンとして出力するステップ
をさらに実行することを含む、請求項４〜９のいずれか一項に記載の方法。
【請求項１１】
前記コンピュータが、
第３のログメッセージを前記所定のキャラクタの前後で分割して、当該分割した各部分をノードとし、当該ノードそれぞれを前記第３のログメッセージの先頭から順に並べて第３の有向グラフ構造を作成するステップと、
前記第３の有向グラフ構造中のノードが前記オートマトン中のノードと一致するかを判断するステップと、
前記第３の有向グラフ構造中のノードが前記オートマトン中のノードと一致しないことに応じて、
前記第１の分岐ノードが追加された第１の有向グラフ構造中のノードと前記第３の有向グラフ構造中のノードとを比較して、前記第１の分岐ノードが追加された第１の有向グラフ構造中のノードと前記第３の有向グラフ構造中のノードとの間で文字列が一致するノード以外のノードを検出するステップと、
前記検出したノードのうち、前記第３の有向グラフ構造中の前記検出したノードを、前記第１の分岐ノードが追加された第１の有向グラフ構造に第２の分岐ノードとして追加するステップ
をさらに実行することを含み、
前記推定するステップが、前記第２の分岐ノードが追加された第１の有向グラフ構造に基づいて行われる、
請求項１０に記載の方法。
【請求項１２】
前記第３の有向グラフ構造中のノードが前記オートマトン中のノードと一致するかを判断するステップが、
前記第３の有向グラフ構造中の少なくとも１つのノードが前記オートマトン中の前記統合がされたノードと所定の条件を満たすことに応じて、前記第３の有向グラフ構造中のノードが前記オートマトン中のノードと一致すると判断するステップ
を含む、請求項１１に記載の方法。
【請求項１３】
前記検出するステップが、
前記第１の有向グラフ構造中のノードと前記第２の有向グラフ構造中のノードとの間で文字列が異なるノードが現れた場合に、当該異なるノードにおいて部分的に一致するノードが最も多くなる部分グラフ及びパスを探索するステップ
を含む、請求項１〜３のいずれか一項に記載の方法。
【請求項１４】
前記探索するステップが、メモ化再帰の技術を用いて行われる、請求項１３に記載の方法。
【請求項１５】
前記推定するステップが、
前記分岐ノードが追加された第１の有向グラフ構造の始点ノードから終点ノードを通る少なくとも１つのパスを走査して、前記フォーマットを推定するステップ
を含む、請求項１〜３のいずれか一項に記載の方法。
【請求項１６】
前記パスが複数ある場合に、前記フォーマットが、複数のパスそれぞれ上にあるノードそれぞれに関連付けられた、前記第１の部分、及び、前記第２の部分、並びに任意的に、前記第３の部分を含む、請求項１５に記載の方法。
【請求項１７】
前記所定のキャラクタが、記号又は空白文字である、請求項１〜１６のいずれか一項に記載の方法。
【請求項１８】
前記第２の部分が、任意の文字列を示す記号である、請求項１〜１７のいずれか一項に記載の方法。
【請求項１９】
ログメッセージのフォーマットを推定する為のコンピュータであって、
第１のログメッセージを所定のキャラクタの前後で分割して、当該分割した各部分をノードとし、当該ノードそれぞれを前記第１のログメッセージの先頭から順に並べて第１の有向グラフ構造を作成し、且つ、第２のログメッセージを前記所定のキャラクタの前後で分割して、当該分割した各部分をノードとし、当該ノードそれぞれを前記第２のログメッセージの先頭から順に並べて第２の有向グラフ構造を作成する有向グラフ構造作成手段と、
前記第１の有向グラフ構造中のノードと前記第２の有向グラフ構造中のノードとを比較して、前記第１の有向グラフ構造中のノードと前記第２の有向グラフ構造中のノードとの間で文字列が一致するノード以外のノードを検出するノード検出手段と、
前記検出したノードのうち、前記第２の有向グラフ構造中の前記検出したノードを、前記第１の有向グラフ構造に第１の分岐ノードとして追加する有向グラフ構造変更手段と、
前記第１の分岐ノードが追加された第１の有向グラフ構造に基づいて、前記フォーマットを推定するフォーマット推定手段であって、前記フォーマットが、前記文字列が一致するノードに関連付けられた第１の部分、及び、前記第１の有向グラフ構造中の前記検出したノードと前記第２の有向グラフ構造中の前記検出したノードとの間で文字列の出現傾向が類似するノードに関連付けられた第２の部分、並びに任意的に、前記文字列の出現傾向が類似する前記ノード以外のノードに関連付けられた第３の部分を含む、前記フォーマット推定手段と
を備えている、前記コンピュータ。
【請求項２０】
ログメッセージのフォーマットを推定する為のコンピュータ・プログラムであって、請求項１〜１８のいずれか一項に記載の方法の各ステップを実行させる、前記コンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ログメッセージのフォーマットを推定する技法に関する。
【背景技術】
【０００２】
コンピュータ・システムは、ときどきはトラブルや障害に見舞われることが避けられない。それらは、例えば、ハードウェアの障害、ローカル・ネットワークの障害、インターネットの障害、ソフトウェアのバグ、又はデータの破損などのさまざまな原因による。
【０００３】
上記トラブルや障害が起きたときに、その原因を解析できるように、例えばオペレーティング・システム、ミドルウェア、又はアプリケーション・プログラムの様々なレベルで、ログメッセージ（例えば、システム・ログ、オペレーティング・システム・ログ、又はアプリケーション・ログ）を生成する手段が講じられる。
【０００４】
ログメッセージは、一般的に次のような性質を持つ。
−  予めソフトウェア内部などで規定されているフォーマットに従い、出力されるメッセージを含む。
−  １つのメッセージは、文字を含む記号で構成されるシーケンスである。
−  メッセージは人間が可読であるものには限らないが、意味のある粒度で分解できる必要がある。
−  可読な文字列は、所定のキャラクタ、例えば空白文字（半角若しくは全角のスペースでありうる）又は記号（例えば、特殊な記号）で分割されている。
【０００５】
さて、システムの障害時には、上記性質をもつログメッセージが大量に生成されることがある。その際、ログメッセージから状況を把握し、早期に問題を解決するためには、迅速に原因を特定する必要がある。
【０００６】
しかしながら、ログメッセージは、機械的に生成されるが構造データになっていないものが多い。従って、ログメッセージを機械的に対応させる為に、予め人手による多くの作業やコストが必要である。
【０００７】
ログメッセージでは人間の可読性（readability）が考慮されている。生成された文字列から意味を認識する技術として、テキスト・マイニングなどの自然言語解析的アプローチが既知である。そこで、ログメッセージに自然言語解析的アプローチを適用することも考えられる。しかしながら、ログメッセージは必ずしも自然言語的構文に従っている訳ではなく、また一文の長さも通常の文章に比べて短いなど、ログメッセージ特有の傾向がある。従って、ログメッセージに対して、自然言語解析的アプローチを単純に適用するのではなく、上記自然言語解析的アプローチとは異なるアプローチを適用する必要がある。
【０００８】
また、データ・サイエンティストの作業の半分以上は、データ統合、データ・クレンジング及びデータ変換であるとも言われている。
【０００９】
下記特許文献１は、ログメッセージが、図４に示すようにシステムの利用状況やデータ通信の記録で、操作やデータの送受信が行われた日時、行われた操作の内容、送受信されたデータの中身等からなっており、ユーザが解読するには難解なメッセージが多く、またメッセージの発生条件や今後の対処方法を決定することが困難な場合が多いこと（段落００３９）、また、システムログ等は運用時間が長いと、数千行にもなることがあり、重要なメッセージを的確に見つけ出すことが困難であること（段落００４０）、及び、そこで、無視していいメッセージを水色、ログ記録領域不足（ｆｉｌｅ  ｓｙｓｔｅｍ  ｆｕｌｌ），温度異常、ＳＣＳＩエラー等の重要なメッセージを燈色のように色分けすることでログ内容を容易に判断できるようにすると共に、システムログ等をｈｔｍｌ形式で表示し、かつ、その対策方法がハイパーリンクして貼り付けるようにしていること（段落００４１）を記載する。
【００１０】
下記特許文献２は、監視の対象とするログファイル中のログデータからあらかじめ定義されたデータ項目に対応する値を切り出して規定されたデータ項目の値を配列する正規化されたログデータを作成して蓄積することを記載する（請求項１）。
【００１１】
下記非特許文献１〜４はそれぞれ、ログメッセージを処理するための技法を記載する。
【先行技術文献】
【特許文献】
【００１２】
【特許文献１】特開２００５−２６６９１９号公報
【特許文献２】特開平１０−２９３７０４号公報
【非特許文献】
【００１３】
【非特許文献１】R. Vaarandi, “A breadth-first algorithm for mining frequent patterns from event logs”, Proceedings of the 2004 IFIP International Conference on Intelligence in Communication Systems, 2004, pp. 293〜308＜URL:http://ristov.users.sourceforge.net/publications/intellcomm04-final.pdf＞から入手可能
【非特許文献２】A. A. Makanju, A. N. Zincir-Heywood, and E. E. Milios, “Clustering event logs using iterative partitioning”, KDD ’09: Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, New York, NY, USA: ACM, 2009, pp. 1255〜1264＜URL:http://dl.acm.org/citation.cfm?id=1557154&dl=ACM&coll=DL&CFID=519942606&CFTOKEN=51228911＞から入手可能
【非特許文献３】L. Tang, T. Li, and C. shing Perng, “Logsig: Generating system events from raw textual logs”, Proceedings of ACM CIKM, 2011＜URL:http://users.cis.fiu.edu/~taoli/pub/liang-cikm2011.pdf＞から入手可能
【非特許文献４】K. Q. Zhu, K. Fisher, and D. Walker, “Incremental learning of system log formats”, SIGOPS Oper. Syst. Rev., Vol. 44, No. 1, pp. 85〜90, March, 2010＜URL:https://www.cs.princeton.edu/~dpw/papers/incremental-0609.pdf＞から入手可能
【発明の概要】
【発明が解決しようとする課題】
【００１４】
ログメッセージ（例えば、システム・ログ、オペレーティング・システム・ログ、又はアプリケーション・ログ）のフォーマットは、プログラム（例えば、システム・アプリケーション、又はサーバ・アプリケーション）内に保持されているもの、又は、プログラムの命令として持つものでありうる。ログメッセージのフォーマットとは一般的に、固定部と可変部（変数を含む）の組み合わせの情報のことをいう。例えば、Ｃ言語のコードで、printf("xxx %s yyy", param);という関数があった場合に、当該関数から"xxx ppp yyy"が出力されたとする。当該出力のうち、"xxx"及び"yyy"が固定部であり、"ppp"が可変部である。ほとんどのログメッセージは、固定部と可変部とから構成されている。
【００１５】
ログメッセージのフォーマットを明らかにすることで、例えば以下に示す事項を実現することが可能になる：（１）ログの種類を分類すること；及び、（２）統計情報などの数値、又は、ユーザ名若しくはホスト名などの識別情報を取得すること。
【００１６】
ログの種類を分類することが実現できることによって、例えば、ログの発生傾向を機械的に知ることが可能になったり、又は、パターン・マイニングなどの分析の実施が可能になったりする。
【００１７】
統計情報などの数値、又は、ユーザ名若しくはホスト名などの識別情報を取得することが実現できることによって、例えば、当該取得した数値や識別情報を異常検知やレポート作成、若しくは、ルールベースの分析或いはイベント検知に利用できるようになったり、又は、人間がログを見る際に当該取得した数値や識別情報を使用して、着目すべき部分を視覚的に分かることができるようになったりする。
【００１８】
従って、本発明は、複数のログメッセージに共通するフォーマットを推定することを可能にすることを目的とする。
【課題を解決するための手段】
【００１９】
本発明は、ログメッセージのフォーマットを推定する技法、特にはプログラムが持つ又はプログラムに記載されているログメッセージのフォーマットを推定する技法を提供する。当該技法は、ログメッセージのフォーマットを推定する方法、並びに、ログメッセージのフォーマットを推定する為のコンピュータ、そのコンピュータ・プログラム及びコンピュータ・プログラム製品を包含しうる。
【００２０】
本発明に従う上記技法は、複数のログメッセージを一つの有向グラフ構造として捉えることによって、当該有向グラフ構造からログメッセージのフォーマットを推定することを特徴とする。
【００２１】
（本発明に従う第１の態様）
【００２２】
本発明に従う第１の態様において、ログメッセージのフォーマットを推定する方法は、コンピュータが、
第１のログメッセージを所定のキャラクタの前後で分割して、当該分割した各部分をノードとし、当該ノードそれぞれを上記第１のログメッセージの先頭から順に並べて第１の有向グラフ構造を作成するステップと、
第２のログメッセージを上記所定のキャラクタの前後で分割して、当該分割した各部分をノードとし、当該ノードそれぞれを上記第２のログメッセージの先頭から順に並べて第２の有向グラフ構造を作成するステップと、
上記第１の有向グラフ構造中のノードと上記第２の有向グラフ構造中のノードとを比較して、上記第１の有向グラフ構造中のノードと上記第２の有向グラフ構造中のノードとの間で文字列が一致するノード以外のノードを検出するステップと、
上記検出したノードのうち、上記第２の有向グラフ構造中の上記検出したノードを、上記第１の有向グラフ構造に第１の分岐ノードとして追加するステップと、
上記第１の分岐ノードが追加された第１の有向グラフ構造に基づいて、上記フォーマットを推定するステップであって、上記フォーマットが、上記文字列が一致するノードに関連付けられた第１の部分、及び、上記第１の有向グラフ構造中の上記検出したノードと上記第２の有向グラフ構造中の上記検出したノードとの間で文字列の出現傾向が類似するノードに関連付けられた第２の部分、並びに任意的に、上記文字列の出現傾向が類似する上記ノード以外のノードに関連付けられた第３の部分を含む、上記推定するステップと
を実行することを含む。
【００２３】
本発明の一つの実施態様において、上記方法は、上記コンピュータが、
上記第２の有向グラフ構造を作成するステップ、上記検出するステップ、及び上記追加するステップを繰り返すステップ
をさらに実行することを含みうる。
【００２４】
本発明の一つの実施態様において、上記推定するステップが、上記繰り返しが所定回数行われた後における上記追加するステップで作成された有向グラフ構造に基づいて行われうる。
【００２５】
本発明の一つの実施態様において、上記方法は、上記コンピュータが、
上記第１の分岐ノードが追加された第１の有向グラフ構造において、上記文字列の出現傾向が類似する上記ノードを一つのノードに統合するステップ
をさらに実行するステップを含み、
上記推定するステップが、上記文字列の出現傾向が類似する上記ノードが一つのノードに統合された第１の有向グラフ構造に基づいて行われうる。
【００２６】
本発明の一つの実施態様において、上記文字列の出現傾向が類似することが、
文字種別が類似する文字列が所定の割合以上であること、
文字長さが所定の長さ以上であること、
文字の編集距離が近いこと、又は、
それらの少なくとも２つの組み合わせ
に基づいて判断されうる。
【００２７】
本発明の一つの実施態様において、上記方法は、上記コンピュータが、
上記第２の有向グラフ構造を作成するステップ、上記検出するステップ、上記追加するステップ、及び上記統合するステップを繰り返すステップ
をさらに実行することを含みうる。
【００２８】
本発明の一つの実施態様において、上記推定するステップが、上記繰り返しが所定回数行われた後における上記統合するステップで作成された有向グラフ構造に基づいて行われうる。
【００２９】
本発明の一つの実施態様において、上記分岐ノードが追加された第１の有向グラフ構造が、上記文字列が一致する２つのノードと、上記第１の有向グラフ構造中の上記検出した少なくとも１つのノード及び上記第２の有向グラフ構造中の上記検出した少なくとも１つのノードとからなる閉路を有し、上記第１の有向グラフ構造中の上記検出した少なくとも１つのノード及び上記第２の有向グラフ構造中の上記検出した少なくとも１つのノードが、上記文字列が一致する上記２つのノード間にありうる。
【００３０】
本発明の一つの実施態様において、上記検出するステップが、上記閉路が複数形成されている場合に、
上記文字列の出現傾向が類似することを上記複数の閉路のうちの小さい閉路から再帰的に判定するステップ
をさらに含みうる。
【００３１】
本発明の一つの実施態様において、上記方法は、上記コンピュータが、
上記文字列の出現傾向が類似する上記ノードが一つのノードに統合された第１の有向グラフ構造をオートマトンとして出力するステップ
をさらに実行することを含みうる。
【００３２】
本発明の一つの実施態様において、上記方法は、上記コンピュータが、
第３のログメッセージを上記所定のキャラクタの前後で分割して、当該分割した各部分をノードとし、当該ノードそれぞれを上記第３のログメッセージの先頭から順に並べて第３の有向グラフ構造を作成するステップと、
上記第３の有向グラフ構造中のノードが上記オートマトン中のノードと一致するかを判断するステップと
上記第３の有向グラフ構造中のノードが上記オートマトン中のノードと一致しないことに応じて、
上記第１の分岐ノードが追加された第１の有向グラフ構造中のノードと上記第３の有向グラフ構造中のノードとを比較して、上記第１の分岐ノードが追加された第１の有向グラフ構造中のノードと上記第３の有向グラフ構造中のノードとの間で文字列が一致するノード以外のノードを検出するステップと、
上記検出したノードのうち、上記第３の有向グラフ構造中の上記検出したノードを、上記第１の分岐ノードが追加された第１の有向グラフ構造に第２の分岐ノードとして追加するステップ
をさらに実行することを含み、
上記推定するステップが、上記第２の分岐ノードが追加された第１の有向グラフ構造に基づいて行われうる。
【００３３】
本発明の一つの実施態様において、上記第３の有向グラフ構造中のノードが上記オートマトン中のノードと一致するかを判断するステップが、
上記第３の有向グラフ構造中の少なくとも１つのノードが上記オートマトン中の上記統合がされたノードと所定の条件を満たすことに応じて、上記第３の有向グラフ構造中のノードが上記オートマトン中のノードと一致すると判断するステップ
を含みうる。
【００３４】
本発明の一つの実施態様において、上記検出するステップが、
上記第１の有向グラフ構造中のノードと上記第２の有向グラフ構造中のノードとの間で文字列が異なるノードが現れた場合に、当該異なるノードにおいて部分的に一致するノードが最も多くなる部分グラフ及びパスを探索するステップ
を含みうる。
【００３５】
本発明の一つの実施態様において、上記探索するステップが、メモ化再帰の技術を用いて行われうる。
【００３６】
本発明の一つの実施態様において、上記推定するステップが、
上記分岐ノードが追加された第１の有向グラフ構造の始点ノードから終点ノードを通る少なくとも１つのパスを走査して、上記フォーマットを推定するステップ
を含みうる。
【００３７】
本発明の一つの実施態様において、上記パスが複数ある場合に、上記フォーマットが、複数のパスそれぞれ上にあるノードそれぞれに関連付けられた、上記第１の部分、及び、上記第２の部分、並びに任意的に、上記第３の部分を含みうる。
【００３８】
本発明の一つの実施態様において、上記所定のキャラクタが、記号又は空白文字でありうる。
【００３９】
本発明の一つの実施態様において、上記第２の部分が、任意の文字列を示す記号でありうる。
【００４０】
（本発明に従う第２の態様）
【００４１】
本発明に従う第２の態様において、ログメッセージのフォーマットを推定する為のコンピュータは、
第１のログメッセージを所定のキャラクタの前後で分割して、当該分割した各部分をノードとし、当該ノードそれぞれを上記第１のログメッセージの先頭から順に並べて第１の有向グラフ構造を作成し、且つ、第２のログメッセージを上記所定のキャラクタの前後で分割して、当該分割した各部分をノードとし、当該ノードそれぞれを上記第２のログメッセージの先頭から順に並べて第２の有向グラフ構造を作成する有向グラフ構造作成手段と、
上記第１の有向グラフ構造中のノードと上記第２の有向グラフ構造中のノードとを比較して、上記第１の有向グラフ構造中のノードと上記第２の有向グラフ構造中のノードとの間で文字列が一致するノード以外のノードを検出するノード検出手段と、
上記検出したノードのうち、上記第２の有向グラフ構造中の上記検出したノードを、上記第１の有向グラフ構造に第１の分岐ノードとして追加する有向グラフ構造変更手段と、
上記第１の分岐ノードが追加された第１の有向グラフ構造に基づいて、上記フォーマットを推定するフォーマット推定手段であって、上記フォーマットが、上記文字列が一致するノードに関連付けられた第１の部分、及び、上記第１の有向グラフ構造中の上記検出したノードと上記第２の有向グラフ構造中の上記検出したノードとの間で文字列の出現傾向が類似するノードに関連付けられた第２の部分、並びに任意的に、上記文字列の出現傾向が類似する上記ノード以外のノードに関連付けられた第３の部分を含む、上記フォーマット推定手段と
を備えている。
【００４２】
本発明の一つの実施態様において、上記コンピュータが、
上記有向グラフ構造作成手段により、上記第２の有向グラフ構造を作成すること、上記ノード検出手段により、上記第１の有向グラフ構造中のノードと上記第２の有向グラフ構造中のノードとの間で文字列が一致するノード以外のノードを検出すること、及び上記有向グラフ構造変更手段により、上記第２の有向グラフ構造中の上記検出したノードを上記第１の有向グラフ構造に第１の分岐ノードとして追加することを繰り返しうる。
【００４３】
本発明の一つの実施態様において、上記フォーマット推定手段が、上記繰り返しが所定回数行われた後において上記有向グラフ構造変更手段により作成された有向グラフ構造に基づいて、上記フォーマットの推定を行いうる。
【００４４】
本発明の一つの実施態様において、上記有向グラフ構造変更手段が、
上記第１の分岐ノードが追加された第１の有向グラフ構造において、上記文字列の出現傾向が類似する上記ノードを一つのノードに統合すること
をさらに実行し、
上記フォーマット推定手段が、上記文字列の出現傾向が類似する上記ノードが一つのノードに統合された第１の有向グラフ構造に基づいて、上記フォーマットの推定を行いうる。
【００４５】
本発明の一つの実施態様において、上記文字列の出現傾向が類似することが、
文字種別が類似する文字列が所定の割合以上であること、
文字長さが所定の長さ以上であること、
文字の編集距離が近いこと、又は、
それらの少なくとも２つの組み合わせ
に基づいて判断されうる。
【００４６】
本発明の一つの実施態様において、上記コンピュータが、
上記有向グラフ構造作成手段により、上記第２の有向グラフ構造を作成すること、上記ノード検出手段により上記第１の有向グラフ構造中のノードと上記第２の有向グラフ構造中のノードとの間で文字列が一致するノード以外のノードを検出すること、上記有向グラフ構造変更手段により、上記第２の有向グラフ構造中の上記検出したノードを上記第１の有向グラフ構造に第１の分岐ノードとして追加すること、及び上記有向グラフ構造変更手段により、上記第１の分岐ノードが追加された第１の有向グラフ構造において、上記文字列の出現傾向が類似する上記ノードを一つのノードに統合することを繰り返しうる。
【００４７】
本発明の一つの実施態様において、上記フォーマット推定手段が、上記繰り返しが所定回数行われた後において上記有向グラフ構造変更手段により上記統合することで作成された有向グラフ構造に基づいて、上記フォーマットの推定を行いうる。
【００４８】
本発明の一つの実施態様において、上記分岐ノードが追加された第１の有向グラフ構造が、上記文字列が一致する２つのノードと、上記第１の有向グラフ構造中の上記検出した少なくとも１つのノード及び上記第２の有向グラフ構造中の上記検出した少なくとも１つのノードとからなる閉路を有し、上記第１の有向グラフ構造中の上記検出した少なくとも１つのノード及び上記第２の有向グラフ構造中の上記検出した少なくとも１つのノードが、上記文字列が一致する上記２つのノード間にありうる。
【００４９】
本発明の一つの実施態様において、上記ノード検出手段が、上記閉路が複数形成されている場合に、さらに、
上記文字列の出現傾向が類似することを上記複数の閉路のうちの小さい閉路から再帰的に判定しうる。
【００５０】
本発明の一つの実施態様において、上記コンピュータが、
上記文字列の出現傾向が類似する上記ノードが一つのノードに統合された第１の有向グラフ構造をオートマトンとして出力するオートマトン出力手段
をさらに備えうる。
【００５１】
本発明の一つの実施態様において、
上記有向グラフ構造作成手段がさらに、第３のログメッセージを上記所定のキャラクタの前後で分割して、当該分割した各部分をノードとし、当該ノードそれぞれを上記第３のログメッセージの先頭から順に並べて第３の有向グラフ構造を作成し、
上記ノード検出手段がさらに、上記第３の有向グラフ構造中のノードが上記オートマトン中のノードと一致するかを判断し、
上記第３の有向グラフ構造中のノードが上記オートマトン中のノードと一致しないことに応じて、
上記ノード検出手段がさらに、上記第１の分岐ノードが追加された第１の有向グラフ構造中のノードと上記第３の有向グラフ構造中のノードとを比較して、上記第１の分岐ノードが追加された第１の有向グラフ構造中のノードと上記第３の有向グラフ構造中のノードとの間で文字列が一致するノード以外のノードを検出し、
上記有向グラフ構造変更手段がさらに、上記検出したノードのうち、上記第３の有向グラフ構造中の上記検出したノードを、上記第１の分岐ノードが追加された第１の有向グラフ構造に第２の分岐ノードとして追加し、
上記フォーマット推定手段がさらに、上記フォーマットの推定を、上記第２の分岐ノードが追加された第１の有向グラフ構造に基づいて行いうる。
【００５２】
本発明の一つの実施態様において、上記ノード検出手段が上記第３の有向グラフ構造中のノードが上記オートマトン中のノードと一致するかを判断することが、
上記ノード検出手段がさらに、上記第３の有向グラフ構造中の少なくとも１つのノードが上記オートマトン中の上記統合がされたノードと所定の条件を満たすことに応じて、上記第３の有向グラフ構造中のノードが上記オートマトン中のノードと一致すると判断することを含みうる。
【００５３】
本発明の一つの実施態様において、上記ノード検出手段が、
上記第１の有向グラフ構造中のノードと上記第２の有向グラフ構造中のノードとの間で文字列が異なるノードが現れた場合に、当該異なるノードにおいて部分的に一致するノードが最も多くなる部分グラフ及びパスを探索しうる。
【００５４】
本発明の一つの実施態様において、上記ノード検出手段が、上記探索をメモ化再帰の技術を用いて行いうる。
【００５５】
本発明の一つの実施態様において、上記フォーマット推定手段が、
上記分岐ノードが追加された第１の有向グラフ構造の始点ノードから終点ノードを通る少なくとも１つのパスを走査して、上記フォーマットを推定しうる。
【００５６】
本発明の一つの実施態様において、上記パスが複数ある場合に、上記フォーマットが、複数のパスそれぞれ上にあるノードそれぞれに関連付けられた、上記第１の部分、及び、上記第２の部分、並びに任意的に、上記第３の部分を含みうる。
【００５７】
本発明の一つの実施態様において、上記所定のキャラクタが、記号又は空白文字でありうる。
【００５８】
本発明の一つの実施態様において、上記第２の部分が、任意の文字列を示す記号でありうる。
【００５９】
（本発明に従う第３の態様）
【００６０】
本発明に従う第３の態様において、コンピュータ・プログラム及びコンピュータ・プログラム製品は、上記コンピュータに、本発明に従う第１の態様のログメッセージのフォーマットを推定する方法の各ステップを実行させる。
【００６１】
本発明の実施態様に従うコンピュータ・プログラムはそれぞれ、一つ又は複数のフレキシブル・ディスク、ＭＯ、ＣＤ−ＲＯＭ、ＤＶＤ、ＢＤ、ハードディスク装置、ＵＳＢに接続可能なメモリ媒体、ＲＯＭ、ＭＲＡＭ、ＲＡＭ等の任意のコンピュータ読み取り可能な記録媒体に格納することができる。当該コンピュータ・プログラムは、記録媒体への格納のために、通信回線で接続する他のデータ処理システム、例えばコンピュータからダウンロードしたり、又は他の記録媒体から複製したりすることができる。また、本発明の実施態様に従うコンピュータ・プログラムは、圧縮し、又は複数に分割して、単一又は複数の記録媒体に格納することもできる。また、様々な形態で、本発明の実施態様に従うコンピュータ・プログラム製品を提供することも勿論可能であることにも留意されたい。本発明の実施態様に従うコンピュータ・プログラム製品は、例えば、上記コンピュータ・プログラムを記録した記憶媒体、又は、上記コンピュータ・プログラムを伝送する伝送媒体を包含しうる。
【００６２】
本発明の上記概要は、本発明の必要な特徴の全てを列挙したものではなく、これらの構成要素のコンビネーション又はサブコンビネーションもまた、本発明となりうることに留意すべきである。
【００６３】
本発明の実施態様において使用されるコンピュータの各ハードウェア構成要素を、複数のマシンと組み合わせ、それらに機能を配分し実施する等の種々の変更は当業者によって容易に想定され得ることは勿論である。それらの変更は、当然に本発明の思想に包含される概念である。ただし、これらの構成要素は例示であり、そのすべての構成要素が本発明の必須構成要素となるわけではない。
【００６４】
また、本発明は、ハードウェア、ソフトウェア、又は、ハードウェア及びソフトウェアの組み合わせとして実現可能である。ハードウェアとソフトウェアとの組み合わせによる実行として、上記コンピュータ・プログラムをインストールされたコンピュータにおける当該プログラムの実行が典型的な例として挙げられる。かかる場合、当該コンピュータ・プログラムが当該コンピュータのメモリにロードされて実行されることにより、当該コンピュータ・プログラムは、当該コンピュータを制御し、本発明にかかる処理を実行させる。当該コンピュータ・プログラムは、任意の言語、コード、又は、表記によって表現可能な命令群から構成されうる。そのような命令群は、当該コンピュータが特定の機能を直接的に、又は、１．他の言語、コード若しくは表記への変換及び、２．他の媒体への複製、のいずれか一方若しくは双方が行われた後に、実行することを可能にするものである。
【発明の効果】
【００６５】
従来技術であるログメッセージの分析手法、例えば自然言語処理に従い推定されたログメッセージのフォーマットには、乱雑且つノイズが入り易い。一方、本発明の実施態様に従い推定されたログメッセージのフォーマットでは、フォーマットの定義を持たないログメッセージに対して、パラメータ部分（所謂、ログメッセージの可変部）を判定することが可能になるという利点を有する。
【００６６】
例えば、複数の種類のログメッセージがあった場合に、各ログメッセージをキーとして取り扱うことで、ログメッセージ同士の関係性を探し出す処理ができる。そして、当該ログメッセージ同士の関係性を見つけて相関−ルールにすることによって、関係するトランザクションを見つけやすくするなどの効果がもたらされる。
【００６７】
また、パラメータ分が数値の場合、又は、出現する文字若しくは単語の傾向がつかみやすい場合に、当該パラメータの変化を元に異常検知に利用することが可能である。例えば、システムのトラブル対応中においても断続的に異常が発生する場合もあるので、他の事象とログメッセージからわかる異常を付き合わせることによって、問題箇所の特定につながりやすくなる。
【００６８】
さらに、パラメータを元にログメッセージを視覚化することによって、ログメッセージに関連付けられたシステムの全容把握や問題箇所の特定が容易になる。
【００６９】
また、従来技術であるクラスタリングベースの手法ではログメッセージの可変部が多かったり、自由な書式で出力されるログメッセージがあると、同じような構造でも別のログメッセージ種別であると判断されてしまったりする。一方、本発明の実施態様に従い推定されたログメッセージのフォーマットでは、上記問題を回避するとともに、構造の一致する部分を判定することが可能である。また、本発明の実施態様に従いログメッセージのフォーマットを推定する技法は、数値、ユーザ名又はホスト名などの類似した項目を抜き出し易い為に、ログメッセージから適切なパラメータの抽出をすることが期待できる。
【００７０】
また、本発明の実施態様に従うと、ログメッセージはある程度決まった形式で出力されるという性質から上記可変部の検出が容易になり、同時に多くの可変部が同じノード（既存の有向グラフ構造中のノード）に集約することが期待される。上記性質から、有向グラフ構造がログメッセージの数に応じて爆発的に成長することなしに、有向グラフ構造の探索範囲がある程度収束することが期待できる。
【００７１】
従って、本発明の実施態様に従うと、ログメッセージを元にしたデータ分析をする際の作業時間を短縮することが可能となる。
【図面の簡単な説明】
【００７２】
【図１】本発明の実施態様において使用されうるコンピュータを実現するためのハードウェア構成の一例を示した図である。
【図２】本発明の実施態様に従い、ログメッセージからフォーマットを推定する処理を示すためのダイアグラムを示す。
【図３】本発明の実施態様に従い、ログメッセージからフォーマットを推定する処理を示すためのダイアグラムを示す。
【図４】本発明の実施態様に従い、ログメッセージからフォーマットを推定する処理を示すためのダイアグラムを示す。
【図５Ａ】本発明の実施態様に従い、ログメッセージからフォーマットを推定する処理において、既存の有向グラフ構造に対して部分的に一致するノードが最も多くなる部分グラフとパスを探索する処理を示すためのダイアグラムを示す。
【図５Ｂ】本発明の実施態様に従い、ログメッセージからフォーマットを推定する処理において、メモ化再帰の技術を用いてパスを探索するためのダイアグラムを示す。
【図５Ｃ】本発明の実施態様に従い、ログメッセージからフォーマットを推定する処理において、文字列の出現傾向が類似するノードを検出ためのダイアグラムを示す。
【図５Ｄ】本発明の実施態様に従い、ログメッセージからフォーマットを推定する処理において、文字列の出現傾向が類似するノードを検出ためのダイアグラムを示す。
【図６Ａ】本発明の実施態様において、ログメッセージを有向グラフ構造で可視化したものを示す。
【図６Ｂ】本発明の実施態様に従い、図６Ａに示す有向グラフ構造を簡略化した後の有向グラフ構造の例を示す。
【図７Ａ】本発明の実施態様において、ログメッセージを有向グラフ構造で可視化したものを示す。
【図７Ｂ】本発明の実施態様に従い、図７Ａに示す有向グラフ構造を簡略化した後の有向グラフ構造の例を示す。
【図８Ａ】本発明の実施態様において、ログメッセージを有向グラフ構造で可視化したものを示す。
【図８Ｂ】本発明の実施態様に従い、図８Ａに示す有向グラフ構造を簡略化した後の有向グラフ構造の例を示す。
【図９Ａ】本発明の実施態様に従い、ログメッセージからフォーマットを推定する処理を示すフローチャートである。
【図９Ｂ】図９Ａに示すフローチャート中のパス探索の処理の詳細を示すフローチャートである。
【図９Ｃ】図９Ａに示すフローチャート中のパス探索の処理の詳細を示すフローチャートである。
【図１０】図１に従うハードウェア構成を好ましくは備えており、図９Ａ〜図９Ｃそれぞれに示すフローチャートに従って本発明の実施態様を実施するコンピュータの機能ブロック図の一例を示す図である。
【発明を実施するための形態】
【００７３】
本発明の実施形態を、以下に図面に従って説明する。以下の図を通して、特に断らない限り、同一の符号は同一の対象を指す。本発明の実施形態は、本発明の好適な態様を説明するためのものであり、本発明の範囲をここで示すものに限定する意図はないことを理解されたい。
【００７４】
図１は、本発明の実施態様において使用されうるコンピュータの一例を示した図である。
【００７５】
本発明の実施態様に従うコンピュータは、１又は複数のコンピュータから構成されうる。
【００７６】
図１は、本発明の実施態様において使用されうるコンピュータを実現するためのハードウェア構成の一例を示した図である。
【００７７】
コンピュータ（１０１）は例えば、デスクトップ・コンピュータ、ノートブック・コンピュータ、ウルトラブック・コンピュータ、又はサーバ・コンピュータでありうる。
【００７８】
コンピュータ（１０１）は、ＣＰＵ（１０２）とメイン・メモリ（１０３）とを備えており、これらはバス（１０４）に接続されている。ＣＰＵ（１０２）は好ましくは、３２ビット又は６４ビットのアーキテクチャに基づくものである。当該ＣＰＵ（１０２）は例えば、インテル社のＣｏｒｅ（商標  ｉ）シリーズ、Ｃｏｒｅ（商標）  ２シリーズ、Ａｔｏｍ（商標）シリーズ、Ｘｅｏｎ（登録商標）シリーズ、Ｐｅｎｔｉｕｍ（登録商標）シリーズ若しくはＣｅｌｅｒｏｎ（登録商標）シリーズ、ＡＭＤ（Advanced Micro Devices）社のＡシリーズ、Ｐｈｅｎｏｍ（商標）シリーズ、Ａｔｈｌｏｎ（商標）シリーズ、Ｔｕｒｉｏｎ（商標）シリーズ若しくはＳｅｍｐｒｏｎ（商標）、又は、インターナショナル・ビジネス・マシーンズ・コーポレーションのＰｏｗｅｒ（商標）シリーズでありうる。
【００７９】
バス（１０４）には、ディスプレイ・コントローラ（１０５）を介して、ディスプレイ（１０６）、例えば液晶ディスプレイ（ＬＣＤ）が接続されうる。また、液晶ディスプレイ（ＬＣＤ）は例えば、タッチパネル・ディスプレイ又はフローティング・タッチ・ディスプレイであってもよい。ディスプレイ（１０６）は、コンピュータ（１０１）上で動作中のソフトウェア、例えば本発明の実施態様に従うコンピュータ・プログラムが稼働することによって表示される情報（例えば、ログメッセージ、有向グラフ構造、又はログメッセージのフォーマット）を、適当なグラフィック・インタフェースで表示するために使用されうる。
【００８０】
バス（１０４）には任意的に、例えばＳＡＴＡ又はＩＤＥコントローラ（１０７）を介して、記憶装置（１０８）、例えばハードディスク又はソリッド・ステート・ドライブに接続されうる。
【００８１】
バス（１０４）には任意的に、例えばＳＡＴＡ又はＩＤＥコントローラ（１０７）を介して、記憶装置（１０８）、ドライブ（１０９）、例えばＣＤ、ＤＶＤ又はＢＤドライブが接続されうる。
【００８２】
バス（１０４）には、周辺装置コントローラ（１１０）を介して、例えばキーボード・マウス・コントローラ又はＵＳＢバスを介して、任意的に、キーボード（１１１）及びマウス（１１２）が接続されうる。
【００８３】
記憶装置（１０８）には、オペレーティング・システム、Ｗｉｎｄｏｗｓ（登録商標）ＯＳ、ＵＮＩＸ（登録商標）、Ｌｉｎｕｘ（登録商標）（例えば、ＲｅｄＨａｔ（登録商標）、Ｄｅｂｉａｎ（登録商標））、ＭａｃＯＳ（登録商標）、及びＪ２ＥＥなどのＪａｖａ（登録商標）処理環境、Ｊａｖａ（登録商標）アプリケーション、Ｊａｖａ（登録商標）仮想マシン（ＶＭ）、Ｊａｖａ（登録商標）実行時（ＪＩＴ）コンパイラを提供するプログラム、本発明の実施態様に従うコンピュータ・プログラム、及びその他のプログラム、並びにデータ（例えば、用語リスト、コンテンツ）が、メイン・メモリ（１０３）にロード可能なように記憶されうる。
【００８４】
記憶装置（１０８）は、コンピュータ（１０１）内に内蔵されていてもよく、当該コンピュータ（１０１）がアクセス可能なようにケーブル（例えば、ＵＳＢケーブル又はＬＡＮケーブル）を介して接続されていてもよく、又は、当該コンピュータ（１０１）がアクセス可能なように有線又は無線ネットワークを介して接続されていてもよい。
【００８５】
ドライブ（１０９）は、必要に応じて、例えばＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ又はＢＤ−ＲＯＭからプログラム、例えばオペレーティング・システム又はアプリケーションを記憶装置（１０８）にインストールするために使用されうる。
【００８６】
通信インタフェース（１１４）は、例えばイーサネット（登録商標）・プロトコルに従う。通信インタフェース（１１４）は、通信コントローラ（１１３）を介してバス（１０４）に接続され、コンピュータ（１０１）を通信回線（１１５）に有線又は無線接続する役割を担い、コンピュータ（１０１）のオペレーティング・システムの通信機能のＴＣＰ／ＩＰ通信プロトコルに対して、ネットワーク・インタフェース層を提供する。通信回線は例えば、有線ＬＡＮ接続規格に基づく有線ＬＡＮ環境、又は無線ＬＡＮ接続規格に基づく無線ＬＡＮ環境、例えばＩＥＥＥ８０２．１１ａ／ｂ／ｇ／ｎなどのＷｉ−Ｆｉ無線ＬＡＮ環境、若しくは携帯電話網環境（例えば、３Ｇ、又は４Ｇ（ＬＴＥを含む）環境）でありうる。
【００８７】
コンピュータ（１０１）は、通信回線（１１５）を介して例えば他の装置（例えば、コンピュータ又はネットワーク・アタッチト・ストレージ）からのデータを受信し、記憶装置（１０８）上に格納しうる。
【００８８】
図２、図３及び図４はそれぞれ、本発明の実施態様に従い、ログメッセージからフォーマットを推定する処理を示すためのダイアグラムを示す。
【００８９】
図２に示すダイアグラムは、本発明の実施態様に従い、ログメッセージからフォーマットを推定する処理の第１の例示的態様を示す。
【００９０】
ステップ２０１において、コンピュータ（１０１）は、一つのログメッセージ（２１１）を例えばログメッセージを記憶した記憶媒体（例えば、図１に示す記憶装置（１０８））から取得する。ログメッセージ（２１１）は、「A,BB:CCC」という文字及び記号からなるものとする。コンピュータ（１０１）は、ログメッセージ（２１１）を所定のキャラクタ（例えば、記号又は空白文字）の前後で分割する。ログメッセージ（２１１）を所定のキャラクタの前後で分割した後の文字列は次の通りである：「A」，「,」，「BB」，「:」，「CCC」。コンピュータ（１０１）は、当該分割した各文字列をノードとして、当該ノードそれぞれをログメッセージ（２１１）の先頭から順に並べて、ログメッセージ（２１１）についての有向グラフ構造（２２１）を作成する。
【００９１】
ステップ２０２において、コンピュータ（１０１）は、新たに、一つのログメッセージ（２１２）を例えばログメッセージを記憶した上記記憶媒体から取得する。ログメッセージ（２１２）は、「A,XX  YY:CCC」（「XX」と「YY」との間に空白文字がある）という文字及び記号からなるものとする。コンピュータ（１０１）は、ログメッセージ（２１２）を所定のキャラクタ（例えば、記号又は空白文字）の前後で分割する。ログメッセージ（２１２）を所定のキャラクタの前後で分割した後の文字列は次の通りである：「A」，「,」，「XX」，「YY」，「:」，「CCC」。コンピュータ（１０１）は、当該分割した各文字列をノードとして、当該ノードそれぞれをログメッセージ（２１２）の先頭から順に並べて、ログメッセージ（２１２）についての有向グラフ構造（２２２）を作成する。なお、図２に示す本分割の態様は、空白文字をノードとして扱っていない場合の例を示している。
【００９２】
ステップ２０３において、コンピュータ（１０１）は、ログメッセージ（２１１）からの有向グラフ構造（２２１）中のノードと、ログメッセージ（２１２）からの有向グラフ構造（２２２）中のノードとを比較して、有向グラフ構造（２２１）中のノードと有向グラフ構造（２２２）中のノードとの間で文字列が一致するノードを検出する。コンピュータ（１０１）は、上記比較によって、上記ノード間でノード「A」，「,」，「:」及び「CCC」が一致することを検出する。また、コンピュータ（１０１）は、上記比較によって、上記ノード間で一致しない文字列、すなわち、有向グラフ構造（２２１）中のノード「BB」、並びに、有向グラフ構造（２２２）中のノード「XX」及びノード「YY」を検出する。なお、上記比較において、上記ノード間で一致しない文字列をどのように決定するかについては、図５Ａ及びそれに対応する発明の詳細な説明において詳しく述べる。
【００９３】
引き続き、コンピュータ（１０１）は、上記比較によって、上記ノード間で一致したノード「A」，「,」，「:」及び「CCC」を同一のものとみなし、ログメッセージ（２１１）からの有向グラフ構造（２２１）中のノード「A」，「,」，「:」及び「CCC」それぞれに、ログメッセージ（２１２）からの有向グラフ構造（２２２）中のノード「A」，「,」，「:」及び「CCC」それぞれを統合する。従って、実質的には、ログメッセージ（２１１）からの有向グラフ構造（２２１）中のノード「A」，「,」，「:」及び「CCC」は変更されず、ノード「A」とノード「,」との間のエッジ上の数字、並びに、ノード「:」及びノード「CCC」間のエッジ上の数字がそれぞれ１インクリメントされる。当該ノード間のエッジ上の数字は、ログメッセージ（２１１）からの有向グラフ構造（２２１）のノードと他の有向グラフ構造の対応するノードとが統合した数字を示す。
【００９４】
また、コンピュータ（１０１）は、ログメッセージ（２１１）からの有向グラフ構造（２２１）に対して、ログメッセージ（２１２）からの有向グラフ構造（２２２）中の上記一致しない文字列に関連付けられたノード「XX」及び「YY」を分岐ノードとして追加し、有向グラフ構造（２２３）を作成する（すなわち、有向グラフ構造（２２１）を更新して、有向グラフ構造（２２３）を作成する）。
【００９５】
ステップ２０４において、コンピュータ（１０１）は、２つの有向グラフ構造（２２２）及び有向グラフ構造（２２３）を統合したことに応じて、有向グラフ構造（２２３）のうち分岐ノードを有する閉路（２３１）において、主ノードの文字列と分岐ノードの文字列との出現傾向が類似するかを判断する。すなわち、コンピュータ（１０１）は、主ノード「BB」の文字列と、分岐ノード「XX」及びノード「YY」の文字列との出現傾向が類似するかを判断する。主ノード「BB」と分岐ノード「XX」及びノード「YY」は、閉路（２３１）において、分岐開始直後のノードから分岐したノードが合流する直前までの間に含まれるノードである。コンピュータ（１０１）は、主ノード「BB」の文字列と、分岐ノード「XX」及び分岐ノード「YY」の文字列との出現傾向が類似することに応じて、主ノード「BB」と分岐ノード「XX」及び分岐ノード「YY」とを一つのノード（２３２）に統合する。そして、コンピュータ（１０１）は、上記統合したノード（２３２）に、任意の文字列を示すアスタリスク（*）を当該統合ノードが有する文字列として与えて、有向グラフ構造（２２４）を作成する（すなわち、有向グラフ構造（２２３）を更新して、有向グラフ構造（２２４）を作成する）。
【００９６】
ステップ２０５において、コンピュータ（１０１）は、ステップ２０１及びステップ２０２と同様に、一つのログメッセージ（図示せず）「A,ZZ:CCC」を例えばログメッセージを記憶した記憶媒体（例えば、図１に示す記憶装置（１０８））から取得し、当該取得したログメッセージを所定のキャラクタ（例えば、記号又は空白文字）の前後で分割する。上記取得したログメッセージを所定のキャラクタの前後で分割した後の文字列は次の通りである：「A」，「,」，「ZZ」，「:」，「CCC」。コンピュータ（１０１）は、当該分割した各文字列をノードとして、当該ノードそれぞれを上記取得したログメッセージの先頭から順に並べて、上記取得したログメッセージについての有向グラフ構造（２２５）を作成する。
【００９７】
引き続き、コンピュータ（１０１）は、有向グラフ構造（２２４）中のノードと、有向グラフ構造（２２５）中のノードとを比較して、有向グラフ構造（２２４）中のノードと有向グラフ構造（２２５）中のノードとの間で文字列が一致するノードを検出する。コンピュータ（１０１）は、上記比較によって、上記ノード間でノード「A」，「,」，「:」及び「CCC」が一致することを検出する。また、コンピュータ（１０１）は、上記比較によって、上記ノード間で一致しない文字列、すなわち、有向グラフ構造（２２４）中のノード「*」、並びに、有向グラフ構造（２２５）中のノード「ZZ」を検出する。
【００９８】
また、コンピュータ（１０１）は、有向グラフ構造（２２４）に対して、有向グラフ構造（２２５）中の上記一致しない文字列に関連付けられたノード「ZZ」を分岐ノードとして追加し、有向グラフ構造（２２６）を作成する（すなわち、有向グラフ構造（２２４）を更新して、有向グラフ構造（２２６）を作成する）。
【００９９】
ステップ２０６において、コンピュータ（１０１）は、有向グラフ構造（２２６）のうち分岐ノードを有する閉路（２４１）において、主ノードの文字列と分岐ノードの文字列との出現傾向が類似するかを判断する。すなわち、コンピュータ（１０１）は、主ノード「*」の文字列と、分岐ノード「ZZ」の文字列との出現傾向が類似するかを判断する。コンピュータ（１０１）は、主ノード「*」の文字列と、分岐ノード「ZZ」の文字列との出現傾向が類似することに応じて、主ノード「*」と分岐ノード「ZZ」とを一つのノードに統合する。そして、コンピュータ（１０１）は、上記統合したノードに、任意の文字列を示すアスタリスク（*）を当該統合ノードが有する文字列として与えて、有向グラフ構造（２２７）を作成する（すなわち、有向グラフ構造（２２６）を更新して、有向グラフ構造（２２７）を作成する）。
【０１００】
ステップ２０７において、コンピュータ（１０１）は、有向グラフ構造（２２７）に基づいて、フォーマットを推定する。当該推定されたフォーマット（２２８）は、文字列が一致するノード「A」及び「,」、文字列が一致しないノード「*」、並びに、文字列が一致するノード「:」及び「CCC」を含む。
【０１０１】
図３に示すダイアグラムは、本発明の実施態様に従い、ログメッセージからフォーマットを推定する処理の第２の例示的態様を示す。
【０１０２】
ステップ３０１〜３０３それぞれにおいて行われる処理は、図２Ａに示すステップ２０１〜２０３それぞれにおいて行われる処理と同じである。従って、ステップ３０１〜３０３それぞれについての説明は、ステップ２０１〜２０３それぞれについての上記説明を参照されたい。
【０１０３】
ステップ３０１〜ステップ３０３の処理によって、コンピュータ（１０１）は、有向グラフ構造（３２３）を作成する。
【０１０４】
ステップ３０４において、コンピュータ（１０１）は、ステップ３０１及びステップ３０２と同様に、一つのログメッセージ（図示せず）「A,ZZ:CCC」を例えばログメッセージを記憶した記憶媒体（例えば、図１に示す記憶装置（１０８））から取得し、当該取得したログメッセージを所定のキャラクタ（例えば、記号又は空白文字）の前後で分割する。上記取得したログメッセージを所定のキャラクタの前後で分割した後の文字列は次の通りである：「A」，「,」，「ZZ」，「:」，「CCC」。コンピュータ（１０１）は、当該分割した各文字列をノードとして、当該ノードそれぞれを上記取得したログメッセージの先頭から順に並べて、上記取得したログメッセージについての有向グラフ構造（３２４）を作成する。
【０１０５】
引き続き、コンピュータ（１０１）は、有向グラフ構造（３２３）中のノードと、有向グラフ構造（３２４）中のノードとを比較して、有向グラフ構造（３２３）中のノードと有向グラフ構造（３２４）中のノードとの間で文字列が一致するノードを検出する。コンピュータ（１０１）は、上記比較によって、上記ノード間でノード「A」，「,」，「:」及び「CCC」が一致することを検出する。また、コンピュータ（１０１）は、上記比較によって、上記ノード間で一致しない文字列、すなわち、有向グラフ構造（３２３）中のノード「BB」、「XX」及びノード「YY」、並びに、有向グラフ構造（３２４）中のノード「ZZ」を検出する。
【０１０６】
コンピュータ（１０１）は、上記比較によって、上記ノード間で一致したノード「A」，「,」，「:」及び「CCC」を同一のものとみなし、有向グラフ構造（３２３）中のノード「A」，「,」，「:」及び「CCC」それぞれに、有向グラフ構造（３２４）中のノード「A」，「,」，「:」及び「CCC」それぞれを統合する。従って、実質的には、有向グラフ構造（３２３）中のノード「A」，「,」，「:」及び「CCC」は変更されず、ノード「A」とノード「,」との間のエッジ上の数字、並びに、ノード「:」及びノード「CCC」間のエッジ上の数字がそれぞれ１インクリメントされる。
【０１０７】
また、コンピュータ（１０１）は、有向グラフ構造（３２３）に対して、有向グラフ構造（３２４）中の上記一致しない文字列に関連付けられたノード「ZZ」を分岐ノードとして追加し、有向グラフ構造（３２５）を作成する（すなわち、有向グラフ構造（３２３）を更新して、有向グラフ構造（３２５）を作成する）。
【０１０８】
ステップ３０５において、コンピュータ（１０１）は、３つの有向グラフ構造（３２１，３２２，及び３２４）を統合したことに応じて、ステップ３０６で作成された有向グラフ構造（３２５）中に複数の閉路がある場合、当該複数の閉路のうち分岐ノードを有する閉路のうちの内包されるより小さい閉路（３３１）において、主ノードの文字列と分岐ノードの文字列との出現傾向が類似するかを判断する。すなわち、コンピュータ（１０１）は、主ノード「BB」の文字列と、分岐ノード「XX」及びノード「YY」の文字列との出現傾向が類似するかを判断する。コンピュータ（１０１）は、主ノード「BB」の文字列と、分岐ノード「XX」及び分岐ノード「YY」の文字列との出現傾向が類似することに応じて、主ノード「BB」と分岐ノード「XX」及び分岐ノード「YY」とを一つのノード（３３２）に統合する。そして、コンピュータ（１０１）は、上記統合したノード（３３２）に、任意の文字列を示すアスタリスク（*）を当該統合ノードが有する文字列として与えて、有向グラフ構造（３２６）を作成する（すなわち、有向グラフ構造（３２５）を更新して、有向グラフ構造（３２６）を作成する）。
【０１０９】
ステップ３０６において、コンピュータ（１０１）は、有向グラフ構造（３２６）のうち分岐ノードを有する閉路（３４１）において、主ノードの文字列と分岐ノードの文字列との出現傾向が類似するかを判断する。すなわち、コンピュータ（１０１）は、主ノード「*」の文字列と、分岐ノード「ZZ」の文字列との出現傾向が類似するかを判断する。コンピュータ（１０１）は、主ノード「*」の文字列と、分岐ノード「ZZ」の文字列との出現傾向が類似することに応じて、主ノード「*」と分岐ノード「ZZ」とを一つのノード（３４２）に統合する。そして、コンピュータ（１０１）は、上記統合したノード（３４２）に、任意の文字列を示すアスタリスク（*）を当該統合ノードが有する文字列として与えて、有向グラフ構造（３２７）を作成する（すなわち、有向グラフ構造（３２６）を更新して、有向グラフ構造（３２７）を作成する）。
【０１１０】
ステップ３０７において、コンピュータ（１０１）は、有向グラフ構造（３２７）に基づいて、フォーマットを推定する。当該推定されたフォーマット（３２９）は、文字列が一致するノード「A」及び「,」、文字列が一致しないノード「*」、並びに、文字列が一致するノード「:」及び「CCC」を含む。
【０１１１】
図４に示すダイアグラムは、本発明の実施態様に従い、ログメッセージからフォーマットを推定する処理の第３の例示的態様を示す。
【０１１２】
ステップ４０１〜４０３それぞれにおいて行われる処理は、図２Ａに示すステップ２０１〜２０３それぞれにおいて行われる処理と同じである。従って、ステップ４０１〜４０３それぞれについての説明は、ステップ２０１〜２０３それぞれについての上記説明を参照されたい。
【０１１３】
ステップ４０１〜ステップ４０３の処理によって、コンピュータ（１０１）は、有向グラフ構造（４２３）を作成する。
【０１１４】
ステップ４０４において、コンピュータ（１０１）は、ステップ４０１及びステップ４０２と同様に、一つのログメッセージ（図示せず）「A, XX  YY:CCC」（「XX」と「YY」との間に空白文字がある）を例えばログメッセージを記憶した記憶媒体（例えば、図１に示す記憶装置（１０８））から取得し、当該取得したログメッセージを所定のキャラクタ（例えば、記号又は空白文字）の前後で分割する。上記取得したログメッセージを所定のキャラクタの前後で分割した後の文字列は次の通りである：「A」，「,」，「XX」，「YY」，「:」，「CCC」。コンピュータ（１０１）は、当該分割した各文字列をノードとして、当該ノードそれぞれを上記取得したログメッセージの先頭から順に並べて、上記取得したログメッセージについての有向グラフ構造（４２４）を作成する。
【０１１５】
引き続き、コンピュータ（１０１）は、有向グラフ構造（４２３）中のノードと、有向グラフ構造（４２４）中のノードとを比較して、有向グラフ構造（４２３）中のノードと有向グラフ構造（４２４）中のノードとの間で文字列が一致するノードを検出する。コンピュータ（１０１）は、上記比較によって、上記ノード間でノード「A」，「,」，「:」及び「CCC」が一致することを検出する。また、コンピュータ（１０１）は、上記比較によって、上記ノード間で有向グラフ構造（４２３）中の分岐ノード「XX」と、有向グラフ構造（４２４）中のノード「XX」とが一致することを検出する。また、コンピュータ（１０１）は、上記比較によって、上記ノード間で一致しない文字列、すなわち、有向グラフ構造（４２３）中のノード「BB」、並びに、有向グラフ構造（４２４）中のノード「YY」及びノード「ZZ」を検出する。
【０１１６】
コンピュータ（１０１）は、上記比較によって、上記ノード間で一致したノード「A」，「,」，「:」及び「CCC」を同一のものとみなし、有向グラフ構造（４２３）中のノード「A」，「,」，「:」及び「CCC」それぞれに、有向グラフ構造（４２４）中のノード「A」，「,」，「:」及び「CCC」それぞれを統合する。従って、実質的には、有向グラフ構造（４２３）中のノード「A」，「,」，「:」及び「CCC」は変更されず、ノード「A」とノード「,」との間のエッジ上の数字、並びに、ノード「:」及びノード「CCC」間のエッジ上の数字がそれぞれ１インクリメントされる。
【０１１７】
また、コンピュータ（１０１）は、有向グラフ構造（４２３）中の分岐ノードに対して、有向グラフ構造（４２２）中の上記一致しない文字列に関連付けられたノード「ZZ」を分岐ノードとしてさらに追加し、有向グラフ構造（４２５）を作成する（すなわち、有向グラフ構造（４２３）を更新して、有向グラフ構造（４２５）を作成する）。
【０１１８】
ステップ４０５において、コンピュータ（１０１）は、３つの有向グラフ構造（４２１，４２２，及び４２４）を統合したことに応じて、ステップ４０４で作成された有向グラフ構造（４２５）中に複数の閉路がある場合、当該複数の閉路のうち分岐ノードを有する閉路のうちの内包されるより小さい閉路（４３１）において、ノード「YY」の文字列と、分岐ノード「ZZ」の文字列との出現傾向が類似するかを判断する。コンピュータ（１０１）は、ノード「YY」の文字列と、分岐ノード「ZZ」の文字列との出現傾向が類似することに応じて、ノード「YY」と分岐ノード「ZZ」とを一つのノード（４３２）に統合する。そして、コンピュータ（１０１）は、上記統合したノード（４３２）に、任意の文字列を示すアスタリスク（*）を当該統合ノードが有する文字列として与えて、有向グラフ構造（４２６）を作成する（すなわち、有向グラフ構造（４２５）を更新して、有向グラフ構造（４２６）を作成する）。
【０１１９】
ステップ４０６において、コンピュータ（１０１）は、有向グラフ構造（４２６）のうち分岐ノードを有する閉路（４４１）において、主ノードの文字列と分岐ノードの文字列との出現傾向が類似するかを判断する。すなわち、コンピュータ（１０１）は、主ノード「BB」の文字列と、分岐ノード「XX」及び分岐ノード「*」の文字列との出現傾向が類似するかを判断する。コンピュータ（１０１）は、主ノード「BB」の文字列と、分岐ノード「XX」及び分岐ノード「*」の文字列の文字列との出現傾向が類似していないことに応じて、有向グラフ構造（４２６）に対して変更を加えない。
【０１２０】
引き続き、コンピュータ（１０１）は、有向グラフ構造（４２６）に基づいて、２つのフォーマットを推定する。当該推定されたフォーマット（４２７）は、文字列が一致するノード「A」及び「,」、文字列が一致しないノードであって、文字列の出現傾向が類似する上記ノード以外のノード「BB」、並びに、文字列が一致するノード「:」及び「CCC」を含む。また、当該推定されたフォーマット（４２８）は、文字列が一致するノード「A」及び「,」、文字列が一致しないノードであって、文字列の出現傾向が類似するノード以外のノード「XX」、文字列が一致しないノードであって、文字列の出現傾向が類似するノード「*」、並びに、文字列が一致するノード「:」及び「CCC」を含む。
【０１２１】
図５Ａは、本発明の実施態様に従い、ログメッセージからフォーマットを推定する処理において、既存の有向グラフ構造に対して部分的に一致するノードが最も多くなる部分グラフとパスを探索する処理を示すためのダイアグラムを示す。
【０１２２】
有向グラフ構造（２２１）は、図２に示すステップ２０１において作成されたものである。また、有向グラフ構造（２２２）は、図２に示すステップ２０２において作成されたものである。有向グラフ構造（２２１）は、有向グラフ構造（２２２）よりも先に作成されているので、既存の有向グラフ構造である。
【０１２３】
コンピュータ（１０１）は、図２に示すステップ２０３において、有向グラフ構造（２２１）中のノードと、有向グラフ構造（２２２）中のノードとを比較して、有向グラフ構造（２２１）中のノードと有向グラフ構造（２２２）中のノードとの間で文字列が一致するノードを検出する。
【０１２４】
コンピュータ（１０１）は、有向グラフ構造（２２１，２２２）それぞれの先頭ノードから上記比較を行うことよって、上記ノード間でノード「A」及び「,」（５０１）が一致することを検出する。
【０１２５】
次に、コンピュータ（１０１）は、上記比較によって、一致しない部分（５０２）が現れることに応じて、有向グラフ構造（２２１）中の部分的に一致するノードが最も多くなる部分グラフ及びパスを探索する。コンピュータ（１０１）は、有向グラフ構造（２２１）中のノード「BB」，「:」及び「CCC」、並びに、有向グラフ構造（２２２）中のノード「XX」，「YY」，「:」及び「CCC」について、図５Ａに示す全てのノードの組み合わせ（５１１，５１２，５１３及び５１４）をリストし、ノードが一致する数が最も多くなる組み合わせを検索する。その結果、コンピュータ（１０１）は、上記組み合わせ（５１２）において、２つのノード「:」及びノード「CCC」が一致することから、有向グラフ構造（２２１）中のノード「BB」、並びに、有向グラフ構造（２２２）中のノード「XX」及びノード「YY」が一致しない文字列を有することを検出する。また、コンピュータ（１０１）は、上記組み合わせ（５１２）において、ノード「:」及びノード「CCC」が上記ノード間でさらに一致するノードであることを検出する。
【０１２６】
以上の通りであるので、コンピュータ（１０１）は、上記比較によって、上記ノード間でノード「A」，「,」，「:」及び「CCC」が一致することを検出し、且つ、上記ノード間で一致しない文字列、すなわち、有向グラフ構造（２２１）中のノード「BB」、並びに、有向グラフ構造（２２２）中のノード「XX」及びノード「YY」を検出する。
【０１２７】
図５Ａに示す有向グラフ構造（２２１）及び有向グラフ構造（２２２）の例では、分岐構造を有していない場合における探索を示した。コンピュータ（１０１）は、有向グラフ構造中に分岐構造がある場合には、当該分岐ノードを有する部分グラフ及びパスの全てについて探索を行う。
【０１２８】
なお、コンピュータ（１０１）は、有向グラフ構造（２２１）中の部分的に一致するノードが最も多くなる部分グラフ及びパスを探索するが、従来の単純な探索順序の処理方法では、当該コンピュータ（１０１）計算量が大幅に増えてしまう。そこで、下記図５Ｂにおいて説明するように、コンピュータ（１０１）は、メモ化再帰の技術を適用した探索順序の処理方法を用いて、有向グラフ構造（２２１）中の部分的に一致するノードが最も多くなる部分グラフ及びパスを探索しうる。
【０１２９】
図５Ｂは、本発明の実施態様に従い、ログメッセージからフォーマットを推定する処理において、メモ化再帰の技術を用いてパスを探索するためのダイアグラムを示す。
【０１３０】
コンピュータ（１０１）は、例えば図２に示すステップ２０３の処理、すなわち、有向グラフ構造（２２１）中のノードと、有向グラフ構造（２２２）中のノードとを比較して、有向グラフ構造（２２１）中のノードと有向グラフ構造（２２２）中のノードとの間で文字列が一致するノードを検出する処理において、有向グラフ構造に関わらず、全てのノードと接続する可能性を試さなくてはならない。図２に示すステップ２０５、図３に示すステップ３０３及びステップ３０４、並びに、図４に示すステップ４０３及びステップ４０４においても同様に、有向グラフ構造に関わらず、全てのノードと接続する可能性を試さなくてはならない。
【０１３１】
図５Ｂ上段に示す探索順序の処理方法は従来の探索順序の処理方法を示す。コンピュータ（１０１）は、入力されたログメッセージから作成された有向グラフ構造（５２１）中のノードを、構築済みの有向グラフ構造（５２２）中のノードと比較する。コンピュータ（１０１）は、従来の探索順序の処理方法に従うと、まず矢印（５３１）に沿って全てのノードを探索し、次に、矢印（５３２）に沿って全てのノードを探索する。従って、コンピュータ（１０１）は、既に探索済みの経路であっても、繰り返し探索を行うために効率が悪い。また、従来の探索順序の処理方法に従うと、計算量は、既存のノード数ｎ及び入力されたログメッセージＬに対して、Ｏ（Ｌｎ）相当になってしまう。
【０１３２】
図５Ｂ下段に示す探索順序の処理方法はメモ化再帰の技術を適用した探索順序の処理方法を示す。コンピュータ（１０１）は、入力されたログメッセージから作成された有向グラフ構造（５２１）中のノードを、構築済みの有向グラフ構造（５２２）中のノードと比較する。コンピュータ（１０１）は、メモ化再帰（メモ化ともいう）を適用した探索順序の処理方法に従うと、最初に、矢印（５４１）に沿って全てのノードを最後まで探索し、その探索結果をメモに記録する。当該メモは、どのノード同士を比較したのかという記録と、その結果を記録したものである。次に、コンピュータ（１０１）は、矢印（５４２）に沿ってノードを探索する。しかし、コンピュータ（１０１）は、上記最初の探索で作成したメモを参照し、２度目以降の探索において当該メモ中に上記比較の記録がなければ探索を続け、一方当該メモ中に上記比較の結果の記録（例えば、ノードＹ１とノードＹ２との組み合わせでその先のノード間の比較の結果の記録）がある場合には、例えばノードＹ２からＣへのパスはすでに矢印（５４１）に示す探索において既に探索済みであるので、一度探索したパスであるノードＹ２からＣへの探索を行わずに、上記メモの探索結果を読み込む。従って、メモ化再帰の技術を適用した探索順序の処理方法に従うと、一度探索したパスを再度探索しないですむことによって、空間計算量がＯ（Ｌ・ｎ）とより多く必要とされる代わりに、時間計算量がＯ（Ｌ・ｎ２）程度に抑制される。
【０１３３】
図５Ｃは、本発明の実施態様に従い、ログメッセージからフォーマットを推定する処理において、文字列の出現傾向が類似するノードを検出ためのダイアグラムを示す。
【０１３４】
有向グラフ構造（４２５）は、図４に示すステップ４０４において作成されたものである。
【０１３５】
コンピュータ（１０１）は、図４に示すステップ４０５において、有向グラフ構造（４２５）中に複数の閉路が包含関係にある場合、当該複数の閉路のうち分岐ノードを有する閉路のうちの内包されるより小さい閉路（４３１）において、ノード「YY」の文字列と、分岐ノード「ZZ」の文字列との出現傾向が類似するかを判断する。コンピュータ（１０１）は、ノード「YY」の文字列と、分岐ノード「ZZ」の文字列との出現傾向が類似することに応じて、ノード「YY」と分岐ノード「ZZ」とを一つのノード（４３２）に統合する。そして、コンピュータ（１０１）は、上記統合したノード（４３２）に、任意の文字列を示すアスタリスク（*）を当該統合ノードが有する文字列として与えて、有向グラフ構造（４２６）を作成する。
【０１３６】
コンピュータ（１０１）は、文字列の出現傾向が類似するかどうかを例えば、以下に示す事項に基づいて判断しうる：
（１）文字種別が類似する文字列が所定の割合以上であること；
（２）文字長さが所定の長さ以上であること；若しくは、
（３）文字の編集距離が近いこと；又は、
（４）（１）〜（３）の少なくとも２つの組み合わせ。
【０１３７】
（１）文字種別が類似する文字列が所定の割合以上であること
上記文字列は例えば、英字若しくは数字、又は、漢字、平仮名若しくは片仮名などでありうる。例えば、統計情報などの数値、又は、ユーザ名若しくはホスト名などの識別情報といったパラメータとして取り扱われるものの多くは、出現する文字種別が類似する傾向にある為に、文字列が所定の割合以上になりやすい傾向がある。所定の割合は、ログメッセージの解析者が任意に設定しうる。
【０１３８】
（２）文字長さが所定の長さ以上であること
文字長さは例えば、半角での文字長さ若しくは全角での文字長さ、又は、それらの組み合わせの文字長さでありうる。文字長さは例えば、平均文字長さとして設定しうる。平均文字長さは例えば、１．５文字のように生の整数でなくともよい。所定の長さは、ログメッセージの解析者が任意に設定しうる。
【０１３９】
（３）文字の編集距離が近いこと
文字の編集距離は例えば、編集距離（レーベンシュタイン距離とも呼ばれる）とも呼ばれる手法に従って算出されうる。例えば、文字列１「abcde」、文字列２「abdce」及び文字列３「aedcb」があった場合には、文字列１と文字列２の方が文字列２と文字列３の方よりも編集距離（すなわち、順序である）が近いということが出来る為に、文字列１と文字列２の方が文字列２と文字列３の方よりもより類似していると捉えることが可能である。
【０１４０】
また、設定によっては、文字列の出現傾向を無条件に一致させるようにすることも可能である。このように、文字列の出現傾向を無条件に一致させることは、ログメッセージの例えば利用者が既知の情報として「ここは可変部になる」ということを明示的に指定したい場合に、そのような指定を可能にすることで、完全に機械的な推定をするのでなく、当該利用者の知見も利用できるというメリットをもたらす。
【０１４１】
次に、コンピュータ（１０１）は、有向グラフ構造（４２６）中にさらに閉路がある場合、当該閉路中のノードについて、文字列の出現傾向が類似するかを再帰的に判断する。すなわち、コンピュータ（１０１）は、有向グラフ構造（４２６）のうち分岐ノードを有する閉路（４４１）において、主ノード「BB」の文字列と、分岐ノード「XX」及び分岐ノード「*」の文字列との出現傾向が類似するかを判断する。主ノード「BB」と分岐ノード「XX」及び分岐ノード「*」は、閉路（４４１）において、分岐開始直後のノードから分岐したノードが合流する直前までの間に含まれるノードである。
【０１４２】
コンピュータ（１０１）は、主ノード「BB」の文字列と、分岐ノード「XX」及び分岐ノード「*」の文字列の文字列との出現傾向が類似していないことに応じて、有向グラフ構造（４２６）に対して変更を加えない。引き続き、コンピュータ（１０１）は、有向グラフ構造（４２６）に基づいて、２つのフォーマット（４２７及び４２８）を推定する。
【０１４３】
一方、コンピュータ（１０１）は、主ノード「BB」の文字列と、分岐ノード「XX」及び分岐ノード「*」の文字列の文字列との出現傾向が類似していることに応じて、主ノード「BB」と分岐ノード「XX」及び分岐ノード「*」とを一つのノード（４５１）に統合する。そして、コンピュータ（１０１）は、上記統合したノード（４５１）に、任意の文字列を示すアスタリスク（*）を当該統合ノードが有する文字列として与えて、有向グラフ構造（４６１）を作成する。引き続き、コンピュータ（１０１）は、有向グラフ構造（４６１）に基づいて、フォーマットを推定する。当該推定されたフォーマット（４６２）は、文字列が一致するノード「A」及び「,」、文字列が一致しないノード「*」、並びに、文字列が一致するノード「:」及び「CCC」を含む。
【０１４４】
図５Ｄは、本発明の実施態様に従い、ログメッセージからフォーマットを推定する処理において、文字列の出現傾向が類似するノードを検出ためのダイアグラムを示す。
【０１４５】
ステップ５５１に示す有向グラフ構造（２２３）は、図２のステップ２０１〜２０３に示す処理を経て作成されたものである。従って、有向グラフ構造（２２３）の作成方法については、図２のステップ２０１〜２０３の説明を参照されたい。
【０１４６】
ステップ５５１において、コンピュータ（１０１）は、２つの有向グラフ構造を統合したことに応じて、有向グラフ構造（２２３）のうち分岐ノードを有する閉路において、主ノード「BB」の文字列と分岐ノード「XX」及びノード「YY」の文字列との出現傾向が類似するかを判断する。コンピュータ（１０１）は、主ノード「BB」の文字列と、分岐ノード「XX」及び分岐ノード「YY」の文字列との出現傾向が類似することに応じて、主ノード「BB」と分岐ノード「XX」及び分岐ノード「YY」とを一つのノードに統合する。そして、コンピュータ（１０１）は、上記統合したノードに、任意の文字列を示すアスタリスク（*）を当該統合ノードが有する文字列として与えて、有向グラフ構造（２２４）を作成する。
【０１４７】
ステップ５５２において、コンピュータ（１０１）は、有向グラフ構造（２２４）をオートマトン（５６１）として出力し、例えばオートマトンを記憶する記憶媒体（例えば、図１に示す記憶装置（１０８））に格納する。
【０１４８】
ステップ５５３において、コンピュータ（１０１）は、図２のステップ２０１〜２０２に示すステップ２０１及びステップ２０２と同様に、一つのログメッセージ（図示せず）「A,F  G  H:CCC」(「F」と「G」との間及び「G」と「H」との間にそれぞれ空白文字がある）を例えばログメッセージを記憶した記憶媒体（例えば、図１に示す記憶装置（１０８））から取得し、当該取得したログメッセージを所定のキャラクタ（例えば、記号又は空白文字）の前後で分割する。上記取得したログメッセージを所定のキャラクタの前後で分割した後の文字列は次の通りである：「A」，「,」，「F」，「G」，「H」，「:」，「CCC」。コンピュータ（１０１）は、当該分割した各文字列をノードとして、当該ノードそれぞれを上記取得したログメッセージの先頭から順に並べて、上記取得したログメッセージについての有向グラフ構造（５７１）を作成する。
【０１４９】
引き続き、コンピュータ（１０１）は、オートマトン（５６１）中のノードと、有向グラフ構造（５７１）中のノードとを比較して、有向グラフ構造（５７１）中のノードがオートマトン（５６１）中のノードと一致するかを判断する。コンピュータ（１０１）は、上記比較によって、上記ノード間でノード「A」，「,」，「:」及び「CCC」が一致することを検出する。また、コンピュータ（１０１）は、上記比較によって、有向グラフ構造（５７１）中のノード（「F」，「G」，及び「H」）がオートマトン（５６１）中のノード（「*」）と一致しないことを検出する。次に、コンピュータ（１０１）は、有向グラフ構造（５７１）中のノード（「F」，「G」，及び「H」）の文字列とオートマトン（５６１）中のノード（「*」）の文字列との出現傾向が類似するかを判断する。コンピュータ（１０１）は、文字列（「F」，「G」，及び「H」）が文字列「*」の出現傾向が類似するかどうかを例えば、文字列「*」を任意の文字列とするだけでなく、文字列「*」に統合する前の文字列（「BB」，「XX」，及び「YY」）の例えば文字種別若しくは文字長さ又は文字の編集距離に応じて判断しうる。コンピュータ（１０１）は、上記出現傾向が類似することに応じて、有向グラフ構造（５７１）中のノード（「F」，「G」，及び「H」）の文字列とオートマトン（５６１）中のノード（「*」）の文字列とが一致するものとみなして取り扱うことができる。一方、コンピュータ（１０１）は、上記出現傾向が類似しないことに応じて、有向グラフ構造（５７１）中のノード（「F」，「G」，及び「H」）の文字列とオートマトン（５６１）中のノード（「*」）の文字列とが一致しないものとみなして取り扱うことができる。
【０１５０】
コンピュータ（１０１）は、有向グラフ構造（５７１）中のノードがオートマトン（５６１）中のノードと一致することに応じて、有向グラフ構造（２２４）を変更しない。一方、コンピュータ（１０１）は、有向グラフ構造（５７１）中のノードがオートマトン（５６１）中のノードと一致しないことに応じて、有向グラフ構造（２２４）に対して、一致しないノードを分岐ノードとして追加する処理に進める。
【０１５１】
コンピュータ（１０１）は、有向グラフ構造（５７１）中のノードがオートマトン（５６１）中のノードと一致しない場合に、一致しないノードに従って例えば以下に示す４種類の有向グラフ構造（５８１，５８２，５８３及び５８４）を生成しうる。
【０１５２】
有向グラフ構造（５８１）は、オートマトン（５６１）中のノード「A」，「,」，「:」，「CCC」が有向グラフ構造（５７１）中の対応するノードと一致し、且つ、オートマトン（５６１）中のノード「*」の文字列と有向グラフ構造（５７１）中のノード「G」及び「H」の文字列の出現頻度が類似する場合に有向グラフ構造（２２４）から生成されるものであり、分岐ノード「F」は上記文字列の出現頻度が類似するノード以外のノードである。
【０１５３】
有向グラフ構造（５８２）は、オートマトン（５６１）中のノード「A」，「,」，「:」，「CCC」が有向グラフ構造（５７１）中の対応するノードと一致し、且つ、オートマトン（５６１）中のノード「*」の文字列と有向グラフ構造（５７１）中のノード「H」の文字列の出現頻度が類似する場合に有向グラフ構造（２２４）から生成されるものであり、分岐ノード「F」及び「G」は上記文字列の出現頻度が類似するノード以外のノードである。
【０１５４】
有向グラフ構造（５８３）は、オートマトン（５６１）中のノード「A」，「,」，「:」，「CCC」が有向グラフ構造（５７１）中の対応するノードと一致し、且つ、オートマトン（５６１）中のノード「*」の文字列と有向グラフ構造（５７１）中のノード「F」の文字列の出現頻度が類似する場合に有向グラフ構造（２２４）から生成されるものであり、分岐ノード「G」及び「H」は上記文字列の出現頻度が類似するノード以外のノードである。
【０１５５】
有向グラフ構造（５８４）は、オートマトン（５６１）中のノード「A」，「,」，「:」，「CCC」が有向グラフ構造（５７１）中の対応するノードと一致し、且つ、オートマトン（５６１）中のノード「*」の文字列と有向グラフ構造（５７１）中のノード「F」及び「G」の文字列の出現頻度が類似する場合に有向グラフ構造（２２４）から生成されるものであり、分岐ノード「H」は上記文字列の出現頻度が類似するノード以外のノードである。
【０１５６】
ステップ５５４において、コンピュータ（１０１）は、有向グラフ構造（５８１，５８２，５８３，又は５８４）に基づいて、１又は複数のフォーマットを推定しうる。以下では、向グラフ構造（５８１，５８２，５８３，又は５８４）に基づいて、２つのフォーマットを推定した場合について説明する。
【０１５７】
有向グラフ構造（５８１）に基づいて推定されたフォーマット（５９１）は、文字列が一致するノード「A」及び「,」、文字列の出現傾向が類似するノード「*」、並びに、文字列が一致するノード「:」及び「CCC」を含む。また、有向グラフ構造（５８１）に基づいて推定されたフォーマット（５９２）は、文字列が一致するノード「A」及び「,」、文字列が一致しないノードであって、文字列の出現傾向が類似するノード以外のノード「F」、文字列の出現傾向が類似するノード「*」、並びに、文字列が一致するノード「:」及び「CCC」を含む。
【０１５８】
有向グラフ構造（５８２）に基づいて推定されたフォーマット（５９３）は、文字列が一致するノード「A」及び「,」、文字列の出現傾向が類似するノード「*」、並びに、文字列が一致するノード「:」及び「CCC」を含む。また、有向グラフ構造（５８２）に基づいて推定されたフォーマット（５９４）は、文字列が一致するノード「A」及び「,」、文字列が一致しないノードであって、文字列の出現傾向が類似するノード以外のノード「F」及び「G」、文字列の出現傾向が類似するノード「*」、並びに、文字列が一致するノード「:」及び「CCC」を含む。
【０１５９】
有向グラフ構造（５８３）に基づいて推定されたフォーマット（５９５）は、文字列が一致するノード「A」及び「,」、文字列の出現傾向が類似するノード「*」、並びに、文字列が一致するノード「:」及び「CCC」を含む。また、有向グラフ構造（５８３）に基づいて推定されたフォーマット（５９６）は、文字列が一致するノード「A」及び「,」、文字列の出現傾向が類似するノード「*」、文字列が一致しないノードであって、文字列の出現傾向が類似するノード以外のノード「G」及び「H」、並びに、文字列が一致するノード「:」及び「CCC」を含む。
【０１６０】
有向グラフ構造（５８４）に基づいて推定されたフォーマット（５９７）は、文字列が一致するノード「A」及び「,」、文字列の出現傾向が類似するノード「*」、並びに、文字列が一致するノード「:」及び「CCC」を含む。また、有向グラフ構造（５８４）に基づいて推定されたフォーマット（５９８）は、文字列が一致するノード「A」及び「,」、文字列の出現傾向が類似するノード「*」、文字列が一致しないノードであって、文字列の出現傾向が類似するノード以外のノード「H」、並びに、文字列が一致するノード「:」及び「CCC」を含む。
【０１６１】
図６Ａは、本発明の実施態様において、ログメッセージを有向グラフ構造で可視化したものを示す。
【０１６２】
有向グラフ構造（６０１）は、本発明の実施態様に従い、複数のログメッセージから作成された個々の有向グラフ構造を文字列が一致するノードで統合した後の有向グラフ構造の一部を示したものであり、しかし、文字列の出現傾向が類似するノードの統合を実施していない状態のものである。有向グラフ構造（６０１）中、例えばノード（６１１）からノード（６２１）へのエッジ上の数字２３は、ノード（６１１）からノード（６２１）へのパスを有する有向グラフ構造が２３個統合されていることを意味する。
【０１６３】
有向グラフ構造（６０１）において、ノード（６１１）は閉路の起点ノードであり、ノード（６７１）は当該閉路の終点ノードであり、当該閉路内に複数の閉路がある。有向グラフ構造（６０１）中、各ノード（６２１，６３１，６４１〜６４８）は、ＵＲＬを含むログメッセージに基づく起点ノードから終点ノードまでの各パス上にある一つのノードである。また、有向グラフ構造（６０１）中、ノード（６５１）は、システムのエラーメッセージに基づく起点ノードから終点ノードまでの一つのパス上にある一つのノードである。また、有向グラフ構造（６０１）中、ノード（６６１〜６６６）は、システムのエラーメッセージに基づく起点ノードから終点ノードまでの一つのパス上にある複数のノードである。有向グラフ構造（６０１）では、上記したとおり、起点ノードから終点ノードまでの各パス上に、１又は複数の異なる数のノードがともに存在するように、ログメッセージが所定のキャラクタの前後で分割されている。
【０１６４】
図６Ｂは、本発明の実施態様に従い、図６Ａに示す有向グラフ構造において、ノード間で文字列の出現傾向が類似するノードを統合し簡略化した後の有向グラフ構造の例を示す。
【０１６５】
有向グラフ構造（６０２）において、ノード（６８１）は、図６Ａに示す１０個のノード（６２１，６３１，及び６４１〜６４８）を文字列の出現傾向が類似するノードとして統合した後のノードであり、且つ、ノード（６８２）は、図６Ａに示す７個のノード（６５１，及び６６１〜６６６）を文字列の出現傾向が類似するノードとして統合した後のノードである。
【０１６６】
図７Ａは、本発明の実施態様において、ログメッセージを有向グラフ構造で可視化したものを示す。
【０１６７】
有向グラフ構造（７０１）は、本発明の実施態様に従い、複数のログメッセージから作成された個々の有向グラフ構造を、文字列が一致するノードで統合した後の有向グラフ構造の一部を示したものであり、しかし、文字列の出現傾向が類似するノードの統合を実施していない状態のものである。
【０１６８】
有向グラフ構造（７０１）は、ログメッセージ中の一部である「Feb  25  XX:XX:XX」（XXは、可変数値を示す）を有向グラフ構造として可視化したものである。
【０１６９】
有向グラフ構造（７０１）は、３つの閉路（７３１，７３２，及び７３３）を有する。閉路（７３１）は、起点ノード（７１２）及び終点ノード（７１５）を有し、起点ノード（７１２）から終点ノード（７１５）までの各パス上に一つの各ノード（７１３，及び７１４）を有する。閉路（７３２）は、起点ノード（７１５）及び終点ノード（７２０）を有し、起点ノード（７１５）から終点ノード（７２０）までの各パス上に一つの各ノード（７１６，７１７，７１８，及び７１９）を有する。閉路（７３３）は、起点ノード（７２０）及び終点ノード（７２７）を有し、起点ノード（７２０）から終点ノード（７２７）までの各パス上に一つの各ノード（７２１，７２２，７２３，７２４，７２５，及び７２６）を有する。
【０１７０】
図７Ｂは、本発明の実施態様に従い、図７Ａに示す有向グラフ構造において、ノード間で文字列の出現傾向が類似するノードを統合し簡略化した後の有向グラフ構造の例を示す。
【０１７１】
有向グラフ構造（７０２）において、ノード（７４１）は、図７Ａに示す２のノード（７１３及び７１４）を文字列の出現傾向が類似するノードとして統合した後のノードであり、ノード（７４２）は、図７Ａに示す４個のノード（７１６，７１７，７１８，及び７１９）を文字列の出現傾向が類似するノードとして統合した後のノードであり、且つ、ノード（７４３）は、図７Ａに示す６個のノード（７２１，７２２，７２３，７２４，７２５，及び７２６）を文字列の出現傾向が類似するノードとして統合した後のノードである。
【０１７２】
図８Ａは、本発明の実施態様において、ログメッセージを有向グラフ構造で可視化したものを示す。
【０１７３】
有向グラフ構造（８０１）は、本発明の実施態様に従い、複数のログメッセージから作成された個々の有向グラフ構造を、文字列が一致するノードで統合した後の有向グラフ構造の一部を示したものであり、しかし、文字列の出現傾向が類似するノードの統合を実施していない状態のものである。
【０１７４】
有向グラフ構造（８０１）は、ログメッセージが自然言語を含む場合において、当該自然言語的な出力内容でも複数回全く同じものが出力されることで、ノードが分離されることを示す。また、有向グラフ構造（８０１）中、点線部分で示す部分（Ａ，Ｂ，Ｃ，及びＤ）はそれぞれ、パス上で連続しているノード群を示す。
【０１７５】
図８Ｂは、本発明の実施態様に従い、図８Ａに示す有向グラフ構造において、ノード間で文字列の出現傾向が類似するノードを統合し簡略化した後の有向グラフ構造の例を示す。
【０１７６】
有向グラフ構造（８０２）において、ノード（８８１）は、図８Ａに示す２つのノード（８４２及び８５１）を文字列の出現頻度が類似するノードとして統合した後のノードであり、且つ、ノード（８８１）は、図８Ａに示す６個のノード（８６１，８６２，及び８６３、並びに、８７１，８７２，及び８７３）を文字列の出現頻度が類似するノードとして統合した後のノードである。
【０１７７】
図９Ａ〜図９Ｃは、本発明の実施態様に従い、ログメッセージからフォーマットを推定する処理を示すフローチャートである。
【０１７８】
図９Ａは、ログメッセージからフォーマットを推定する処理の為のメイン・フローチャートを示す。
【０１７９】
ステップ９０１において、コンピュータ（１０１）は、ログメッセージからフォーマットを推定する処理を開始する。
【０１８０】
ステップ９０２において、コンピュータ（１０１）は、これ以上入力するログメッセージがあるかを判断する。コンピュータ（１０１）は、入力するログメッセージがあることに応じて、処理をステップ９０３に進める。一方、コンピュータ（１０１）は、これ以上入力するログメッセージがないことに応じて、処理をステップ９１２に進める。
【０１８１】
コンピュータ（１０１）は、上記ログメッセージを、例えばログメッセージを記憶した記憶媒体（例えば、図１に示す記憶装置（１０８））から取得したり、又は、ログメッセージを生成するアプリケーションから取得したりしうる。
【０１８２】
ステップ９０３において、コンピュータ（１０１）は、ステップ９０２で入力したログメッセージを所定のキャラクタの前後で分割する。当該所定のキャラクタは例えば、記号又は空白文字でありうる。当該記号は例えば、  ［  ，］  ，「  ，  」  ，  “，  ”  ，  ：  ，  ；  ，＝  ，  ＞  ，  及び  ＜  （全角又は半角でありうる）でありうるが、これらに限定されるものでない。空白文字は例えば、全角又は半角のスペース文字でありうる。
【０１８３】
上記分割されたログメッセージは例えば、式  S={s0，s1，... }で表されうる。当該式において、各部分は、{s0}，{s1}，... である。各部分の文字列は例えば、英字、数字、又は２バイト文字（例えば、漢字、平仮名若しくはカタカナ）でありうる。また、各部分の文字列の数は、１又は複数でありうる。
【０１８４】
コンピュータ（１０１）は、上記分割されたログメッセージの各部分  {s0}，{s1}，... をそれぞれノードとし、当該ノードそれぞれを、上記ログメッセージの先頭から順に並べて、有向グラフ構造を作成する。コンピュータ（１０１）は、上記有向グラフ構造を作成する際に、上記所定のキャラクタを当該有向グラフ構造中のノードとして扱ってもよく、又は、上記所定のキャラクタを当該有向グラフ構造中のノードとして扱わずに除外してもよい。ログメッセージの例えば利用者は、コンピュータ（１０１）が例えば空白文字をノードとして扱うか又はノードとして扱わないかを任意に選択可能である。コンピュータ（１０１）は、当該作成された有向グラフ構造を例えば、例えば有向グラフ構造を記憶する記憶媒体（例えば、図１に示す記憶装置（１０８））又はメモリ（１０３）に格納しうる。
【０１８５】
ステップ９０４において、コンピュータ（１０１）は、これまでに受信したログメッセージが一つであるかを判断する。コンピュータ（１０１）は、これまでに受信したログメッセージが一つでないことに応じて、処理をステップ９０４に進める。一方、コンピュータ（１０１）は、これまでに受信したログメッセージが一つであることに応じて、処理をステップ９０２に戻し、次の（すなわち、２回目以降の）ログメッセージを受信するのを待つ。
【０１８６】
ステップ９０５において、コンピュータ（１０１）は、既存の有向グラフ構造を、例えば有向グラフ構造を記憶する記憶媒体（例えば、図１に示す記憶装置（１０８）又はメモリ（１０３））から読み出す。引き続き、コンピュータ（１０１）は、当該読み出した既存の有向グラフ構造中の先頭ノードnを読み出す。
【０１８７】
ステップ９０６において、コンピュータ（１０１）は、メモ化再帰の技術を用いて作成された探索結果のメモmが例えば探索結果のメモmを記憶する記憶媒体（例えば、図１に示す記憶装置（１０８）又はメモリ（１０３））に保存されていることに応じて、当該メモmを上記記憶媒体から読み出す。
【０１８８】
ステップ９０７において、コンピュータ（１０１）は、どのノードとどのノードが一致するかを探索するために、有向グラフ構造中のどこのパスを通すかを関数  P, c←パス探索(si, n, m)  に従って決める。コンピュータ（１０１）は、si及びnをキーとして、メモmを参照し、当該siで示されるノードが既に探索されているかを調べる。
Pは、探索結果Pを表す。
cは、どこのパスを通るのが良いかを示すscoreを表す。当該scoreは、下記図９Ｃ示すステップ９３８の処理の返り値が２値であるのでそれに併せて記載しているパラメータであり、実質的にはこの後に使うものでない。
siは、ステップ９０２で入力されたログメッセージから作成された有向グラフ構造中のノードを表し、現在調査対象のノードを表す。
nは、ステップ９０５で読み出した既存の有向グラフ構造中のノードを表し、現在調査対象のノードを表す。
mは、探索結果のメモmを表す。
【０１８９】
ステップ９０７の処理の詳細は、下記図９Ｂ及び図９Ｃに示すフローチャートに従って別途説明する。
【０１９０】
ステップ９０８において、コンピュータ（１０１）は、ステップ９０３で作成した有向グラフ構造中のノードと、既存の有向グラフ構造中のノードと比較して、ステップ９０３で比較した有向グラフ構造中のノードと既存の有向グラフ構造中のノードとの間で文字列が一致するノード以外のノードを検出する。そして、コンピュータ（１０１）は、上記検出したノードを、上記既存の有向グラフ構造に分岐ノードとして追加する。すなわち、コンピュータ（１０１）は、探索結果Pに含まれるが、既存の有向グラフ構造中にまだ存在していないノードを、既存の有向グラフ構造に対して分岐ノードとして追加する。
【０１９１】
ステップ９０９において、コンピュータ（１０１）は、探索結果Pから、ステップ９０３で作成した有向グラフ構造を辿り、当該有向グラフ構造中のノード中のＳｎとＳｍ（但し、n＜m）とで閉路となる箇所を探索し、当該閉路となる箇所があるか判断する。当該探索の時点では、既存の有向グラフ構造内においても、ステップ９０３で作成した有向グラフ構造内のノードと一致する部分があるので、既存の有向グラフ構造を辿り、当該既存の有向グラフ構造中のノード中のＳｎとＳｍ（但し、n＜m）とで閉路となる箇所を探索することと同視することが可能である。当該Ｓｎは閉路の起点ノードに該当し、Ｓｍは閉路の終点ノードに該当するものである。コンピュータ（１０１）は、当該閉路となる箇所の探索において、異なるノードにおいて部分的に一致するノードが最も多くなる部分グラフ及びパスを探索しうる。また、コンピュータ（１０１）は、閉路となる箇所が複数ある場合には、当該複数の閉路のうちの内包されるより小さい閉路から順に探索する。コンピュータ（１０１）は、上記閉路となる箇所があることに応じて、処理をステップ９１０に進める。一方、コンピュータ（１０１）は、上記閉路となる箇所がないことに応じて、処理をステップ９０２に戻す。
【０１９２】
ステップ９１０において、コンピュータ（１０１）は、ステップ９０９において探索した閉路中の上記Ｓｎと上記Ｓｍとの間に存在するノードを比較して、当該ノード間で文字列の出現傾向が類似するかを判断する。コンピュータ（１０１）は、上記ノード間で文字列の出現傾向が類似することに応じて、処理をステップ９１１に進める。一方、コンピュータ（１０１）は、上記ノード間で文字列の出現傾向が類似しないことに応じて、処理をステップ９０２に戻す。
【０１９３】
ステップ９１１において、コンピュータ（１０１）は、ステップ９１０において文字列の出現傾向が類似すると判断されたノードを一つのノードに統合する。そして、コンピュータ（１０１）は、当該統合したノードに、任意の文字列を示す記号（例えばワイルドカードであり、例えば疑問符（?）又はアスタリスク（*）でありうる）を入れる。コンピュータ（１０１）は、閉路が無くなるまでステップ９０９〜ステップ９１１の処理を再帰的に行う。
【０１９４】
ステップ９１２において、コンピュータ（１０１）は、有向グラフ構造に基づいてフォーマットを推定するかどうかを判断する。コンピュータ（１０１）は、フォーマットを推定することに応じて、処理をステップ９１３に進める。一方、コンピュータは、フォーマットを推定しないことに応じて、処理を終了ステップ９１４に進める。
【０１９５】
ステップ９１３において、コンピュータ（１０１）は、有向グラフ構造に基づいて、例えば有向グラフ構造中の始点ノードから終点ノードに通るパスを走査することによってフォーマットを推定する。当該推定されたフォーマットは、文字列が一致するノードに関連付けられた第１の部分（文字列である）、及び、上記ノード間で文字列の出現傾向が類似するノードに関連付けられた第２の部分（文字列である）、並びに任意的に、上記ノード間で文字列の出現傾向が類似するノード以外のノードに関連付けられた第３の部分（文字列である）を含みうる。
【０１９６】
ステップ９１４において、コンピュータ（１０１）は、ログメッセージからフォーマットを推定する処理を終了する。
【０１９７】
図９Ｂ〜図９Ｃは、図９Ａに示すフローチャート中のパス探索の処理（９０７）の詳細を示すフローチャートである。
【０１９８】
ステップ９２１において、コンピュータ（１０１）は、ステップ９０７に示すパス探索の処理を開始する。
【０１９９】
ステップ９２２において、コンピュータ（１０１）は、ステップ９０２で入力されたログメッセージから作成した有向グラフ構造中のノードと、ステップ９０５で読み出した既存の有向グラフ構造中のノード同士を比較したメモ  m[si, n]が既に存在するかを判断する。コンピュータ（１０１）は、メモ  m[si, n]が既に存在することに応じて、処理をステップ９２３に進める。一方、コンピュータ（１０１）は、メモ  m[si, n]が存在していないことに応じて、処理をステップ９２３に進める。
【０２００】
ステップ９２３において、コンピュータ（１０１）は、メモ  m[si, n]が存在していないことに応じて、ステップ９０５で読み出した既存の有向グラフ構造中のノードnの次にある次のノード集合をNとする。
【０２０１】
ステップ９２４において、コンピュータ（１０１）は、メモ  m[s, n]が既にメモとして存在していることから、当該メモ  m[s,n]の値を出力として戻し、ステップ９０７に示すパス探索の処理を終了する。そして、コンピュータ（１０１）は、処理を図９Ａに示すステップ９０８に進める。
【０２０２】
ステップ９２５において、コンピュータ（１０１）は、ステップ９０５で読み出した既存の有向グラフ構造中のノード集合Nに、ステップ９０２で入力されたログメッセージから作成した有向グラフ構造中のノードsiの次のノードsi+1があるかを探索する（P←{a | a ∈ N, si+1 = a}）。
【０２０３】
ステップ９２６において、コンピュータ（１０１）は、max_scoreに0を代入して初期化し、且つ、good_pathにnil（null）を代入して初期化する。
【０２０４】
ステップ９２７において、コンピュータ（１０１）は、p = φであるか（すなわち、ステップ９２５に示すP←{a | a ∈ N, si+1 = a}を満たすノードが存在しないこと）判断する。φは、一般的な空集合を意味する。コンピュータ（１０１）は、p = φであること（すなわち、一致すること）に応じて、処理をステップ９３０に進める。一方、コンピュータ（１０１）は、p = φでないこと（すなわち、一致しないこと）に応じて、処理をステップ９２９に進める。
【０２０５】
ステップ９２８において、コンピュータ（１０１）は、次のノードの集合Nから、１つのノードｑを取得する（q ∈ N）。ｑは、既存の有向グラフ構造中の次のノードを代入するものである。
【０２０６】
ステップ９２９において、コンピュータ（１０１）は、どのノードとどのノードが一致するかを探索するために、次のノードについてパス探索を関数  (si+1, p, m) （ここでは、pの代わりにgood_pathに、及びcの代わりにmax_scoreにそれぞれ返り値が代入されている）を再帰的に繰り返し、good_path, max_scoreを戻り値として出力する。
【０２０７】
ステップ９３０において、コンピュータ（１０１）は、どのノードとどのノードが一致するかを探索するために、有向グラフ構造中のどこのパスを通るかをパス探索関数  P, score←パス探索(si, q, m)  （ここで、パス探索の左辺は第１値としてパスを有し、第２値としてスコアの変数を有する）に従って決める。スコアは、ノードが一致する場合には大きい値になるようにし、一方、出現頻度が類似する場合にはその値よりも低くなるように設定されている。
【０２０８】
ステップ９３１において、コンピュータ（１０１）は、ステップ９３０で求めたスコアがmax_scoreよりも大きいかを判断する。コンピュータ（１０１）は、スコアがmax_scoreよりも大きいことに応じて処理をステップ９３１に進める。一方、コンピュータ（１０１）は、スコアがmax_scoreと等しいか又は小さいことに応じて処理をステップに進める。
【０２０９】
ステップ９３２において、コンピュータ（１０１）は、max_scoreにステップ９３０で求めたスコアを代入し、且つ、good_pathにステップ９３０で探索した探索結果Pを代入する。
【０２１０】
ステップ９３３において、コンピュータ（１０１）は、既存の有向グラフ構造中の次のノードを探索して、当該次のノードのスコアを求めて、最大となるスコアであるノードを探索するために、ステップ９２８からステップ９３２を繰り返す。すなわち、コンピュータ（１０１）は、ノードの集合Nに含まれるすべての要素qを順番に上記パス探索関数に入力して調べ、その中で最もスコアの高いパスを探し出す。このようにして、コンピュータ（１０１）は、ステップ９０２で入力されたログメッセージから作成した有向グラフ構造中のノードが、既存の有向グラフ構造中のどこを通るのが最も適切かを調べる。
【０２１１】
ステップ９３４において、コンピュータ（１０１）は、max_score += スコア計算(si, n)とする。すなわち、コンピュータ（１０１）は、ステップ９０２で入力されたログメッセージから作成した有向グラフ構造中のノードが、既存の有向グラフ構造中のどのパスを通るかを探索する過程で、最もスコアが高くなるパスを探索する為に、スコアを加算する。
【０２１２】
ステップ９３５において、コンピュータ（１０１）は、si = nかを判断する。すなわち、コンピュータ（１０１）は、siとnの各文字列が一致しているかを判断する。コンピュータ（１０１）はsi = nであることに応じて、処理をステップ９３６に進める。一方、コンピュータ（１０１）はsi = nでないことに応じて、処理を終了ステップ９３７に進める。
【０２１３】
ステップ９３６において、コンピュータ（１０１）は、good_path = si + good_pathとし、文字列が一致するノードの列の集合を集めていく。すなわち、コンピュータ（１０１）は、パスを連結して、good_pathに最適なパスを保存するようにしていく。good_pathは、文字列が一致するノードの列の集合を示す。
【０２１４】
ステップ９３７において、コンピュータ（１０１）は、メモmとしてステップ９３６で求めたgood_pathとそのscoreを、メモmを記憶する記憶媒体に記録する。
【０２１５】
ステップ９３８において、コンピュータ（１０１）は、ステップ９０７に示すパス探索の処理を終了する。そして、コンピュータ（１０１）は、処理を図９Ａに示すステップ９０８に進める。
【０２１６】
図１０は、図１に従うハードウェア構成を好ましくは備えており、図９Ａ〜図９Ｃそれぞれに示すフローチャートに従って本発明の実施態様を実施するコンピュータの機能ブロック図の一例を示す図である。
【０２１７】
コンピュータ（１００１）は、図１に示すコンピュータ（１０１）に示されている構成、例えばＣＰＵ（１０２）、メイン・メモリ（１０３）、記憶装置（１０８）、及びディスク（１０８）を備えている。
【０２１８】
コンピュータ（１００１）は、有向グラフ構造作成手段（１０１１）、ノード検出手段（１０１２）、有向グラフ構造変更手段（１０１３）、及びフォーマット推定手段（１０１４）を備えている。コンピュータ（１００１）は任意的に、オートマトン出力手段（１０１５）をさらに備えていてもよい。
【０２１９】
有向グラフ構造作成手段（１０１１）は、第１のログメッセージを所定のキャラクタの前後で分割して、当該分割した各部分をノードとし、当該ノードそれぞれを上記第１のログメッセージの先頭から順に並べて第１の有向グラフ構造を作成し、且つ、第２のログメッセージを上記所定のキャラクタの前後で分割して、当該分割した各部分をノードとし、当該ノードそれぞれを上記第２のログメッセージの先頭から順に並べて第２の有向グラフ構造を作成する。
【０２２０】
また、有向グラフ構造作成手段（１０１１）は、さらに、第３のログメッセージを上記所定のキャラクタの前後で分割して、当該分割した各部分をノードとし、当該ノードそれぞれを上記第３のログメッセージの先頭から順に並べて第３の有向グラフ構造を作成しうる。
【０２２１】
有向グラフ構造作成手段（１０１１）は、図９に記載のステップ９０２〜９０７、並びに、図９Ｂ及び図９Ｃに記載の各ステップを実行しうる。
【０２２２】
ノード検出手段（１０１２）は、上記第１の有向グラフ構造中のノードと上記第２の有向グラフ構造中のノードとを比較して、上記第１の有向グラフ構造中のノードと上記第２の有向グラフ構造中のノードとの間で文字列が一致するノード以外のノードを検出する。
【０２２３】
また、ノード検出手段（１０１２）は、上記閉路が複数形成されている場合に、さらに、上記文字列の出現傾向が類似することを上記複数の閉路のうちのより小さい閉路から再帰的に判定しうる。
【０２２４】
また、ノード検出手段（１０１２）は、上記第１の有向グラフ構造中のノードと上記第２の有向グラフ構造中のノードとの間で文字列が異なるノードが現れた場合に、当該異なるノードにおいて部分的に一致するノードが最も多くなる部分グラフ及びパスを探索しうる。
【０２２５】
また、ノード検出手段（１０１２）は、上記探索をメモ化再帰の技術を用いて行いうる。
【０２２６】
ノード検出手段（１０１２）は、図９に記載のステップ９０９〜９１１を実行しうる。
【０２２７】
有向グラフ構造変更手段（１０１３）は、上記検出したノードのうち、上記第２の有向グラフ構造中の上記検出したノードを、上記第１の有向グラフ構造に第１の分岐ノードとして追加する。
【０２２８】
また、有向グラフ構造変更手段（１０１３）は、上記第１の分岐ノードが追加された第１の有向グラフ構造において、上記文字列の出現傾向が類似する上記ノードを一つのノードに統合しうる。
【０２２９】
有向グラフ構造変更手段（１０１３）は、図９に記載のステップ９０８を実行しうる。
【０２３０】
フォーマット推定手段（１０１４）は、上記第１の分岐ノードが追加された第１の有向グラフ構造に基づいて、上記フォーマットを推定する。当該フォーマットが、上記文字列が一致するノードに関連付けられた第１の部分、及び、上記第１の有向グラフ構造中の上記検出したノードと上記第２の有向グラフ構造中の上記検出したノードとの間で文字列の出現傾向が類似するノードに関連付けられた第２の部分、並びに任意的に、上記文字列の出現傾向が類似する上記ノード以外のノードに関連付けられた第３の部分を含む。
【０２３１】
また、フォーマット推定手段（１０１４）は、上記分岐ノードが追加された第１の有向グラフ構造の始点ノードから終点ノードを通る少なくとも１つのパスを走査して、上記フォーマットを推定しうる。
【０２３２】
フォーマット推定手段（１０１４）は、図９に記載のステップ９１２及び９１３を実行しうる。
【０２３３】
オートマトン出力手段（１０１５）は、上記文字列の出現傾向が類似する上記ノードが一つのノードに統合された第１の有向グラフ構造をオートマトンとして出力する。
【図１】
0005988447.tif 000002
【図２】
0005988447.tif 000003
【図３】
0005988447.tif 000004
【図４】
0005988447.tif 000005
【図５Ａ】
0005988447.tif 000006
【図５Ｂ】
0005988447.tif 000007
【図５Ｃ】
0005988447.tif 000008
【図５Ｄ】
0005988447.tif 000009
【図６Ａ】
0005988447.tif 000010
【図６Ｂ】
0005988447.tif 000011
【図７Ａ】
0005988447.tif 000012
【図７Ｂ】
0005988447.tif 000013
【図８Ａ】
0005988447.tif 000014
【図８Ｂ】
0005988447.tif 000015
【図９Ａ】
0005988447.tif 000016
【図９Ｂ】
0005988447.tif 000017
【図９Ｃ】
0005988447.tif 000018
【図１０】
0005988447.tif 000019