Horspool和Sunday
目的:
以Horspool和Sunday算法为载体,试图在减少思维断层情况下学习作者算法思想
目录:
1:Horspool算法:简单的力量
2:Horspool代码实现
3:Sunday算法过程
4:Sunday代码实现
5:重新半理性审视BF、KMP、BM、Horspool和Sunday。(关键)
1:Horspool算法过程:简单的力量
Horspool算法的思路非常简单。它是对BM算法的一个简化。在BM中,作者使用了两种启发性规则即:坏字符规则和好后缀规则。Horspool认为,在某个字符匹配失败的情况下,挑选最后一个字符应用坏字符规则总是能够产生最大的跳跃距离。
过程阐述:
Horspool算法从右向左对字符匹配,如果最后一个字符相同,则匹配下一个字符,直到所有字符相同或者某一个字符不同;无论匹配成功与否,都根据最后一个字符进行在模式串中出现的位置进行移动。
如图:
所以Horspool算法只设计了一个shift算法来计算匹配失败的时候移动距离。
根据模式串,初始化一个数组。数组中保存的是该字符距离末位的距离。
之后从后向前开始匹配,匹配失败则从数组中取出对应移动距离
2:Horspool代码实现
public static int horspool(String target,String pattern){ //预处理 int skip []= precessChars(pattern); // int lengthMinusOne = pattern.length()-1; int i,j,k; for(k = lengthMinusOne;k<target.length();k+=skip[target.charAt(k)]){ //j>=0&&target.charAt(i)==pattern.charAt(j) 顺序不能改变 否则报数组越界 for(i=k,j=lengthMinusOne;j>=0&&target.charAt(i)==pattern.charAt(j);--j,--i){ //空 } if(j == -1){ return i+1; } } return -1; } private static int[] precessChars(String pattern){ final int count = 256; int [] skip = new int[count]; for(int j=0;j<count;j++){ skip[j] = pattern.length(); } //遍历到pattern.length()-1 不包含最后一个字符 for(int i =0;i<pattern.length()-1;i++){ char c = pattern.charAt(i); skip[c]=pattern.length()-1-i; } return skip; }
3:Sunday算法
其实Sunday算法也是BM算法的一个简化,和Horspool很是相像。差别在于当匹配失败的时候,Sunday算法选取的是最后一个字符的下一个字符进行匹配。但是Sunday算法并不要求匹配的时候从前到后或者是从后到前,甚至可以从中间开始匹配。
4:Sunday代码实现
//从后向前 public static int sunday_back(String target,String pattern){ //预处理 int skip []= precessChars(pattern); // int length = pattern.length(); int i,j,k; for(k = length;k<=target.length();k+=skip[target.charAt(k)]){ for(i=k-1,j=length-1;j>=0&&target.charAt(i)==pattern.charAt(j);--j,--i){ //空 } if(j == -1){ return i+1; } } return -1; } //从前向后 public static int sunday_forward(String target,String pattern){ //预处理 int skip []= precessChars(pattern); // int length = pattern.length(); int i,j,k; for(k = length;k<=target.length();k+=skip[target.charAt(k)]){ for(i=k-length,j=0;j<length&&target.charAt(i)==pattern.charAt(j);j++,i++){ //空 } if(j == length){ return k-length; } } return -1; } //预处理数组 private static int[] precessChars(String pattern){ final int count = 256; int [] skip = new int[count]; for(int j=0;j<count;j++){ skip[j] = pattern.length(); } //遍历到pattern.length()-1 不包含最后一个字符 for(int i =0;i<pattern.length()-1;i++){ char c = pattern.charAt(i); skip[c]=pattern.length()-i; } return skip; }
关于Sunday和Horspool算法,两者到底有多少差别,其实很难做出比较。一般来讲,Sunday算法能带来更大的平均移动距离。但是至于谁更快一些,可能涉及到内存引用次数等问题,需要大量的实验。
5:重新审视BF、KMP、BM、Horspool和Sunday。
当匹配失败的时候,到底怎么样才能跳跃式前进的距离最远呢?其实经过对Horspool和Sunday的分析,会得到一些启发。
Horspool中取当前字符中最后一个进行移位;Sunday算法选择最后一个字符的后一个进行移位。
启示1:既然Sunday选取最后一个的下一位,平均移位距离有所增加,何不选择最后一个的下两位呢?
启示2:何不综合Sunday和Horspool算法,将每次移位前取两者进行比较后更大者移动呢?
对于启示1,可以这样考虑,如果能够无限制的选取下一位,如果目标串中有个模式串中没有的字符X,岂不是就可以直接跳过X了?
对于启示2,实际上也是BF、KMP、和BM算法的差异所在之处。
通过上图比较,我们可以看出,如果综合Sunday算法和Horspool算法来考虑,效率不一定高,因为每次都将两者数组取出来的值比较一次,还不如就按照其中一个算法进行,这个时间内可能已经又向前迈进了一大步。
其实总和Sunday和Horspool的想法并没有错,我们最好的情况下就是将每个字符要移动的情况下都计算出来,取最大的(有点贪婪),但是就是在你根据不同字符计算需要移动的位置的时候,已经花费的大把大把的时间,可能Sunday算法已经执行完毕。所以我们要做的是在最少的时间内将获得的信息发挥最大的价值。
于是BF是怎么做的,简单的根据第一个字符进行移动;而KMP是根据已经匹配的字符的最大前缀(和该最大前缀相同的后缀是最靠近匹配失败的字符的)移动,如果符合KMP要求的后缀是多个字符,实际上相当于我们的启示2,比较了多个字符取其大,这个时候利用了预处理数组next,可以在o(1)时间内完成,是很有效果的。KMP实际可以稍微改动一下,并不利用已经匹配的字符,只是根据匹配失败的字符移动,相信效率会有所提升。再到后来的BM算法,终于发现了后缀匹配,但是BM算法还只是在利用坏字符规则的时候是根据匹配失败字符移动,好后缀规则实则起不到太大的作用,只是一个配角。然后Horspool彻底的摒弃了好后缀规则,就像我们曾经根据启示2试图总和Sunday和Horspool一样,Horspool没有这样做,而是选取了好后缀规则和坏字符规则中的一个即坏字符规则,这样做思路反而变得简单,收到的效果也还比BM好很多。而至于Sunday算法,做的更绝,直接选择最后一个字符的下一个字符,这个是能够选得最后一个字符了。用图片表示:
其实大量的信息都是在自己画的图上,能够半理性的展示这些算法的思想。
相关推荐
使用Boyer-Moore-Horspool-Sunday 算法进行字符串匹配的系列函数
字符串匹配算法之Horspool算法(英文原版)
算法设计 horspool算法 最优 最差输入算法设计 horspool算法 最优 最差输入算法设计 horspool算法 最优 最差输入算法设计 horspool算法 最优 最差输入算法设计 horspool算法 最优 最差输入算法设计 horspool算法 ...
Boyer–Moore–Horspool Boyer–Moore–Horspool algorithmalgorithmBoyer–Moore–Horspool algorithmBoyer–Moore–HorspooBoyer–Moore–Horspool algorithml algorithm
字符串匹配 DNA序列题目 利用Horspool算法实现 最块匹配方案
单模式匹配Horspool algorithm
用C++实现字符串模式匹配算法中的horspool算法
里面有三个实例,第三个例子是采用自己手动输入的方式,是Horspool算法不可多得的学习实例,欢迎大家分享。
此资源属于算法分析课程的实验,只供学习使用。本人很少上CSDN,有兴趣,有需要的话可以发E-MAIL:hzz865@21cn.com
Horsepool算法是Boyer-Moore算法的简化版本,这也是一个空间换时间的典型...算法把模式P和文本T的开头字符对齐,从模式的最后一个字符开始比较,如果尝试比较失败了,它把模式向后移。每次尝试过程中比较是从右到左的。
C#实现horspool匹配算法C# 不过注解不详细 ,希望可以帮到在学习算法的同学们
usage:四种字符串匹配算法的实现(Sunday、KMP、Boyer-Moore、horspool)的测试 各文件说明: search_string.h 头文件,包含了对各个函数的声明; search_string.c 包含了头文件中所有函数的具体实现; search_...
使Naive和Boyer Moore Horspool可视化,以帮助您了解这些算法的工作方式以及它们之间的比较方式。 目标 字符串匹配问题的目的是找到单词中所有出现的单词。 天真的算法 使用两个嵌套循环搜索文本。 外循环遍历所有...
各种字符串匹配方法的总结,通俗易懂,五脏俱全
streamsearch是的模块,它允许使用Boyer-Moore-Horspool算法搜索流。 该模块主要基于的Hongli Lai的Streaming Boyer-Moore-Horspool C ++实现。 要求 -v0.8.0或更高版本 安装 npm install streamsearch 例子 var...
主要介绍了PHP实现的字符串匹配算法,简单描述了sunday算法的概念与原理,并结合实例形式分析了php基于sunday算法实现字符串匹配操作相关技巧,需要的朋友可以参考下
Horspool扩展算法及其在方块苗文模式匹配中的应用
Boyer-Moore-Horspool Wordsearch饼干
C++ 实现模式匹配算法 通过手动输入母串和子串,返回匹配成功的第一个字符位置
排序:归并排序,希尔排序,快速排序,堆排序 匹配:KMP,BM,Sunday,KR,Horspool 查找:二分查找