中文多模式匹配算法性能的分析与研究-《计算机技术与发展》

文章信息/Info

Title:: Analysis and Research of Chinese Multi-pattern Matching Algorithm Performance

Keywords:: multi-pattern matching; Chinese environment; AC algorithm; WM algorithm; Wang algorithm

摘要:: 模式匹配算法一般不具有所有环境下的通用性，不同的算法在不同语义环境下的表现，往往差异较大。为实现中文环境下对模式串的快速多模式匹配，选择出在中文环境下的最优匹配算法，分析了几种经典的多模式匹配算法。通过对各个算法设计思路、时间性能与空间性能的研究，推导出基于“坏字符”的算法设计思路最适用于中文环境下大字符集、短字符串的特点，并通过实验对理论推测的中文环境最优算法-Wang算法的性能与其他几种经典算法的性能进行了比较，验证了理论推导的正确性。

Abstract:: Generally,pattern matching algorithms do not have the versatility of all circumstances. For realizing the fast multi-pattern matc-hing,selecting the optimal matching algorithm under the Chinese environment,analyze several common multi-pattern matching algo-rithm. By researching the various algorithm design ideas,the time and space performance,deduced that the design idea based on the"bad character" is the best way which can be used to fast matching under Chinese environment,and the experiment shows that the Wang algo-rithm is the optimal algorithm under Chinese environment compared with other classical algorithm,and verifies the correctness of theory deduction.