久保山 哲二

インターネット上のXMLやHTML文書等の半構造データの増大にともない、膨大な半構造データを効率よく比較・照合するための手法や、複数の半構造データを統合するための手法が求められている。これまでに半構造データのための様々な照合・結合手法が提案されているものの、これらの手法を統一的に記述するためのフレームワークが存在しなかった。そこで、本稿では、木の近似照合の意味論を木構造間のノード写像として定式化し、木構造間のノード写像が与えられたときに、その写像が属する近似照合のクラスを効率よく同定するアルゴリズムを示す。このアルゴリズムは、クラスの同定過程で、2つの木構造が矛盾なく結合できるかどうかを調べ、結合可能な場合は、実際に結合木を構成する。

本稿では, ラベル無し順序木のqグラム距離について考察する.まず, qグラムを線グラフに同型なノード数qの木と定義し, 2つの木のqグラム距離を2つの文字列のqグラム距離と同様に定義する.そして, 後行順の深さ列を用いることで, ノード数nの木Tのすべてのqグラムを, O(n^2)時間O(q)領域で数えあげる単純なアルゴリズムEnumGramを設計する.次に, このEnumGramを, O(qn)時間O(qd)領域のアルゴリズムLinearEnumGramに改良する.ここで, dはTの深さである.したがって, T_1とT_2のqグラム距離D_q(T_1, T_2)は, O(qmax{n_1, n_2})時間O(qmax{d_1, d_2})領域で計算することができる.ただし, n_iおよびd_iはT_iの中のノード数およびT_iの深さである.

インターネット上のXMLやHTML文書等の半構造データの増大にともない、膨大な半構造データを効率よく比較・照合するための手法や、複数の半構造データを統合するための手法が求められている。これまでに半構造データのための様々な照合・結合手法が提案されているものの、一般的なフレームワークが存在しないため同様の手法が独立に繰り返し提案されることも少なくない。本稿では、2つの半構造データを結合するための一般的かつ理論的なフレームワークを提供する。本手法では、まず、木の編集距離の概念を用いて2つの木の近似照合を行い、2つの木の間で類似しているノードの対応をとる。次に、対応のとれたノード同士を重ね合わせ、その他の全てのノードが、もとの木における階層構造を保つように新しい木を生成する。このような数理的なフレームワークによって、様々な照合・統合手法に統一的な観点を提供し、効率的な実装のための基礎を与える。

インターネット上のXMLやHTML文書等の半構造データの増大にともない、膨大な半構造データを効率よく比較・照合するための手法や、複数の半構造データを統合するための手法が求められている。これまでに半構造データのための様々な照合・結合手法が提案されているものの、一般的なフレームワークが存在しないため同様の手法が独立に繰り返し提案されることも少なくない。本稿では、2つの半構造データを結合するための一般的かつ理論的なフレームワークを提供する。本手法では、まず、木の編集距離の概念を用いて2つの木の近似照合を行い、2つの木の間で類似しているノードの対応をとる。次に、対応のとれたノード同士を重ね合わせ、その他の全てのノードが、もとの木における階層構造を保つように新しい木を生成する。このような数理的なフレームワークによって、様々な照合・統合手法に統一的な観点を提供し、効率的な実装のための基礎を与える。

インターネット上の XML や HTML 文書等の半構造データの増大にともない、膨大な半構造データを効率よく比較・照合するための手法や、複数の半構造データを統合するための手法が求められている。これまでに半構造データのための様々な照合・結合手法が提案されているものの、一般的なフレームワークが存在しないため同様の手法が独立に繰り返し提案されることも少なくない。本稿では、2 つの半構造データを結合するための一般的かつ理論的なフレームワークを提供する。本手法では、まず、木の編集距離の概念を用いて2つの木の近似照合を行い、2つの木の間で類似しているノードの対応をとる。次に、対応のとれたノード同士を重ね合わせ、その他の全てのノードが、もとの木における階層構造を保つように新しい木を生成する。このような数理的なフレームワークによって、様々な照合・統合手法に統一的な観点を提供し、効率的な実装のための基礎を与える。With the rapid growth of semistructured data such as XML and HTML documents on the Internet, we need efficient methods for comparing, matching and integrating semistructured data. Although there have been diversity of these methods recently, no comprehensive framework has been available. In this paper, we formulate and provide a new framework for merging semistructured data. In this framework, we firstly find a set of node-to-node correspondences between two trees by approximate matching based on tree edit distance. Then, we merge two trees by overlaying these corresponding nodes, and locating the other nodes so that each ancestor relation in two trees is preserved. This mathematical framework gives a unifying view of matching and merging semistructured data, and is beneficial to efficient implementations.

