A fast algorithm for approximate pattern matching

作者：Li, Yong-Jun^*; Ao, Dao-Gan

来源：Journal of South China University of Technology(Natural Science Edition), 2012, 40(6): 103-108.

DOI：10.3969/j.issn.1000-565X.2012.06.017

• Approximate pattern matching
• Dynamic programming algorithm
• Fast algorithms
• Filtering strategies
• Matching time
• Pattern strings
• Sub-strings
• Text string

In order to improve the performance of the dynamic programming algorithm, a traditional method of solving the approximate pattern matching problem, a novel filtering-type approximate pattern matching algorithm is proposed, which combines the advantages of the dynamic programming algorithm, splits the pattern string into smaller pattern pieces with the same length, divides the text string to be matched into sub-strings and further establishes the corresponding index. Moreover, a new filtering strategy is proposed to eliminate the redundancy of the match examination. Example results show that the proposed algorithm is superior to the existing ones due to its small match time cost and high performance, especially under the condition of long pattern string matching; and that, as compared with the traditional dynamic programming algorithm, the proposed algorithm reduces the match time by more than 50% when the pattern string length is more than 45.

• 出版日期2012-6
• 单位华南理工大学