基于C#实现并对比三种基本的字符串匹配算法-RK算法-KMP算法-朴素算法

happybirthday

发布日期: 2018-11-05 18:07:17 浏览量: 283
评分:
star star star star star star star star star star_border
*转载请注明来自write-bug.com

1 需求分析

1.1 系统目标

  • 实现题目说所要求的三种匹配算法的算法设计,算法实现,程序能够稳定,准确的运行并实现字符串匹配的功能,做出相应的窗体界面程序

  • 分析完成三种算法的时间复杂度,通过程序实验实现三种算法之间用时的比较

  • 按时撰写完成课程设计的文档和进度表

  • 优化设计程序的健全度和用户体验

1.2 系统功能需求

  • 文本的输入选择功能

    • 可以选择键入英文文本或者从文件中读入英文文本
  • 错误检查功能

    • 可以检查输入的英文文本以及输入的模式串中是否有非英文文本字符,如果有提示修改并重新输入
  • 字符串匹配算法选择功能

    • 提供朴素算法、Rabin-Karp算法、KMP算法,3种算法进行比较这四个选择
  • 重复匹配功能

    • 如果文本中多次出现需要匹配的模式串,输出重复出现的次数,以及每次在主串中匹配成功的初始位置
  • 时间的计算和比较

    • 选择一种算法匹配,如果匹配成功,输出该算法匹配成功所花费的时间,如果匹配失败,则输出匹配失败。选择3种算法比较,如果匹配成功,输出3种算法匹配成功耗时和耗时最长和最短的算法的名字,如果匹配失败,则输出匹配失败
  • 显示文本功能

    • 匹配之后会显示每次在主串中匹配成功的位置,点击位置,会弹出文本框,显示匹配上的位置

1.3 系统关键技术

  • hash散列法。Rabin-Karp 算法的实现原理需要用到hash散列法,将所有的字符分别映射到(0.1.2…n)中。文本的匹配转换成数字的匹配,文本字符串右移通过减去最高位,乘上进制数,再加上下一位字符对应的hash值,实现巧妙的右移

  • 在RK算法中会出现一个问题,一旦模式串的长度过大,减去最高位,乘上进制数,再加上下一位字符对应的hash值,实现右移的时候有可能会溢出,使得该算法失效,于是使用求余的方法来解决,mod一个比较合适的质素,可以避免其溢出

  • KMP的关键以及精华在于next数组。Next[i] = j 表示0…j-1与i-j ….i-1这两段匹配串是相同的。Next数组的定义为Next[0] = -1,Next[1] = 0;接下来的Next都通过递推的方式求出。

2 算法设计

2.1 系统整体思路

由于选题原因,开发设计从三个方面分别进行,分别是:朴素匹配算法的设计和实现,KR算法的设计和实现,KMP算法的设计和实现。

2.2 关键数据结构设计

顺序结构存储字符串,next数组。

2.3 朴素算法

2.3.1 算法基本思想

将主串S中某个位置i起始的子串和模式串P相比较。即从 j=0 起比较 S[i+j] 与 P[j],若相等,则在主串 S 中存在以 i 为起始位置匹配成功的可能性,继续往后比较( j逐步增1 ),直至与P串中最后一个字符相等为止,否则改从S串的下一个字符起重新开始进行下一轮的”匹配”,即将串T向后滑动一位,即 i 增1,而 j 退回至0,重新开始新一轮的匹配。

2.3.2 算法流程图

2.4 Rabin-Karp算法

2.4.1 算法基本思想

预处理长度与模式串长度相同的主串长度,每一字符哈希映射对应0…N中的一个。根据所在的位乘上相应的进制数相加成一个整型数。匹配转换成两个整型数的比较,如果两个整型数相等,说明他们哈希值相同,有可能是相同的串,于是深入匹配这两段串,如果匹配失败,模式串往后移开始新一轮的匹配。

2.4.2 算法流程图

2.5 KMP算法

2.5.1 算法基本思想

用模式串预处理Next数组,Next[i] = j 表示0…j-1与i -j -1….i-1这两段匹配串是相同的。每次匹配失败后,模式串并不是直接重头开始,而是从Next数组里找出起始位置,这样减少了不必要的匹配,节省了时间。

2.5.2 算法流程图

3 算法实现

3.1 开发语言及工具

  • 开发语言:C#

  • 开发工具:visual studio

3.2 算法关键代码

3.2.1 朴素算法关键代码

将主串S中某个位置i起始的子串和模式串P相比较。即从 j=0 起比较 S[i+j] 与 P[j],若相等,则在主串 S 中存在以 i 为起始位置匹配成功的可能性,继续往后比较( j逐步增1 ),直至与P串中最后一个字符相等为止,否则改从S串的下一个字符起重新开始进行下一轮的”匹配”,即将串T向后滑动一位,即 i 增1,而 j 退回至0,重新开始新一轮的匹配。

匹配部分的代码:

3.2.2 Rabin-Karp算法关键代码

预处理最高位和主串哈希值以及模式串哈希值的代码。

预处理长度与模式串长度相同的主串长度,每一字符哈希映射对应0…N中的一个。根据所在的位乘上相应的进制数相加成一个整型数。

匹配转换成两个整型数的比较,如果两个整型数相等,说明他们哈希值相同,有可能是相同的串,于是深入匹配这两段串,如果匹配失败,模式串往后移开始新一轮的匹配,以为通过主串减去最高位,乘上进制数再加上最低位。

3.2.3 KMP算法关键代码

预处理next数组的代码。

通过递推往下求next数组,当p[i] == p[k] 则说明p[0..k] == p[i-k..i],于是就有next[i+1] = k+1;

