Approximate matching of complex structures

Abstract

Approximate pattern-matching form the basis of many commercial applications in such as bio-informatics and information extraction. We present algorithms for approximate matching of trees (ordered and unordered) and acyclic graphs based on edit distance measures under the degree-1 constraint with worst case execution time of O(|T1|.|T2|.k^2logk) and O(|T1|^2.|T2|^2.k^2logk) respectively. The implication of these algorithms being that the relevant information is located at the leaves of a tree or at the periphery of a graph. We also present an algorithm to perform approximate matching of a string with a special type of regular expression where the kleene closure (*) is only allowed to be bound to a single character in a worst case execution time of O(|S|^3) for a given string S . Our performance evaluation indicates that our proposed techniques indeed outperform an existing well-known algorithm for approximate regular expression matching in terms of execution times.