Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/14303
Title: Approximate matching of complex structures
Authors: RAJIV PANICKER
Keywords: Approximate Pattern Matching, Graph Algorithms, Information Retrieval, Regular Expressions, Tree Algorithms
Issue Date: 19-Oct-2004
Source: 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.
URI: http://scholarbank.nus.edu.sg/handle/10635/14303
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

OPEN

NoneView/Download
RajivPanicker - MSC2004 - Title.pdf21 kBAdobe PDF

OPEN

NoneView/Download

Page view(s)

194
checked on Dec 1, 2017

Download(s)

225
checked on Dec 1, 2017

Google ScholarTM

Check


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