インターネット上の XML や HTML 文書等の半構造データの増大にともない、膨大な半構造データを効率よく比較・照合するための手法や、複数の半構造データを統合するための手法が求められている。これまでに半構造データのための様々な照合・結合手法が提案されているものの、一般的なフレームワークが存在しないため同様の手法が独立に繰り返し提案されることも少なくない。本稿では、2 つの半構造データを結合するための一般的かつ理論的なフレームワークを提供する。本手法では、まず、木の編集距離の概念を用いて2つの木の近似照合を行い、2つの木の間で類似しているノードの対応をとる。次に、対応のとれたノード同士を重ね合わせ、その他の全てのノードが、もとの木における階層構造を保つように新しい木を生成する。このような数理的なフレームワークによって、様々な照合・統合手法に統一的な観点を提供し、効率的な実装のための基礎を与える。With the rapid growth of semistructured data such as XML and HTML documents on the Internet, we need efficient methods for comparing, matching and integrating semistructured data. Although there have been diversity of these methods recently, no comprehensive framework has been available. In this paper, we formulate and provide a new framework for merging semistructured data. In this framework, we firstly find a set of node-to-node correspondences between two trees by approximate matching based on tree edit distance. Then, we merge two trees by overlaying these corresponding nodes, and locating the other nodes so that each ancestor relation in two trees is preserved. This mathematical framework gives a unifying view of matching and merging semistructured data, and is beneficial to efficient implementations.

木の近似照合は広い適用領域をもち、半構造化文書やRNA2次構造の類似性判定、XMLのスキーマ発見・統合、プログラムの差分検出をはじめとする様々な分野で、独立に多様なアルゴリズムが提案されている。木の近似照合アルゴリズムの多くは、編集距離による操作的な記述により特徴づけられてきたが、独立して提案されてきたこれらの様々なアルゴリズムの関連性については、ほとんど研究されていない。本論文では、編集距離に基づく既存の様々な木の近似照合を統一的に記述するための数学的モデルを提案する。文字列においては、アラインメントと編集距離が、その計算において等価であるが、これを木に拡張した場合、両者が等価ではなくなることが知られている。 本提案モデルを用いて、木のアラインメントと等価な編集距離のクラスを同定する。すなわち、従来、別々のアルゴリズムであると考えられていた木のアラインメントと less-constrainded 編集距離が等価であることを示す。The notion of tree edit distance provides a unifying framework for measuring distance and finding approximate common patterns between two trees. In prior work, the edit distance measures have been not well-formalized. So the essentially equivalent distance measures have been independently proposed as the measures different from each other. In this paper, we present a theoretical framework for tree edit distance. By using our framework, we establish the relationship between alignment of trees, and a tree edit distance measure called less-constrained edit distance.

木の近似照合は広い適用領域をもち、半構造化文書やRNA2次構造の類似性判定、XMLのスキーマ発見・統合、プログラムの差分検出をはじめとする様々な分野で、独立に多様なアルゴリズムが提案されている。木の近似照合アルゴリズムの多くは、編集距離による操作的な記述により特徴づけられてきたが、独立して提案されてきたこれらの様々なアルゴリズムの関連性については、ほとんど研究されていない。本論文では、編集距離に基づく既存の様々な木の近似照合を統一的に記述するための数学的モデルを提案する。文字列においては、アラインメントと編集距離が、その計算において等価であるが、これを木に拡張した場合、両者が等価ではなくなることが知られている。本提案モデルを用いて、木のアラインメントと等価な編集距離のクラスを同定する。すなわち、従来、別々のアルゴリズムであると考えられていた木のアラインメントとless-constrainded編集距離が等価であることを示す。

Shock treeは二次元形状を効果的に抽象化する手法である。TorselloとHancockは、shock treeの照合のために、木構造の教師なし学習手法を提案している。この手法で核になるのは、木の編集距離を用いて2つの木を結合する手続きである。しかし、この手法においては、2つの木の結合後の構造が木になることは保証されておらず、木が得られなかった場合は、その結果を棄却して、別の組み合わせを試すというアドホックな方法を用いている。本稿では、2つの木を結合した結果が木になるための本質的な条件を示す。この条件は、木構造アラインメント計算が、less-constrainedという制約型の木の編集距離の計算と等価であることを証明することによって示される。また、結合して得られる木が一意に定まるための条件について考察する。

