半構造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完全であることを示した.最後に,「部分木の移動」のコストが移動対象の頂点にのみ依存し,かつ,操作系列に含まれる「部分木の移動」操作の数がある定数以下に抑えられている場合,併合を行うための操作系列でコスト最小のものが多項式時間で得られることを示した.

In this study, the model is similar to that of the XML researchers, who share the same category and share the same information as each other. In this study, two XML employees were involved in this study. In this study, we did the same thing in the same way. This is the best way to get rid of the problem. This is the best way to get rid of it. The purpose of this study is to make sure that the preface is very important in this study. XML. In the previous year, the reporter reported that two XML customers were registered in the previous year, and the operators used the operation (1) to append, (2) to delete, (3) to limit the cost of each operation (for each operation). This year, there are three major operations and (4) part of the wooden movement, which is appended to the operation, and the two XML operations are reviewed. The results of this study showed that the results of this study were successful. In this case, the two XML operations series are in combination with the customer operation series, and the XML operation series are in combination with each other in terms of multi-item time distribution. For the second time, 2 XML keys do not have an integer K number, and the number below K is below K. It is possible to decide whether or not to make a decision on the problem. The NP is fully open. Finally, the "partial log movement" operation series contains the "partial log movement" operation number below the set number, and the combination of the operation series and the minimum cycle time of the operation series is valid.

项目成果

Nobutaka Suzuki: "On Merging Structured Documents with Move Operation"Proceedings of the International Symposium on Information and Communication Technologies (ISICT03). 256-261 (2003)

Nobutaka Suzuki：“论将结构化文档与移动操作合并”信息与通信技术国际研讨会 (ISICT03) 论文集。