多关键词匹配算法.ppt

文档介绍：String Match多关键词匹配算法
计算所软件室谭建龙
2002-11
内容
String Match 算法分类
AC自动机算法介绍
CW跳跃算法
Suffix Tree算法
总结和展望
问题介绍
多关键词匹配( Keywords Matching)有时也称为多模式匹配(Multiple Pattern Matching )或者字典匹配(Directory Matching、Set Matching),是一个经典的算法问题,它研究从大量数据中快速匹配多个关键字(多个模式)的技术。
关键词匹配算法根据对文本还是模式进行预先处理分为索引方案和非索引方案。索引方案可以对文本先进行预先处理,再进行关键词匹配。我们主要考虑是非索引方案。
String Match 算法分类
针对数据流的线性算法
AC算法线性算法
CW算法亚线性算法
数值型算法MPHF算法
针对静态文档的索引算法
Index方法
后缀树算法Suffix Tree
局限和挑战
白硕:
数据包还原的性能压力
使用大规模并行机、合理的负载均衡策略
在线多关键词全文扫描匹配的性能压力
需要算法的改进,尤其需要支持串比较流水作业的专用芯片
谢谢