Approximate matching of XML document with regular hedge grammar

Abstract

A regular hedge grammar is a formal method to specify XML schema. An XML document can be viewed as an ordered labeled tree. Given an XML schema, finding the sequence of changes with minimum cost is not just of theoretical interest. This problem can be modeled, as given, as an ordered labeled tree (forest) F and as a regular hedge grammar P. We consider the minimum edit distance required to transform the forest F into F′ so that F′ is exactly matched by P. By introducing a leaf forest, we design an algorithm for solving this problem in time O(F ² P(F + log P)), where F is the size of the forest and P is the size of the grammar. To our knowledge, this is the first algorithm to transform an XML document (ordered labeled tree) to conform to the schema (tree grammar).

Keywords:

• Document transformation
• Pattern matching
• Tree editing
• Algorithm design