改进的中文字串多模式匹配算法  

Improved Multiple Pattern Algorithm for Chinese String Matching

作　　者：沈洲[1] 王永成[1] 刘功申[1] 

机构地区：[1]上海交通大学电子信息学院,上海200030

出　　处：《情报学报》2002年第1期27-32,共6页Journal of the China Society for Scientific and Technical Information

基　　金：8 6 3计划资助项目 (合同号 :86 3 30 6 ZD0 3 0 4 1)

摘　　要：针对中文字串匹配问题 ,提出了一种改进的多模式匹配算法。该算法采用新型组合状态自动机 ,解决了对大字符集语言构建字符完全Hash表时可能遇到的存储空间膨胀问题。此外 ,算法还充分利用中文大字符集语言的优势 ,将QS算法的思想融入到多模式匹配应用中 ,取得了良好的效果。实验结果显示 ,本算法明显优于DFSA算法 ,在平均情况下所花费时间仅为DFSA算法的 70 33%。For the problem of Chinese string matching, an improved multiple pattern matching algorithm is provided. The unbearable memory cost problem which results from constructing Hash table for large character set, is resolved with the new combinatorial state automata. In addition, for taking full use of the advantage of Chinese which is a large character set, we combined the theory of QS algorithm into the application of multiple pattern matching. At last, the experiment data show that the new algorithm is much better than DFSA algorithm. For the average case, the time spent by new algorithm is only 70 33percent of that spent by the DFSA.

关 键 词：匹配 中文字附串 有限状态自动机 多模式匹配 算法 组合状态自动机 QS算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]