基于内容过滤的模式匹配算法比较.pdfVIP

第 1期 (总 l35期) 情报探索 2009年 1月 基于内容过滤的模式匹配算法比较 曹娴静 黄小键 (福建师范大学社会历史学院 福州 350007) (厦门市思明区会展 中心南里 169号 福建 361001) 摘 要 针对 网络文本 内容 ，将入侵检测系统q-使用的多模式匹配算法进行 了q-英文模式匹．fit／g45-效率 的对比．发现这些 算法普遍更适合于英文模式匹配，而在 中文模式匹配 中的运行效率较低。为此提 出了基于内容过滤的模式匹配算法的改进思路。 关键词 多模式匹配 算法比较 算法 中圈分类号 ：G354．4 文献标识码 ：A 文章编号 ：1005—8O95(2()09)01—0092一()3 1 算法简介 模式串集 P中所有关键字长度总和：有哪些信誉好的足球投注网站阶段 ，最好 1．1 有限 自动机 (AC)算法 情况下时间复杂度是 0(n／minlen)．最坏情况下时间 在多模式匹配算法 中，AC算法是最著名的算法 复杂度是 O(nmanxlen)，平均情况下时间复杂度涉 之一。该算法是把所有关键字合并到一个集合中利 及到字符出现的概率。 用有限 自动机的原理同时接收集合中的所有串。在 1．3 Wu—Manber算法 算法实现中，不区分中英文，将其作为统一的字符集 Wu—Manber算法将多个模式 “合并”为一个模式 对待 ，即按照中文的编码规则 ：将一个汉字作为两个 考虑 ，每次看 B个字符。具体的办法是首先计算模式 字符处理。该算法 的基本思想是这样的：在预处理阶 集 {P}的最小模式长度 m，以后对模式集处理时只看 段 ，有 限 自动机算法建立三个 函数即转向函数 (go． 每个模式的前 m个字符 。另外 ，对每个模式计算一 to)、失效函数 (failure)和输 出函数 (output)，由此构 个 hash值(散列值)，把每个 hash值对应的模式使用 造一个树型有限 自动机。这样 ，模式匹配的处理过程 链表链接起来 ，在进行匹配的时候，它使用表Hash[ _ ] 就变成 了状态转换的处理过程 ，由 “start”状态开始。 选择关键词集合 中的一个子集与 当前文本进行 匹 在有哪些信誉好的足球投注网站查找阶段 ．通过这三个函数的交叉使用扫描 配 ，减少无谓的匹配运算。Wu—Manber算法还构造了 文本．定位出关键字在文本中的所有 出现位置。有限 一 个不 良字符移动距离表 (Shift¨)，利用当前块字 自动机 的构造使每个状态仅仅是一个前缀的代表 。 符 W 查 Shift[]表 ，向后移动 Shift[W]个字符寻找下 当文本的下个字符不是想要的字符时，转到一个模 一 个匹配入 口点；如果 Shift[W]等于 0．表示 W 是一 式的最长前缀所代表的那个状态 。这个状态也就是 个可能的匹配入 口。使用Shiftf1表可以跳过那些不 当前状态的合适的后缀。应用有限 自动机算法对一 可能成功的匹配人 口，提高匹配的速度。Wu—Manber 个长度为n个字节的文本T进行扫描 ，由于 T中的 算法的时间复杂度在最好的情况能达到 0(B*n／m) 每个字符仅有一个状态转换函数 ，因此在扫描阶段 (B是块字符的长度，是算法在每一个入V1点计算块 所需的时间复杂度在 0(n)，并且与具体模式的长度 字符的时间，n为模式集fP1的尺寸 ，m是最小模式的 和模式集的大小无关。 长度)。