Please use this identifier to cite or link to this item:
Title: Approximate matching of complex structures
Keywords: Approximate Pattern Matching, Graph Algorithms, Information Retrieval, Regular Expressions, Tree Algorithms
Issue Date: 19-Oct-2004
Citation: RAJIV PANICKER (2004-10-19). Approximate matching of complex structures. ScholarBank@NUS Repository.
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.
Appears in Collections:Master's Theses (Open)

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
RajivPanicker - MSC2004.pdf457.29 kBAdobe PDF


RajivPanicker - MSC2004 - Title.pdf21 kBAdobe PDF



Page view(s)

checked on Nov 4, 2018


checked on Nov 4, 2018

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.