A new string matching algorithm based on logical indexing

摘要

Searching process performance is very important in this modern world that consists of various advanced technology. String matching algorithm is one of the most commonly applied algorithms for searching. String that contains sequences of character is the simplest representation of any complex data in our real life, such as search engine database, finger print minutiae, or DNA sequence. The current most famous string algorithms are Knuth-Morris-Pratt (KMP) algorithm and Boyer-Moore (BM) algorithm. Boyer-Moore algorithm and KMP algorithm are not efficient in some cases. We introduced a new variation of string matching algorithm based on Logical-Indexing (LI), which is more efficient than those algorithms. Logical-Indexing algorithm implements a new function or method and defines different jumping rules compared to others. The indexes of texts and patterns are used to reduce the number of comparisons. Index enables us to analyze the condition of comparison without directly comparing each character in the pattern. Theoretically, we have proven that Logical-Indexing algorithm can skip more characters than KMP and BM algorithm by analyzing KMP's and BM's weaknesses then giving the better solution that are implemented in LI. Furthermore, experiments conducted on various combinations of pattern matching cases also demonstrate that the average number of LI's direct comparisons is smaller than KMP's and BM's algorithm.