一种适合中文的多模式匹配算法

被引：4

作者：

侯整风

杨波

朱晓玲

机构：

[1] 合肥工业大学计算机与信息学院

来源：

计算机科学 | 2013年 / 40卷 / 11期

基金：

安徽省自然科学基金;

关键词：

多模式匹配; AC算法; 邻接链表; 有限状态自动机;

D O I：

暂无

中图分类号：

TP393.08 [];

学科分类号：

0839 ; 1402 ;

摘要：

中文字符的相互独立性导致AC算法的时空性能急剧下降。针对此问题,对AC算法的存储结构进行了改进,提出了一种适合中文的多模式匹配算法———ACSC算法。该算法以邻接链表存储有限状态自动机,尝试解决存储空间快速膨胀问题,并将状态"0"的长链表转化为散列链表,以提高算法的匹配效率。实验结果表明,ACSC算法具有良好的时空性能。

引用

收藏

页码：117 / 121

页数：5

相关论文

共 8 条

[1] AC多模式匹配算法研究 [J].

巫喜红 ;

曾锋 .

计算机工程, 2012, 38 (06) :279-281

[2] 一种改进的多模式匹配算法在Snort中的应用 [J].

王培凤 ;

李莉 .

计算机科学, 2012, 39 (02) :72-74+79

[3] 网络控制系统的简要回顾及展望 [J].

杜大军 ;

费敏锐 ;

宋杨 ;

李雪 .

仪器仪表学报, 2011, 32 (03) :713-721

[4] 一种基于位图的多模式匹配算法 [J].

张元竞 ;

张伟哲 .

哈尔滨工业大学学报, 2010, 42 (02) :277-280

[5] 改进的多模式匹配算法 [J].

王永成 ;

沈州 ;

许一震 ;

不详 .

计算机研究与发展 , 2002, (01) :55-60

[6] A VERY FAST SUBSTRING SEARCH ALGORITHM [J].

SUNDAY, DM .

COMMUNICATIONS OF THE ACM, 1990, 33 (08) :132-142

[7]

A fast string searching algorithm[J] . Robert S. Boyer,J. Strother Moore.Communications of the ACM . 1977 (10)

[8]

Efficient string matching[J] . Alfred V. Aho,Margaret J. Corasick.Communications of the ACM . 1975 (6)