HashTrie:一种空间高效的多模式串匹配算法

经典的多模式串匹配算法AC的内存开销巨大,已经无法满足当前高速网络环境下大规模特征串实时匹配的应用需求。针对这一问题,提出一种空间高效的多模式串匹配算法—Hash Trie。该算法运用递归散列函数,将模式串集合的信息存储在位向量中,以取代状态转移表来减少空间消耗,并利用Rank操作进行快速匹配校验。理论分析表明,Hash Trie算法的空间复杂度为O(|P|),与模式串集合的规模|P|线性相关,与字符集大小σ无关,优于经典多模式串匹配算法AC的空间复杂度O(|P|σlog|P|)。在随机数据集和真实数据集(Snort、Clam AV和URL)上的测试结果表明,Hash Trie算法比AC算法节约高达99.6%的存储空间,匹配速度约为AC算法的一半左右。Hash Trie算法适合于模式串集合规模较大、模式串长度较短的多模式串匹配问题,是一种空间高效的多模式串匹配算法。