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

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