规则数量无关的多布尔表达式匹配算法  

Multiple Boolean Expression Algorithm Without Expression Size

作　　者：宋云[1] 龙际珍[1] 

机构地区：[1]长沙理工大学计算机与通信工程学院,湖南长沙410076

出　　处：《软件导刊》2012年第3期57-59,共3页Software Guide

基　　金：湖南省科技计划项目(2009JT3003);长沙市科技计划重点项目(K1104022-11)

摘　　要：经典的关键词表达式(query expressiont keywords expression)是搜索引擎(web retrieve)和数据库等使用的查询语言。但是在网络内容分析系统中,如果单纯使用关键词作为查询条件,会存在很多误报情况,所以网络内容分析系统-般采用表达式作为查询条件。提出了一种新关键词表达式匹配算法。这种算法改进了经典计数算法(pred-icate counting algorithm)中不适合网络内容分析环境的数据结构,对比计数算法需要平方级的算法复杂度,新算法可以在线性复杂度内容扫描阶段完成关键词表达式匹配工作。新算法去除了底层多串匹配性能的影响,并通过更多的内存占用,在匹配速度方面可以提高近200%。we present a combination keyword matching algorithm called ExprAnto.ExprAuto is an automation algorithm that carl handle the query expression which combinate the keywords with＂and＂or‘or＇.For monitoring thousands of networkdata flows,we adapt the predicate counting algorithm to the automation algorithm.Although ExprAuto USeS much more spaces than predicate counting algorithm,it is faster than the predicate counting algorithm.ExproAuto can use O（1）tohandle data stream item but the predicate counting algorithm must use O（n）（n is expression size）.The expression matching algorithms for massive data stream.

关 键 词：内容过滤 多模式串匹配 自动机 DFA 

分 类 号：TP312[自动化与计算机技术—计算机软件与理论]