第２３卷第１期２０１０年２月
模式识别与人工智能
ＰＲ＆ＡＩ
Ｖ０１．２３Ｎｏ．１
Ｆｅｂ２０１０一种改进的字符串模式匹配算法
胡金柱熊春秀舒江波周星程文涛
（华中师范大学计算机科学系武汉４３００７９）
摘要提出一种改进的字符串模式匹配算法．该算法对文本串进行预处理，即对文本串中不存在于模式串中的字符以及文本串中剩下的出现次数最少的字符分别进行标记，再通过匹配模式串的首尾字符来减少出现次数最少的字符的标记个数．发生匹配失败时，将模式串直接滑动到标记了的出现次数最少的字符处．通过实验证明，该算法的移动次数和比较次数有较大减少，耗费的额外空间的大小也不超过模式串的长度，进一步提高模式匹配的效率．
关键词模式匹配，文本串，模式串，预处理
中图法分类号ＴＰ３９１
ＡｎＩｍｐｒｏｖｅｄＣｈａｒａｃｔｅｒＳｔｒｉｎｇＰａｔｔｅｒｎＭａｔｃｈｉｎｇＡｌｇｏｒｉｔｈｍ
ＨＵＪｉｎ－Ｚｈｕ，ＸＩＯＮＧＣｈｕｎ—Ｘｉｕ，ＳＨＵＪｉａｎｇ－Ｂｏ，ＺＨＯＵＸｉｎ，ＣＨＥＮＧＷｅｎ－Ｔａｏ
（ＤｅｐａｒｔｍｅｎｔｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅ，ＨｕａｚｈｏｎｇＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ，Ｗｕｈａｎ４３００７９）
ＡＢＳＴＲＡＣＴ
Ｂｙａｎａｌｙｚｉｎｇａｖａｒｉｅｔｙｏｆｉｍｐｒｏｖｅｄｐａｔｔｅｒｎｍａｔｃｈｉｎｇａｌｇｏｒｉｔｈｍｓ，ａｎｐａｔｔｅｒｎｍａｔｃｈｉｎｇａｌｇｏｒｉｔｈｍｉｓ
ｉｍｐｒｏｖｅｄ．Ｆｉｒｓｔｌｙ，ｔｈｅｔｅｘｔｓｔｒｉｎｇｉｓｐｒｅｐｒｏｃｅｓｓｅｄ．Ｔｗｏｋｉｎｄｓｏｆｃｈａｒａｃｔｅｒｓａｒｅｍａｄｅ
ｕｐ．Ｏｎｅｄｏｅｓｎｏｔｅｘｉｓｔ
ｉｎｔｈｅｐａｔｔｅｒｎｓｔｒｉｎｇ，ａｎｄｔｈｅｏｔｈｅｒｉｓｔｈｅｃｈａｒａｃｔｅｒｓｔｈａｔａｐｐｅａｒｔｈｅｌｅａｓｔ．Ｓｅｃｏｎｄｌｙ，ｔｈｒｏｕｇｈｍａｔｃｈｉｎｇｂｏｔｈｔｈｅｆｉｒｓｔｃｈａｒａｃｔｅｒａｎｄｔｈｅｌａｓｔｃｈａｒａｃｔｅｒｏｆｔｈｅｐａｔｔｅｒｎｓｔｒｉｎｇ，ｔｈｅｎｕｍｂｅｒｏｆｔｈｅｍａｒｋｅｄｃｈａｒａｃｔｅｒｓｗｈｉｃｈ
ａｐｐｅａｒｔｈｅｌｅａｓｔｉｓｒｅｄｕｃｅｄ．Ｉｆｔｈｅｍａｔｃｈｉｎｇｆａｉｌｓ，ｔｈｅｐａｔｔｅｒｎｓｔｒｉｎｇｄｉｒｅｃｔｌｙｓｌｉｄｅｓｔｏｔｈｅｎｅｘｔｍａｒｋｅｄｃｈａｒａｃｔｅｒｗｈｉｃｈａｐｐｅａｒｓｔｈｅｌｅａｓｔ．Ｆｉｎａｌｌｙ，ｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｔｈｅｆｒｅｑｕｅｎｃｉｅｓｏｆｔｈｅｍｏｖｅｍｅｎｔ
ａｎｄｔｈｅｃｏｍｐａｒｉｓｏｎｄｅｃｒｅａｓｅｄｇｒｅａｔｌｙｂｙｔｈｅｉｍｐｒｏｖｅｄａｌｇｏｒｉｔｈｍ，ａｎｄｔｈｅａｄｄｉｔｉｏｎａｌｃｏｓｔｏｆｓｐａｃｅｉｓｌｅｓｓｔｈａｎｔｈｅｌｅｎｇｔｈｏｆｔｈｅｐａｔｔｅｒｎｓｔｒｉｎｇ．Ｍｏｒｅｏｖｅｒ，ｔｈｅｅｆｆｉｃｉｅｎｃｙｏｆｔｈｅｐａｔｔｅｒｎｍａｔｃｈｉｎｇｉｓｉｍｐｒｏｖｅｄ．
ＫｅｙＷｏｒｄｓＰａｔｔｅｒｎＭａｔｃｈｉｎｇ，Ｔｅｘｔ
Ｓｔｒｉｎｇ，ＰａｔｔｅｒｎＳｔｒｉｎｇ，Ｐｒｅｐｒｏｃｅｓｓｉｎｇ
ｌ引言
随着网络信息的迅速膨胀，字符串模式匹配的应用越来越广泛．在网络安全入侵检测系统…、计算机病毒特征码匹配、搜索引擎、ＤＮＡ序列匹配、拼写检查、文本编辑‘２｜、信息检索、数据处理、数据压缩‘３１和
水国家教育部重点研究基地重大研究项目（Ｎｏ．０７ＪＪＤ７４００６３）、湖北省科技攻关项目（Ｎｏ．２００７ＡＡｌ０１ｅ４９）资助
收稿日期：２００９—０４—０６
作者简介胡金柱，男，１９４７年生，教授，主要研究方向为软件工程与分布式信息系统．Ｅ－ｍａｉｌ：ｘｉｏｎｇｃｈｕｎｘｉｕ＠１２６．ｃｏｍ．熊春秀，女，１９８４年生，硕士研究生，主要研究方向为软件工程与分布式信息系统．舒江波，男，１９８２年生，博士研究生，主要研究方向为软件工程、中文信息处理．周星，女，１９８５年生，硕士研究生，主要研究方向为软件工程与分布式信息系统．程文涛，男，１９８２年生，硕士研究生，主要研究方向为软件工程与分布式信息系统．
万方数据