Shock treeは二次元形状を効果的に抽象化する手法である。TorselloとHancockは、shock treeの照合のために、木構造の教師なし学習手法を提案している。この手法で核になるのは、木の編集距離を用いて2つの木を結合する手続きである。しかし、この手法においては、2つの木の結合後の構造が木になることは保証されておらず、木が得られなかった場合は、その結果を棄却して、別の組み合わせを試すというアドホックな方法を用いている。本稿では、2つの木を結合した結果が木になるための本質的な条件を示す。この条件は、木構造アラインメント計算が、less-constrainedという制約型の木の編集距離の計算と等価であることを証明することによって示される。また、結合して得られる木が一意に定まるための条件について考察する。

複数の木に共通する木構造パタンを発見するための新しい手法について提案する。本手法では、木の編集距離に基づき、木の近似照合を行い、複数の木のノード間の対応を求めることにより、パタン発見を行う。

Webページからの情報抽出のために、Webラッパーを(半)自動生成するための様々な研究が行われている。本研究では、Webラッパー生成のために木の編集距離を用いてHTML文書やXML文書のような半構造データから、共通パタンを近似的にみつけることを目的とする。共通パタンは、複数のWebページの構文木の構造的類似性を見つけ出し、構文木を木構造アラインメントにより結合することにより生成する。木の各ノードには、出現頻度に応じた重み付けをする。プログラムにより機械的に生成された複数のWebページのみでなく、テンプレートを元に人手による編集を経て作成された複数のWebページ間に共通する構造を柔軟に抽出し、Webラッパーを生成する手法を提案する。

Webページからの情報抽出のために、Webラッパーを(半)自動生成するための様々な研究が行われている。本研究では、Webラッパー生成のために木の編集距離を用いてHTML文書やXML文書のような半構造データから、共通パタンを近似的にみつけることを目的とする。共通パタンは、複数のWebページの構文木の構造的類似性を見つけ出し、構文木を木構造アラインメントにより結合することにより生成する。木の各ノードには、出現頻度に応じた重み付けをする。プログラムにより機械的に生成された複数のWebページのみでなく、テンプレートを元に人手による編集を経て作成された複数のWebページ間に共通する構造を柔軟に抽出し、Webラッパーを生成する手法を提案する。

2つの木構造間の類似性を比較する手段として編集距離による様々な手法が提案されている。木構造アラインメントもその1つであり、2つの木を共にグラフマイナーとして包含するような共通木を見つける手法である。文字列については、編集距離計算とアラインメント計算は本質的に等価であることが知られている。しかし、木の場合には、一般的にこのような等価性は成り立たない。本稿では、木の編集距離と木構造アラインメントの関連性について考察し、木構造アラインメントの計算が、less-constrainedという制約型の木の編集距離計算と等価であることを、両者のマッピング条件の等価性を証明することによって示す。また、木構造アラインメントにより共通木が一意に定まるマッピング条件を示す。

木構造を埋め込める変数を含む順序木で記述した木構造パタンと半構造データの編集距離を計算することにより変数部分の情報抽出を行う手法について提案する。

グラフ構造、特に木構造は、様々なデータを表現する手段として、重要な役割を果たしており、グラフ構造データ、木構造データからの知識発見が注目されている。項木(term tree)とは、木構造をしたデータのパターンを表現するための、変数を含むデータ構造であり、一階項(first order term)よりも表現力が大きい。我々は、木構造データからの知識発見の効率化のため、項木と木の単一化可能性を効率的に判定するアルゴリズムを提案している。項木と木が単一化可能であるとは、項木が表すパターンに木が適合することである。この単一化可能性判定アルゴリズムを実現し、実験によりその有効性を確認したので報告する。また、グラフ構造データからの知識発見システムへの応用についても述べる。

We present a new method to eliminate redundant inferences caused by case-splitting in MGTP. There are two types of redundancies eliminated by the method: One is that the same sub-proof tree may be generated at several descendant nodes after a case-splitting occurs. Another is caused by useless model candidate extensions with irrelevant non-Horn clauses. Both types of redundancies can be eliminated by combining the folding-up function that conveys unit lemmata obtained from solved descendant nodes to a proper antecedent node and the NHM function that suppresses useless model extensions. The method has been implemented in MGTP. We evaluate its effects on a UNIX workstation for some typical problems taken from the TPTP problem library.

Factorization used in resolution provers can be effectively applied to model generation provers in order to eliminate the redundancies in case splittings. We propose a new factorization-based technique called a static/dynamic lemma generation, and present its efficient implementation on MGTP(Model Generation Theorem Prover). Experimental results obtained by running MGTP with the technique for several problems from the TPTP library demonstrate the effectiveness of the proposed technique and implementation.