半構造XMLデータからのスキーマ抽出及び変換アルゴリズムの開発

开发半结构化 XML 数据的模式提取和转换算法

基本信息

批准号：
14780330
负责人：
鈴木伸崇
金额：
$ 1.98万
依托单位：
Okayama Prefectural University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Young Scientists (B)
财政年份：
2002
资助国家：
日本
起止时间：
2002 至 2003
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-14780330/
关键词：
XML データ変換スキーマ抽出アルゴリズム

项目摘要

本研究のスキーマ抽出は,構造の類似したXMLデータ同士を同じクラスに分類し,同じクラスに属するデータを共通の構造に変換する,という手順で行われる.これを実現するため,本研究では構造の異なる2個のXMLデータを同じ構造に変換(この処理を以下では併合と呼ぶ)するアルゴリズムの開発等を行った(このようなアルゴリズムが得られれば,クラスタリング的手法と本アルゴリズムを組み合わせることによりスキーマ抽出を行うことができる).本研究では,XMLデータをラベル付き順序木とみなす.前年度,報告者は2個のXMLデータを併合するためのアルゴリズムを構成したが,このアルゴリズムでは併合の際に用いる操作が(1)頂点の追加,(2)頂点の削除,(3)頂点のラベルの変更,という3種のものに限定されていた(各操作にはコストが付与される).今年度は,これら3種の操作に加えて(4)部分木の移動,という操作を追加した上で,2個のXMLデータを併合する問題について考察した.本研究で得られた結果は次の通りである.まず,2個のXMLデータおよび操作系列が与えられた場合に,その操作系列をXMLデータに適用して併合を行う多項式時間アルゴリズムを構成した.次に,2個のXMLデータおよび整数Kに対して,それらXMLデータがコストK以下で併合可能か否かを決定する問題がNP完全であることを示した.最後に,「部分木の移動」のコストが移動対象の頂点にのみ依存し,かつ,操作系列に含まれる「部分木の移動」操作の数がある定数以下に抑えられている場合,併合を行うための操作系列でコスト最小のものが多項式時間で得られることを示した.

这项研究中的架构提取是通过将具有相似结构的XML数据分类为同一类而进行的，并将属于同一类的数据转换为共同结构。为了实现这一目标，在这项研究中，我们开发了一种算法，该算法将两个具有不同结构的XML数据转换为相同的结构（以下称为合并）（如果获得了这种算法，则可以通过将群集方法与此算法结合方法来执行架构提取）。在这项研究中，我们认为XML数据标记为订单树。在上一年中，记者构建了一种用于合并两个XML数据的算法，但是在此算法中，合并中使用的操作仅限于三种类型：（1）添加顶点，（2）删除顶点，（3）（3）更改Vertices标签（每种操作限制为三种操作）（每种操作均限制了二英语）。在本研究中获得的结果（4）在添加了两个XML数据和一个多项式算法的情况下，将其运用到XML数据中，我们表明了两个XML数据，该数据是在XML数据中添加的，该数据是在两个XML数据中，在此XML数据中，该数据是XML的数据，该数据是XML的数据，该数据是在XML数据中，该数据是在两个XML数据上，该数据是在XML数据上， “移动子树”仅取决于运动目标的顶点，如果操作系列中包含的“移动子树”操作的数量仅限于一定的常数或更小时，则可以在多项式时间中获得操作序列的最低成本。