(57)【要約】【課題】  複数のＸＭＬ文書の間の類似度を高速かつ低コストで高効率で検出することができる類似度検出方法、およびＸＭＬ文書の統合方法ならびにシステムの提供。【解決手段】  一のＸＭＬ文書Ｔｂと、他のＸＭＬ文書Ｔｔとを、それぞれ独立して意味を持つ最大の部分木構造に構成する段階（Ａ）と、前記ＸＭＬ文書Ｔｂを構成する部分木の葉ノードクラスタと、前記ＸＭＬ文書Ｔｔを構成する部分木の葉ノードクラスタとを照合して、照合する葉ノードクラスタの間で同じ内容を有する葉ノードの個数の比率に基づいて部分木間の類似度を求める段階（Ｄ）と、前記部分木間の類似度からＸＭＬ文書間の類似度を求める段階（Ｃ）とを含むＸＭＬ文書の類似度を検出方法、ＸＭＬ文書の統合方法およびシステム。【選択図】      図１
2007052556.tif 000002
【特許請求の範囲】
【請求項１】
複数のＸＭＬ文書の類似度を検出する方法であって、
一のＸＭＬ文書Ｔｂと、他のＸＭＬ文書Ｔｔとの間の類似度を検出するに際して、
ＸＭＬ文書Ｔｂと、ＸＭＬ文書Ｔｔとを、それぞれ独立して意味を持つ最大の部分木構造に構成する段階（Ａ）と、
前記ＸＭＬ文書Ｔｂを構成する部分木の葉ノードクラスタと、前記ＸＭＬ文書Ｔｔを構成する部分木の葉ノードクラスタとを照合して、照合する葉ノードクラスタの間で同じ内容を有する葉ノードの個数の比率に基づいて部分木間の類似度を求める段階（Ｄ）と、
前記部分木間の類似度からＸＭＬ文書間の類似度を求める段階（Ｃ）とを含むことを特徴とする複数のＸＭＬ文書の類似度検出方法。
【請求項２】
複数のＸＭＬ文書の類似度を検出する方法であって、
一のＸＭＬ文書Ｔｂと、他のＸＭＬ文書Ｔｔとの間の類似度を検出するに際して、
ＸＭＬ文書Ｔｂと、ＸＭＬ文書Ｔｔとを、それぞれ３階以上の階層構造を有する木構造の部分木として分割する段階（Ａ）と、
前記ＸＭＬ文書Ｔｂを構成するｋb個（ｋbは２以上の整数）の部分木ｔbi（ｉは１≦ｉ≦ｋbの整数）が含む葉ノードクラスタＬｂと、前記ＸＭＬ文書Ｔｔを構成するｋt個（ｋｔは２以上の整数）の部分木ｔtj（ｊは１≦ｊ≦ｋtの整数）が含む葉ノードクラスタＬｔとを照合して、葉ノードクラスタＬｂが有する葉ノードの個数ｎbiと、葉ノードクラスタＬｂと葉ノードクラスタＬｔとの間で同じ内容を有する葉ノードの個数ｎとに基づいて、下記式（１）：
【数１】
2007052556.tif 000010
で表される部分木の類似度Ｓ（ｔbi，ｔtj）を、部分木ｔbiと部分木ｔtjの全組み合わせ（ｋb×ｋt通り）について求める段階（Ｂ）と、
前記の部分木ｔbiと部分木ｔtjの全組み合わせについて求められた部分木の類似度Ｓ（ｔbi，ｔtj）において、ｉ番目の部分木ｔbiと、１からｋt番目の部分木ｔtjとの各組み合わせに対してそれぞれ求められる前記部分木の類似度Ｓ（ｔbi，ｔtj）の中で、最大の値をＳM［ｉ］として、下記式（２）：
【数２】
2007052556.tif 000011
で表されるＸＭＬ文書間類似度Ｓ（Ｔｂ，Ｔｔ）を求める段階（Ｃ）とを含むことを特徴とする請求項１に記載の複数のＸＭＬ文書の類似度検出方法。
【請求項３】
前記段階（Ａ）は、自己から最も遠い子孫ノードまでの最大距離が３以上である或いは子ノード二つ以上を持つノードを候補ノードとし、前記候補ノードの子ノードの中で、候補ノードの個数ｎと、最も遠い子孫ノードまでの距離ｄと、所定の定数φ（０＜φ≦１）とに基づいて、下記式（３）で表されるパラメータｗを求め、木構造の中でそれぞれの上端から末端までの候補ノードが構成するトップダウンパスでｗが一番大きなノードで、ＸＭＬ文書ＴｂおよびＸＭＬ文書Ｔｔを独立して意味を持つ部分木に分割して行うことを特徴とする請求項２に記載の複数のＸＭＬ文書の類似度検出方法。
ｗ＝ｎ×ｄφ                                （３）
【請求項４】
前記段階（Ｂ）は、各葉ノードクラスタが含む葉ノードが有する構文解析対象文字データを照合して、前記葉ノードクラスタＬｂが含む葉ノードと、前記葉ノードクラスタＬｔが含む葉ノードとが同一の内容のものであるか否かを決定することを特徴とする請求項１または請求項２に記載の複数のＸＭＬ文書の類似度検出方法。
【請求項５】
請求項２〜請求項４のいずれか１項に記載のＸＭＬ文書の類似度検出方法によって求められたＸＭＬ文書間類似度Ｓ（Ｔｂ，Ｔｔ）が所定の値よりも高い値を示す部分木ｔbi，ｔtjの組み合わせを選び、その２つの部分木が含む異なる葉ノードクラスタを抽出して差分とし、その差分を一方のＸＭＬ文書の部分木に付加することで、２つのＸＭＬ文書の統合を行うことを特徴とする複数のＸＭＬ文書の統合方法。
【請求項６】
複数のＸＭＬ文書の類似度をコンピュータによって検出するシステムであって、
前記コンピュータが、
一のＸＭＬ文書Ｔｂと、他方のＸＭＬ文書Ｔｔとを、それぞれ複数の部分木で構成される木構造に分割する部分木分割部と、
前記分割によって形成される、ｋb個の部分木ｔbi（１≦ｉ≦ｋb：ｋbは２以上の整数）で構成されるＸＭＬ文書Ｔｂと、ｋt個の部分木ｔtj（１≦ｊ≦ｋt：ｋtは２以上の整数）で構成されるＸＭＬ文書Ｔｔとについて、部分木ｔbiを構成するｎbi個の葉ノードを持つ葉ノードクラスタＬｂと、部分木ｔtjを構成する葉ノードクラスタＬｔとを照合して、葉ノードクラスタＬｂと葉ノードクラスタＬｔとの間で同じ内容を有する葉ノードの個数ｎを求め、下記式（１）に従って、部分木の類似度Ｓ（ｔbi，ｔtj）を求める部分木類似度演算部と、
【数３】
2007052556.tif 000012
前記の部分木ｔbiと部分木ｔtjの全組み合わせについて求められた部分木の類似度Ｓ（ｔbi，ｔtj）において、ｉ番目の部分木ｔbiと、１からｋt番目の部分木ｔtjとの各組み合わせに対してそれぞれ求められる前記部分木の類似度Ｓ（ｔbi，ｔtj）の中で、最大の値をＳM［ｉ］として、下記式（２）：
【数４】
2007052556.tif 000013
で表されるＸＭＬ文書間類似度Ｓ（Ｔｂ，Ｔｔ）を求めるＸＭＬ類似度演算部とを備えることを特徴とする複数のＸＭＬ文書の類似度検出システム。
【請求項７】
複数のＸＭＬ文書の類似度をコンピュータによって検出して、ＸＭＬ文書を統合するシステムであって、
前記コンピュータが、
一のＸＭＬ文書Ｔｂと、他方のＸＭＬ文書Ｔｔとを、それぞれ複数の部分木で構成される木構造に分割する部分木分割部と、
前記分割によって形成される、ｋb個の部分木ｔbi（１≦ｉ≦ｋb：ｋbは２以上の整数）で構成されるＸＭＬ文書Ｔｂと、ｋt個の部分木ｔtj（１≦ｊ≦ｋt：ｋtは２以上の整数）で構成されるＸＭＬ文書Ｔｔとについて、部分木ｔbiを構成するｎbi個の葉ノードを持つ葉ノードクラスタＬｂと、部分木ｔtjを構成する葉ノードクラスタＬｔとを照合して、葉ノードクラスタＬｂと葉ノードクラスタＬｔとの間で同じ内容を有する葉ノードの個数ｎを求め、下記式（１）に従って、部分木の類似度Ｓ（ｔbi，ｔtj）を求める部分木類似度演算部と、
【数５】
2007052556.tif 000014
前記の部分木ｔbiと部分木ｔtjの全組み合わせについて求められた部分木の類似度Ｓ（ｔbi，ｔtj）において、ｉ番目の部分木ｔbiと、１からｋt番目の部分木ｔtjとの各組み合わせに対してそれぞれ求められる前記部分木の類似度Ｓ（ｔbi，ｔtj）の中で、最大の値をＳM［ｉ］として、下記式（２）：
【数６】
2007052556.tif 000015
で表されるＸＭＬ文書間類似度Ｓ（Ｔｂ，Ｔｔ）を求めるＸＭＬ類似度演算部と、
前記ＸＭＬ類似度演算部によって求められたＸＭＬ文書間類似度Ｓ（Ｔｂ，Ｔｔ）が所定の値よりも高い値を示す部分木ｔbi，ｔtjの組み合わせを選び、その２つの部分木が含む異なる葉ノードクラスタを抽出して差分とし、その差分を一方のＸＭＬ文書の部分木に付加することで、２つのＸＭＬ文書の統合を行う統合演算部を備えることを特徴とする複数のＸＭＬ文書の統合システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のＸＭＬ文書の類似度検出方法および類似性検出システム、ならびに複数のＸＭＬ文書の統合方法に関する。
【背景技術】
【０００２】
近年、様々なデータが、ＸＭＬ（eＸｔｅｎｓｉｂｌｅ  Ｍａｒｋｕｐ  Ｌａｎｇｕａ
ｇｅ）によって記述されることが多くなってきている。例えば、ＭＡＧＥ（ＭｉｃｒｏＡｒｒａｙ  ａｎｄ  Ｇｅｎｅ  Ｅｘｐｒｅｓｓｉｏｎ：ｈｔｔｐ：／／ｗｗｗ．ｍｇｅｄ．ｏｒｇ／Ｗｏｒｋｇｒｏｕｐｓ／ＭＡＧＥ／ｍａｇｅ．ｈｔｍｌ参照）、ＤＢＬＰ（Ｄｉｇｉｔａｌ  Ｂｉｂｌｉｏｇｒａｐｈｙ  ＆  Ｌｉｂｒａｒｙ  Ｐｒｏｊｅｃｔ：ｈｔｔｐ：／／ｗｗｗ．ｄｂｌｐ．ｕｎｉ−ｔｒｉｅｒ．ｄｅ／ｘｍｌ／参照）、ＡＣＭ  ＳＩＧＭＯＤ  Ｒｅｃｏｒｄ（ｈｔｔｐ：／／ｗｗｗ．ａｃｍ．ｏｒｇ／ｓｉｇｍｏｄ／ｒｅｃｏｒｄ／ｘｍｌ／参照）等のデータソースが、インターネット上にＸＭＬ文書によって公開されている。しかし、こうしたＸＭＬによって記述された複数のデータソースには、同じ情報が含まれていても、異なる構造でデータ化されている。例えば、ＸＭＬ文書に記述される文書型定義（ＤＴＤ：Ｄｏｃｕｍｅｎｔ  Ｔｙｐｅ  Ｄｅｆｉｎｉｔｉｏｎ）は、ＸＭＬ文書の構造に関する情報を取得するために、有用であるとされているが、同じＤＴＤで記述されているＸＭＬデータソースであっても、繰り返し或いは選択的な要素の数の違いで、同一の木構造に構成されていない。
【０００３】
そこで、利用者がより完全で有用な情報に容易にアクセスして利用できるように、ＸＭＬ文書同士を照合して、類似した情報を含むデータを統合し、より有用なデータとすることが、様々な分野で望まれている。例えば、バイオインフォマティクス（生命情報科学）の分野では、大量のデータがＸＭＬで記述されているが、各データには、類似の情報が混在しているため、各データから有用な情報を抽出して、それらのデータを統合することが求められている。また、論文の書誌的情報についても、同様に、データを統合することが求められている。例えば、図１４（ａ）に示すＸＭＬ文書「Ｂｉｂｌｉｏｇｒａｐｈｙ」と、図１４（ｂ）に示すＸＭＬ文書「ＰａｐｅｒＲｅｃｏｒｄ」とは、異なるＤＴＤで記述されているＸＭＬ文書の例である。これらの２つのＸＭＬ文書は、異なる構造を有するものであるが、同じデータ項目（例えば、この図１４（ａ）および（ｂ）に示す例では「ａｒｔｉｃｌｅ」）の中に、一方のＸＭＬ文書に含まれない情報が、他方のＸＭＬ文書に含まれている。すなわち、図１４（ａ）に示すＸＭＬ文書では「ｐａｇｅｓ」、図１４（ｂ）に示すＸＭＬ文書では「ｖｏｌｕｍｅ」が、それぞれ他方のＸＭＬ文書に含まれていない情報である。したがって、これらの同じデータが異なる構造で記述されたＸＭＬ文書同士を統合して、各ＸＭＬ文書が保有する全ての情報を含む新たなＸＭＬ文書とすることができれば、より完全で有用な情報に利用者が容易にアクセスすることができるデータベースの構築が可能となる。特に、近年、Ｗｅｂ上に蓄積され、公開されるデータが爆発的に増加している状況では、そのデータを統合することが重要となってきている。
【０００４】
このようなＸＭＬ文書同士を照合して、類似した情報を含むデータを統合する場合、まず、類似しているＸＭＬ文書を比較して、類似した部分を抽出する必要がある。そのため、従来、木の編集距離（Ｔｒｅｅ  Ｅｄｉｔ  Ｄｉｓｔａｎｃｅ）によって、ＸＭＬ文書における木構造の各ノードの間の相違を抽出することが行われ、あるいは提案されてきた。しかし、木の編集距離の計算は、高コストを要し、大きなＸＭＬ文書には適用できない、という問題がある。すなわち、複数のＸＭＬ文書の間の類似度を測るため、従来は、ＸＭＬ文書を構成する木構造について、二つの木構造の各ノードに対して、削除、挿入、置き換え、といった操作を行って同じ木構造に変更するために要する操作の手数を数えて木の編集距離を求め、木の編集距離が小さいものは類似しているとして、類似した部分木を見つけ出し、その部分木の異なる部分を統合する手法が取られていた（非特許文献１）。
【０００５】
しかし、木の編集距離による方法は、計算コストがノードの個数の４乗に比例して増加するため、ＸＭＬ文書のサイズが大きくなって対応する木構造を構成するノード数が増えると、実用に耐え得る時間で類似度を算出することが困難となるという問題点があった。
【０００６】
また、部分木の葉ノードの部分のみが異なるような場合、葉ノードの部分までは同じであるため、木の編集距離による方法では部分木の間の差を検出し難いという問題点もあった。さらに、ＸＭＬ文書を部分木に分割して、どのように部分木を構成するのか、さらに、どのようにすれば効率的に部分木を構成することができるか、また、部分木同士の類似度の判定という点に関しても、明らかではなかった。
【非特許文献１】S. Guha, H.V. Jagadish, N. Koudas, D. Srivastava and T. Yu. Approximate XML Joins. In Proc. of ACM SIGMOD 2002, pages 287-298, 2002.
【発明の開示】
【発明が解決しようとする課題】
【０００７】
そこで、本発明の第１の目的は、前記の問題を解決し、複数のＸＭＬ文書の間の類似度を高速かつ高効率、さらに低コストで検出することができる複数のＸＭＬ文書の類似度検出方法を提供することにある。
【０００８】
また、本発明の第２の目的は、複数のＸＭＬ文書の間の類似度を高速かつ高効率、さらに低コストで検出することができる複数のＸＭＬ文書の類似度検出システムを提供することにある。
【０００９】
さらに、本発明の第３の目的は、検出された類似度に基づいて複数のＸＭＬ文書を統合する複数のＸＭＬ文書の統合方法およびシステムを提供することにある。
【課題を解決するための手段】
【００１０】
前記課題を解決するため、本発明のＸＭＬ文書の類似度検出方法は、複数のＸＭＬ文書の類似度を検出する方法であって、一のＸＭＬ文書Ｔｂと、他のＸＭＬ文書Ｔｔとの間の類似度を検出するに際して、ＸＭＬ文書Ｔｂと、ＸＭＬ文書Ｔｔとを、それぞれ独立して意味を持つ最大の部分木構造に構成する段階（Ａ）と、前記ＸＭＬ文書Ｔｂを構成する部分木の葉ノードクラスタと、前記ＸＭＬ文書Ｔｔを構成する部分木の葉ノードクラスタとを照合して、照合する葉ノードクラスタの間で同じ内容を有する葉ノードの個数の比率に基づいて部分木間の類似度を求める段階（Ｄ）と、前記部分木間の類似度からＸＭＬ文書間の類似度を求める段階（Ｃ）とを含むことを特徴とする。
【００１１】
このＸＭＬ文書の類似度検出方法では、部分木の分割によって形成される、木構造のＸＭＬ文書Ｔｂと、ＸＭＬ文書Ｔｔとについて、求められるＸＭＬ文書間の類似度に基づいて、複数のＸＭＬ文書の間の類似性を高速かつ低コストで的確に検出することができる。
【００１２】
また、このＸＭＬ文書の類似度検出方法は、一のＸＭＬ文書Ｔｂと、他のＸＭＬ文書Ｔｔとの間の類似度を検出するに際して、ＸＭＬ文書Ｔｂと、ＸＭＬ文書Ｔｔとを、それぞれ３階以上の階層構造を有する木構造の部分木として分割する段階（Ａ）と、前記ＸＭＬ文書Ｔｂを構成するｋb個（ｋbは２以上の整数）の部分木ｔbi（ｉは１≦ｉ≦ｋbの整数）が含む葉ノードクラスタＬｂと、前記ＸＭＬ文書Ｔｔを構成するｋt個（ｋｔは２以上の整数）の部分木ｔtj（ｊは１≦ｊ≦ｋtの整数）が含む葉ノードクラスタＬｔとを照合して、葉ノードクラスタＬｂが有する葉ノードの個数ｎbiと、葉ノードクラスタＬｂと葉ノードクラスタＬｔとの間で同じ内容を有する葉ノードの個数ｎとに基づいて、下記式（１）：
【数７】
2007052556.tif 000003
で表される部分木の類似度Ｓ（ｔbi，ｔtj）を、部分木ｔbiと部分木ｔtjの全組み合わせ（ｋb×ｋt通り）について求める段階（Ｂ）と、前記の部分木ｔbiと部分木ｔtjの全組み合わせについて求められた部分木の類似度Ｓ（ｔbi，ｔtj）において、ｉ番目の部分木ｔbiと、１からｋt番目の部分木ｔtjとの各組み合わせに対してそれぞれ求められる前記部分木の類似度Ｓ（ｔbi，ｔtj）の中で、最大の値をＳM［ｉ］として、下記式（２）：
【数８】
2007052556.tif 000004
で表されるＸＭＬ文書間類似度Ｓ（Ｔｂ，Ｔｔ）を求める段階（Ｃ）とを含むことを特徴とする。
【００１３】
このＸＭＬ文書の類似度検出方法では、部分木の分割によって形成される、木構造のＸＭＬ文書Ｔｂと、ＸＭＬ文書Ｔｔとについて、前記部分木の類似度Ｓ（ｔbi，ｔtj）を求め、さらに、この部分木の類似度Ｓ（ｔbi，ｔtj）から求められるＸＭＬ文書間類似度Ｓ（Ｔｂ，Ｔｔ）に基づいて、複数のＸＭＬ文書の間の類似性を高速かつ低コストで的確に検出することができる。
【００１４】
また、請求項３に係る発明は、前記ＸＭＬ文書の類似度検出方法の前記段階（Ａ）において、自己から最も遠い子孫ノードまでの最大距離が３以上である或いは子ノード二つ以上を持つノードを候補ノードとし、前記候補ノードの子ノードの中で、候補ノードの個数ｎと、最も遠い子孫ノードまでの距離ｄと、所定の定数φ（０＜φ≦１）とに基づいて、下記式（３）で表されるパラメータｗを求め、木構造の中でそれぞれの上端から末端までの候補ノードが構成するトップダウン（ｔｏｐ−ｄｏｗｎ）パスでｗが一番大きなノードで、ＸＭＬ文書ＴｂおよびＸＭＬ文書Ｔｔを独立して意味を持つ部分木に分割して行うことを特徴とする。
ｗ＝ｎ×ｄφ                                （３）
【００１５】
この複数のＸＭＬ文書の類似度検出方法では、前記パラメータｗに基づいて、ＸＭＬ文書ＴｂおよびＸＭＬ文書Ｔｔを独立して意味を持つ部分木に分割することができ、複数のＸＭＬ文書間の類似度の検出を高効率かつ的確に行うことが可能となる。
【００１６】
また、請求項４に係る発明は、前記複数のＸＭＬ文書の類似度検出方法において、前記段階（Ｂ）は、各葉ノードクラスタが含む葉ノードが有する構文解析対象文字データを照合して、前記葉ノードクラスタＬｂが含む葉ノードと、前記葉ノードクラスタＬｔが含む葉ノードとが同一の内容のものであるか否かを決定することを特徴とする。
【００１７】
この複数のＸＭＬ文書の類似度検出方法では、各葉ノードクラスタが含む構文解析対象文字データを照合して、前記葉ノードクラスタＬｂと、前記葉ノードクラスタＬｔとが同一であるか否かを決定することによって、木の編集距離による類似度の検出に比べて、部分木同士の類似度の判定を正確かつ迅速に行うことができるため、複数のＸＭＬ文書間の類似度の検出を高効率かつ的確に行うことが可能となる。
【００１８】
請求項５に係る発明は、前記複数のＸＭＬ文書の類似度検出方法によって求められたＸＭＬ文書間類似度Ｓ（Ｔｂ，Ｔｔ）が所定の値よりも高い値を示す部分木ｔbi，ｔtjの組み合わせを選び、その２つの部分木が含む異なる葉ノードを抽出して差分とし、その差分を一方のＸＭＬ文書の部分木に付加することで、２つのＸＭＬ文書の統合を行うことを特徴とする複数のＸＭＬ文書の統合方法を提供する。
【００１９】
このＸＭＬ文書の統合方法では、前記ＸＭＬ文書間類似度Ｓ（Ｔｂ，Ｔｔ）が高い値を示す部分木ｔbi，ｔtjの組み合わせを選び、２つのＸＭＬ文書の統合を行うことによって、低コストかつ高効率で複数のＸＭＬ文書を統合することが可能となる。
【００２０】
さらにまた、請求項６に記載の発明は、複数のＸＭＬ文書の類似度をコンピュータによって検出するシステムであって、前記コンピュータが、一のＸＭＬ文書Ｔｂと、他方のＸＭＬ文書Ｔｔとを、それぞれ複数の部分木で構成される木構造に分割する部分木分割部と、前記分割によって形成される、ｋb個の部分木ｔbi（１≦ｉ≦ｋb：ｋbは２以上の整数）で構成されるＸＭＬ文書Ｔｂと、ｋt個の部分木ｔtj（１≦ｊ≦ｋt：ｋtは２以上の整数）で構成されるＸＭＬ文書Ｔｔとについて、部分木ｔbiを構成するｎbi個の葉ノードを持つ葉ノードクラスタＬｂと、部分木ｔtjを構成する葉ノードクラスタＬｔとを照合して、葉ノードクラスタＬｂと葉ノードクラスタＬｔとの間で同じ内容を有する葉ノードの個数ｎを求め、前記式（１）に従って、部分木の類似度Ｓ（ｔbi，ｔtj）を求める部分木類似度演算部と、前記の部分木ｔbiと部分木ｔtjの全組み合わせについて求められた部分木の類似度Ｓ（ｔbi，ｔtj）において、ｉ番目の部分木ｔbiと、１からｋt番目の部分木ｔtjとの各組み合わせに対してそれぞれ求められる前記部分木の類似度Ｓ（ｔbi，ｔtj）の中で、最大の値をＳM［ｉ］として、前記式（２）で表されるＸＭＬ文書間類似度Ｓ（Ｔｂ，Ｔｔ）を求めるＸＭＬ類似度演算部とを備えることを特徴とする複数のＸＭＬ文書の類似度検出システム。
【００２１】
この複数のＸＭＬ文書の類似度検出システムでは、部分木分割部における分割によって形成される、木構造のＸＭＬ文書Ｔｂと、ＸＭＬ文書Ｔｔとについて、前記部分木の類似度Ｓ（ｔbi，ｔtj）を求め、さらに、この部分木の類似度Ｓ（ｔbi，ｔtj）から求められるＸＭＬ文書間類似度Ｓ（Ｔｂ，Ｔｔ）に基づいて、複数のＸＭＬ文書の間の類似性を高速かつ低コストで的確に検出することができる。
【００２２】
また、請求項７に係る発明は、複数のＸＭＬ文書の類似度をコンピュータによって検出して、ＸＭＬ文書を統合するシステムであって、前記コンピュータが、一のＸＭＬ文書Ｔｂと、他方のＸＭＬ文書Ｔｔとを、それぞれ複数の部分木で構成される木構造に分割する部分木分割部と、前記分割によって形成される、ｋb個の部分木ｔbi（１≦ｉ≦ｋb：ｋbは２以上の整数）で構成されるＸＭＬ文書Ｔｂと、ｋt個の部分木ｔtj（１≦ｊ≦ｋt：ｋtは２以上の整数）で構成されるＸＭＬ文書Ｔｔとについて、部分木ｔbiを構成するｎbi個の葉ノードを持つ葉ノードクラスタＬｂと、部分木ｔtjを構成する葉ノードクラスタＬｔとを照合して、葉ノードクラスタＬｂと葉ノードクラスタＬｔとの間で同じ内容を有する葉ノードの個数ｎを求め、下記式（１）に従って、部分木の類似度Ｓ（ｔbi，ｔtj）を求める部分木類似度演算部と、前記の部分木ｔbiと部分木ｔtjの全組み合わせについて求められた部分木の類似度Ｓ（ｔbi，ｔtj）において、ｉ番目の部分木ｔbiと、１からｋt番目の部分木ｔtjとの各組み合わせに対してそれぞれ求められる前記部分木の類似度Ｓ（ｔbi，ｔtj）の中で、最大の値をＳM［ｉ］として、前記式（２）で表されるＸＭＬ文書間類似度Ｓ（Ｔｂ，Ｔｔ）を求めるＸＭＬ類似度演算部と、前記ＸＭＬ類似度演算部によって求められたＸＭＬ文書間類似度Ｓ（Ｔｂ，Ｔｔ）が所定の値よりも高い値を示す部分木ｔbi，ｔtjの組み合わせを選び、その２つの部分木が含む異なる葉ノードクラスタを抽出して差分とし、その差分を一方のＸＭＬ文書の部分木に付加することで、２つのＸＭＬ文書の統合を行う統合演算部を備えることを特徴とする複数のＸＭＬ文書の統合システムを提供する。
【００２３】
この複数のＸＭＬ文書の統合システムでは、前記ＸＭＬ文書間類似度Ｓ（Ｔｂ，Ｔｔ）に基づいて、ＸＭＬ文書間類似度Ｓ（Ｔｂ，Ｔｔ）が高い値を示す部分木ｔbi，ｔtjの組み合わせを選び、２つのＸＭＬ文書を統合することによって、低コストかつ高効率で複数のＸＭＬ文書を統合することが可能となる。
【発明の効果】
【００２４】
本発明の複数のＸＭＬ文書の類似度検出方法および検出システムによれば、複数のＸＭＬ文書の間の類似度を高速かつ高効率、さらに低コストで検出することができる。例えば、従来の木の編集距離による類似度の検出方法では、計算コスト（時間）がノードの個数の４乗に比例して増加するのに対して、計算コストはノードの個数の２乗に比例して増加する。そのため、特に、本発明の方法は、ＸＭＬ文書のサイズが大きくなるほど、従来の方法よりも有効となる。
【００２５】
すなわち、本発明においては、比較するＸＭＬ文書から構成される木構造を解析して意味のある部分木に分割し、類似度の検出に有効な部分木を有する木構造を構成できる。そして、本発明の類似度検出方法では、部分木の葉ノードのみでデータの突合せを行って部分木の類似性を判定することで、低コストで類似した部分を抽出し、高速で類似度を算出し、葉ノードの部分のみが異なってその上位のノードが同じ部分木の間の差を明確にすることができる。従来の方法、例えば、木の編集距離による方法では、部分木の葉ノードの部分のみが異なるような場合、葉ノードの部分までは同じなので、部分木の間の差を明確に検出することが困難であるが、本発明の方法では、その差を明確に検出することが可能となる。
【００２６】
さらに、本発明のＸＭＬ文書の統合方法によれば、複数のＸＭＬ文書に含まれる情報を統合して完全でより有用な情報を含むデータを得ることができる。そして、このＸＭＬ文書の統合に際して、容易に常用の結合方法（例えば、ソート・マージ結合、ネステッド・ループ結合、クラスタ結合、ハッシュ結合等）を適用してＸＭＬ文書を統合できる利点がある。
【００２７】
本発明は、同じデータが異なる構造で記述されたＸＭＬ文書同士を統合して、各ＸＭＬ文書が保有する全ての情報を含む新たなＸＭＬ文書として、より完全で有用な情報に利用者が容易にアクセスすることができるデータベースの構築、さらに、情報の統合による新たな知見が可能となる。例えば、バイオインフォマテックス、文献情報、電子商取引（E-business）等の各種の分野で、ＸＭＬで記述された複数のデータを統合して、調査・研究に有用なデータをを得るために有効である。特に、近年、Ｗｅｂ上に蓄積され、公開されるデータが爆発的に増加している状況では、そのデータを統合することが重要となっているため、本発明のＸＭＬ文書の統合方法およびシステムは、有用である。
【発明を実施するための最良の形態】
【００２８】
次に、本発明の実施形態について、適宜、図面を参照しながら詳細に説明する。
以下、まず、本発明において、２つのＸＭＬ文書Ｔｂ，Ｔｔの類似度を検出する方法について説明する。
この方法は、一のＸＭＬ文書Ｔｂと、他方のＸＭＬ文書Ｔｔとを、それぞれ複数の部分木で構成される木構造に分割して行う段階（Ａ）と、各ＸＭＬ文書を構成する部分木が含む葉ノードクラスタ同士を照合して、部分木の類似度Ｓ（ｔbi，ｔtj）を求める段階（Ｂ）と、２つのＸＭＬ文書Ｔｂ，Ｔｔの類似度であるＸＭＬ文書間類似度Ｓ（Ｔｂ，Ｔｔ）を求める段階（Ｃ）とを含む。
【００２９】
段階（Ａ）は、一のＸＭＬ文書Ｔｂと、他方のＸＭＬ文書Ｔｔとを、それぞれ複数の部分木で構成されるツリー構造に分割する。この段階（Ａ）において、図１（ａ）および図１（ｂ）に示すように、ＸＭＬ文書ＴｂおよびＸＭＬ文書Ｔｔは、それぞれ３階以上の階層構造を有するツリー構造に構成される。すなわち、図１（ａ）に示すように、ＸＭＬ文書Ｔｂは、ｋb個（ｋｂは２以上の整数）の部分木ｔbi（ｉは１≦ｉ≦ｋｂの整数）で構成され、部分木ｔbiのそれぞれは、複数の葉ノードクラスタＬbを含む木構造を形成する。また、図１（ｂ）に示すように、ＸＭＬ文書Ｔｔは、ｋt個（ｋｔは２以上の整数）の部分木ｔtj（ｊは１≦ｊ≦ｋｔの整数）で構成され、各部分木ｔtjは複数の葉ノードクラスタＬtで構成される木構造を形成する。
【００３０】
この段階（Ａ）において、各部分木ｔbi，ｔtjが下記の要件を満足するように分割される。
（ａ）各部分木は、一の独立項目のみを含む。すなわち、部分木は、他の項目に属する情報を含まない。
（ｂ）一の独立項目は、一の部分木しか対応しない。すなわち、一の独立項目は、対応する部分木を１つ以上持たない。
（ｃ）各部分木は、可能な限り代表している項目の多くの情報項目を含む。すなわち、その情報項目に属する多くの葉ノードは、可能な限りその部分木に含まれる。
【００３１】
段階（Ａ）において、適切に分割された部分木を有する木構造として、前記の図１４（ｂ）に示す木構造のＸＭＬ文書（ＰａｐｅｒＲｅｃｏｒｄ）を分割した例を、図２に示す。
このＸＭＬ文書（ＰａｐｅｒＲｅｃｏｒｄ）の木構造において、木構造の先端の「ＸＭＬ」、「Ｊｏｈｎ」、「Ｊａｎｅ」、「１０」、「ＸＭＬＪｏｉｎｓ」等は、それぞれ、部分木「ａｒｔｉｃｌｅ」の葉ノードを示す。
【００３２】
さらに、ＸＭＬ文書ＴｂおよびＴｔのノードの中で、自分から最も遠い子孫ノードまでの最大距離が３以上である或いは子ノード二つ以上を持つノードを候補ノードとし、前記候補ノードの子ノード中で、候補ノードの個数ｎと、最も遠い子孫ノードまでの距離ｄと、所定の定数φ（０＜φ≦１）とに基づいて、下記式（３）で表されるパラメータｗを求め、木構造の中でそれぞれの上端から末端までの候補ノードが構成するトップダウン（top-down）パスでｗが一番大きなノードで、ＸＭＬ文書ＴｂおよびＸＭＬ文書Ｔｔを独立して意味を持つ部分木を分割して行うことが好ましい。
ｗ＝ｎ×ｄφ                                （３）
前記定数φは、予め実験等によって決定することができる。例えば、漸次減少のφ（例えば、φ＝１，０．９，０．８，…）で一つのＸＭＬ文書を前記の方法で分割し、それぞれ分割された部分木の個数（Ｍと示す）と各部分木が含む葉ノードの平均個数（Ｎと示す）と、一番大きなＭ×Ｎ値によって定数φを決定することができる。通常、φは、１である。
【００３３】
このパラメータｗによる部分木の分割は、例えば、下記のアルゴリズムによって行うことができる。
【数９】
2007052556.tif 000005
【００３４】
このパラメータｗによる部分木分割のアルゴリズムを、図２に示す木構造について説明すると、図３に示すように、ルートノードから下ノードへのトップダウン（top-down）パスが２つある。この２つのパスの中で、左側のパス［ＰａｐｅｒＲｅｃｏｒｄ（１，５），ａｒｔｉｃｌｅｓ（２，４），ａｒｔｉｃｌｅ（１，３），ａｕｔｈｏｒｓ（０，２）］においては、パラメータｗの最大値が２×４＝８（ここで、定数φが１と仮定している）であるノード：ａｒｔｉｃｌｅ（２，４）が、分割における候補ノードとなる。また、同様に、右側のパスにおいては、ａｒｔｉｃｌｅ（１，３）が、分割における候補ノードとなる。これによって、ＸＭＬ文書（ＰａｐｅｒＲｅｃｏｒｄ）は、図３中に楕円で囲んだ２つの部分木に分割される。
【００３５】
次に、段階（Ｂ）においては、前記段階（Ａ）で求められた木構造を有するＸＭＬ文書Ｔｂと、ＸＭＬ文書Ｔｔとについて、ＸＭＬ文書Ｔｂを構成するｋb個（ｋｂは２以上の整数）の部分木ｔbi（ｉは１≦ｉ≦ｋｂの整数）を構成する葉ノードクラスタＬｂと、ＸＭＬ文書Ｔｔを構成するｋt個の部分木ｔtj（ｊは１≦ｊ≦ｋt）を構成する葉ノードクラスタＬｔとを照合する。そして、照合の結果、葉ノードクラスタＬｂが有する葉ノードの個数ｎbiと、葉ノードクラスタLｂと葉ノードクラスタLｔとの間で同じ内容を有する葉ノードの個数ｎとに基づいて、前記式（１）で表される部分木の類似度Ｓ（ｔbi，ｔtj）を、部分木ｔbiと部分木ｔtjの全組み合わせ（ｋb×ｋt通り）について求める。
【００３６】
この段階（Ｂ）における各部分木を構成する葉ノード同士の照合による部分木の類似度Ｓ（ｔbi，ｔtj）の算出について、図４に示す木構造を有する２つのＸＭＬ文書Ｔｂ，Ｔｔを例にして説明する。
この図４に示すＸＭＬ文書Ｔｂ，Ｔｔは、それぞれ、２つの部分木ｔb1，ｔb2、ｔt1，ｔt2を有する。ＸＭＬ文書Ｔｂにおいて、部分木ｔb1は葉ノードＡ，Ｂ，Ｃを、部分木ｔb2は葉ノードＣ，Ｄ，Ｅを、それぞれ有する。また、ＸＭＬ文書Ｔｔにおいて、部分木ｔt1は葉ノードＤ，Ａ，Ｅを、部分木ｔt2は葉ノードＡ，Ｃ，Ｅを、それぞれ有する。
【００３７】
この段階（Ｂ）において、部分木ｔbjと部分木ｔtjとの間で同じ値を有する葉ノードは、各葉ノードに含まれる構文解析対象文字データ（ＰＣＤＡＴＡ：ｐａｒｓｅｄ  ｃｈａｒａｃｔｅｒ  ｄａｔａ）を比較して、同一性を判定することができる。これによって、部分木ｔbjと部分木ｔtjとの間で同じ値を有する葉ノードの個数ｎを決定することができる。また、各葉ノードに含まれる文字列のセマンティックスの違いを比較して、同一性の判定を行うこともできる。これによって、より正確な同一性の判定を行うことができるとともに、ＸＭＬ文書の統合に際しては、より精細なＸＭＬ文書の統合が可能となる。
【００３８】
このＸＭＬ文書Ｔｂと、ＸＭＬ文書Ｔｔとの間の類似度の検出において、まず、図５（ａ）に示すように、部分木ｔb1の葉ノードＡ，Ｂ，Ｃに対して、部分木ｔt1の葉ノードＤ，Ａ，Ｅとを照合する。このとき、部分木ｔb1と部分木ｔt1との間では、同じ内容を有する葉ノードの個数（ｎ）は１、部分木ｔb1の個数（ｎb）は３であるから、部分木類似度Ｓ（ｔb1，ｔt1）は、１／３＝０．３３３と計算される。
次に、部分木ｔb1の葉ノードＡ，Ｂ，Ｃに対して、部分木ｔt2の葉ノードＡ，Ｃ，Ｂとを照合する。このとき、部分木ｔb1と部分木ｔt2との間では、同じ内容を有する葉ノードの個数（ｎ）は３、部分木ｔb1の個数（ｎb）は３であるから、部分木類似度Ｓ（ｔb1，ｔt1）は、３／３＝１と計算される。
【００３９】
さらに、図５（ｂ）に示すように、部分木ｔb2の葉ノードＣ，Ｄ，Ｅに対して、部分木ｔt1の葉ノードＤ，Ａ，Ｅとを照合する。このとき、部分木ｔb2と部分木ｔt1との間では、同じ値を有する葉ノードの個数（ｎ）は２、部分木ｔb1の個数（ｎb）は３であるから、部分木類似度Ｓ（ｔb1，ｔt1）は、２／３＝０．６６７と計算される。
【００４０】
次に、部分木ｔb2の葉ノードＣ，Ｄ，Ｅに対して、部分木ｔt2の葉ノードＡ，Ｃ，Ｂとを照合する。このとき、部分木ｔb2と部分木ｔt2との間では、同じ値を有する葉ノードの個数（ｎ）は１、部分木ｔb1の個数（ｎb）は３であるから、部分木類似度Ｓ（ｔb1，ｔt1）は、１／３＝０．３３３と計算される。
【００４１】
次に、段階（Ｃ）においては、前記の部分木ｔbiと部分木ｔtjの全組み合わせについて求められた部分木の類似度Ｓ（ｔbi，ｔtj）において、ｉ番目の部分木ｔbiと、１からｋt番目の部分木ｔtjとの各組み合わせに対してそれぞれ求められた前記部分木の類似度Ｓ（ｔbi，ｔtj）の中で、最大の値をＳM［ｉ］として、前記式（２）で表されるＸＭＬ文書間類似度Ｓ（Ｔｂ，Ｔｔ）を求める。すなわち、１番目の部分木ｔb1と、１からｋt番目の部分木ｔtjとの各組み合わせに対して、それぞれ求められた部分木類似度Ｓ（ｔb1，ｔt1），Ｓ（ｔb1，ｔt2），・・・・，Ｓ（ｔb1，ｔtkt）の中で、最大の部分木類似度の値をＳM［１］とする。同様に、２番目の部分木ｔb2と、１からｋt番目の部分木ｔtjとの各組み合わせに対して、それぞれ求められた部分木類似度Ｓ（ｔb2，ｔt1），Ｓ（ｔb2，ｔt2），・・・・，Ｓ（ｔb2，ｔtkt）の中で、最大の部分木類似度の値をＳM［２］とする。このステップを同様に繰り返して、ＳM［３］，・・・・，ＳM［ｋｂ］を求める。
そして、このようにして求められたＳM［１］〜ＳM［ｋｂ］とによって、前記式（２）で表されるＸＭＬ文書間類似度Ｓ（Ｔｂ，Ｔｔ）を計算する。
【００４２】
この段階（Ｃ）におけるＸＭＬ文書間類似度Ｓ（Ｔｂ，Ｔｔ）の計算について、前記図４に示す図４に示す木構造を有する２つのＸＭＬ文書Ｔｂ，Ｔｔについて求めると、ＳM［１］は１、ＳM［２］は０．６６７となるから、ＸＭＬ文書間類似度Ｓ（Ｔｂ，Ｔｔ）は、前記式（２）から、（１＋０．６６７）／２＝０．８３４と計算される。
【００４３】
以上の段階（Ａ）〜段階（Ｃ）において、求められたＸＭＬ文書間類似度Ｓ（Ｔｂ，Ｔｔ）によって、２つのＸＭＬ文書ＴｂとＸＭＬ文書Ｔｔとの間の類似性を判定して、両ＸＭＬ文書間の統合を行うことができる。例えば、前記ＸＭＬ文書間類似度Ｓ（Ｔｂ，Ｔｔ）が所定のしきい値τ（０＜τ≦１）よりも大きい値を示す場合、ＸＭＬ文書Ｔｂと、ＸＭＬ文書Ｔｔとが、類似性を有し、両ＸＭＬ文書を統合することによって、より有用なＸＭＬ文書からなるデータソースの構築が可能である、と決定することができる。
【００４４】
ここで、前記部分木の類似度Ｓ（ｔbi，ｔtj）の計算、ならびにＸＭＬ文書間類似度Ｓ（Ｔｂ，Ｔｔ）の計算、およびＳ（Ｔｂ，Ｔｔ）としきい値τとの比較を行うアルゴリズムの一例を以下に示す。
【数１０】
2007052556.tif 000006
【００４５】
次に、本発明の複数のＸＭＬ文書の統合方法について説明する。
この方法は、前記の段階（Ａ）と、段階（Ｂ）と、段階（Ｃ）とを含み、さらに、段階（Ｃ）において求められたＸＭＬ文書間類似度Ｓ（Ｔｂ，Ｔｔ）に基づいて、各ＸＭＬ文書を構成する部分木同士で類似度が高いものを選び、各部分木の間の異なる葉ノードを抽出して、その差分を一方の部分木に付加することで、ＸＭＬ文書の統合を行う段階（Ｄ）を含むものである。このとき、予め定めたしきい値τ（０＜τ≦１）以上の部分木類似度を有する部分木同士をヒットした部分木とし、そのヒットした部分木を統合することによって、２つのＸＭＬ文書Ｔｂ，Ｔｔを統合することができる。しきい値τは、統合するＸＭＬ文書の内容、構造、大きさ等によって、統合されたＸＭＬ文書を逐次検証することによって選択することができる。
【００４６】
このＸＭＬ文書の統合に際して、２つのＸＭＬ文書の結合は、特に制限されず、公知の方法を適用して行うことができる。例えば、ソート・マージ結合、ネステッド・ループ結合、クラスタ結合、ハッシュ結合等によって、ＸＭＬ文書の結合を行うことができる。
【００４７】
この複数のＸＭＬ文書の統合によって得られる新たなＸＭＬ文書の具体例として、図１４（ａ）に示すＸＭＬ文書「Ｂｉｂｌｉｏｇｒａｐｈｙ」と、図１４（ｂ）に示すＸＭＬ文書「ＰａｐｅｒＲｅｃｏｒｄ」とを統合したＸＭＬ文書の例を図６に示す。図６に示すとおり、２つのＸＭＬ文書「Ｂｉｂｌｉｏｇｒａｐｈｙ」，「ＰａｐｅｒＲｅｃｏｒｄ」を統合して、両ＸＭＬ文書が含む情報を統合した新たなＸＭＬ文書「ＰａｐｅｒＲｅｃｏｒｄ」を得ることができる。この新たなＸＭＬ文書「ＰａｐｅｒＲｅｃｏｒｄ」は、ＸＭＬ文書に含まれない情報が、他方のＸＭＬ文書に含まれている。すなわち、図１４（ａ）に示すＸＭＬ文書「Ｂｉｂｌｉｏｇｒａｐｈｙ」に含まれるが、図１４（ｂ）に示すＸＭＬ文書「ＰａｐｅｒＲｅｃｏｒｄ」に含まれていない「ｐａｇｅ」の項目をＸＭＬ文書「ＰａｐｅｒＲｅｃｏｒｄ」に付加して、図６に示す新たなＸＭＬ文書「ＰａｐｅｒＲｅｃｏｒｄ」を構成したものである。
【００４８】
前記に説明した実施形態では、２つのＸＭＬ文書Ｔｂ，Ｔｔの類似度を検出する方法およびその類似度に基づいて、２つのＸＭＬ文書を統合する方法について説明したが、本発明の方法は、２つのＸＭＬ文書の類似度の検出および統合する方法のみに限定されず、３以上のＸＭＬ文書の間の類似度の検出および各文書の統合する方法をも含む。すなわち、本発明の方法においては、複数のＸＭＬ文書Ｔ１，Ｔ２，Ｔ３・・・・の中から、一対のＸＭＬ文書を選択し、その２つのＸＭＬ文書の間の類似度を検出するステップを各対のＸＭＬ文書に対して繰り返し、所定の値以上の類似度を示す２つのＸＭＬ文書を選択し、両ＸＭＬ文書を統合して新たなＸＭＬ文書を得ることができる。
【００４９】
次に、前記の複数のＸＭＬ文書の類似度検出方法にしたがって、複数のＸＭＬ文書の類似度を検出するシステム（以下、「ＸＭＬ文書類似度検出システム」という）および複数のＸＭＬ文書の統合システム（以下、「ＸＭＬ文書の統合システム」という）について説明する。
図７は、ＸＭＬ文書類似度検出システム４と、ＸＭＬ文書の統合システム６とを示す。
【００５０】
図７に示すＸＭＬ文書類似度検出システム４は、部分木分割部１と、部分木類似度演算部２と、ＸＭＬ類似度演算部３とを備える。
部分木分割部１は、一のＸＭＬ文書Ｔｂと、他方のＸＭＬ文書Ｔｔとを、それぞれ複数の部分木で構成される木構造に分割して行う。この部分木分割部１における木構造の分割操作については、前記段階（Ａ）について説明したとおりである。
【００５１】
部分木類似度演算部２は、前記部分木の分割によって形成される、ｋb個の部分木ｔbi（１≦ｉ≦ｋb：ｋbは２以上の整数）で構成されるＸＭＬ文書Ｔｂと、ｋt個の部分木ｔtj（１≦ｊ≦ｋt：ｋtは２以上の整数）で構成されるＸＭＬ文書Ｔｔとについて、部分木ｔbiを構成するnbi個のノードを持つ葉ノードクラスタＬｂと、部分木ｔtjを構成する葉ノードクラスタＬｔとを照合して、同じ内容を持つ葉ノードの個数ｎを求め、前記式（１）に従って、部分木の類似度Ｓ（ｔbi，ｔtj）を求める。この部分木類似度演算部２における部分木の類似度Ｓ（ｔbi，ｔtj）の演算は、前記段階（Ｂ）について説明したとおりである。
【００５２】
ＸＭＬ類似度演算部３は、前記の部分木ｔbiと部分木ｔtjの全組み合わせについて求められた部分木の類似度Ｓ（ｔbi，ｔtj）において、ｉ番目の部分木ｔbiと、１からｋt番目の部分木ｔtjとの各組み合わせに対してそれぞれ求められる前記部分木の類似度Ｓ（ｔbi，ｔtj）の中で、最大の値をＳM［ｉ］として、前記式（２）で表されるＸＭＬ文書間類似度Ｓ（Ｔｂ，Ｔｔ）を求める。このＸＭＬ類似度演算部３におけるＸＭＬ文書間類似度Ｓ（Ｔｂ，Ｔｔ）の演算は、前記段階（Ｃ）について説明したとおりである。
【００５３】
また、ＸＭＬ文書の統合システムは、図７に示すとおり、前記の部分木分割部１と、部分木類似度演算部２と、ＸＭＬ類似度演算部３とを備えるＸＭＬ文書類似度検出システム４に、さらに、前記ツリー類似度演算部３によって求められたＸＭＬ文書間類似度Ｓ（Ｔｂ，Ｔｔ）が高い値を示す部分木ｔbi，ｔtjの組み合わせを選び、その２つの部分木が含む異なる葉ノードを抽出して差分とし、その差分を一方のＸＭＬ文書の部分木に付加することで、２つのＸＭＬ文書の統合を行う統合演算部５を備えるものである。
【００５４】
このＸＭＬ文書の統合システムの統合演算部５における２つのＸＭＬ文書の統合の方法は、前記段階（Ｄ）について説明したとおりである。
【００５５】
本発明において、前記の複数のＸＭＬ文書の類似度検出システムおよび複数のＸＭＬ文書の統合システムは、単独のコンピュータにて一体的に実現させることもできるし、部分木分割部１、ツリー類似度演算部２、ＸＭＬ類似度演算部３、または統合演算部５の各部またはその一部がそれぞれ独立した装置で構成されて実現させることもできる。
【００５６】
また、本発明の複数のＸＭＬ文書の類似度検出システムは、コンピュータに記録または格納させることによって、前記の段階（Ａ）〜段階（Ｃ）を行う部分木分割部１、部分木類似度演算部２、ＸＭＬ類似度演算部３が構成されるように記述されたプログラム、およびそのプログラムを記録した記録媒体の形態で提供することができる。さらに、本発明の複数のＸＭＬ文書の統合システムは、コンピュータに記録または格納させることによって、前記の段階（Ａ）〜段階（Ｃ）を行う前記の部分木分割部１、ツリー類似度演算部２およびＸＭＬ類似度演算部３と、前記段階（Ｄ）を行う統合演算部５とが構成されるように記述されたプログラム、およびそのプログラムを記録した記録媒体の形態で提供することができる。
【実施例】
【００５７】
以下、本発明の実施例および比較例により、本発明についてより具体的に説明するが、本発明は、以下の実施例に限定されるものではない。
【００５８】
（実施例、比較例）
実際に、合成データ群と、実データ群とのそれぞれについて、従来の木の編集距離によってＸＭＬ文書間の類似性を検出する場合（比較例）と、本発明の方法によってＸＭＬ文書間の類似性を検出する場合（実施例）とについて、検出効率および効果を評価した。
【００５９】
この実験においては、合成データ群として、ＤＴＤを入力することによってＸＭＬ文書をランダムに生成するＩＢＭ  ＸＭＬ  Ｇｅｎｅｒａｔｏｒ（ｈｔｔｐ：／／ｗｗｗ．ａｌｐｈａｗｏｒｋｓ．ｉｂｍ．ｃｏｍ／ｘｍｌ／参照）を用いて、ＳｉｇｍｏｄＲｅｃｏｒｄ．ｄｔｄ（ｈｔｔｐ：／／ｗｗｗ．ａｃｍ．ｏｒｇ／ｓｉｇｍｏｄ／ｒｅｃｏｒｄ／ｘｍｌ／参照）から、２つのパラメータ：ＭａｘＬｅｖｅｌｓとＭａｘＲｅｐｅａｔｓを変化させることによって、異なるサイズのＸＭＬ文書をランダムに生成させた。
生成したＸＭＬ文書のサイズは、１〜１５０ＫＢ（約０〜５０００ノード）の範囲であった。
【００６０】
一方、実データ群として、下記の２つのＸＭＬ文書を用いた。
（ａ）ＡＣＭ  ＳＩＧＭＯＤ  ｒｅｃｏｒｄのＸＭＬバージョン（ｈｔｔｐ：／／ｗｗｗ．ａｃｍ．ｏｒｇ／ｓｉｇｍｏｄ／ｒｅｃｏｒｄ／ｘｍｌ／参照）から、ＯｒｄｉｎａｒｙＩｓｓｕｅＰａｇｅ，ＰｒｏｃｅｅｄｉｎｇｓＰａｇｅおよびＳｉｇｍｏｄＲｅｃｏｒｄに関するＸＭＬ文書
（ｂ）ＤＢＬＰデータベースのＸＭＬ文書（ｈｔｔｐ：／／ｗｗｗ．ｄｂｌｐ．ｕｎｉ−ｔｒｉｅｒ．ｄｅ／ｘｍｌ／参照）
【００６１】
実験は、下記の条件下で行った。
実験条件：
ＣＰＵ                  インテル社  ＰＥＮＴＩＵＭ（登録商標）  ＩＶ  ２．８０ＧＨｚ
メモリ                  １．０ＧＢ
ＯＳ                    マイクロソフト社  ＷＩＮＤＯＷＳ（登録商標）  ＸＰ  Ｐｒｏｆｅｓｓｉｏｎａｌ
プログラム環境          サン・マイクロシステムズ社  ＪＤＫ（登録商標）  １．４．２
【００６２】
前記合成データ群から、ノード個数が１２００以下のＸＭＬ文書の組み合わせについて、そのＸＭＬ文書の間の類似度の検出を、本発明による方法、および木の編集距離による方法のそれぞれによって行い、計算時間を比較した。結果を図８に示す。図８において、「ＬＡＸ）は本発明による方法を示す。
【００６３】
この図８に示す結果から、本発明の方法は、ノード個数が５００以上の場合には、木の編集距離による方法に比べて圧倒的に早く類似度を検出できることが分かる。したがって、本発明の方法は、ＸＭＬ文書間の類似度の検出を、木の編集距離による場合よりも効率的に行うことができることが分かる。
【００６４】
次に、前記実データ群の（ａ）ＡＣＭ  ＳＩＧＭＯＤ  ｒｅｃｏｒｄのＸＭＬ文書、および（ｂ）ＤＢＬＰデータベースのＸＭＬ文書との２つのＸＭＬ文書について、木の編集距離と、本発明の方法によるＸＭＬ文書間類似度とを求めた。
【００６５】
この木の編集距離およびＸＭＬ文書間類似度の実際の計算に際しては、木の編集距離の計算は非常に時間が掛かるため、（ａ）ＡＣＭ  ＳＩＧＭＯＤ  ｒｅｃｏｒｄのＸＭＬ文書を小さい部分にわけ、同様に、（ｂ）ＤＢＬＰデータベースのＸＭＬ文書を６つのｄｂｌｐ１．ｘｍｌ〜ｄｂｐｌ６．ｘｍｌの各部分に分けた。各部分は、それぞれほぼ同じノード個数を有する。下記表１に、各ＸＭＬ文書の部分におけるノード個数（Ｎｏ．ｏｆ  ｎｏｄｅｓ）と部分木の個数（Ｎｏ．ｏｆ  ｓｕｂｔｒｅｅｓ）を示す。
【表１】
2007052556.tif 000007
【００６６】
このｓｉｇｍｏｄ．ｘｍｌと、６つのｄｂｌｐ１．ｘｍｌ〜ｄｂｌｐ６．ｘｍｌのそれぞれとの組み合わせについて、木の編集距離（Ｔｒｅｅ  ｅｄｉｔ  ｄｉｓｔａｎｃｅ）、ＸＭＬ文書間類似度（Ｔｒｅｅ  ｓｉｍｉｌａｒｉｔｙ  ｄｅｇｒｅｅ）、およびＸＭＬ文書を構成する木構造の中で実際に適合する部分木の個数（Ｎｏ．ｏｆ  ｈｉｔ  ｓｕｂｔｒｅｅｓ）を求めた。結果を表２に示す。
【００６７】
【表２】
2007052556.tif 000008
【００６８】
表２に示す結果から、前記の６つの組み合わせについて求められる木の編集距離は、ほぼ同じ値を示すが、ＸＭＬ文書間類似度（Ｔｒｅｅ  ｓｉｍｉｌａｒｉｔｙ  ｄｅｇｒｅｅ）については、図９に示すように、実際に適合する部分木の個数（Ｎｏ．ｏｆ  ｈｉｔ  ｓｕｂｔｒｅｅｓ）に比例して大きい値を示すことが分かる。
このことから、木の編集距離が同じ値を有する場合でも、本発明の方法によれば、ＸＭＬ文書間の類似度の差を明確に識別できることが分かる。すなわち、部分木の葉ノードの部分のみが異なるような場合、葉ノードの部分までは同じなので、木の編集距離による方法では部分木の間の差が出づらいが、本発明の方法では、その差を明確に出すことが可能となる。
【００６９】
ｓｉｇｍｏｄ．ｘｍｌと、ｄｂｌｐ６．ｘｍｌとの組み合わせにおいて、実際に適合する部分木についての詳細な結果を表３に示す。表３において、ＴM［ｉ］（ｉ＝１〜９）は適合した部分木を示し、ＮsigmodおよびＮdblpは、それぞれ、ｓｉｇｍｏｄ．ｘｍｌおよびｄｂｌｐ６．ｘｍｌにおける適合した部分木が有するノードの個数を示す。また、ＳMおよびＴＥＤｉｓｔは、それぞれ、適合した部分木の間の類似度および木の編集距離（ＴＥＤｉｓｔ）を示す。
【表３】
2007052556.tif 000009
【００７０】
これらの結果から、木の編集距離によって、各ＸＭＬ文書間で適合する部分木を決定することは困難であるが、本発明の方法においては、適当なしきい値を設定することによって、適合する部分木を決定することが可能であることが分かる。したがって、その適合した部分木を統合することによって、より完全な情報を含むＸＭＬ文書を得ることができる。
【００７１】
次に、葉ノードの個数および部分木の個数が、本発明の方法の性能に与える影響を調べた。
まず、前記合成データ群から選択した２つのＸＭＬ文書について、ＸＭＬ文書間類似度（Tree similarity degree）を計算し、その計算に要した時間を図１０（ａ）および図１０（ｂ）に示す。図１０（ａ）のＸ軸は選択した２つのＸＭＬ文書の木構造を構成する葉ノードの総個数を示し、図１０（ｂ）のＸ軸は２つのＸＭＬ文書の木構造を構成する部分木の総個数を示す。
【００７２】
図１０（ａ）および図１０（ｂ）から、ＸＭＬ文書の葉ノードの個数または部分木の個数にほぼ比例して、ＸＭＬ文書間類似度（Tree similarity degree）の計算時間が増加し、葉ノードの個数および部分木の個数の２つの要素がＸＭＬ文書間類似度（Tree similarity degree）の計算時間に与える影響は、ほぼ同じであることことが分かる。また、図１０（ａ）および図１０（ｂ）から、２つのＸＭＬ文書において、葉ノードの総個数が５００以下（３００ＫＢ以下のＸＭＬ文書のサイズ）または部分木の総個数が４００以下の場合には、ＸＭＬ文書間類似度（Tree similarity degree）の計算は、２秒以内で達成されることが分かる。
【００７３】
また、前記合成データ群について、ＸＭＬ文書のサイズの増加に対して、そのＸＭＬ文書の分割によって形成される部分木の個数が、どのように変化するかを調べた。
その結果、図１１に示すように、ＸＭＬ文書のサイズが大きくなるとともに、部分木の個数は増加するが、その部分木の個数は、常に単調に増加しない。これは、部分木が、異なるＤＴＤによって異なる個数の葉ノードを含むことが原因と考えられる。
【００７４】
また、実データ群に関して、ＸＭＬ文書のサイズに対して、分割された部分木の個数を図１２に、ならびに葉ノードの総個数および部分木の総個数に対するＸＭＬ文書間類似度（Tree similarity degree）の計算時間を、それぞれ、図１３（ａ）および図１３（ｂ）に示す。これらの図に示す結果から、実データ群における部分木類似度の計算時間は、合成データ群と同程度の葉ノードの個数の場合でも、合成データ群における場合よりも早く増加することが分かる。これは、ＸＭＬ  Ｇｅｎｅｒａｔｏｒによって生成される合成データに比べて、実データのＰＣＤＡＴＡ値が長いことが原因と考えられる。
【図面の簡単な説明】
【００７５】
【図１】（ａ）および（ｂ）は、それぞれＸＭＬ文書の木構造の例を示す図である。
【図２】部分木に分割されたＸＭＬ文書の木構造の具体例を示す図である。
【図３】パラメータｗによる部分木の分割を説明する図である。
【図４】ツリー構造を有する２つのＸＭＬ文書Ｔｂ，Ｔｔの例を示す図である。
【図５】部分木が含む葉ノードの照合を説明する図である。
【図６】統合されたＸＭＬ文書の具体例を示す図である。
【図７】ＸＭＬ文書類似度検出システムおよびＸＭＬ文書の統合システムを説明する模式図である。
【図８】本発明の方法および木の編集距離による方法にしたがって、ＸＭＬ文書の間の類似度を計算した場合の計算時間を比較した図である。
【図９】２つのＸＭＬ文書において、ＸＭＬ文書間類似度と、実際に適合する部分木の個数との関係を示すグラフである。
【図１０】（ａ）は、合成データ群における葉ノードの総個数とＸＭＬ文書間類似度の計算時間の関係を示す図、（ｂ）は、合成データ群における部分木の総個数に対するＸＭＬ文書間類似度の計算時間の関係を示す図である。
【図１１】合成データ群におけるＸＭＬ文書のサイズと、分割された部分木の個数との関係を示す図である。
【図１２】実データ群におけるＸＭＬ文書のサイズと、分割された部分木の個数との関係を示す図である。
【図１３】（ａ）は、実データ群における葉ノードの総個数とＸＭＬ文書間類似度の計算時間の関係を示す図、（ｂ）は、実データ群における部分木の総個数に対するＸＭＬ文書間類似度の計算時間の関係を示す図である。
【図１４】（ａ）および（ｂ）は、実例として、それぞれＸＭＬ文書の木構造の例を示す図である。
【符号の説明】
【００７６】
１      部分木分割部
２      部分木類似度演算部
３      ＸＭＬ類似度演算部
４      ＸＭＬ文書類似度検出システム
５      統合演算部
【図１】
2007052556.tif 000016
【図２】
2007052556.tif 000017
【図３】
2007052556.tif 000018
【図４】
2007052556.tif 000019
【図５】
2007052556.tif 000020
【図６】
2007052556.tif 000021
【図７】
2007052556.tif 000022
【図８】
2007052556.tif 000023
【図９】
2007052556.tif 000024
【図１０】
2007052556.tif 000025
【図１１】
2007052556.tif 000026
【図１２】
2007052556.tif 000027
【図１３】
2007052556.tif 000028
【図１４】
2007052556.tif 000029