(57)【特許請求の範囲】
【請求項１】
入力文について構文解析を行った後、処理の意味に関係ない部分を除去して抽象構文木を生成し、前記抽象構文木を複数の引数をとり得る各引数に対応する各ノードが同じ階層になるように処理し、
前記抽象構文木について、根ノードに対応する第１階層から所定階層の深さまで見て葉ノード以外の節点ノードの非終端記号が同一となる抽象構文木ごとの集合に分類し、
前記分類された抽象構文木の集合において、終端記号が出現するノードのうち出現する前記終端記号の種類が前記入力文を呼び出す処理の種類の所定数倍以下となる共通部分のノードに対応する文字列を含む文字列パターンを、前記入力文を分類するための分類文字列パターンとして生成する、
ことを特徴とする名寄せ規則生成方法。
【請求項２】
前記分類文字列パターンの生成において、
前記分類された抽象構文木の集合において、終端記号が出現する各ノードのうち出現する前記終端記号の種類が前記処理の種類の前記所定数倍以下となる共通部分のノードに対応する文字列の箇所を列挙し、前記共通部分のノード以外のノードを無視して得られる抽象構文木の種類を数え上げ、
前記数え上げの結果数が所定の上限閾値以上の場合には、前記終端記号の種類が多いノードから順次無視していって前記数え上げの結果数が前記所定の上限閾値よりも少なくなるよう調整する処理を繰り返し実行し、
前記数え上げの結果数が所定の下限閾値よりも小さくなった場合には、前記所定階層の深さを深くして、前記抽象構文木を分類する処理、前記抽象構文木を数え上げる処理、および前記数え上げの結果数を調整する処理を繰り返し実行し、
前記数え上げの結果数が前記所定の下限閾値以上かつ前記所定の上限閾値よりも小さくなった場合に、前記分類された集合に含まれる抽象構文木に対応するもとの入力文から、前記共通部分のノードに対応する文字列の箇所を残した文字列パターンを、前記分類文字列パターンとして生成する、
ことを特徴とする請求項１に記載の名寄せ規則生成方法。
【請求項３】
入力文について構文解析を行った後、処理の意味に関係ない部分を除去し、かつ複数の引数をとり得る各引数に対応する各ノードは同じ階層になるように処理して前記入力文に対応する抽象構文木を生成する抽象構文木生成部と、
前記抽象構文木について、根ノードに対応する第１階層から所定階層の深さまで見て葉ノード以外の節点ノードの非終端記号が同一となる抽象構文木ごとの集合に分類する処理部と、
前記分類された抽象構文木の集合において、終端記号が出現する各ノードのうち出現する前記終端記号の種類が前記入力文を呼び出す処理の種類の所定数倍以下となる共通部分のノードに対応する文字列を含む文字列パターンを、観測される各入力文を分類するための分類文字列パターンとして生成する分類文字列パターン生成部と、
を備えることを特徴とする名寄せ規則生成装置。
【請求項４】
前記分類文字列パターン生成部は、
前記分類された抽象構文木の集合において、終端記号が出現する木のノードのうち出現する前記終端記号の種類が前記処理の種類の前記所定数倍以下となる共通部分のノードに対応する文字列の箇所を列挙し、前記共通部分のノード以外のノードを無視して得られる抽象構文木の種類を数え上げる処理部と、
前記数え上げの結果数が所定の上限閾値よりも多い場合には、前記終端記号の種類が多いノードから順次無視していって前記数え上げの結果数が前記所定の上限閾値よりも少なくなるよう調整する処理を繰り返し実行する処理部と、
前記数え上げの結果数が所定の下限閾値よりも小さくなった場合には、前記所定階層の深さを深くして、前記抽象構文木を分類する処理、前記抽象構文木を数え上げる処理、および前記数え上げの結果数を調整する処理を繰り返し実行する処理部と、
前記数え上げの結果数が前記所定の下限閾値以上かつ前記所定の上限閾値よりも小さくなった場合に、前記分類された集合に含まれる抽象構文木に対応するもとの入力文から、前記共通部分のノードに対応する文字列の箇所を残した文字列パターンを、前記入力文を分類するため、分類文字列パターンとして生成する処理部と、
を備えることを特徴とする請求項３に記載の名寄せ規則生成装置。
【請求項５】
コンピュータに、
入力文について構文解析を行った後、処理の意味に関係ない部分を除去して抽象構文木を生成し、前記抽象構文木を複数の引数をとり得る各引数に対応する各ノードが同じ階層になるように処理し、
前記抽象構文木について、根ノードに対応する第１階層から所定階層の深さまで見て葉ノード以外の節点ノードの非終端記号が同一となる抽象構文木ごとの集合に分類し、
前記分類された抽象構文木の集合において、終端記号が出現する各ノードのうち出現する前記終端記号の種類が前記入力文を呼び出す処理の種類の所定数倍以下となる共通部分のノードに対応する文字列を含む文字列パターンを、各入力文を分類するための分類文字列パターンとして生成する、
処理を実行させるためのプログラム。
【請求項６】
前記分類文字列パターンを生成する処理において、
前記分類された抽象構文木の集合において、終端記号が出現する木のノードのうち出現する前記終端記号の種類が前記処理の種類の前記所定数倍以下となる共通部分のノードに対応する文字列の箇所を列挙し、前記共通部分のノード以外のノードを無視して得られる抽象構文木の種類を数え上げ、
前記数え上げの結果数が所定の上限閾値よりも多い場合には、前記終端記号の種類が多いノードから順次無視していって前記数え上げの結果数が前記所定の上限閾値よりも少なくなるよう調整する処理を繰り返し実行し、
前記数え上げの結果数が所定の下限閾値よりも小さくなった場合には、前記所定階層の深さを深くして、前記抽象構文木を分類する処理、前記抽象構文木を数え上げる処理、および前記数え上げの結果数を調整する処理を繰り返し実行し、
前記数え上げの結果数が前記所定の下限閾値以上かつ前記所定の上限閾値よりも小さくなった場合に、前記分類された集合に含まれる抽象構文木に対応するもとの入力文から、前記共通部分のノードに対応する文字列の箇所を残した文字列パターンを、前記分類文字列パターンとして生成する、
処理を前記コンピュータに実行させるための請求項５に記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、異なる文字列に表されるイベントを同一視してイベントの類別を行うための名寄せ規則生成装置、方法、およびプログラムに関する。
【背景技術】
【０００２】
コンピュータシステムにおいて、イベントの類別が必要になることがある。イベントの類別のためには、システムの可視化が必要である。システムの可視化とは、このイベントのときには必ずこういうイベントが起きるというイベントの関係(モデル)を推定し（モデリング）、推定したモデルに実際の観測データをマッチングすることである。
【０００３】
システムの可視化を行うための技術として、システムのサービス提供機能に手を加えずにシステムの稼働状態を的確に分析できるようにする以下の従来技術が知られている（例えば特許文献１）。この技術では、メッセージ解析手段により、収集したメッセージの内容が解析され、メッセージの発生時刻、メッセージで要求されている処理種別、及びリクエストメッセージかレスポンスメッセージかが判別される。モデル生成指示が入力されると、モデル生成手段により、処理間の呼出関係の確からしさに基づく選択基準に従って選択されたメッセージ集合に基づきサーバ間の呼出の制約条件を満たすトランザクションモデルが生成される。また、分析指示が入力されると、分析手段により、トランザクションモデルに合致するプロトコルログによりトランザクションの処理状態が分析される。  また、多階層サーバシステムのログから、業務処理を特徴付けるURIの部分を抽出する以下の従来技術が知られている（例えば特許文献２）。この技術では、本特徴抽出方法は、下位階層サーバへのメッセージに含まれる業務種別識別子と下位階層サーバで実施された処理の開始時刻及び終了時刻とを含む子ログの各々について、当該子ログに含まれる開始時刻から終了時刻までを包含する開始時刻及び終了時刻を含む親ログである包含親ログを特定し、子ログに含まれる業務種別識別子と包含親ログに含まれるＵＲＩのパスとを子親関係候補テーブルに登録すると共に、当該業務種別識別子と当該ＵＲＩのパスとの組み合わせをカウントして登録する工程と、子親関係候補テーブルから、業務種別識別子毎にカウント値が最も大きい上記組み合わせに含まれるURIのパスを抽出する工程と、子親関係リストにおいて、URIのパスが、他のセットにおけるURIのパスと不一致となるセットを出力する工程とを含む。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００６−１１６８３号公報
【特許文献１】特開２０１０−６７０４７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかし、従来の技術では、HTTPリクエストに基づくURIのような単純な構文ならいいが、SQL（ストラクチャド・クエリ・ランゲージ）のようなデータベース問い合わせ言語のように文脈自由文法で記述される言語の高速な名寄せは困難であるという問題点を有していた。というのも、構文解析器は一般に遅いからである。
【０００６】
また構文解析器の出力する結果は木構造であり、木構造の特定箇所を抽出するよう指定するのは容易ではない。正規表現（ｒｅｇｕｌａｒ  ｅｘｐｒｅｓｓｉｏｎ）を使って適当な部分を取り出して比較するシステムが考えられるが、正規表現は構文的な知識を用いることがでず、文法的に不適切な文字列を取り出してしまうことがあるという問題点を有していた。
【０００７】
そこで、本発明の課題は、適切な箇所を見るパターンを自動生成することにある。
【課題を解決するための手段】
【０００８】
態様の一例では、入力文について構文解析を行った後、処理の意味に関係ない部分を除去して抽象構文木を生成し、前記抽象構文木を複数の引数をとり得る各引数に対応する各ノードが同じ階層になるように処理し、前記抽象構文木について、根ノードに対応する第１階層から所定階層の深さまで見て葉ノード以外の節点ノードの非終端記号が同一となる抽象構文木ごとの集合に分類し、前記分類された抽象構文木の集合において、終端記号が出現するノードのうち出現する前記終端記号の種類が前記入力文を呼び出す処理の種類の所定数倍以下となる共通部分のノードに対応する文字列を含む文字列パターンを、前記入力文を分類するための分類文字列パターンとして生成する。
【発明の効果】
【０００９】
名寄せのための文字列変換規則に相当するパターンの抽出が自動的に可能になる。また、実時間処理を求められるマッチング時に構文解析という重い処理をしないで、パターンマッチだけで処理が可能になる。
【図面の簡単な説明】
【００１０】
【図１】一般的に考えられる名寄せシステムの構成図である。
【図２】名寄せシステムの実施形態の構成図である。
【図３】実施形態における抽象構文木の作成の基本的な考え方の説明図である。
【図４】分類文字列パターン生成部２０１−３のさらに詳細な機能ブロック図である。
【図５】実施形態における文字列パターンの作成の基本的な考え方の説明図である。
【図６】同じ単語が違う箇所に出現する例を説明するための図（その１）である。
【図７】同じ単語が違う箇所に出現する例を説明するための図（その２）である。
【図８】実施形態における抽象構文木の説明図である。
【図９】実施形態において、抽象構文木の名寄せで着目する文字列の特定箇所を説明する図である。
【図１０】名寄せのための変換規則例の説明図である。
【図１１】抽象構文木の深さと形の同一性との関係の説明図である。
【図１２】親候補の種類数の第２の算出方法の説明図である。
【図１３】実施形態の制御処理を示すフローチャートである。
【図１４】実施形態の動作説明図（各葉ノードにおける終端記号の種類の数）である。
【図１５】実施形態の動作説明図（無視するノードと木の種類）である。
【図１６】実施形態の動作説明図（分類文字列パターンの出力）である。
【図１７】実施形態を実現可能なハードウェアの構成図である。
【発明を実施するための形態】
【００１１】
以下、本発明を実施するための形態について図面を参照しながら詳細に説明する。
以下の説明では、まず、システム可視化の名寄せの一般的な考え方について説明した後、その問題点を明らかにし、その後に、本実施形態について説明する。
【００１２】
システムの可視化の例として、インターネット銀行システムで考えてみる。残高照会のトランザクションのモデルを作成するとき、処理中では期間やユーザIDといったトランザクション毎に異なるパラメータもあれば、参照する表のように常に同一なパラメータもある。そのため残高照会のモデルを作成するためには、異なる文字列に表されるイベントを同一視する必要がある。この処理を名寄せと呼ぶ。名寄せとは、本来の意味としては、複数の銀行口座の所有者について、名前、生年月日、住所などの属性情報から、その所有者の同一性を判定することなどを言う。それになぞらえて、文字列中の特定箇所を銀行口座の名寄せの場合でいう属性情報に対応させ、文字列の特定箇所が同じもの同士を同一視する処理を、システムの可視化における名寄せと呼ぶ。すなわち、システムの可視化における名寄せの目的は、イベントの一般化のための文字列の同一視にある。
【００１３】
例えば、インターネット銀行システムにおける残高照会の例におけるシステムの可視化では、ユーザや期間といったパラメータは無視して、口座情報を保存してある表のように常に出現する文字列箇所を見て、名寄せが行われる。
【００１４】
また例えば、HTTP（ハイパー・テキスト・トランスファ・プロトコル）を用いたWWW（ワールド・ワイド・ウェブ）システム（以下、「Webシステム」と呼ぶ）の可視化を考える。この場合、HTTPリクエストについて、特定のcgi（コモン・ゲートウェイ・インタフェース）のパラメータが同一のものを同じものと扱うことにより、ユーザ等のパラメータに依らずある種の処理を同じものと見做す名寄せが行われる。例えば、下記の３つのURI（ユニフォームト・リソース・ロケータ）形式のHTTPリクエストを考える。
http://service.com/index.html?uid=kuroyanagi&com=1
http://service.com/index.html?uid=tanaka&com=1
http://service.com/index.html?uid=shimizu&com=1
この場合に、それぞれユーザIDを示す「uid=kuroyanagi」「uid=tanaka」「uid=shimizu」というパラメータ文字列の箇所に依らず、同一の「com=1」というパラメータ文字列の箇所を見て、名寄せが行われる。
【００１５】
図１は、一般的に考えられる名寄せシステムの構成図である。
モデリング装置１０１は、システムの可視化におけるイベントのモデルを生成する。変換器１０１−２が、モデルとなるイベントの文字列１０１−１を入力し、そのイベントの文字列１０１−１に対して、文字列変換規則１０１−３に従って変換をし、モデルとなるイベントに対応する変換文字列１０１−４を出力する。ここで、文字列変換規則１０１−３は例えば、イベントの文字列１０１−１に対して構文解析を行って木構造を生成するための規則である。変換器１０１−２は、この文字列変換規則１０１−３に従って、イベントの文字列１０１−１に対して構文解析を行い、モデルとなるイベントに対応する木構造の変換文字列１０１−４を生成する。
【００１６】
マッチング装置１０２は、システムの可視化におけるイベントのマッチングを実行する。変換器１０２−２が、実際に観測されたイベントの文字列１０２−１を入力し、そのイベントの文字列１０２−１に対して、モデリング装置１０１における文字列変換規則１０１−３と同じ文字列変換規則１０２−３に従って構文解析を行う。そして、変換器１０２−２は、観測されたイベントに対応する木構造の変換文字列１０２−４を生成する。
【００１７】
そして、各観測されたイベントに対応する変換文字列１０２−４のうち、同じモデルとなるイベントに対応する変換文字列１０１−４に変換されたものが、同一のイベントであると判定される。
【００１８】
より具体的な名寄せシステムとしては例えば、Webサーバ、アプリケーションサーバ、データベースサーバからなる３階層システムにおいて、各トランザクションを観測して各サービス提供機能の処理時間を算出するようなシステムが一般的に考えられる。このようなシステムでは、各計算機上で動くサービス提供機能に手をいれることなく、ネットワーク上を流れるデータ(イベント)を観測して、システムの動作状況を把握する。そして、このようなシステムでは、予め得られたデータからあるイベントがどういう種類のイベントを起こしたかという関係(モデル)を木構造で得て、それに観測データをマッチさせることでイベントの間の起動関係を推定し、各トランザクションについてどの階層でどのくらい処理時間がかかったかを把握することを可能にする。
【００１９】
あるいは、WebシステムにおけるURIの名寄せを行うような手法も考えられる
ここで、HTTPリクエストに基づくURIのような単純な構文のみならず、SQLのようなデータベース問い合わせ言語のように、文脈自由文法で記述される言語の名寄せが必要になるケースも多い。
【００２０】
しかし、上述のような構文解析のみをベースとする一般的に考えられる技術では、文脈自由文法で記述されるイベント文字列に対して、構文解析木の特定箇所を抽出するように、文字変換規則を指定するのは容易ではない。通常、構文解析木のどの特定箇所に着目し他のどの箇所を無視するかを決定することは、自明ではない。また、構文解析の処理は遅いため、モデリングにおいて構文解析を行うのはよいとしても、マッチングにおいて観測される文脈自由文法で記述されるイベントごとにリアルタイムで構文解析を行うことは、困難である。
【００２１】
一方、図１の文字列変換規則１０１−３、１０２−３を、無視する文字列の箇所を正規表現によって指定した文字列変換規則として、変換器１０１−２、１０２−２で文字列変換を行う技術も、一般的に考えられる。例えば、変換規則を、
s/SELECT (.*) FROM .*/SELECT $1 FROM ../g      （１）
とする。この変換規則は、入力されたイベントの文字列として、文字列「SELECT」のあとに、任意の第１の文字列が現れた後に、文字列「FROM」が現れ、その後に任意の第２の文字列が続いて現れた場合に、「SELECT 第１の文字列 FROM」という文字列を変換文字列として出力する規則を指定する。ここで、「s/A/B/g」は、入力された文章全体にわたって文字列パターンAを文字列パターンBに変換する置換演算子を示す。また、上記の変換規則の例（１）において、上記置換演算子中の文字列パターンBに相当する領域中の「$1」は、文字列パターンAに相当する領域中の「(.*)」の部分を参照して転記することを指定する変数である。
【００２２】
上述のような変換規則の例（１）を使って、例えば、
SELECT zandaka FROM table1 WHERE EXISTS (SELECT b FROM t)      （２）
というSQL文として指定される入力されたイベントの文字列を変換することを考える。この場合、本来であれば、
SELECT zandaka FROM ..      （３）
という変換文字列を出力したい。しかし、前述の変換規則の例（１）により、「$1」として、入力されたイベント文字列の例（２）における第２番目に現れる文字列「FROM」までの文字列「 zandaka FROM table1 WHERE EXISTS (SELECT b 」がマッチしてしまう。すなわち、変換文字列は、例えば、
SELECT zandaka FROM table1 WHERE EXISTS (SELECT b FROM ..      （４）
となってしまう。この変換文字列（４）は、意図した変換文字列（３）とは異なるものである。
【００２３】
このように、無視する文字列の箇所を正規表現によって指定した文字列変換規則を使う技術では、正規表現は構文的な知識を用いることができないため、文法的に不適切な文字列を取り出してしまい、マッチングが正しく行われない場合が発生する。
【００２４】
以上のように、文字列変換規則に構文解析を用いたマッチングでは、処理速度が遅い上に文字列変換規則の設定が難しい。一方、文字列変換規則に正規表現を用いたパターンマッチングでは、処理速度は速いが、文脈自由文法を反映させた正確な文字列変換が難しいという問題点がある。
【００２５】
そこで、以下に説明する実施形態では、文脈自由文法による例えばSQL文として指定される（２）のような入力されたイベントの文字列に対して、（３）に示されるような意図した変換文字列を出力できるような名寄せ規則を生成する。本実施形態では、文字列変換規則の置換パターンは、（１）と同様の正規表現を使ったパターンであるが、正規表現を指定する文字列箇所として、文脈自由文法を反映させることのできる適切な文字列箇所を指定できる。
【００２６】
図２は、名寄せシステムの実施形態の構成図である。
モデリング装置２０１は、システムの可視化におけるイベントのモデルとして、文脈自由文法が反映された適切な文字列箇所が正規表現された文字列変換規則の置換パターンである分類文字列パターン２０１−４を生成する。
【００２７】
モデリング装置２０１において、抽象構文木生成部２０１−２は、モデルとなる入力文であるイベントの文字列２０１−１を入力する。そして、各入力文について構文解析を行った後、処理の意味に関係ない部分を除去し、かつ複数の引数をとり得る各引数に対応する各ノードは同じ階層になるように処理して、各入力文に対応する各抽象構文木を生成する。
【００２８】
ここで、抽象構文木とは、構文解析木のうち、プログラムの意味に関係ない部分、例えば括弧やそこに配置されるのが自明であるため文字列の解析上判別する必要のないキーワードを省略したものをいう。図３は、本実施形態における抽象構文木の作成の基本的な考え方の説明図である。説明を簡単にするために、いま例えば、イベントの文字列２０１−１として、図３の（ａ）に示される文字列「（１＋２）＋３」が入力されたとする。これに対して、通常の構文解析を行うと、入力数字「１」「２」「３」や演算記号「＋」のほかに、プログラムの意味に関係ない括弧なども１つのノードとして、図３に示される構文解析木が得られる。これに対して、抽象構文木では、上述の括弧などは除かれて木が構成される結果、文字列の比較に必要な入力数字「１」「２」「３」のみが葉ノードに配置された図３に示されるような木になる。
【００２９】
また、本実施形態の抽象構文木では、イベントの文字列２０１−１として、例えば図３（ｄ）に示されるようなSQL文「SELECT X FROM A,B,C」があったとき、次のような抽象構文木が生成される。リストで表現される部分（カンマで区切られた複数の引数をとり得る部分）「A,B,C」は、各引数「A」「B」「C」に対応するノードが、図３（ｅ）に示されるように、同じ階層になるように展開される。
【００３０】
本実施形態では、十分な量の入力文の文字列２０１−１があるとき、個人idなどの処理の種類と関係ない独立な値は処理の種類よりはるかにたくさんあり、かつtable名などの処理の種類に依存して出現が決まるものは、処理の種類の高々数倍しか存在しない。その数倍の「数」は小さく、大概は1でよい。
【００３１】
以上の事実関係に基づいて、本実施形態では、同じ形の構文のうち、それを呼び出す処理の種類の数倍程度しか出現しない箇所以外は無視して文字列のパターンを作り、それによって文字列を分類する。例えば処理の種類が一種類で、それに対して
DELETE EMPLOYEE WHERE LNAME=suzuki
DELETE EMPLOYEE WHERE LNAME=tanaka
DELETE EMPLOYEE WHERE LNAME=shimizu
：
というデータベースのテーブルEMPLOYEE上のレコードの削除処理が発行されていたとする。この場合、本実施形態では、LNAME=の次の部分は無視していいと判断する。これをLNAMEが人の名前だからという知識を用いず、単に呼び出し元の処理の種類が1つで、その処理の種類に対してたくさん種類がある木分類されたノードの文字列は、処理の種類とは独立だから無視しよう、という方法を本実施形態は採用する。一般に、特定の分類文字列パターンを生成するためには、処理の種類を理解した上で、正規表現にすべき文字列を人間が適切に指定する必要がある。しかし、近年普及が著しいクラウドコンピューティングの分野等において、始めから処理の種類を特定できるとは限らず、そのような場合には適切な正規表現が設定された分類文字列パターンを生成することが困難な場合がある。
【００３２】
そこで、本実施形態は、正規表現を設定すべき文字列を、処理の種類に関する知識を用いずに、抽象構文木に対する判別処理により適切に設定することを可能にするものである。
【００３３】
まず、コンピュータシステムが生成する特定の処理の種類（業務種類）を依頼するイベントの文字列は、例えばSQL文における「SELECT」「DELETE」や「FROM」、「WHERE」などのプログラミング上のキーワードの生成規則は決まっている。また、データをまとめるための括弧などの生成規則も決まっている。そこで、本実施形態では、上述したようにして、これらのキーワードや括弧などが除かれ、かつリストを構成する複数の文字列は同一階層のノードになるような抽象構文木が生成される。そして、このようにして生成された抽象構文木上で、ある深さの階層において、どの値が処理の種類に対して変化せず、どの値が頻繁に変化するかを判別することにより、正規表現を設定すべき文字列を判別できるようにする。なお、リストを構成する複数の文字列が同一階層のノードになるようにするのは、抽象構文木上のある階層まで見て同じ形の抽象構文木かどうかを判定するためである。
【００３４】
以上の抽象構文木に対する判別処理を実行するために、図２のモデリング装置２０１において、分類文字列パターン生成部２０１−３が、抽象構文木生成部２０１−２が生成した各抽象構文木のうち同じ形の各抽象構文木において、以下の処理を実行する。終端記号が出現する各ノードのうち出現する終端記号の種類がイベントの文字列２０１−１を呼び出す処理の種類の所定数倍以下となる共通部分のノードに対応する文字列を含む文字列パターンを生成する。そして、その文字列パターンを、観測される各入力文であるイベントの文字列２０２−１を分類するための分類文字列パターン２０１−４として生成する。このようにして生成される分類文字列パターン２０１−４は、通常の正規表現を使ったパターンであるが、正規表現を指定する文字列箇所として、文脈自由文法を反映させることのできる適切な文字列箇所を指定することが可能となる。これにより、適切に設定された正規表現による高速かつ正確な名寄せ処理が実現される。分類文字列パターン生成部２０１−３のさらに詳細な機能ブロックの構成は、図４を用いて後述する。
入力文であるイベントの文字列２０１−１と分類文字列パターン２０１−４との対応関係は、２０１−５として記憶される。
【００３５】
次に、マッチング装置２０２は、システムの可視化におけるイベントのマッチングを実行する。分類文字列パターンへのマッチ器２０２−２が、実際に観測されたイベントの文字列２０２−１を入力し、そのイベントの文字列２０２−１に対して、モデリング装置２０１が生成した分類文字列パターン２０１−４とでパターンマッチングを実行する。分類文字列パターンへのマッチ器２０２−２は、パターンがマッチすると、入力文であるイベントの文字列２０２−１と分類文字列パターン２０１−４との対応関係が、２０２−３として記憶される。
【００３６】
図４は、図２の分類文字列パターン生成部２０１−３のさらに詳細な機能ブロック図である。
抽象構文木分類処理部４０１は、図２の抽象構文木生成部２０１−２が生成した各抽象構文木について、根ノードに対応する第１階層から所定階層の深さまで見る。そして、所定階層の深さにて、各抽象構文木を、葉ノード以外の節点ノードの非終端記号が同一となる抽象構文木ごとの集合に分類する。葉ノードの部分は、同一の処理の種類であっても比較的頻繁に変化する部分である。そこで、このような葉ノード以外の節点ノードの非終端記号の部分で木の同一性を判別することにより、同じ処理の種類に属するイベントの文字列２０１−１に対応する抽象構文木を、効率よく分類することができる。なお、図３で説明したように、抽象構文木は、リストを構成する複数の文字列が同一階層のノードになるように生成される。一般に、リストを構成する文字列部分についても、同一の処理の種類であっても比較的頻繁に変化する部分である。そこで、このようなリストの葉ノードの部分は、同一階層になるようにすることで、処理の種類毎の抽象構文木の同一性の判別において効率よく除くことができる。
【００３７】
抽象構文木数え上げ処理部４０２は、分類された各抽象構文木の集合において、終端記号が出現する木のノードのうち出現する終端記号の種類が処理の種類の所定数倍以下となる共通部分のノードに対応する文字列の箇所を列挙する。そして、列挙した共通部分のノード以外のノードを無視して得られる抽象構文木の種類を数え上げる。処理の種類が同一である抽象構文木であっても、出現する終端記号の種類が多いノード部分は、名寄せを実行する上で、いろいろな値が出現し得る部分としてパターン化はしないほうがよいと考えられる。そこで、このような部分については、後に正規表現の対象部分とするために、パターン化のための列挙からは除かれる。
【００３８】
数え上げ結果数調整部４０３は、数え上げの結果数が所定の上限閾値以上の場合には、終端記号の種類が多いノードから順次無視していって数え上げの結果数が所定の上限閾値よりも少なくなるよう調整する処理を繰り返し実行する。数え上げの結果数があまりにも多い場合には、あまり精度の良いパターン化がされていないと判定して、終端記号の種類が多いノードから順に、パターン化の対象から削る処理である。
【００３９】
階層深さ制御部４０４は、数え上げの結果数が所定の下限閾値よりも小さくなった場合には、所定階層の深さを深くして、抽象構文木分類処理部４０１、抽象構文木数え上げ処理部４０２、および数え上げ結果数調整部４０３の処理を繰り返し実行させる。数え上げの結果数を減らしすぎて全部が1つになってしまう(つまり全部を同一視する)というのも困るので、そうなった場合には抽象構文木のより深い階層まで木を見て、さらにパターン分類を行うようにする。
【００４０】
分類文字列パターン出力部４０５は、数え上げの結果数が所定の下限閾値以上かつ所定の上限閾値よりも小さくなった場合に、次の動作を実行する。分類された集合に含まれる抽象構文木に対応するもとの入力文であるイベントの文字列２０１−１（図２）から、共通部分のノードに対応する文字列の箇所を残した文字列パターンを、図２の分類文字列パターン２０１−４として生成する。図５は、本実施形態における文字列パターン２０１−４の作成の基本的な考え方の説明図である。説明を簡単にするために、例えば入力されたイベントの文字列２０１−１が、（ａ−１）に示される文字列「１＋２＋３」と（ａ−２）に示される文字列「（１＋２）＋３」のいずれであっても、（ｂ）に示される同じ抽象構文木が生成される。そして、図４の抽象構文木数え上げ処理部４０２により、黒丸で示される数字「３」に対応するノードが、無視できるノードとされて、（ｃ）に示されるパターンの木が決定されたとする。このようにして決定された木から、正規表現を含む文字列パターン２０１−４を作るときに、システムが、どのような規則でイベントの文字列を生成しているかを知る必要がある。そこで、本実施形態では、抽象構文木が生成されるときの元の文字列２０１−１を保存しておき、それに基づいて、文字列パターン２０１−４を生成する。例えば、元の文字列が（ａ−１）に示される文字列「１＋２＋３」であれば、文字列パターン２０１−４は（ｄ−１）に示される「１＋２＋．」となる。また、元の文字列が（ａ−２）に示される文字列「（１＋２）＋３」であれば、文字列パターン２０１−４は（ｄ−２）に示される「（１＋２）＋．」となる。ここで、「．」は、任意の１文字へのマッチを示す正規表現である。上述の文字列中の括弧は、抽象構文木の生成においては重要でないが、図２の分類文字列パターンへのマッチ器２０２−２におけるパターンマッチング処理では、たとえ括弧１つでもマッチング性能に影響する。本実施形態では、システムの文字列生成規則に良く適合した文字列パターン２０１−４を生成することが可能となる。
【００４１】
上記構成の本実施形態の詳細な動作について、以下に説明する。
本実施形態は、以下のようなシステムを前提とする。
まず、本実施形態のシステムは、処理の種類が決まっている。例えば、インターネット銀行の残高照会処理や、入出金明細問合せ処理等である。ここで、処理の種類とは、名寄せの対象となる入力文を呼び出した業務システム上の業務の種類のことをいう。
【００４２】
次に、本実施形態のシステムでは、特定の単語が似た意味の構文解析木の異なる場所には出現しない。図６および図７は、同じ単語が違う箇所に出現する例を説明するための図である。図６は、
SELECT a FROM table WHERE EXISTS (SELECT b FROM t)      （５）
というSQL文を構文解析して得られる構文解析木を示す図である。図６の構文解析木では、まず、第１階層の根ノードに文字列「<SELECT>」が対応付けられる。ここで、「<」と「>」で囲まれた文字列を有するノードは、そのノードを表記する記号が非終端記号であって、そのノードの下にさらに下位層のノードが接続されていることを示している。非終端記号文字列「<SELECT>」に対応するノードの下に接続する第２階層の左から右に向かう６個のノードにはそれぞれ、文字列「SELECT」、「<attribute list>」、「FROM」、「<table name>」、「WHERE」、「<condition>」が対応付けられる。文字列「SELECT」は、データベースのテーブルからレコードデータを取得するためのSQL文法のキーワードを示す終端記号である。「<attribute list>」は、SELECT文によって取得されるテーブルの項目名のリストの文字列を示す葉ノードが対応付いていることを示す非終端記号である。「FROM」は、参照先のテーブルを指定するためのSQL文法のキーワードを示す終端記号である。「<table name>」は、参照先のテーブル名の文字列を示す葉ノードが対応付いていることを示す非終端記号である。「WHERE」は、検索条件を指定するためのSQL文法のキーワードを示す終端記号である。「<condition>」は、検索条件の内容を示す文字列を示すノードが対応付いていることを示す非終端記号である。第２階層の文字列「<attribute list>」に対応するノードの下に接続する第３階層の１つの葉ノードには、実際のテーブル項目名を示す終端記号の文字列「a」が対応付けられる。第２階層の文字列「<table name>」に対応するノードの下に接続する第３階層の１つの葉ノードには、実際のテーブル名を示す終端記号の文字列「table」が対応付けられる。第２階層の文字列「<condition>」に対応するノードの下に接続する第３階層の２つのノードにはそれぞれ、実際の検索条件の内容を示す終端記号の文字列「EXISTS」と非終端記号の文字列「<SELECT>」が対応付けられる。第３階層の文字列「<SELECT>」に対応するノードの下に接続する第４階層の左から右に向かう４個のノードにはそれぞれ、文字列「SELECT」、「<attribute list>」、「FROM」、「<table name>」が対応付けられる。これらの文字列の意味は、既に説明した。第４階層の文字列「<attribute list>」に対応するノードの下に接続する第５階層の１つの葉ノードには、実際のテーブル項目名を示す終端記号の文字列「b」が対応付けられる。第２階層の文字列「<table name>」に対応するノードの下に接続する第５階層の１つの葉ノードには、実際のテーブル名を示す終端記号の文字列「t」が対応付けられる。
【００４３】
図６に対して図７は、
SELECT c FROM s WHERE EXISTS(SELECT d FROM table)      （６）
というSQL文を構文解析して得られる構文解析木を示す図である。このSQL文（６）は、前述の図６に対応するSQL文（５）と比較して、テーブル名「table」が、SQL文法上の異なる位置に現れている。すなわち、SQL文（５）では「FROM」句の中に、SQL文（６）では「EXISTS」句内の「FROM」句の中に、テーブル名「table」がそれぞれ指定されている。図７の構文解析木では、まず、第１階層の根ノードに非終端記号の文字列「<SELECT>」が対応付けられる。文字列「<SELECT>」に対応するノードの下に接続する第２階層の左から右に向かう６個のノードにはそれぞれ、文字列「SELECT」、「<attribute list>」、「FROM」、「<table name>」、「WHERE」、「<condition>」が対応付けられる。それぞれの文字列の意味は、図６の場合と同様である。第２階層の非終端記号の文字列「<attribute list>」に対応するノードの下に接続する第３階層の１つのノードには、実際のテーブル項目名を示す終端記号の文字列「c」が対応付けられる。第２階層の文字列「<table name>」に対応するノードの下に接続する第３階層の１つのノードには、実際のテーブル名を示す文字列「s」が対応付けられる。第２階層の非終端記号の文字列「<condition>」に対応するノードの下に接続する第３階層の２つのノードにはそれぞれ、実際の検索条件の内容を示す終端記号の文字列「EXISTS」と非終端記号の文字列「<SELECT>」が対応付けられる。第３階層の非終端記号の文字列「<SELECT>」に対応するノードの下に接続する第４階層の左から右に向かう４個のノードにはそれぞれ、文字列「SELECT」、「<attribute list>」、「FROM」、「<table name>」が対応付けられる。第４階層の非終端記号の文字列「<attribute list>」に対応するノードの下に接続する第５階層の１つの葉ノードには、実際のテーブル項目名を示す終端記号の文字列「ｄ」が対応付けられる。第２階層の文字列「<table name>」に対応する葉ノードの下に接続する第５階層の１つのノードには、実際のテーブル名を示す終端記号の文字列「table」が対応付けられる。
【００４４】
以上のように、図６のSQL文（５）と図７のSQL文（６）を比較すると、同じテーブル名「table」が、SQL文法中の異なる位置に現れていることがわかる。しかし、本実施形態では、本実施形態が対象とする入力文はシステムがパラメータのみ違える形で生成する文である。従って、同じような処理の種類のグループの中では、同じ意味のテーブル名「table」を表わすのに、SQL文（５）やSQL文（６）のように、違う形で表現されることは、通常はないとして扱う。
【００４５】
上述の前提に加えて、本実施形態では、同じ意味の処理を括弧がついたりつかなかったりというように違う構文で表わすこともないものとして扱う。上述の場合と同様に、本実施形態が対象とする入力文はシステムがパラメータのみ違える形で生成する文だからである。
【００４６】
本実施形態では、前述したように、正規表現を設定すべき文字列を、処理の種類に関する知識を用いずに、抽象構文木に対する判別処理により適切に設定することを可能にするものである。
【００４７】
具体的には、本実施形態では、次のような処理を実行する。
まず、図２の抽象構文木生成部２０１−２が、全ての入力文について構文解析を行って、さらに抽象構文木を生成する。図８は、抽象構文木の例（ａ）とそうでない例（ｂ）を示す図である。抽象構文木とは、構文解析木のうち、プログラムの意味に関係ない部分とプログラミングに用いる特定のキーワードを省略したものをいう。省略するものには、例えば括弧や、「SELECT」「DELETE」「UPDATE」「FROM」「WHERE」「ORDER BY」「EXIST」などがあげられる。木構造は構造上その括弧による区切は不要であるため、構文解析木にあった括弧を省略することができる。図８（ａ）の例では、例えば、
SELECT balance FROM account_yen, account_euro      （７）
という入力文があったとき、このSQL文（７）のような文脈自由言語の入力文について構文解析を行う。文法規則ごとに新たな節点を作成し、葉はその規則における記号に対応させる。その後、処理（プログラム）の意味に関係ないグループ化規則のような部分は無視される。
【００４８】
上記SQL文（７）に対して、構文解析では、図８（ｂ）に示されるような構文解析木が得られるが、これから冗長な部分を取り除くことにより、図８（ａ）に示される抽象構文木が得られる。
【００４９】
すなわち、図８（ｂ）に示される構文解析木では、まず、第１階層の根ノードに非終端記号の文字列「<SELECT>」が対応付けられる。非終端記号文字列「<SELECT>」に対応するノードの下に接続する第２階層の左から右に向かう６個のノードにはそれぞれ、文字列「SELECT」、「<attribute list>」、「FROM」、「<table name>」が対応付けられる。第２階層の文字列「<attribute list>」に対応するノードの下に接続する第３階層の１つの葉ノードには、実際のテーブル項目名を示す終端記号の文字列「balance」が対応付けられる。第２階層の文字列「<table name>」に対応するノードの下に接続する第３階層の１つの葉ノードには、実際のテーブル名の１つを示す終端記号の文字列「account_yen」が対応付けられる。さらに、その下方の階層に向かって、同じくテーブル名の１つを示す終端記号の文字列「account_euro」などが順次対応付けられる。
【００５０】
一方、図８の（ａ）の抽象構文木では、第１階層の根ノードには、図８（ｂ）の場合と同様に、非終端記号の文字列「<SELECT>」が対応付けられる。非終端記号文字列「<SELECT>」に対応するノードの下に接続する第２階層では、図８（ｂ）の終端記号の文字列「SELECT」を有する葉ノードと終端記号の文字列「FROM」を有する葉ノードが除去される。そして、非終端記号の文字列「<attribute list>」を有するノードと非終端記号の文字列「<table name>」を有するノードが残される。
【００５１】
このとき本実施形態では、抽象構文解析木の生成時に、例えばSQL文（７）のFROM句のテーブル名などの、複数の引数を取れるところの各引数であるテーブル名「account_yen」や「account_euro」に対応する各ノードは、同一階層に配置される。これは後述するように、同一の階層でこれら複数の引数を有するパターンが同じかどうか判定するためである。
本実施形態では、以上のようにして抽象構文木を生成するとき、抽象構文木を生成したもとの入力文のイベント文字列とその抽象構文木とで対応関係を保持しておく。
【００５２】
次に、図４の抽象構文木分類処理部４０１が、構文解析して得られた各抽象構文木について、ある深さまで見て、葉ノード以外の節点ノードの非終端記号が同一で葉ノード部分の終端記号が同一の抽象構文木ごとに、各集合に分類する。なお、葉ノードは、非終端記号は異なってもよい。
【００５３】
図９は、本実施形態において、抽象構文木の名寄せで着目する文字列の特定箇所を説明する図である。図９の（ａ）、（ｂ）、（ｃ）の３種類の抽象構文木が入力されているとする。図９（ａ）の抽象構文木は、下記のSQL文から生成される。
DELETE EMPLOYEE WHERE LNAME=tanaka      （８）
そして、図９（ａ）の抽象構文では、第１階層の根ノードに非終端記号の文字列「<DELETE>」が対応付けられる。非終端記号文字列「<DELETE>」に対応するノードの下に接続する第２階層の２個のノードにはそれぞれ、非終端記号の文字列「<table name>」と非終端記号の文字列「<condition>」が対応付けられる。第２階層の文字列「<table name>」に対応するノードの下に接続する第３階層の１つの葉ノードには、実際のテーブル項目名を示す終端記号の文字列「EMPLOYEE」が対応付けられる。第２階層の文字列「<condition>」に対応するノードの下に接続する第３階層の１つのノードには、非終端記号の文字列「<eq>」が対応付けられる。第３階層の文字列「<eq>」に対応するノードの下に接続する第４階層の２つのノードには、終端記号の文字列「LNAME」と終端記号の文字列「tanaka」が対応付けられる。図９（ｂ）の抽象構文木では、図９（ａ）の抽象構文木に対して、第４階層の終端記号の文字列「tanaka」が「kuroyanagi」に変更された以外は、図９（ａ）の抽象構文木と同一である。図９（ｃ）の抽象構文木も、図９（ａ）の抽象構文木に対して、第４階層の終端記号の文字列「tanaka」が「shimizu」に変更された以外は、図９（ａ）の抽象構文木と同一である。これらの３つの抽象構文木について、根ノードが含まれる第１階層から順に見た場合、第２階層において、非終端記号の文字列「<table name>」と同じく非終端記号の文字列「<condition>」が、図９（ａ）、（ｂ）、（ｃ）の３つの抽象構文木で同一である。従って、これらの３つの抽象構文木は、１つの集合に分類される。
【００５４】
なお、本実施形態では、抽象構文木のノードに対応付けられる条件や表の名前が一部同一のものを同一視はしないが、同一視するように実施することも可能である。
次に、図４の抽象構文木数え上げ処理部４０２が、分類された各抽象構文木の集合で、終端記号が出現する各ノードのうち、その出現する終端記号の種類が処理の種類の所定数倍以下となる共通部分のノードに対応する文字列の箇所を列挙する。そして、それらの共通部分のノード以外のノードを無視して得られる抽象構文木の種類を数え上げる。
【００５５】
今、図９に示されるように同一の集合に分類された３つの抽象構文木（ａ）、（ｂ）、（ｃ）において、終端記号が出現するノードとしては、１種類の終端記号の文字列「EMPLOYEE」に対応する第３階層のノードがある。また、１種類の終端記号の文字列「LNAME」に対応する第４階層のノードがある。さらに、３種類の終端記号の文字列「tanaka」「kuroyanagi」「shimizu」に対応する第４階層のノードがある。
【００５６】
いま例えば、処理の種類が１種類で、所定数倍を１とすれば、上記終端記号が出現するノードのうち、終端記号の種類が処理の種類×所定数倍＝１種類のみのノード「EMPLOYEE」と「LNAME」が列挙される。そして、これら２つのノード以外のノードを無視して得られる抽象構文木の種類が数え上げられる。これにより、数え上げの結果は１種類となる。
【００５７】
ここで、数え上げの結果数があまりにも多くなって所定の上限閾値以上の場合には、終端記号の種類が多いノードから順次無視していって数え上げの結果数が所定の上限閾値よりも少なくなるように調整する処理を繰り返し実行する。この処理は、図４の数え上げ結果数調整部４０３により実行される。
【００５８】
一方、数え上げの数を減らしすぎて抽象構文木の種類が所定の下限値より小さくなってしまう（例えば1つになってしまう、つまり全部を同一視する)というのも困るので、そうなった場合にはより深い階層まで抽象構文木を見て、さらに分類を繰り返す。この処理は、図４の階層深さ制御部４０４により実行される。
【００５９】
以上のようにして、数え上げの結果数が適切な数になった場合に、分類された集合に含まれる抽象構文木に対応するもとの入力文から、無視しない共通部分のノードに対応する文字列の箇所を残した文字列パターンを、分類文字列パターンとして生成する。この処理は、図４の分類文字列パターン出力部４０５により実行される。
【００６０】
図１０は、名寄せのための変換規則例、すなわち観測される各入力文を分類するための分類文字列パターンの例の説明図である。図９（ａ）、（ｂ）、（ｃ）の集合に対する上述の数え上げの処理により、図１０（ａ）に示される分類文字列パターンの木が得られる。図中、黒丸は、数え上げ処理において無視するノード部分である。前述のように、ノード「EMPLOYEE」と「LNAME」が残される。これと、前述した（８）のもとのSQL文とから、下記のように、無視するノードに対応する文字列部分が正規表現された図１０（ｂ）または下記に示される分類文字列パターンが生成される。
DELETE EMPLOYEE WHERE LNAME=.*      （８）
ここで、「LNAME=」に続く「.」は任意の１文字を指定可能なことを示し、「*」は直前の任意の１文字の繰り返しを許すことを示している。
【００６１】
前述したように、本実施形態では、同じ意味を与える文を違う構文で与えることはないと仮定することから、意味に違いのない抽象構文木を与える具体的な構文（入力文）はもともと同じと考えられる。このため、括弧がついていたりいなかったりという差はないと考えられるため、以上のようにして分類文字列パターンを作ることができる。
【００６２】
図１１は、抽象構文木の深さと形の同一性との関係の説明図である。前述したように、抽象構文木を集合に分類する際には、根ノードに対応する第１階層から所定階層の深さまで見て葉ノード以外の節点ノードの非終端記号が同一となる抽象構文木をまとめる。この場合、例えば図１１（ａ）と（ｂ）に示される２つの抽象構文木は、第２階層までしか見ないなら、葉ノード以外の節点ノードの非終端記号の文字列「<table name>」と非終端記号「<condition>」の文字列が２つの抽象構文木で同一である。このため、２つの抽象構文木は、同じ形と解釈される。一方、第３階層まで見る場合には、葉ノード以外の節点ノードの非終端記号の文字列は「<eq>」と「<in>」というように２つの抽象構文木で同一ではない。このため、２つの抽象構文木は、違う形と解釈される。このように、根ノードに対応する第１階層から所定階層の深さまで見て葉ノード以外の節点ノードの非終端記号が同一となる抽象構文木をまとめることは、分類文字列パターンの特性を決定する上で、重要な判断要素である。
【００６３】
以上説明した本実施形態の動作においては、抽象構文木から共通部分のノードを抽出するための判定基準として、文字列の種類が入力文を呼び出した処理の種類の所定数倍以下となるものを基準として判定している。このため、入力文を呼び出した処理の種類を決定する処理が必要となる。
【００６４】
本実施形態では、複数のイベントがあって、あるイベントが別のイベントを引き起こしているとき、引き起こすイベントを親、引き起こされるイベントを子と呼ぶ。例えば、銀行振込みという処理の種類（業務種類）を依頼するリクエストイベントがユーザコンピュータからアプリケーションサーバに対して送信された場合を考える。このとき、そのリクエストイベントを受信したアプリケーションサーバが、データベースサーバに対して、銀行振込の処理を指定するＳＱＬ文のイベントをさらに発行したとする。このとき、銀行振込みを依頼するリクエストイベントが親、それに従って発行されるＳＱＬ文のイベントが子となる。
【００６５】
2つのイベントe,fが親子(eが親、fが子)である場合に、イベントの属性a1(e),a1(f),a2(e),a2(f),...が関係a1(e) R1 a1(f), a2(e) R2 a2(f),...を満たしているとする。任意の2つのイベントg,hが関係a1(g) R1 a1(h), a2(g) R2 a2(h),....を満たすとき、gはhの親候補(hはgの子候補)であるという。
システム可視化における例：R1,R2属性:
イベントの開始時刻、終了時刻の組関係:<s1,e1>R1<s2,e2> ≡ s1<s2 ∧ e2<e1
ここで、「∧」は論理記号で「かつ」を意味する。また、「≡」は左の定義は右を意味する。属性:イベントは場所pから場所qへ送られるメッセージで表される文字列として、p,qの組関係： <p1,q1>R2<p2,q2> ≡ q1=p2 という関係がある。
【００６６】
以下に、親候補の種類数の第１の算出方法について説明する。
まず、各イベントの文字列に対して親候補を列挙する。システム可視化の場合には、開始終了時刻の包含関係で親子候補は決まる。本実施形態では、同じ種類の各イベントの文字列について、各親候補を調べ、頻度が多い順に累積度数を取って、全体の90%が入る種類を候補数とする。
【００６７】
例えば、同じ形の文の文字列群、
s1,s2,s3,s4,s5
の親候補の文字列群をそれぞれ、
{H11,H21},{H12,H31,H41},{H12,H22},{H11,H51},{H23,H32}
とする。ここで、H12のうちH1はイベントの種類を表し、添え字は同一イベントのIDを表わす。つまり例えば、H11,H12は、同じ種類の別のイベントの文字列である。この結果、親候補の集合Sは、
S = {H21,H22,H23}∪{H11,H12}∪{H31,H32}∪{H41} ∪{H51}
となる。これを添字を削除して頻度順に並べると、
H2,H2,H2,H1,H1,H3,H3,H4,H5
となる。左から全体9個の90%を取ると切り下げでH1,H2,H3,H4の4種類が、親候補の種類数として決定される。
【００６８】
次に、親候補の種類数の第２の算出方法について説明する。第２の算出方法では、既存のモデリング手法を使ってモデリングし、親子関係を確定する。図１２は、親候補の種類数の第２の算出方法の説明図である。今、親イベントの文字列H1と、子イベントの文字列S1、S2、S3等との親子関係のパターンとして、図１２の（ａ）、（ｂ）、（ｃ）の３パターンがあったとする。これらのパターンより、既存のモデリング手法により、例えば図１２の（ｄ）に示されるように、「H1とS1についてのみ親子関係が確定しその他の子イベントについては任意」というようなモデルが決定できたとする。そして、新たなイベントの文字列として、（ｅ）に示されるS4または（ｆ）に示されるS5が入力された場合を考える。この場合、（ｄ）のモデルを適用することにより、「イベントS4またはS5の親候補はH1である」というように親子関係を算出することができる。この場合、誤った名寄せは多少あるかもしれない。しかしそれらは、図１２（ｄ）に示されるように、多少のぶれを吸収できるように広めの範囲をカバーするようなモデルに作成されたモデルにより確定した親子関係を使うことで、親候補を1つに定めることができる。
本実施形態では、以上の第１または第２の親候補の種類数の算出方法により、処理の種類を決定すればよい。
【００６９】
図１３は、図２および図４に示されるモデリング装置２０１に対応する実施形態の制御処理を示すフローチャートである。このフローチャートは例えば、後述する図１７に示されるハードウェア構成を有するコンピュータにおいて、ＣＰＵ１７０１がメモリ１７０２等に記憶された制御プログラムを実行する処理である。以下、このフローチャートの詳細について、図１４から図１６の動作説明図を参照しながら説明する。
【００７０】
以下のフローチャートの制御処理において、処理の種類（業務種類）がセットされる変数をｎとする。また、a,b,cを正の定数とし、b≧aとする。そして、an（a×n）を、抽象構文木から共通部分のノードを抽出するための判定基準としての、処理の種類の所定数倍として定まる閾値とする。また、bn（b×n）を、前述した本実施形態の原理説明における数え上げの結果数の所定の上限閾値とする。さらに、cを、前述した本実施形態の原理説明における数え上げの結果数の所定の下限閾値とする。また、所定階層数を制御するための変数Ｌの初期値を０とする。
【００７１】
まず、各入力文について構文解析が行われる（図１３のステップＳ１４０１）。さらに、各構文解析木から、処理の意味に関係ない部分を除去し、かつ複数の引数をとり得る各引数に対応する各ノードは同じ階層になるように処理して、各入力文に対応する各抽象構文木が生成される（図１３のステップＳ１３０２）。以上の処理は、図２の抽象構文木生成部２０１−２の機能に対応する。この処理により例えば、３つの入力文から図９の（ａ）、（ｂ）、（ｃ）に示されるような３種類の抽象構文木が生成される。
【００７２】
次に、変数Lの値（初期値は０）以上で葉ノードが出現する抽象構文木上の最小の階層（所定階層）の深さがL’とされる。図９（ａ）、（ｂ）、（ｃ）の例では、終端記号の文字列「EMPLOYEE」に対応する葉ノードが最初に出現するため、L’=3となる。階層L’まで抽象構文木が比較されて、同じ形のものごとに分類される。前述した図９の例では、第３階層において、非終端記号の文字列「<eq>」が、（ａ）、（ｂ）、（ｃ）の３つの抽象構文木で同一である。従って、これらの３つの抽象構文木が、１つの集合に分類される。続いて、分類された各抽象構文木の集合において、終端記号が出現する各葉ノードにおいて、それぞれの出現する終端記号の種類が数え上げられる。前述の図９の抽象構文木群の例に対しては、図１４に例示されるように、終端記号の文字列「EMPLOYEE」に対応するノードIが１種類、終端記号の文字列「LNAME」に対応するノードIIが１種類である。また、終端記号の文字列「tanaka,kuroyanagi,shimizu」に対応するノードIIIが３種類である。その後、所定階層数制御用の変数Lに現在の所定階層数L’の値がセットされる（以上、図１３のステップＳ１３０３）。以上の処理は、図２の分類文字列パターン生成部２０１−３内の図４の抽象構文木分類処理部４０１の機能および抽象構文木数え上げ処理部４０２の一部の機能に対応する。
【００７３】
次に、ステップＳ１３０３で分類された同一の形の抽象構文木の集合ついて、親候補の種類が案出されて、変数nに設定される（図１３のステップＳ１３０４）。処理の種類（業務種類）nは、前述した親子候補の種類数の第１または第２の算出方法に基づいて決定することができる。
【００７４】
次に、前述したように、分類された各抽象構文木の集合において、ステップＳ１３０３で数え上げられた終端記号が出現する各葉ノードの種類のうち、種類がanの値以下の箇所以外が無視されて、抽象構文木が分類され、種類が数え上げられる（図１３のステップＳ１３０５）。いま例えば、処理の種類ｎが１と求まり、定数aの値が1である場合、anの値は1となる。これにより、図１４に示されるノードIIIは無視され、ノードIとIIがカウントされる。この結果、抽象構文木の種類は図１５（ａ）に示されるように１種類となる。一方例えば、処理の種類nが4と求まり、定数aの値が1である場合、anの値は４となる。これにより、図１４に示されるノードI、II、IIIのすべてがカウントされ、無視されるノードは無い。この結果、抽象構文木の種類は図１５（ｂ）に示されるように、３種類となる。以上の処理は、図２の分類文字列パターン生成部２０１−３内の図４の抽象構文木数え上げ処理部４０２の一部の機能に対応する。
【００７５】
次に、ステップＳ１３０５で数え上げられた抽象構文木の種類が、所定の上限閾値bn以上であるか否かが判定される（図１３のステップＳ１３０６）。この処理は、図２の分類文字列パターン生成部２０１−３内の図４の数え上げ結果数調整部４０３の一部の機能に対応する。
【００７６】
数え上げられた抽象構文木の種類が所定の上限閾値bn以上でステップＳ１３０６の判定がyesならば、ステップＳ１３０７が実行される。ここでは、現在処理している抽象構文木の集合において、終端記号の種類が最も多いノードが除かれて無視され、再び抽象構文木の種類がカウントされる。例えば、前述したように、an=4である場合において、ノードI、II、IIIのすべてがカウントされて抽象構文木の種類=3となった場合（図１５（ｂ）の場合）で、変数bの値を1とすれば、抽象構文木の種類=3は、bnの値3以上となる。この場合には、ステップＳ１３０７で、図１５（ｂ）に示される抽象構文木の集合において、終端記号の種類が３種類（図１４参照）と最も多いノードIIIが除かれて無視される。その後再び、数え上げられた抽象構文木の種類が分類して数え上げられ（図１３のステップＳ１３０７→Ｓ１３０８）、所定の上限閾値bnよりも大きいか否かが判定される（図１３のステップＳ１３０８→Ｓ１３０６）。上述の例では、ノードIIIが無視された結果、抽象構文木の種類が、図１５（ａ）に示されるように１種類となる。そして、ステップＳ１３０６の判定がnoとなる。以上の処理は、図２の分類文字列パターン生成部２０１−３内の図４の数え上げ結果数調整部４０３の一部の機能に対応する。
【００７７】
数え上げられた抽象構文木の種類が所定の上限閾値bn以下となりステップＳ１３０６の判定がnoならば、数え上げられた抽象構文木の種類が所定の下限閾値cより小さいか否かが判定される（図１３のステップＳ１３０９）。この処理は、図２の分類文字列パターン生成部２０１−３内の図４の階層深さ制御部４０４の一部の機能に対応する。
【００７８】
数え上げの数を減らしすぎて抽象構文木の種類が所定の下限値より小さくなってしまう（例えば1つになってしまう、つまり全部を同一視する状態になってしまう)場合には、ステップＳ１３０９の判定がyesとなる。この場合には、ステップＳ１３０３に戻って、より深い階層まで抽象構文木を見て、さらに分類が繰り返される。つまり、変数Lの値（現在は3になっている）以上で葉ノードが出現する抽象構文木上の最小の階層（所定階層）の深さがL’とされる。この処理は、図２の分類文字列パターン生成部２０１−３内の図４の階層深さ制御部４０４の一部の機能に対応する。
【００７９】
ステップＳ１３０９の判定がnoならば、上述の数え上げの処理により、例えば図１６（ａ）に示される抽象構文木から、図１６（ｂ）に示される分類文字列パターンの木が得られる。図中、黒丸は、数え上げ処理において無視するノード部分である。この例では、ノード「EMPLOYEE」が残される。これと、例えば図１６（ｃ）に示される元のSQL文、
DELETE EMPLOYEE WHERE LNAME=Brown      （９）
とから、下記のように、無視するノードに対応する文字列部分が正規表現された図１６（ｄ）または下記に示される分類文字列パターンが生成される。
DELETE EMPLOYEE WHERE .*      （１０）
ここで、「LNAME=」に続く「.」は任意の１文字にマッチする正規表現を示し、「*」は直前の任意の１文字の繰り返しにマッチする正規表現を示している。この動作原理については、図５を使って前述した。なお、上述の例では、残されたノード部分は「EMPLOYEE」の１種類である。これに対して、この部分のパターンが複数種類残った場合には、それぞれのパターンを含む上記（１０）式と同様の分類文字列パターンが複数パターン生成される。
【００８０】
以上説明した実施形態により、名寄せのための文字列変換規則に相当するパターンの抽出が自動的に可能になる。また、実時間処理を求められるマッチング時に構文解析という重い処理をしないで、パターンマッチだけで処理が可能になる。
【００８１】
図１７は、上記名寄せシステムをソフトウェア処理として実現できるコンピュータのハードウェア構成の一例を示す図である。
図１７に示されるコンピュータは、ＣＰＵ１７０１、メモリ１７０２、入力装置１７０３、出力装置１７０４、外部記憶装置１７０５、可搬記録媒体１７０９が挿入される可搬記録媒体駆動装置１７０６、及び通信インタフェース１７０７を有し、これらがバス１７０８によって相互に接続された構成を有する。同図に示される構成は上記システムを実現できるコンピュータの一例であり、そのようなコンピュータはこの構成に限定されるものではない。
【００８２】
ＣＰＵ１７０１は、当該コンピュータ全体の制御を行う。メモリ１７０２は、プログラムの実行、データ更新等の際に、外部記憶装置１７０５（或いは可搬記録媒体１７０９）に記憶されているプログラム又はデータを一時的に格納するＲＡＭ等のメモリである。ＣＵＰ１７０１は、プログラムをメモリ１７０２に読み出して実行することにより、全体の制御を行う。
【００８３】
入出力装置１７０３は、ユーザによるキーボードやマウス等による入力操作を検出し、その検出結果をＣＰＵ１７０１に通知し、ＣＰＵ１７０１の制御によって送られてくるデータを表示装置や印刷装置に出力する。
【００８４】
外部記憶装置１７０５は、例えばハードディスク記憶装置である。主に各種データやプログラムの保存に用いられる。
可搬記録媒体駆動装置１７０６は、光ディスクやＳＤＲＡＭ、コンパクトフラッシュ等の可搬記録媒体１７０９を収容するもので、外部記憶装置１７０５の補助の役割を有する。
【００８５】
通信インターフェース１７０７は、例えばＬＡＮ（ローカルエリアネットワーク）又はＷＡＮ（ワイドエリアネットワーク）の通信回線を接続するための装置である。
本実施形態によるシステムは、図１３のフローチャート等で実現される機能を搭載したプログラムをＣＰＵ１７０１が実行することで実現される。そのプログラムは、例えば外部記憶装置１７０５や可搬記録媒体１７０９に記録して配布してもよく、或いはネットワーク接続装置１７０７によりネットワークから取得できるようにしてもよい。
【符号の説明】
【００８６】
１０１、２０１  モデリング装置
１０２、２０２  マッチング装置
１０１−１、１０２−２、２０１−１、２０２−１  イベントの文字列
１０１−２、１０２−２  変換器
１０１−３、１０２−３  文字列変換規則
１０１−４、１０２−４  変換文字列
２０１−２  抽象構文木生成部
２０１−３  分類文字列パターン生成部
２０１−４  分類文字列パターン
２０１−５、２０２−３  文字列とパターンの対応
２０２−２  分類文字列パターンへのマッチ器
４０１  抽象構文木分類処理部
４０２  抽象構文木数え上げ処理部
４０３  数え上げ結果数調整部
４０４  階層深さ制御部
４０５  分類文字列パターン出力部
【図１】
0005681041.tif 000002
【図２】
0005681041.tif 000003
【図３】
0005681041.tif 000004
【図４】
0005681041.tif 000005
【図５】
0005681041.tif 000006
【図１２】
0005681041.tif 000007
【図１７】
0005681041.tif 000008
【図６】
0005681041.tif 000009
【図７】
0005681041.tif 000010
【図８】
0005681041.tif 000011
【図９】
0005681041.tif 000012
【図１０】
0005681041.tif 000013
【図１１】
0005681041.tif 000014
【図１３】
0005681041.tif 000015
【図１４】
0005681041.tif 000016
【図１５】
0005681041.tif 000017
【図１６】
0005681041.tif 000018