一种快速模式近似匹配算法

华南理工大学学报(自然科学版) ›› 2012, Vol. 40 ›› Issue (6): 103-108.

一种快速模式近似匹配算法

李拥军敖道敢

华南理工大学计算机科学与工程学院，广东广州 510006

收稿日期:2011-12-26 修回日期:2012-03-13 出版日期:2012-06-25 发布日期:2012-05-03
通信作者: 李拥军(1968-) ，男，博士，副教授，主要从事计算机网络与人工智能研究． E-mail:liyj@scut.edu.cn
作者简介:李拥军(1968-) ，男，博士，副教授，主要从事计算机网络与人工智能研究．
基金资助:
国家自然科学基金资助项目( 61070015) ; 广东省科技计划项目( 2011B010200039) ; 广州市科技计划项目( 11C42080722)

A Fast Algorithm for Approximate Pattern Matching

Li Yong-jun Ao Dao-gan

School of Computer Science and Engineering,South China University of Technology,Guangzhou 510006,Guangdong,China

Received:2011-12-26 Revised:2012-03-13 Online:2012-06-25 Published:2012-05-03
Contact: 李拥军(1968-) ，男，博士，副教授，主要从事计算机网络与人工智能研究． E-mail:liyj@scut.edu.cn
About author:李拥军(1968-) ，男，博士，副教授，主要从事计算机网络与人工智能研究．
Supported by:
国家自然科学基金资助项目( 61070015) ; 广东省科技计划项目( 2011B010200039) ; 广州市科技计划项目( 11C42080722)

摘要/Abstract

摘要： 为进一步提升传统的近似模式匹配问题解决方法——动态规划算法的性能，提出了一种新的过滤型近似模式匹配算法．该算法结合动态规划算法，切分模式串得到长度相等且更小的模式片; 在此基础上将待匹配的文本串分割成子串，并建立相应的索引; 同时设计了一个新的过滤策略来消除匹配检查中的冗余．通过实例将文中方法与现有方法进行对比，结果表明: 文中方法的匹配时间较短，匹配性能优于现有方法; 随着模式串长度的增加，文中算法的优越性更为明显，模式串长度大于45 后，文中算法的匹配时间可比传统动态规划算法缩短一半以上．

关键词: 近似模式匹配, 动态规划算法, 匹配时间

Abstract:

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.

Key words: approximate pattern matching, dynamic programming algorithm, matching time

李拥军敖道敢. 一种快速模式近似匹配算法[J]. 华南理工大学学报(自然科学版), 2012, 40(6): 103-108.

Li Yong-jun Ao Dao-gan. A Fast Algorithm for Approximate Pattern Matching[J]. Journal of South China University of Technology(Natural Science Edition), 2012, 40(6): 103-108.