论文部分内容阅读
随着计算机、通信与网络的飞速发展,信息泄漏等问题受到了越来越多的关注。基于内容的网络信息审计,是保证信息不被泄漏,防止非法信息传播的有效手段,其关键技术为多模式文本匹配。在我国现有的网络环境下,多模式文本匹配将会面临中英文混合处理这一特殊难题。传统的多模式匹配在此环境下,则会产生空间膨胀、误匹配或漏匹配等问题。且随着网络数据信息规模的日益增加,对内容审计的实时性有了更高的要求。论文的主要工作包括:(1)在Trie结构的基础上,提出了一种基于节点添加的中英混合多模式匹配算法—NA-Trie。该算法通过添加少量的节点,以避免中文首字节错位匹配等问题。算法能够正确处理模式串同时含有中英文字符这一情况,有效避免错误匹配的发生;并且简化匹配过程,消去了多余的分支语句,使得算法更易于并行加速。给出一种基于记忆化存储状态结果的优化算法,通过预处理所有状态节点,记忆化地保存各状态所能获得的匹配数。该算法降低了匹配算法的时间常数,减少了时间开销,在一定程度上提高了匹配效率。(2)分多个小文本、单个大文本两种情况,利用GPU对多模式匹配进行并行优化。并针对单个大文本情形,给出一种基于文本拆分的并行文本匹配算法。该算法通过预处理以去除中文文本的数据相关性,再进行文本拆分和并行匹配,以大幅提升算法匹配效率。设计并实现了一种基于GPU的通用并行文本匹配原型系统,该原型系统模块化了并行匹配过程,提供了统一的函数接口。研究人员只需将自己的核心匹配代码嵌入到接口函数中,即可完成多模式匹配算法的并行优化。该原型系统简化了编码过程,提高了开发效率。