XMLデータと正規木文法との間のK最適編集操作列を求めるアルゴリズムの開発

点击翻译按钮获取中文摘要

妥当でないXMLデータが得られた場合,それを妥当なものに変換する必要がある.しかし,XMLデータやスキーマの構造が複雑であった場合,妥当でないXMLデータを妥当なものに手作業で変換するのは困難である.本研究では,主にXMLデータとスキーマ(正規木文法)との間のK最適編集操作列(コストが小さいものから順にK個のもの)を求める問題について考察した.そして,前年度において,妥当でないXMLデータd,正規木文法G,正の整数Kに対して,dとGとの間のK最適編集操作列を求める問題がNP困難であることを示し,この問題を解くための偽多項式時間アルゴリズムを開発している.今年度は,まず,このアルゴリズムについて評価・検討を行った.その結果,概ね所望の変換結果が得られるものの,XMLデータやスキーマの形状によっては,所望の変換が行われない場合があることが分かった.この原因は,変換が編集操作列のこすとにのみ基づいて行われる(ユーザの意図を必ずしも反映できない)ためであると考えられる.この問題に対処するため,本研究では新たなアルゴリズムを追加的に開発 したより具体的には,「スキーマが更新され,XMLデータの妥当性が損なわれた」という場合を想定、スキーマに適用された更新操作列を手がかりとして,このような更新操作列から推測される(更新操作列に沿ってXMLデータを変換する)XML変換アルゴリズムを開発した.