多模匹配
给出一个关键词列表(模式串),和一段字符串text。输出text中存在的关键词。
以上也是多模匹配的定义, 多模的名字应该来源与模式匹配(两个字符串之间的匹配,我们常听的KMP算法)
多模匹配有以下场景: 关键字过滤, 分词, 入侵检测, 病毒检测
算法实现
AC算法实现
AC自动机+trie树实现高效多模式匹配字典(java源码)
WM(Wu-Manber)算法
案例说明
输入:
关键字数组:[“研究”, “脂肪酶”, “水平下”, “哮喘”, “正相关”, “表达式”, “研究结果”]
待匹配字符:“该研究结果表明,IL-17A和IL-9高表达以及脂肪酶、CCL11水平下降与成人哮喘之间呈正相关。”
输出:
匹配成功关键词组:[‘研究’, ‘研究结果’, ‘脂肪酶’, ‘水平下’, ‘哮喘’, ‘正相关’]
测试结果:TODO
AC与WM对比:
内存占用:WM改进算法比AC改进算法的内存小很多;
预处理: WM改进算法比AC改进算法的预处理时间小很多;
匹配速度:WM算法的匹配速度跟加载的模式串内容有很大的关系;
AC算法跟加载的模式串内容无关;
前缀:如果前缀内容大量相似,WM改进算法的Shift表和HASH表冲突比较多,匹配慢。
AC算法优化:采用双数组来优化内存占用。