一种面向中文的快速字串多模式匹配算法  

A Fast Multiple Pattern Algorithm for Chinese String Matching

作　　者：沈洲[1] 王永成[1] 许一震[1] 

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

出　　处：《上海交通大学学报》2001年第9期1285-1289,共5页Journal of Shanghai Jiaotong University

基　　金：国家"8 6 3"高科技资助项目 ( 86 3-30 6 -ZD0 3-0 4-1)

摘　　要：针对中文字串匹配问题 ,提出一种快速多模式匹配算法 .算法采用新型组合状态自动机 ,将2个状态组合起来匹配一个双字节字符 ,从而解决了双字节字符构建完全 Hash表时带来的存储空间膨胀问题 ;同时考虑到待匹配模式串中的字符在大字符集中呈稀疏分布的特点 ,尝试将单模式QS匹配算法的思想与 DFSA算法进行结合 ,应用于多模式匹配中 .实验结果显示 ,本算法明显优于 DFSA算法 ,平均所花费时间仅为 DFSA算法的 45 .2 % .For the problem of Chinese string matching, a fast multiple pattern matching algorithm was provided. With the new combinatorial state automata, the unbearable memory cost problem which results from constructing Hash table for every double byte characters, is resolved by binding two states to match one double byte character. The characters in the specified strings, which would be searched in the whole text, represent a kind of sparse distribution state in the large character set language. So, we try to combine the advantages of QS algorithm with the DFSA algorithm and apply to the multiple pattern matching. The experiment datas show that the new algorithm is much better than the DFSA algorithm. For the average case, the time spent by the new algorithm is only 45.2% of that spent by the DFSA.

关 键 词：字符串 有限状态自动机 多模式匹配 单模式QS匹配 DFSA算法 存储空间膨胀 

分 类 号：TP391.1[自动化与计算机技术—计算机应用技术]