【作者】 李莉；

【导师】 林劼；

【作者基本信息】 福建师范大学 ， 软件工程， 2016， 硕士

【摘要】 KMP算法和BM算法是经典的基于字符比较的单模式匹配算法。KMP算法的文本指针每次只能增加1个单位,模式串每次的右移量都小于当前j值,KMP的总体效率并不高。BM算法没有综合考虑好后缀规则与坏字符规则之间的前驱后继关系,整体的匹配效率也不高。目前基于BM算法的改进算法比较多,经典的改进算法有QS和FJS算法等,其算法的改进空间还有很大。针对以上的问题,提出了三种新的基于字符比较的单模式匹配算法。首先,基于KMP算法提出一种改进算法-KMPP算法,KMPP算法是结合KMP算法和BM算法的优点提出的新算法。在模式串的j处匹配失败时,模式串先右移next[j]单位后,如果模式串的末字符与相应的文本字符不匹配时,则用该文本字符进行坏字符匹配,文本指针i移动的距离就是这两步的右移量,从而使指针i每次移动的距离达到最远,提高算法的运行效率。其次,在QS算法的基础上提出一种改进方案一QSP算法。QSP算法在预处理部分从左向右找出模式串中出现1次以上的单字符,得到maxPos值和两个数组,在匹配部分,选择性的引用两个数组进行右移,保证每次的移动量最大。在字符比较之前,QSP算法对模式串进行分析,从而避免在匹配阶段出现不必要的字符比较,算法的运行速度得到一定的提高。最后,针对FQS算法提出一种新算法-FQSP算法。FQS算法是QS算法的一种改进算法,FQSP算法引用FQS算法得到的pos值,将P[pos]字符与模式串对应的下一字符组合起来考虑,进行最大距离的右移,从而提高算法的运行效率。这三种改进算法在"gene.txt"、"bible.txt"和“1 OOM.txt”三种数据集上进行相关的实验,并将这三种改进方案分别与近几年的改进算法进行对比分析,进一步验证三种新算法的有效性。更多还原

【Abstract】 KMP algorithm and BM algorithm are classical single pattern matching algorithms. In KMP, the pointer in the text can only move one character at one time, the moving distance of the pattern pointer j is less than the current value of j at each time, hence, the comparison is not efficient. As for BM algorithm, the current BM algorithm and its variant did not consider the relationship of precursor and successor between good suffix and bad character rules, thus their overall matching efficiency is not high enough. There are many BM variant algorithms at present, QS algorithm and F.1S algorithm are the most well-known improved algorithms of it, however, there is still much room for improvement. To the above three problems, we propose three novel single pattern matching algorithms based on character comparison.Firstly, the KMPP, an improved algorithm based on the KMP, is proposed. It combines the advantages of the KMP algorithm with BM algorithm together. When a mismatch occurs at pattern position j, the pattern moves to right for the distance of the value of next[j]. If at this time, the last character of pattern does not match with the corresponding text position, then the bad character rule is used. The moving distance of pointer i in the text is a combination of the above two-steps jumping distance, thus the pointer can move farthest at each time. It is an efficient pattern matching algorithm.Secondly, the QSP algorithm, an improvement to the QS algorithm, is proposed. The core idea of QSP algorithm is to find all characters that appear more than once in the pattern string from left to right, and obtain the maxPos value and two arrays in the preprocessing phase. During the matching phase, in order to move the pointer farthest at each time, it moves to right by using the two arrays smartly. Because the preprocessing of the pattern string before the character comparisons, the unnecessary character comparisons in the matching phase are avoided, thus the matching speed is improved greatly.Finally, the third new algorithm is FQSP algorithm which is based on FQS algorithm. The FQS algorithm is an improved algorithm of QS algorithm. In order to move farthest, it gets the value of pos from FQS algorithm, and considers the character of P[pos] with the next character in the pattern. Its efficiency is higher than the FQS algorithm.In the three proposed novel algorithms, the datasets of "gene.txt"、"bible.txt" and "100M.txt" are used in experimental sections. The experimental results are compared with the state-of-the-art algorithms. The efficiency of these three algorithms is presented.更多还原