每次匹配失败后,模式串并不是直接重头开始,而是从Next数组里找出起始位置,这样减少了不必要的匹配,节省了时间。

3.3 主要功能界面

3.3.1 文本输入的选择功能

可以选择从文件中导入英文文本,或者手动输入英文文本。

选择从文件中导入后的界面

选择手动输入后的界面

3.3.2 错误检查功能

检查输入的文本和匹配字符串中是否有非英文字符,若有,则提示出错。

3.3.3 字符串匹配算法选择功能

可以选择相应的算法进行字符串匹配。

3.3.4 重复匹配功能

当匹配字符串在文本中多次出现,则输出匹配成功的次数,和每次匹配成功的起始位置。

若匹配失败,则输出匹配失败。

3.3.5 时间的计算和比较

选择单独是算法,则是输出第一次匹配成功所花费的时间。

选择3种算法进行比较,则输出3种匹配所花费的时间和匹配耗时最多和最少的算法名称。

3.3.6 显示文本功能

点击下面的数字,可以显示匹配上的串在文本中的位置。

4 算法分析

4.1 算法复杂性分析

4.1.1 朴素算法

朴素的字符串匹配过程可以形象的看成一个包含模式的“模板”P沿文本T移动,同时对每个位移注意模板上的字符是否与文本中的相应字符相等。外层循环的次数最多为len(s) - len(p),内层循环的次数最多为len(p),最坏情况下的时间复杂度:O((len(T) - len(P) + 1) * len(P))。

4.1.2 Rabin-Karp算法

Horner法则p = p[m] + 10(p[m -1] + 10(p[m-2]+…+10(p[2]+10p[1])…)),求出模式字符串的哈稀值p,而对于文本字符串来说,对应于每个长度为m的子串的 哈稀值为t(s+1)=10(t(s)-10^(m-1)T[s+1])+T[s+m+1],然后比较此哈稀值与模式字符串的哈稀值是否相等,若不相同, 则字符串一定不同,若相同,则需要进一步的按位比较,所以它的最坏情况下的时间复杂度为O(mn)。

4.1.3 KMP算法

KMP算法之所以叫做KMP算法是因为这个算法是由三个人共同提出来的,就取三个人名字的首字母作为该算法的名字。其实KMP算法与BF算法的区别就在于KMP算法巧妙的消除了指针i的回溯问题,只需确定下次匹配j的位置即可,使得问题的复杂度由O(mn)下降到O(m+n)。

4.2 算法优缺点分析

4.2.1 朴素算法的优缺点

  • 优点:朴素算法简单易懂,代码容易实现

  • 缺点:时间复杂度太高,字符串和英文文本中连续相同的子串太多的时候花费时间比较大

4.2.2 Rabin-Karp算法优缺点

  • 优点:思路新颖,用hash映射后的值进行字符串匹配,巧妙移位,代码不难实现

  • 缺点:因为用到hash,会出现冲突,进行多次不必要的深度匹配,浪费了时间。进制数和质素需要适当的选取

4.2.3 KMP算法的优缺点

  • 优点:运用next数组很快的找到匹配失败后应该重新匹配的启示位置,而不是重头再来。节省了时间

  • 缺点:求next数组需要一定的时间开销

总的来说,字符串和英文文本有较少的连续相同子串的时候,朴素是不错的选择,这个时候朴素的时间可以接近o(n),而Rabin-Karp和KMP都需要启动时间,就有可能比朴素慢。当字符串和英文文本有较多的连续相同子串的时候,KMP是个不错的选择,他的next数组就能很好的解决匹配失败后字符串该从哪里开始的问题,使时间接近于o(n)。而这时候朴素的复杂度是接近o(n^2)的。RK算法适合较长的英文文本匹配,这样可以忽略他的启动时间,文本较短的时候会跑不过朴素,重复较多的常文本也许会跑不过KMP,其他请客都比这两个算法要快。

5 项目总结

经过了一个月的努力,终于成功的完成了整个项目系统。一开始对RK,KMP算法的一无所知,在查阅了大量资料,翻阅了许多博客后,学会了这些算法,并且知道了这些算法的优缺点和适合在什么场合使用。小组三人分工合作,让我们体会到了在完成项目的过程中合作的难度和重要性。

同时,在代码初步完成后,我们进行了大量的测试工作,我们曾经以为KMP算法不管在什么情况下都是耗时最少的,朴素算法不管在什么情况下都是耗时最多的,RK算法则处于两者之间。测试后我们发现我们错了,每种算法在不同的情况下会有不同的效果,并没有绝对的谁会最快,谁会最慢,测试工作完成后,发现命令行操作界面并不美观,也不适合广大用户,于是我们对用户体验进行优化,做了一个系统界面,把所有的功能都实现,方便用户使用。

在这一过程中,我们发现了大量的不足,同时也了解到要完成一个健壮性极强,用户体验很好的软件需要些什么。经过许多讨论和修改,最终完成了界面的制作。总之,在这次课程设计中,我们不仅学会了新的算法,还了解了算法的本质,学会对算法进行纵向比较,也学会了如何完成一个优秀的软件。总之,收获良多。

上传的附件 cloud_download 基于C#实现并对比三种基本的字符串匹配算法.7z ( 709.48kb, 4次下载 )
error_outline 下载需要5点积分

keyboard_arrow_left上一篇 : 基于时空数据分析的决策支持报告 基于easyx实现的小蓝鲸跑酷游戏 : 下一篇keyboard_arrow_right



happybirthday
2018-11-05 18:07:56
对比并实现三种基本的字符串匹配算法:RK算法、KMP算法、朴素算法

发送私信

都说你眼中开倾世桃花,却如何一夕桃花雨下

6
文章数
11
评论数
最近文章
eject