Approximate XML document matching
Approximate XML document matching
复制标题
近似 XML 文档匹配
DOI：
10.1145/1066677.1066857
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
Guangming Xing
中科院分区：
文献类型：
--
作者：
E. Canfield;Guangming Xing
规则模糊语法是一种指定XML模式的形式化方法。XML文档可以看作是一个有序的标记树。以最小的成本计算XML文档与模式之间的近似匹配不仅在理论上很有趣。该问题可以建模为：给定有序标记树<i>F</i>和规则树篱语法<i>P</i>，如何计算将森林<i>F</i>转化为<i>F'</i>，使<i>F'</i>与<i>P</i>精确匹配的最小编辑距离。本文引入叶林，给出了在<i>O</i>(<i>F</i><sup>2</sup><i>P</i>(<i>F</i> + log <i>P</i>))时间内求解该问题的算法，其中<i>F</i>为森林的大小，<i>P</i>为语法的大小。据作者所知，这是第一个将XML文档（有序标记树）转换为符合模式（树语法）的算法。
Regular Hedge Grammar is a formal method to specify XML schema. XML document can be viewed as an ordered labeled tree. Computing the approximate matching between an XML document with a schema with minimum cost is not only theoretically interesting. This problem can be modeled as: Given an ordered labeled tree <i>F</i> and a regular hedge grammar <i>P</i>, how to compute the minimum edit distance to transform the forest <i>F</i> into <i>F'</i> so that <i>F'</i> is exactly matched by <i>P</i>. In this paper, with the introduction of leaf forest, we gave an algorithm for this problem in <i>O</i>(<i>F</i><sup>2</sup><i>P</i>(<i>F</i> + log <i>P</i>)) time, where <i>F</i> is the size of the forest and <i>P</i> is the size of the grammar. From the authors' knowledge, this is the first algorithm to transform an XML document (ordered labeled tree) to conform to a schema (tree grammar).