多关键词匹配算法.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 局限和挑战 白硕： 数据包还原的性能压力 使用大规模并行机、合理的负载均衡策略 在线多关键词全文扫描匹配的性能压力 需要算法的改进，尤其需要支持串比较流水作业的专用芯片 * * 谢谢 *