论文部分内容阅读
字符串匹配是计算机研究领域中的一个古老、经典而且被广泛研究的课题,是信息检索领域和计算机生物学领域等的关键技术之一。在当今的互联网时代,对匹配算法的需求日新月异,对处理的实时性的需求越来越高。这些都对原有的字符串匹配技术提出了新的挑战,有必要对原字符串匹配技术进行改进和优化。本文主要是对高效的多字符串匹配算法——Wu-Manber算法进行研究。本文针对Wu-Manber算法的散列表HASH的表项:HASH()链表的不足,提出了基于非空公共子后缀模式的处理算法;而后综合前人对Wu-Manber算法的SHIFT表的改进,提出更加高效的字符串匹配算法;进而提出一种在大规模串匹配时对Wu-Manber算法的改进。本文的研究成果具体如下:1.基于非空公共子后缀的Wu-Manber算法的改进:针对Wu-Manber算法在处理公共子后缀模式情况下的不足,本文提出了一种基于非空公共子后缀模式的处理算法。该算法把同一next链表中有非空公共子后缀的模式汇集在一起,进一步减小了next链表的平均长度。在匹配过程中减少了字符比较的次数,从而提高算法的运行效率。本文对搜狗实验室给出的相关文档进行全文检索实验,并和原Wu-Manber算法、前人提出的改进算法进行比较。实验结果表明,本文提出的改进算法有效地减少了匹配过程中字符比较的次数,从而提高匹配的速度和效率。2.对Wu-Manber算法的综合改进:对1中提出的算法进行了改进,在对next链表进行分类的同时把含有非空公共子后缀的结点提到链表的前部;并整合了前人提出的“精确的不良字符转移和弱化的良好后缀转移的改进”方法。新改进的算法充分利用以上两种算法的优点,使匹配过程中字符比较的次数得到了进一步减少。新改进的Wu-Manber匹配算法在实验中取得了更高的效率,比原算法提高到4.6%以上。3.Wu-Manber算法在大规模模式串下的改进:对1提出的算法进行了改进,把原算法中next链表中结点的Same_Subsuffix域分裂成两个子域,使得在大规模模式串的情况下,搜索过程中字符比较的次数进一步减少,新算法的效率比原算法有进一步的提高。实验结果表明,当模式串较少时,新算法效率与原算法相比有一定的损失。而随着模式串的增加,新算法具有更高的效率。因此,新算法比原算法具有更大的适用范围。