论文部分内容阅读
模式(字符串)匹配是计算机领域中的一个重要的研究方向,该问题是计算机科学中的基础问题之一,在学术界和工业界有着广泛的研究与应用。模式匹配算法被广泛应用到涉及文本处理的各个领域,在网络安全、信息检索、文本过滤、以及生物信息学中都是关键问题。随着互联网、海量文本检索、计算生物信息学的高速发展,模式匹配问题中的规则数也迅速的增大,模式匹配算法面临的挑战也越来越大。特别是在我国网络安全领域中,当前一些模式匹配算法已经很难满足在中文字符环境下的较大规模模式集匹配系统的性能要求。因此,迫切需要在较大规模模式串下构造性能突出的模式匹配算法。本文首先介绍了模式匹配的一些经典算法,如BF算法、KMP算法、BM算法、AC算法、AC_BM算法和WM算法。其次,在较大规模多模式环境下,对于中文字符集,本文提出了一种基于WM算法的改进的多模式匹配算法——MSCZ算法。改进策略包括:1.利用二级哈希策略削减了WM算法在中文较大规模模式集下的高内存空间占用与高冲突的情况。2.对于中文模式串出现的前缀包含情况,通过模式串前缀压缩策略,解决了HASH表中模式串链过长的问题。3.通过进一步对压缩后的HASH表模式串链,建立二叉查找树,将原有WM算法查找时的线性时间复杂度转化为了对数时间复杂度,提升了算法在模式集规模较大时性能。实验表明MSCZ算法相对于WM算法在性能上有了较大的提升。最后,本文对MSCZ算法在Hadoop Mapreduce框架下进行了并行化设计与实现。本文提出了MSCZ算法的Hadoop Mapreduce并行化方案,旨在提高MSCZ算法对海量数据集的处理速度。针对MSCZ算法在Hadoop Mapreduce并行化过程中存在的输入数据量为大量小文件时,系统启动过多作业而导致的系统性能低下的问题,通过自定义文件输入格式,将多个小文件作为一个作业输入,降低作业个数。实验表明Hadoop Mapreduce并行化的MSCZ算法相对于串行的MSCZ算法性能有较大的提升。