A Comparative Performance Analysis of Approximate String Matching
Shivani Jain · 2013
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.