A Comparative Performance Analysis of Approximate String Matching
Shivani Jain1, A.L.N. Rao2
1Shivani Jain, Department of IT, Mewar University, Chittorgarh (Rajasthan), India.
2Dr. A.L.N Rao, Department of IT, MU, MTU Galgotia Engineering College, Greater Noida (U.P), India.
Manuscript received on 12 October 2013 | Revised Manuscript received on 20 October 2013 | Manuscript Published on 30 October 2013 | PP: 123-128 | Volume-3 Issue-5, October 2013 | Retrieval Number: E1263103513/13©BEIESP
Open Access | Editorial and Publishing Policies | Cite | Mendeley | Indexing and Abstracting
© The Authors. Blue Eyes Intelligence Engineering and Sciences Publication (BEIESP). This is an open access article under the CC-BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/)
Abstract: This paper presents a comparative study to evaluate experimental results for approximate string matching algorithms on the basis of edit distance. We compare the algorithms in terms of the number of character comparisons and the running time for molecular data, binary alphabets English alphabets etc. The terms like word processors, web search engine, molecular sequence, DNA sequence analysis and natural language processing have lead to the development of many algorithms in the field of pattern matching in a string. Amongst the various string searching algorithms being used, here the focus is mainly approximate implementation of pattern matching algorithms such as Knuth-Morris-Pratt, Boyer-Moore, Raita, Horspool based on PHP. The comparison between these algorithms is done with the help of Levenshtein distance. It also describes the importance of design of efficient “Approximate Pattern Search Algorithms in molecular database, binary alphabets, English alphabets and so on”. This approach is advantageous from all other string-pattern matching algorithms in terms of time complexity. Therefore this procedure improves the efficiency of approximate string matching and gives the near-optimal results.
Keywords: Pattern Matching, Edit Distance, Approximate String Searching, Levenshtein Distance.
Scope of the Article: Measurement & Performance Analysis