一种大规模关键词匹配方法

摘要

一种大规模关键词匹配方法。包括预处理阶段和模式匹配阶段。预处理阶段包括关键词特征串裁剪、基于关键词特征串集合的多个简单布隆过滤器(Bloom Filter)的构造，基于关键词特征串集合的哈希表构造；模式匹配阶段包括：利用先前构造的简单布隆过滤器序列实现当前窗口中文本串不与任何关键词特征串匹配的快速判定；在判定失败情况下执行与候选关键词的精确匹配；文本扫描过程中，可以利用递归算法快速计算出当前文本相对于各简单布隆过滤器的当前散列值。本发明充分利用了待匹配文本与关键词匹配成功概率异常低的特点，利用了递归散列算法高效的特点，可实现大规模关键词场景下的高速匹配，非常适合病毒检测等在线病毒扫描应用。

主权项

1. 一种大规模关键词匹配方法，包括预处理阶段和模式匹配阶段，其特征在于包括以下步骤：A)所述预处理阶段包括以下步骤：A1、根据设定的关键词特征串长度，对关键词集合中各关键词进行特征串抽取，构成关键词特征串集合；A2、构造多个仅包含一个散列函数且该散列函数支持递归运算的简单布隆过滤器，将关键词特征串集合同时映射到多个简单布隆过滤器中；A3、构造一个哈希表，将关键词特征串集合映射到哈希表各单元中，对于具有哈希值冲突的元素，用链表方式串接起来；A4、构建一个包含所有原始关键词的线性表，步骤A3中建立的关键词特征串哈希表项中包含对应原始关键词的索引号；B)所述模式匹配阶段包括以下步骤：B1、设置一个与关键词特征串等长度的文本匹配窗口，首先将文本匹配窗口与待匹配文本左对齐；B2、以当前文本匹配窗口中文本串为输入，依次使用各简单布隆过滤器及其递归散列公式，实现当前文本串不与任何关键词特征串匹配的快速判定：如果基于某一简单布隆过滤器成功实现对当前文本串的快速排除判定，则直接跳跃到步骤B5执行；如果基于当前简单布隆过滤器的排除判定失败，则继续使用下一个简单布隆过滤器；如果所有简单布隆过滤器都执行排除判定失败，则进入步骤B3；B3、依据文本匹配窗口中文本串检索关键词特征串哈希表，如果找到匹配的关键词特征串表项，则执行步骤B4；如果未找到任何匹配表项，则直接跳跃到步骤B5执行；B4、根据关键词特征串表项中的索引号从原始关键词线性表读取对应的原始关键词，并与当前匹配窗口处文本串进行全长度字符串比较，如果匹配成功则报告一个成功的关键词匹配事件；继续执行步骤B5；B5、将当前文本匹配窗口向右移动1字节，并跳跃到步骤B2继续执行，直至整个文本扫描结束。