Approximate XML document matching

ABSTRACT

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 F and a regular hedge grammar P, how to compute the minimum edit distance to transform the forest F into F' so that F' is exactly matched by P. In this paper, with the introduction of leaf forest, we gave an algorithm for this problem in O(F²P(F + log P)) time, where F is the size of the forest and P 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).

REFERENCES

• 1: Shasha, D., Zhang, K. Approximate Tree Pattern Matching, chapter 14 Pattern Matching Algorithms (eds. Apostolico, A. and Galil, Z.), Oxford University Press, June 1997.
• 2: Murata, M Hedge Automata: A Formal Model for XML Schemata http://www.xml.gr.jp/relax/hedge_nice.html
• 3: Gene Myers, Approximately matching context-free languages, Information Processing Letters, v.54 n.2, p.85-92, April 28, 1995 [doi>10.1016/0020-0190(95)00007-Y]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms

General Terms:
Algorithms

Keywords:
XML, approximate matching, design of algorithm, document transformation, tree, tree grammar