两个字符串搜索算法的比较及改进

两个字符串搜索算法的比较及改进 摘要:字符串搜索算法在实际生活中被广泛应用，它是计算机基础科学的一个重要部分，现在比较著名的字符串搜索算法包括BF(Brute Force)算法、KMP(Knuth Morris Pratt)算法和BM(Boyer Moore)算法等。本文比较了BF算法、BM算法的搜索效率以及基于BM算法的改进。 关键词:字符串搜索;BF算法;BM算法 中图分类号:TP301.6 文献标识码:A 文章编号:1003-9767(2011)04-0134-02 有关的，当模式串Pattern 中的某一字符串 与比较部分1. 引言 在计算机科学领域，字符串搜索问题一直都是研究的焦点之一。相同时，可让模式传Pattern直接右移s位。这可以通过 函 在多数的操作系统中，字符串搜索算法是现存的实际软件执行的基本 数算出来。 函数定义如下式?: 组成部分。而且，字符串搜索算法强调的是程序方法在其他计算机科 ? 学领域(系统或软件)中作为一定的范例。在计算机科学理论 中，字符串搜索算法在面对挑战性问题时同样也起着重要的作用。 3. BF算法和BM算法的比较实例字符串搜索算法是一种重要的运算方法，字符串搜索算法是对于 设定正文字符串(Text ):patbegadefabcde ，模式字符串(pattern):abcde。 和长度为 的模式字符串Pattern= 长度为 的正文字符串Text= 由于根据BF算法的基本思想将上述两个字符串进行搜索比较， (模式字符串集)，要找到 ，， 得出的结果是:正文字符串长度为15，模式字符串长度为5，搜索次 模式字符串Pattern在正文字符串Text的首次出现，如果模式字符串 数为11，字符比较次数为17，匹配次数为1。这就证明这个例子匹配 Pattern在正文字符串Text中找到，则搜索成功，否则搜索失败。 在众成功。 多的字符串搜索算法中，BF (Brute Force )算法是最简 但是如果根据BM算法的基本思想将上述两个字符串进行搜索比 单的一种字符串搜索方法，但是它的搜索效率很低。到了1977年， 较，其搜索过程跟BF算法的搜索过程有很大区别，并且比BF算法的 Robert Boyer和L.Moore发表了一种新的精确字符串匹配算法(Boyer 搜索效率有了很大的提高，以下表1是BM算法的搜索过程(其中，加 Moore)算法，这种算法在逻辑上相对于已有的算法有了很大的超 粗并加下划线的字符表示不匹配字符): 越。它对要搜索的字符串实施逆序字符比较，而且有一种找到了不匹 表1 BM算法的搜索过程 配字符就不需要对整个字符串进行搜索的方法。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 T p a t b e g a d e f a b c d e 2. BF和BM算法的介绍 第一 次a b c d e 2.1 BF(Brute Force)算法。BF算法是一种最简单但效率最差 第二次a b c d e 的字符串搜索算法，它首先将模式字符串Pattern中的 与正文字符串 第三次a b c d e 第四次a b c d e Text中的 开始进行比较，如果不匹配就将 与 比较 直到 与 由上表可知，其搜索结果为:正文字符串长度为15，模式字符串 匹配为止，再将 之后的字符与的进行比较，若相同，则继续 长度为5，搜索次数为4，字符比较次数为9，匹配次数为1。 显然易往下比较;但当正文字符串Text中任一个字符 与Pattern中的 不匹 见，BM算法比BF算法的搜索次数和字符比较次数都要 配时，又要返回 ，即将 对齐 继续开始下一次的比较，重复上述 过 高，因而BM算法的搜索效率比BF算法的效率要高。 程。若Pattern中的所有字符都比较完，则说明匹配成功，否则匹配 失 败。 2.2 BM(Boyer Moore)算法。BM算法是一个从右向左比较字 4. BM的改进算法(IBM算法)符的搜索算法，开始比较时，要将正文字符串Text的 与模式字符串 4.1 IBM算法的基本思想。IBM算法的思想与BM算法基本相同。Pattern的 对齐，其中n为正文字符串Text的长度，m为模式字符串 IBM算法是首先从 和 开始自右向左进行比较，如果匹配成功，那 Pattern的长度。从 与 开始进行比较，当发现某次比较中出现不匹 配 么就用时，就采用两条启发性规则，并且取两者的右移最大值来计算模式 串函数检查 是否在模式串Pattern中只出现过一次，如果是 的右移距离(设模式串右移后对准了正文串的第i个字符)，即坏 字那样就用一个变量only记录下这次匹配过程中第一个 的指针i的 符规则和好后缀规则两个规则，然后再将 与 对齐并开始新一轮 的比 值，然后继续进行比较。但在比较中出现匹配失败时，就将文本字符较。如果 与 匹配，即表明匹配成功，否则匹配失败。 串Text的指针i修改为m+only，重新开始新一轮的搜索比较;如果only 的记录值为0，表示匹配失败处之后的所有字符可能多次出现在模式 (1)坏字符规则(Bad Character)。当Pattern中的某个字符与 Text中的某个字符不相同时，就使用坏字符规则右移模式串Pattern， 串Pattern中，为了不丢失任何匹配成功的可能，下一次比较执行按照 坏字符规则来移动字符，并进行新一轮的从右向左的字符比较。 右移模式串Pattern的位数可以通 过 函数计算出来。 函数定义如下 4.2 BM算法的改进方法。在BM算法中，搜索要运用到坏字符规 式?(其中x 是正文字符串中的某个字符):则和好后缀规则，但是在IBM(改进的BM算法)中，只用到坏字符 规则，好后缀规则去掉，并加上另一个新的规则，这就是字符重复规 则。首先定义一个函数，其中x为正文串Text中的字符，这个函数 主要记录正文串Text中的x字符有没有在模式串Pattern中重复出现。如 果只出现一次，则该字符的;但如果该字符不止出现一次， (2)好后缀规则(Good Suffix)。这个规则与模式串Pattern 由表2可见，其搜索结果为:正文字符串长度为15，模式字 则该字符的。函数设计如下式?: 长度为5，搜索次数为3，字符比较次数为8。显然，在相同的搜 例中，IBM算法的搜索次数和字符比较次数都比BM算法的搜索 4.3 BM算法与IBM算法的比较。假如模式字符串Pattern跟正文字 和字符比较次数要少，这就表明IBM算法比BM算法搜索效率有 进。 符串Text进行从 的“返前”匹配比较过程时，失败于 Pattern，并当only 时(即在模式串Pattern中 和 处，且有 只出现了一次)，设指针i的值为 ，那么有only ，如果 5. 结束语 表示移 原BM算法向后移动的值记为 ，其中 在实际的计算机基础应用中，字符串搜索算法相当重要， 。 搜索算法的搜索匹配效率对现有的计算机技术具有相当大的影响动的位数;改进后的BM算法指针i向右移动的值记为 大多数字符串搜索比较的情况下，它能提高模式匹配的速度，减显然 ，所以， 因此改进后的算法在多数情况下可以加快字符串搜索比较的速度。较的次数，对字符串具有明显加速效果，同时又没有增加算法的 以下用上述BF算法与BM算法的比较实例来分析IBM算法的搜索 度，因此有很大的使用价值。过程和搜索效率。其正文字符串和模式字符串都与上述实例一样，然 而用IBM搜索算法的搜索过程则如下表2(其中，加粗并加下划线的 参考文献:为匹配失败的地方): [1]潭浩强. C语言程序设计(第二版)[M] . 北京:清华大表2 IBM算法的搜索过程 社，1999 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 [2]李师贤，李文军，周晓聪. 面向对象程序设计基础[M] .T p a t b e g a d e f a b c d e 高等教育出版社，1998 第一 次a b c d e [3]苗杰，邵品洪. BM模式匹配算法的改进研究[J] . 现代图 第二次a b c d e 技术，1994(3) 第三次a b c d e [4]赵一瑾. 一个改进的BM串匹配算法[J] . 计算机研究与发 1998(1) 4.4 比较结论 (上接第133页) SqlCommand cmd = new SqlCommand(strSQL, conn); 统后自行修改密码，也可请管理员初始密码，用户的基本信息可以由用户自行提交修改，但需管理员核准信息后方可生效。 验证码:系统int i = cmd.ExecuteNonQuery(); 产生一串随机的由数字和字母组成的字符并生成图 conn.Close(); 片，用户根据图片在登录时输入验证框进行验证，用以减少暴力 破解的可能，增加系统安全性。 4. 结束语3.2角色模块 系统根据权限控制模块对不同角色的登录用户，进 本系统在分析了院校在多媒体教室管理的背景下，提出了多行特定界面 教师使用记录和信息反馈系统的分析研究，设计并给出了功能需构造，提供不同的功能和权限。因篇幅所限，这里仅举例使用者(教 师)角色。教师使用自己的用户名登录系统后，系统根据权限控制模 合院校相关部门的实际使用的系统模型，并付诸实施。经过实际 块的判断确定该用户的使用者(教师)角色，然后系统构造出含有使 使用，实践证明，该系统有效的提高了管理部门的信息统计，有用教室使用记录登记，信息反馈，在线交流和用户信息编辑等模块的 获取了师生的需求和信息反馈，并实现了计算机信息统计，提高界面返回给客户浏览器，用户根据浏览器上的功能使用系统。当用户 作效率。提交记录或其他信息时，浏览器将信息返回给系统后台，程序经过判 断存入数据库，完成数据提交。主要代码举例如下: 参考文献:string strSQl = "insert into UsersInfo(用户,记录,时间)values('" + 用 [1] #sub687468 户 + "','" + 记录+ "','" + 时间 + "')" [2]John Kauffman 、Fabio Claudio Ferracchiat (著)i、 SqlConnection conn = new SqlConnection(connStr); (译),ASP.NET数据库入门经典—VB.NET编程篇，清华大学出 conn.Open(); 2002(12)