基于Sunday算法的改良单模式匹配算法

摘要：Unicode编码的中文环境下应用Sunday算法时，如直接使用中文字符生成失效跳转表，将造成空间膨胀，而将中文字符拆分为两个字节进行处理，虽可以降低空间消耗，但匹配的执行速度又会受影响。针对Sunday算法应用于Unicode编码的字符拆分环境时所产生的时间性能降低问题，结合Unicode中文单元的内部关联性，优化了原Sunday算法的辅助跳转表与匹配规则，从而在解决Unicode下算法空间膨胀问题的同时，提升了Sunday算法在此环境下的时间性能，并利用模拟实验对改良算法的时间与空间性能进行了实验证明。

关键词： 模式匹配； Unicode编码； KMP算法； B-M算法； Sunday算法

中图分类号： TP301.6 文献标志码： A

0引言

模式匹配算法广泛应用在特征码检测、文件索引、生物DNA序列分析等领域。作为计算机技术中最基本的算法之一，对模式匹配算法的研究起步较早，也是历来计算机算法领域研究的热点。

模式匹配算法的性能，不仅由算法设计方式决定，也受到其所使用的字符与语义环境的影响，同一种模式匹配算法应用于不同的环境时，其性能很可能产生较大的差异，因此设计模式匹配算法时，只有充分分析了算法设计思想与算法所使用环境的匹配度，才能发挥出算法的最高性能。

由于大部分模式匹配算法都是由国外学者提出，因此这些算法通常更适合于英文字符环境，所以这些算法应用于中文环境时，往往存在可继续优化的空间。

本文在分析了近年来多种模式匹配算法的基础上，结合分析了Unicode编码中文环境的特点，对Sunday算法在中文环境下进行了适应性的优化，以提升原算法应用于中文环境时的时间与空间性能。

5结语

本文分析了KMP算法、BM算法以及Sunday算法的设计思路与适应特点，结合中文检索环境，从Sunday算法入手，实现了一种用于Unicode编码环境下的改良算法，在Unicode编码字符的拆分编码环境下，补偿了Sunday算法因降低空间消耗而造成的时间效能损失，并通过实验证明，此环境下，改良算法的时间性能稳定优于Sunday算法，实现了算法低空间消耗、高时间效率的设计目的。本文算法可广泛应用在中文Unicode编码环境下的关键字检索与关键字匹配中。

参考文献：

[1]TANGY.ResearchondesignofnextfunctionofKMPalgorithm[J].ComputerTechnologyandDevelopment，2009，19（6）：98-101.

[2]WUX，LINGJ.AnatomyofBMpatternmatchingalgorithm[J].ComputerEngineeringandDesign，2007，28（1）；29-30.

[3]BOYERR，MOOREJ.Afaststringsearchingalgorithm[J].CommunicationsofACM，1977，20（10）：762-772.

[4]ZHANGH，FANM.ImprovedalgorithmforBMstringmatching[J].ApplicationResearchofComputers，2009，26（9）：49-51.

[5]XUC，SUNW，DAIZ，etal.ImprovedalgorithmofBMforintrusiondetection[J].ApplicationResearchofComputers，2006，23（11）：89-91.

[6]LIB，XIAOS，LIY.TheimprovingalgorithmofBM[J].JournalofLogisticalEngineeringUniversity，2008，24（1）；54-57.

[7]CAIX，DAIG，YANGL.Fasteralgorithmforsinglepatternmatching[J].ApplicationResearchofComputers，2008，25（1）；45-47.

[8]WANGT.TheresearchforsinglepatternmatchingalgorithmbasedonBMandBMHS[D].Hefei：HefeiUniversityofTechnology，2010.

[9]WANGZ，ZHAOY，JIANGZ.Studyonpatternmatchingalgorithmfornetworkprocessing[J].ApplicationResearchofComputers，2007，24（12）：310-312.

[10]ZHANGZ.ThedesignandimplementationofstringmatchingalgorithminWebcontentmonitoringsystembasedonHierarchicalclassification[D].Nanjing：NanjingUniversityofScienceandTechnology，2004.

[11]SHANY，JIANGY，TIANS.ImprovedpatternmatchingalgorithmofBMHSforintrusiondetection[J].ComputerEngineering，2009，35（24）：170-173.

[12]SONGY，SHENC，LIF.TheextendedHorspoolalgorithmforpatternmatchingofChinese[J].SoftwareGuide，2009，8（6）；48-50.