半構造化文書に対する変換規則の帰納推論

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

半構造化文書のフォーマットであるXMLの登場によって,計算機間で交換されるデータの大部分がXML文書へと移行しつつある.XMLの登場によって,データの解析処理とデータに対する操作が標準化され,各アプリケーション間でデータをやりとりするために必要であった変換操作がXMLに対する操作という統一的な手法によって行うことが可能となった.しかし,XMLではその構造を規定するタグをも自由に定義できるという柔軟性から,XMLの応用は多岐に及び,必要とされる変換すべてを人手によって記述することは現実的に不可能である.本研究は,そのような計算機間で交換される大量のXML文書間の変換を,入力となる文書と出力となる文書だけを具体例として与え,それらの間に必要な変換規則を自動的に推論する手法の開発と,そのために必要な理論の展開を目的とする.XML文書の変換とはあるXML文書の一部を取り出し,新たなXML文書を取り出されたXML文書の一部から再構成することである.ここで重要な問題となるのはXML文書の一部がどのように取り出されているかを推論することである.申請者は,半構造化文書を生垣としてとらえ,生垣上の汎化関係を考えることで,与えられた例の間の共通の構造と同時にXML文書ごとに異なる取り出されるべき部分をとらえることができるということを明らかにした.また,効率よく求めることができる共通の構造として極大共通生垣を提案した.極大共通生垣は文字列上の最長部分文字列を生垣上に自然に拡張したものであり,極大共通生垣を実際のXML文書に対して求めることで高い再現率で情報抽出を行うことが可能であることを示した.