精华内容
下载资源
问答
  • Sunday

    2019-10-24 09:46:35
    Sunday
  • 在分析几种经典模式匹配算法的基础上,对当前应用最广泛的Sunday算法提出了改进的算法Zhusunday.算法主要改进之处是:在字符串从右向左匹配过程中,当文本字符中出现不匹配模式字符串的字符且该文本字符不是坏字符时,...
  • Sunday算法

    2019-10-17 15:53:27
    Sunday算法的思想跟BM算法很相似,不过Sunday采用模式匹配的思想,在匹配失败的时候关注的是主串中参加匹配的最末尾字符的下一位字符。 平均性能的时间复杂度为O(n) 最差情况的时间复杂度为O(n * m) #include<...

    Sunday算法的思想跟BM算法很相似,不过Sunday采用模式匹配的思想,在匹配失败的时候关注的是主串中参加匹配的最末尾字符的下一位字符。

    平均性能的时间复杂度为O(n)
    最差情况的时间复杂度为O(n * m)

    #include<bits/stdc++.h>
    
    using namespace std;
    
    int main(void)
    {
    	string source = "Hello world,hello china,hello beijing", part = "china";
    	int index = 0, i = 0, j = 0, next = 0;//index 主要用来记录每一次的匹配位置 i 每一次新的循环起始位置 j用来记录子串的遍历位置,next记录下一个起始位置
    	while (i < source.length())
    	{
    		next = i + part.length();
    		index = i;
    		j = 0;
    		if (part[j] != source[index])
    		{
    			//重新计算i的下一个位置
    			if (next < source.length())
    			{
    				int cut = 0;
    				for (int z = 0; z < part.length(); z++)if (source[next] == part[z])cut = z;
    				if (cut == 0 && source[next] != part[0])next++;
    				else next -= cut;
    			}
    			i = next;
    			continue;
    		}
    		else
    		{
    			while (j < part.length())
    			{
    				if (part[j] != source[index])
    				{
    					//重新计算i的下一个位置
    					if (next < source.length())
    					{
    						int cut = 0;
    						for (int z = 0; z < part.length(); z++)if (source[next] == part[z])cut = z;
    						if (cut == 0 && source[next] != part[0])next++;
    						else next -= cut;
    					}
    					i = next;
    					break;
    				}
    				index++;
    				j++;
    			}
    			if (j == part.length())break;
    		}
    	}
    	if (j == part.length())cout << "找到了,位置是: " << index - j;
    	else cout << "没找到";
    }
    

    匹配原理:
    从前往后匹配:

    • 如果遇到不匹配情况判断母串 S参与匹配的最后一位的下一位字符,如果该字符出现在模板串 T 中,选择最右出现的位置进行对齐;
    • 否则直接跳过该匹配区域。

    例子

    S:substring searching
    T:search

    步骤1:
    在这里插入图片描述
    第二个字符u!=e,则直接跳到末尾i处,判断i是否存在于模式串T中

    步骤2:
    此时发现i不存在于模式串T中,后移一位,继续判断。
    在这里插入图片描述

    此时n!=s,则直接跳到末尾处,判断r是否存在于模式串T中

    步骤3:
    发现模式串T中存在r,则直接对其。
    在这里插入图片描述

    展开全文
  • KMP、BM、Sunday、Horspool、strstr字符串匹配算法的性能比较 一、简介 简介:字符串匹配算法,顾名思义,在一个给定的字符文本内搜寻出自己想要找的一个字符串,平常所用的各种文本编辑器里的ctrl+F大多就是使用的...

    KMP、BM、Sunday、Horspool、strstr字符串匹配算法的性能比较

    一、简介

    简介:字符串匹配算法,顾名思义,在一个给定的字符文本内搜寻出自己想要找的一个字符串,平常所用的各种文本编辑器里的ctrl+F大多就是使用的这些字符匹配算法。本文通过用c语言实现4种比较受欢迎的字符匹配算法,在同一文本下搜寻同一关键字符串,用来和c库函数strstr作时间上的性能比较,同时也对实现的4种算法做对应比较。各个算法名称如下:(对各个算法详细原理感兴趣的伙伴自行去查询,下面只做简要介绍,文中的T都代表文本串,即要搜索的范围,P代表要搜索的目标串,红色代表失配,黄色代表一些P串和T串中相同的字符)

    1、strstr():c语言的库函数

    函数原型:char* strstr(char* str1,char* str2);//包含在<string.h>中

    原理简述:暴力匹配,从左到右依次匹配。

    文本串T

    A

    B

    C

    F

    D

    L

    K

           

    模式串P

    K

    L

    F

    C

    F

             

    第一次移动

    K

    L

    F

    C

    F

            

    第二次移动

    K

    L

    F

    C

    F

           

    2、KMP(Knuth-Morris-Pratt)算法:

    原理简述:KMP相对strstr做了一些改进,它和strstr一样,都是从左到右依次匹配,当出现失配时,比如,文本串T是“ABCGHABDHKLOEM,”,模式串P是“ABCGHABCF”,当匹配到第八个字符“C”时失配,因为第一、二字符是“AB”,与当前失配字符“C”(第八个)的前两个字符刚好是一样的,于是将整个P串向右移动5个位置,使得第一、二个字符“AB”与文本串T中的"AB"相对,然后继续从P串的第三个字符“C”往后匹配(注意,与当前失配字符的前1个以上字符相等的字符必须是从P串第一个字符开始的,否则不算是满足规则,当不存在时,与strstr一样,只往前移动一个位置)。

    文本串T

    A

    B

    C

    G

    H

    A

    B

    D

    H

    K

    L

    O

    E

    M

     

    模式串P

    A

    B

    C

    G

    H

    A

    B

    C

    F

          

    第一次移动

    开头有相同前缀,

    A

    B

    C

    G

    H

    A

    B

    C

    F

     

    第二次移动

    开头无相同前缀

    A

    B

    C

    G

    H

    A

    B

    C

    F

    实现代码如下:

    /*
    function:KMP的next数组求解(预处理)
    Param:
    @p 需要匹配的字符串
    @next 需要匹配的字符串对应的next数组
    */
    void KMPPre(char* p, int KMP_next[])
    {
        int pLen=strlen(p);
        KMP_next[0]=-1;
        int k=-1;
        int j=0;
        while(j<pLen-1){
            //p[k]表示前缀,p[j]表示后缀  
            if(k==-1||p[j]==p[k]){
                ++j;
                ++k;
                if(p[j]!=p[k])
                    KMP_next[j]=k;
                else if(KMP_next[k]!=-1)//若是k是0的话,它的next[0]是-1,
                    KMP_next[j]=KMP_next[k];
                else
                    KMP_next[j]=0;
            }
            else{
                k=KMP_next[k];
            }
        }
    }
    /*
    function:
    		KMP字符匹配算法
    Param:
    @s 文本内容
    @sLen 文本内容长度
    @p 需要匹配的字符串
    @pLen 需要匹配的字符串长度
    @next[] 辅助数组
    */
    char* KmpSearch(char* s,int sLen,char* p,int pLen,int next[])
    {
    	int i=0;
    	int j=0;
    	while(i<sLen&&j<pLen){
    		//①如果j=-1(代表又回到了P串的开头第一个字符,因为next[0]=-1),或者当前字符匹配成功(即S[i]==P[j]),都令i++,j++    
    		if(j==-1||s[i]==p[j]){
    			i++;
    			j++;
    		}
    		else{
    			//②如果j!=-1,且当前字符匹配失败,则令i不变(当前s串失配的地方),j=next[j]    
    			//next[j]即为j所对应的next值(其实就是和它含有相同前缀的地方,比如P为"AFHKAFOIU",则next[6]=2,即第7个字符“O”的前两个字符"AF"(第五、六个字符)有相同前缀"AF"(第一、二个字符))
    			j=next[j];
    		}
    	}
    	if(j==pLen){
    		return &s[i-j];
    	}
    	else{
    		return NULL;
    	}
    }

    总结:原理不难理解,但是我们也发现了,KMP的匹配规则是和模式串P的内容有关系的,特别是对那种有大量重复字符的字符串有很大帮助,基于这个匹配规则,每次匹配一个模式串P时,都要相应生成一个辅助数组(人们都习惯成为next数组),这个数组记录着与模式串P中每个字符失配时需要移动的位置数有关的值。具体计算在此不做详细介绍,需要了解的伙伴自行查询。所有的实现代码在上面已给出。

    3、BM(Boyer-Moore)算法:

    原理简述:BM算法有两个匹配规则,一个是坏字符规则,另一个是好后缀规则。匹配顺序是从右向左(即从模式串p的最后一个字符开始匹配,然后依次向左匹配)。

    (1)、坏字符规则:当失配时,若模式串p中当前失配字符的左半部分存在文本串T当前失配字符时,则将模式串整体向右移动,使两个串的相等字符对应匹配,然后又开始从右向左匹配,若模式串p中存在多个该字符时,使用最靠右的一个字符。

    如下表a,从右向左匹配,即从P串的最后一个字符"D"开始匹配,由于P串的"D"和T串的"F"不相等,故在P串中找"F",刚好P中有"F",取最靠右的字符"F",所以P串整体向右移动两个位置,使得P中的"F"和T中的"F"对上,然后又从最后一个字符开始匹配。

    a、当失配字符在P串的最右端时

    文本串T

    A

    B

    C

    F

    O

    U

    P

    K

    M

    模式串P

    F

    F

    C

    D

     

     

     

     

     

    移动后

    F

    F

    C

    D

       

    b、当失配字符在P串的中部位置时,

    文本串T

    A

    B

    C

    F

    O

    U

    P

    K

    M

    模式串P

    F

    D

    F

     

     

     

     

     

    移动后

    C

    F

    D

    F

       

    c、若失配时,不存在相同字符,则P串向右移动strlen(P)个位置。

    文本串T

    A

    B

    C

    F

    O

    U

    P

    K

    M

    模式串P

    A

    L

    C

    D

     

     

     

     

     

    移动后

      

    A

    L

    C

    D

     

    实现代码如下:

    /*
    function:求解坏字符数组
    Param:
    @pattern 需要匹配的字符串
    @bmBc 坏字符数组
    @m 需要匹配的字符串长度
    @
    */
    void PreBmBc(char *pattern,int m,int bmBc[])
    {
        int i;
        for(i=0;i<256;i++){//一个字符占八位,共256个字符,把所有字符都覆盖到,这里的初始化是将所有字符失配时的移动距离都赋值为m
            bmBc[i]=m;
        }
        for(i=0;i<m-1;i++){//针对模式串pattern中存在的每一个字符,计算出它们最靠右的(非最后一个字符)地方距离串末尾的距离,即它们失配时该移动的距离,这一操作更新了初始化中一些字符的移动距离
            bmBc[pattern[i]]=m-1-i;
        }
    }

    (2)、好后缀规则:当已经有部分字符匹配通过,然后遇到失配时,处理方法将会有变化。

    若P串中当前失配位置的左半部分(前缀)存在与右半部分相等的子串(即以当前失配字符为边界的右半后缀)或者后缀的子串时,P串将整体向右移动,使得最靠右的该子串(可能存在多个)和T串的相应子串相对,然后重新从最右的字符开始匹配。若左半前缀不存与后缀相同的字符串或者后缀的子串时,P串整体向右移动strlen(P)个位置。(注:若只存在子串时必须是从最左第一个字符往后才算是后缀的子串,如AFCDAF中,第一、二个字符“AF”算是以C为分界的后缀“DAF”的子串,但是对于KAFCDAF来说,同样以C为边界时,前缀中不存在后缀DAF的子串,第二、三个字符AF并不算它的子串,因为第一个字符K和D都不相等了,自然和T串中的已经匹配的“D”也不等,故不用做多余的比较操作了,应该直接跳过)。

    a、存在与后缀相同的前缀时;(可在最左)

    文本串T

    A

    B

    C

    F

    A

    F

    P

    K

    M

    O

    L

    模式串P

    A

    F

    C

    D

    A

    F

     

     

     

     

     

    “F”!=”D”,执行移动,按前缀往前移动

    文本串T

    A

    B

    C

    F

    A

    F

    P

    K

    M

    O

    L

    模式串P

     

     

     

     

    A

    F

    C

    D

    A

    F

     

    存在与后缀相同的前缀时;(也可不在最左)

    文本串T

    K

    A

    B

    C

    F

    A

    F

    P

    K

    M

    O

    L

    模式串P

    A

    A

    F

    C

    D

    A

    F

     

     

     

     

     

    “F”!=”D”,执行移动,按前缀往前移动

    文本串T

    K

    A

    B

    C

    F

    A

    F

    P

    K

    M

    O

    L

    模式串P

     

     

     

     

    A

    A

    F

    C

    D

    A

    F

     

    b、存在与后缀子串相同的前缀时;(下表中P串以"D"为边界,后缀为"FAF","AF"属于子串,必须从最左开始)

    文本串T

    A

    B

    C

    F

    A

    F

    P

    K

    M

    O

    L

    模式串P

    A

    F

    D

    F

    A

    F

     

     

     

     

     

    “C”!=”D”,执行移动,按前缀(后缀子串)往前移动

    文本串T

    A

    B

    C

    F

    A

    F

    P

    K

    M

    O

    L

    模式串P

     

     

     

     

    A

    F

    D

    F

    A

    F

     

    c、与后缀子串相同的前缀为啥要在最左;

    文本串T

    A

    B

    C

    F

    D

    A

    F

    K

    M

    O

    L

    模式串P

    K

    A

    F

    C

    D

    A

     F

     

     

     

     

    若是我们将KAF中的AF移到相应位置时,K和D注定不相等,那又何必多余比较

    文本串T

    A

    B

    C

    F

    D

    A

    F

    K

    M

    O

    L

    模式串P

     

     

     

     

    K

    A

    F

    C

    D

    A

     F

    代码如下:

    /*
    function:好后缀辅助数组(好后缀长度)求解前的预处理操作,即求出模式串中各个字符失配时相应的相同前缀长度
    Param:
    @pattern 需要匹配的字符串
    @suff 好后缀辅助数组的相同前缀长度数组
    @m 需要匹配的字符串长度
    */
    void suffix(char *pattern,int m,int suff[]) {
       int f, g, i;
       suff[m-1]=m;
       g=m-1;
       for(i=m-2;i>=0;--i){
          if(i>g&&suff[i+m-1-f]<i-g)
             suff[i]=suff[i+m-1-f];
          else {
             if(i< g)
                g=i;
             f=i;
             while(g>=0&&pattern[g]==pattern[g+m-1-f])
                --g;
             suff[i]=f-g;
          }
       }
    }
    /*
    function:好后缀数组求解方法
    Param:
    @pattern 需要匹配的字符串
    @bmGs 好后缀数组
    @m 需要匹配的字符串长度
    */
    void PreBmGs(char *pattern,int m,int bmGs[])
    {
        int i, j;
        int suff[maxNum];  
        // 计算后缀数组
        suffix(pattern,m,suff);//看上一个函数
        // 先全部赋值为m,初始化
        for(i=0;i<m;i++){
            bmGs[i]=m;
        }
        // 当只存在后缀的相同子串时,如"ASDKGJOELHKSD"在"L"处失配时,第二、三个字符"SD"就是就是"L"的后缀"HKSD"的相同子串,子串必须是从第一个字符开始的
        j=0;
        for(i=m-1;i>=0;i--){
            if(suff[i]==i+1){
                for(;j<m-1-i;j++){
                    if(bmGs[j]==m)
                        bmGs[j]=m-1-i;
                }
            }
        }
        //当存在后缀的相同前缀时,如"HKSDKGJOELHKSD"在"L"处失配时,
        //第一、二、三、四个字符"HKSD"就是就是"L"的后缀"HKSD"的相同前缀,
        //相同前缀可以不从第一个字符开始,如"MHKSDKGJOELHKSD"在"L"处失配时,第二、三、四、五个字符"HKSD"就是就是"L"的后缀"HKSD"的相同前缀,
        for(i=0;i<=m-2;i++){
            bmGs[m-1-suff[i]]=m-1-i;
        }
    }

    最终的匹配函数如下:

    /*
    function:Boyer-Moore字符匹配算法
    Param:
    @text 文本内容
    @Tlen 文本内容长度
    @pattern 需要匹配的字符串
    @Plen 需要匹配的字符串长度
    */
    char* BoyerMoore(char *text,int Tlen ,char *pattern,int Plen,int bmBc[],int bmGs[])
    {
        int i,pos;
        pos=0;
        while(pos<=Tlen-Plen){
            for(i=Plen-1;i>=0&&pattern[i]==text[i+pos];i--);
            if(i < 0){
                return &text[pos];
            }
            else{
                pos+=MAX(bmBc[text[i+pos]]-Plen+1+i,bmGs[i]);//MAX为求两个数中最大的一个,使用了宏定义#define MAX(x, y) (x)>(y) ? (x):(y)
            }
        }
        return NULL;
    }

    总结:坏字符规则和好后缀规则是独立计算的,最后P串具体按那个规则走,是通过对比两个规则计算出来需要往后移动的位置数的大小,取其中最大的。从原理可看出,BM每次匹配前也需要做预处理,需要针对模式串P分别生成一个坏字符辅助数组和好后缀辅助数组,它们分别存放着各自规则下模式串P的字符发生失配时,需要相应地向右移动的位置数,在此也不做介绍。实现代码如上。

    4、Sunday算法:

    原理简述:Sunday的处理方式与BM不同的是,它只关注文本串T中当前与模式串P最后一个字符相对应的字符的下一个字符(我说的清楚了吗?),直接上图吧。sunday只关心下图标绿色的“L”。当P串和T串匹配过程中出现失配时,若在P串中当前的失配字符"K"的左半部分(无)不存在T中当前与模式串P最后一个字符"F"相对应的字符"D"的下一个字符"L"时,P串整体向右移动strlen(p)+1个位置。(匹配时从左向右依次匹配)

    a、不存在时,整体向右移动strlen(p)+1;

    文本串T

    A

    B

    C

    F

    D

    L

    K

    H

    R

    J

    K

    模式串P

    K

    A

    F

    C

    F

     

     

        

    移动后

    K

    A

    F

    C

    F

    b、当存在时,则和BM的坏字符规则一样,将P串右移使得P串中最右的“L”和T中的“L”相对。

    文本串T

    A

    B

    C

    F

    D

    L

    K

    H

    R

    J

    K

       

    模式串P

    K

    L

    F

    C

    F

             

    移动后

    K

    L

    F

    C

    F

         

    代码如下:

    /*
    function:Sunday字符匹配算法预处理
    Param:
    @sun_shift 最终存放每个字符失配时该右移的距离
    @p 需要匹配的字符串
    @lenP 需要匹配的字符串长度
    */
    void SundayPre(int sun_shift[],char* P,int lenP)
    {
        int i;
        for(i=0;i<maxNum;i++){
           sun_shift[i]=lenP+1;
        }
        for(i=0;i<lenP;i++){
            sun_shift[P[i]]=lenP-i;
        }
    }
    
    /*
    function:Sunday字符匹配算法
    Param:
    @T 文本内容
    @lenT文本内容长度
    @p 需要匹配的字符串
    @lenP 需要匹配的字符串长度
    @sun_shift 最终存放每个字符失配时该右移的距离
    */
    char* Sunday(char* T,int lenT,char* P,int lenP,int shift[]){
    	int i;
        int pos=0;
        int j;
        while(pos<=lenT-lenP) {
            j=0;
            while(T[pos+j]==P[j]&&j<lenP) j++;
            if(j>=lenP){
                return &T[pos];//匹配成功,返回地址
            }
            else{
    
    			pos+=shift[T[pos+lenP]];
    		}
        }
        return NULL;
    }
    

    总结:sunday匹配前也需要做一个预处理,生成一个辅助数组,它也是存放着,当发生失配时,模式串P需要向右移动的位置数。

    5、Horspool算法:

    原理简述:Horspool也是一种改进匹配的算法,它的匹配规则有点像BM的坏字符规则,但是却也不一样,BM的坏字符规则关注当前失配的字符(失配字符可能是在最后一个,也有可能是在中间,也可能在开头),然而当发生失配时,Horspool都只关注T串中与P串最后一个字符相对应的字符(匹配时从右向左依次匹配),如图:

    a、失配时(最后一个字符失配),只关注最后一个字符;

    文本串T

    A

    B

    C

    F

    A

    F

    P

    K

    M

    O

    L

    模式串P

    A

    F

    C

    D

    A

    C

     

     

     

     

     

    “F”!=”C”,执行移动、P前半部分存在T当前的最后一个字符“F”

    文本串T

    A

    B

    C

    F

    A

    F

    P

    K

    M

    O

    L

    模式串P

     

     

     

     

    A

    F

    C

    D

    A

    C

     

    b、失配时(中间字符失配),只关注最后一个字符;

    文本串T

    A

    B

    C

    E

    A

    F

    P

    K

    M

    O

    L

    模式串P

    E

    F

    C

    D

    A

    F

     

     

     

     

     

    “D”!=”E”,执行移动、P前半部分存在T当前的最后一个字符“F”

    文本串T

    A

    B

    C

    E

    A

    F

    P

    K

    M

    O

    L

    模式串P

     

     

     

     

    E

    F

    C

    D

    A

    C

     

    代码如下:

    /*
    function:horspool字符匹配算预处理
    Param:
    @P 需要匹配的字符串
    @lenP 需要匹配的字符串长度
    */
    void horspoolPre(int hors_d[],char* P,int lenP)
    {
        int i;
        for(i=0;i<maxNum;i++){
            hors_d[i]=lenP;
        }
        for(i=0;i<(lenP-1);i++){
            hors_d[P[i]]=lenP-i-1;
        }
    }
    /*
    function:horspool字符匹配算法
    Param:
    @T 文本内容
    @lenT 文本内容长度
    @P 需要匹配的字符串
    @lenP 需要匹配的字符串长度
    @hors_d[] 辅助数组
    */
    char* horspool(char *T, int lenT, char *P, int lenP,int hors_d[])  
    {  
        int i,pos,j; 
        pos=0;  
        while(pos<=(lenT-lenP)){  
            j=lenP-1;  
            while(j>=0&&T[pos+j]==P[j]) j--;  
            if(j==-1){
                return &T[pos];
    		}			 
            else{  
                pos+=hors_d[T[pos+lenP-1]];
    		}
        }  
        return NULL;  
    }

    总结:很明显,Horspool也需要一个预处理操作,需要一个辅助数组。

    二、测试

    1、测试准备工作:

    运行环境:

                系统:centos6.4

               语言:Linux c

    (1)、构建一个稍微大一点的文本串,本测试构造的文本串如下图(在程序中赋值给char*型变量,下图是用双引号将文本串用多行显示);

     

    (2)、选一个关键字符串,本测试选了“MY_TEST_string”作为要匹配的关键字符串;

    (3)、 4种自己实现的算法在匹配前都需要一些预处理工作,本文比较中不将这些预处理时间计入运行时间;

    2、测试开始:

    测试的关键代码如下:(其余四种算法也是相同的处理方式,感兴趣的看官可到GitHub上下载完整代码,https://github.com/scu-igroup/string_match

           ///KmpSearch///
    		gettimeofday(&start,NULL);//起始时间
    		for(i=0;i<times;i++){//为运行次数
    			if(i==0){
    				temp[0]=KmpSearch(My_TXT,len_txt,pattern,lenp,KMP_next);//返回结果,可用来验证是否真的找到了模式串pattern所在位置
    			}
    			else
    				KmpSearch(My_TXT,len_txt,pattern,lenp,KMP_next);//循环调用
    		}
    		gettimeofday(&end,NULL);//结束时间
    		dif_sec=end.tv_sec-start.tv_sec;//相差的秒数
    		dif_usec=end.tv_usec-start.tv_usec;//相差的微秒数
    		printf("KMP running time  is %ld 秒 (%ld 微秒)\n",dif_sec, dif_sec*1000000+dif_usec);//最终时间换算,欲知详情请自行查询结构体struct timeval

    (1)、将关键字符串放文本串开头,然后测试各个算法程序匹配所花时间:

    总结:结果很明显,当我们要匹配的字符串在文本串开头时,strstr()远远落后于其他四种算法,而sunday与horspool优于BM、KMP,BM匹配速度相当于KMP的三倍。

    (2)、将关键字符串放文本串中间位置,然后测试各个算法程序匹配所花时间:

    总结:当我们将匹配的字符串放在文本串中部时,sunday继续保持着优势,horspool也仍然优于BM、KMP,除开让人很惊讶的KMP,strstr相对于其他三种算法来说仍然是垫底(讲道理,KMP不应该表现得如此菜,它应该比strstr快速才对。所以可能是本人的实现代码有问题,在上面已给出实现代码,供各位看官找找错,我实在是汗颜,未能发现问题)。

    (3)将关键字符串放文本串末尾,然后测试各个算法程序匹配所花时间:

    总结:当我们要匹配的字符串在文本串尾部时,sunday依然一路在秀,可谓是“一枝独秀”,依然完胜其余四种算法。horspool显然被strstr毙掉了,不过它仍然压着BM和KMP。差点让我掉下下巴的KMP,再次成功让我怀疑自己的实现代码有严重的BUG。strstr这次反而“翻身”做老二了,又让小伙伴惊呆了(这时应该有很多看官开始嘲笑了,“Are you fucking kidding me!!!!!”,BM、KMP、Horspool怎么会比strstr慢呢?,这也是我疑惑的地方。。。)

    三、总结

    从测试结果来看,五种算法中,只有sunday没让我们失望,在三种情境下依然保持着自己的强势匹配速度,而Horspool也不差,一直都领先于BM和KMP。strstr是很多人都在用的函数,毕竟c把它封装好了,用起来方便,它的表现还是相对可以的,毕竟它是暴力匹配,总要多花时间。最让人想不通的就是KMP的表现了,从原理上来说,最次也是和strstr一样(本文测试都把KMP的nxet数组求解过程在预处理阶段给单独处理了,不计入运行时间),毕竟它每一次匹配的跳跃是大于等于1的,而strstr每次都只移动一位。当匹配串在文本串尾部时,BM也没有比strstr快,这也是很出人意外。

    四、不足之处

    1、样本串的选择没有尽可能覆盖多种情景;

    2、strstr是c语言的库函数,它的实现方式应该经过了开发者无数次推敲优化,而自己实现的另外四种算法可能不够优化,多了一些冗余计算,导致没把算法优势最大化,因为strstr是系统内部函数,运行多次可能也会有自动优化;

    3、测试方式不够全面,得出的结论有些偏差,仅供大家做参考;

    所有完整代码请移步到:https://github.com/scu-igroup/string_match

     

    展开全文
  • 1.Sunday算法关键思想 通过解析传统Sunday算法我发现它实现跳转的关键思想在于第二步,我们深入解析下第二步的原理: we should working hard work h为什么要和work中的元素逐个比较?我们可以这样理解: 1) 当h和w...

    优化算法思路:

    1.Sunday算法关键思想
    通过解析传统Sunday算法我发现它实现跳转的关键思想在于第二步,我们深入解析下第二步的原理:

    we should working hard
    work

    h为什么要和work中的元素逐个比较?我们可以这样理解:
    1) 当h和w比较时,我们可以确定houl和work是否可能匹配
    2) 当h和o比较时,我们可以确定shou和work是否可能匹配
    3) 当h和r比较时,我们可以确定 sho和work是否可能匹配
    4) 当h和k比较时,我们可以确定e sh和work是否可能匹配
    也就是说,这次比较我们可以确定e shoul和work的关系。
    we should working hard
    work

    那么我们的优化策略就有了:
    当h和work经过比较后发现h不在work中,我们可以直接跳过oul,用d来重复h的操作,以此类推,直到找到匹配项。

    改进后的Sunday算法:

    我们假设有一个字符串A长度为n 一个字符串B长度为m
    我们使用Sunday算法在A中查找是否存在B

    我们假设每次比较的时间为1,本文的复杂度分析主要是最坏复杂度分析

    1) 将A,B首字母对齐

    2) 查看B最后一个字符对应的A的位置(初始为m)上的字符是否在B中存在m次比较

    3) 若存在,则将B中对应位置与其对齐后倒序比较,若全部相等则找到目标,否则执行步骤4 m-1次比较

    4) 若不存在则将检查m+m位置上的字符是否在B中存在。m次比较

    图示过程:

    w	e		s	h	o	u	l	d		w	o	r	k	i	n	g		h	a	r	d
    w	o	r	k							
    

    1)首先查看s是否在work中存在,结果为不存在,跳过4位到l上
    2)检查l在work中是否存在,结果为不存在,跳过4位到o上
    3)检查o在work中是否存在,发现存在,则将两个串中的o对齐得到下面的:

    w	e		s	h	o	u	l	d		w	o	r	k	i	n	g		h	a	r	d
    										w	o	r	k								
    

    4)检查它们相对应的串是否匹配,结果发现匹配,得到结果,配对完毕。

    复杂度分析
    我们拿传统Sunday算法的最坏复杂度情况进行计算:

    类似下面情况的查找的复杂度最坏:
    wordkkkkkkkkkkkkkkkkkkk
    work

    通过计算这样的复杂度为:
    O(n,m)=(2m-1)n/m
    化简后就是:O(n,m)=2
    n-n/m
    我们知道当n远大于m的时候,其时间复杂度可以近似看成:O(n)=n

    这与传统的Sunday相比近似快了一倍。

    代码实现

    public int Sunday(String haystack, String needle) {
            int hayLen = haystack.length();//主串长度
            int nLen = needle.length();//子串长度
            int i=nLen-1;
            int l=0;
            int j=0;
    
            if(hayLen>nLen)
            {
                while(i<hayLen) {
                    l=i;
                    for (j=nLen-1;j>=0;j--)
                    {
                        if (needle.charAt(j)==haystack.charAt(i)) {
                            i += nLen - 1 - j;
                            if (i < hayLen){
                                for (int n = nLen - 1; n >= 0; n--) {
                                    if (needle.charAt(n) != haystack.charAt(i--)) {
                                        break;
                                    } else if (n == 0) {
                                        return i + 1;
                                    }
                                }
                            i = l;
                            break;
                           }
                            else{
                                return -1;
                            }
                        }
                    }
                    i+=nLen;
                    continue;
                    }
                return -1;
            }
            else{
                System.out.println("后者比前者长,不能进行查找操作");
                return -1;
            }
    
    }
    

    实现代码也少了许多,更简洁。

    测试比较
    针对上面两种算法我选取了一个下面的测试方法:
    1.最坏情况测试:

    public static void main(String[] args) {
            String a="wordkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk" +
                    "kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk" +
                    "kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk" +
                    "kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk" +
                    "kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk" +
                    "kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk" +
                    "kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk" +
                   "kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkwork";
            String b="work";
            BetterSunday01 find=new BetterSunday01();
            long startTime = System.currentTimeMillis();    //获取开始时间
            int i=0;
            for(int j=0;j<1000000;j++) {
                i = find.Sunday(a, b);
            }
            long endTime = System.currentTimeMillis();    //获取结束时间
            System.out.println(i);
            System.out.println("算法运行时间为:"+(endTime - startTime) + "ms");
    }
    

    传统算法的结果为:
    在这里插入图片描述

    优化后的算法结果为:
    在这里插入图片描述
    经计算改进后的算法针对上面的测试方法比传统的算法快了近67.5%。

    2.一般情况测试:
    从网上截取了一段正常的两万多字的文本并对它们进行测试发现它们的查找速度基本相同。
    综合而言,本文对Sunday算法的优化提高了此查找算法的稳定性以及平均复杂度。

    展开全文
  • sunday 算法python实现

    2019-06-27 16:43:27
    同为字符串查找的算法, Sunday真的比KMP简单太多了。 理解也很简单: 假设有 字符串 A, 待比较字符串 B, 需要查找 A是否包含B。 对齐A的i位置和B的0位置, i从0开始。 如果A[i] 元素和B[0]相同,就继续比较A...

    同为字符串查找的算法, Sunday真的比KMP简单太多了。

    理解也很简单:

    下面的文字可能比较难理解, 可以参考这个博主的博客理解
    [字符串匹配——Sunday算法]https://blog.csdn.net/q547550831/article/details/51860017
    假设有 字符串 A, 待比较字符串 B, 需要查找 A是否包含B。

    1. 对齐A的i位置和B的0位置, i从0开始。

    2. 如果A[i] 元素和B[0]相同,就继续比较A的下一个元素和B的下一个值,比较len(B)次, 就是看A这段字符串是不是B, 如果是就退出结束了。当然事情可能没这么简单, 如果不是,我们就得把B往后移动, 对齐到A的后面位置去。暴力方法的话, 是B每次往后移动一个位置,跟A比较一次。 KMP/BM/Sunday 这些算法都是计算位移的, 即尽可能多的跳过无用的元素, 减少比较的次数。

    3. 如果在第二步从i到i+len(B)-1的比较过程中有一个位置不相同,就直接去看 A[i + len(B)]是否在B中。 如果不同, 说明什么? 此时,我们已知对齐到i位置时的A跟B不相同了, 这下好了,i+len(B)的位置也不同, 我们本来是应该接着从i+1位置对齐开始比较的, 这下没必要了。 因为假设B出现在A的i+1开始的位置,则A[i+len(B)]这个值一定会出现在B中(因为从A的i+1开始取的这段len(B)长的字符串肯定会越过A的i+len(B)的位置, i+1+len > i+len)。 然而, 我们已经知道A[i+len(B)]不在B中了, 所以反证A[i+1]到A[i+len(B)] 这一大块肯定都不包含B,都可以跳过去了。然后,又回到了步骤1。

    4. 当然, 上一步也可能A[i+len(B)] 就在B中, 假设出现在B的倒数第x个位置。 这说明可能从i+1开始, A的字符串就包含B了。 这里,我们也不用一步步往后移动了, 直接把A的i+len(B)位置跟B的 x位置对齐不就行了吗。 此时再判断A这段是否跟B相同。 这样其实又回到了步骤3、4, 循环往复。

    5. 退出条件是直到A中找到了B或者找到了最后也没找到, 最后这段只要比较到两个字符串尾巴对齐就可以了, 即len(A) - len(B)的位置。

    def sunday_find(src, dst):
        len_src = len(src)
        len_dst = len(dst)
        i = 0
        while i < len_src - len_dst + 1:
            flag = 0
            shift = len_dst
            for j in range(0, len_dst):
                if src[i+j] != dst[j]:
                    flag = -1
                    break
    
            if flag == 0:
                return i
    
            p = dst.rfind(src[i+shift])
            if p == -1:
                shift = len_dst + 1
            else:
                shift = len_dst - p
    
            i = i + shift
    
        return -1
    
    
    if __name__ == "__main__":
        text = "here_examplfe_v_example"
        pattern = "ple"
        pos = sunday_find(text, pattern)
        print pos
    
    展开全文
  • 例如: 输入: S:‘abcabdabe’ T:‘abd’ 输出: 3 解决方案 字符串匹配的问题有很多算法,这里用的是Sunday算法,Sunday算法是Daniel M.Sunday于1990年提出的字符串模式匹配。其核心思想是:在匹配过程中,模式...
  • Sunday算法java实现

    万次阅读 2017-04-06 17:25:18
    Daniel M.Sunday于1990年提出的字符串模式匹配。其效率在匹配随机的字符串时比其他匹配算法还要更快,同时其实现方式比KMP,BM的实现容易太多。   算法原理 作为一个字符串模式匹配算法,Sunday算法的核心在于...
  • 字符串匹配——Sunday算法

    万次阅读 多人点赞 2016-07-08 13:03:34
    字符串匹配——Sunday算法基本思想及举例Sunday算法由Daniel M.Sunday在1990年提出,它的思想跟BM算法很相似:1只不过Sunday算法是从前往后匹配,在匹配失败时关注的是主串中参加匹配的最末位字符的下一位字符。...
  • Sunday算法详解

    2018-01-25 17:48:45
    Sunday算法是Daniel M.Sunday于1990年提出的字符串模式匹配。其效率在匹配随机的字符串时比其他匹配算法还要更快。Sunday算法的实现可比KMP,BM的实现容易太多。 二:分析 假设我们有如下字符串: A = ...
  • sunday算法简单解析

    2018-08-03 15:42:26
    sunday算法解析 ##### Sunday算法由Daniel M.Sunday在1990年提出,它的思想跟BM算法很相似: 只不过Sunday算法是从前往后匹配,在匹配失败时关注的是文本串中参加匹配的最末位字符的下一位字符。 如果该字符...
  • 一、Sunday算法思想 备注:因为Sunday理解起来比较简单,就直接用参考的文章内容了。链接:https://www.cnblogs.com/sunsky303/p/11693792.html Sunday算法是从前往后匹配,在匹配失败时关注的是主串中参加匹配的...
  • Sunday算法实现

    2019-03-25 16:21:50
    字符串模式匹配算法 sunday算法实现。说到字符串匹配算法,立马就想到了KMP算法,谁让KMP这么经典呢,各种算法教材里必然有KMP啊。但是KMP算法太复杂了,比KMP更简单更高效的算法就是Sunday算法。
  • 本文介绍了比KMP算法更优化的BM算法和Sunday算法
  • c#实现sunday算法实例

    2020-09-05 02:22:48
    Sunday算法思想跟BM算法很相似,在匹配失败时关注的是文本串中参加匹配的最末位字符的下一位字符,下面是用C#实现sunday的实例代码,有需要的朋友可以参考一下
  • 根据上面的步骤我写了一个在一个字符串中查找另一个字符串的算法 java实现代码如下: public int Sunday(String haystack, String needle) { int hayLen = haystack.length();//主串长度 int nLen = needle.length()...
  • Java实现Sunday算法

    千次阅读 2017-05-26 10:18:26
    Sunday算法是Daniel M.Sunday于1990年提出的字符串模式匹配。其核心思想是:在匹配过程中,模式串发现不匹配时,算法能跳过尽可能多的字符以进行下一步的匹配,从而提高了匹配效率。相比于另外几个著名的字符串匹配...
  • 基于SunDay匹配算法改良的寻找字节集易语言源码
  • 我的sunday_code

    2014-12-11 14:07:23
    开始起航......
  • 优点:SunDay不多说匹配模式灵活(固定的匹配模式你只能从头开始定位而不能自选位置)
  • 算法之Sunday算法

    2021-05-31 21:23:41
    Sunday算法由Daniel M.Sunday在1990年提出,它的思想跟BM算法很相似: Sunday算法 算法是比BM 和KBM更高效的算法,它不关注好后缀与坏字符,只关注文本串中参加匹配的最末位字符的下一位字符的情况 Sunday算法是从...
  • sunday.cpp

    2019-07-02 19:04:41
    用C++实现字符串模式匹配算法中的sunday算法
  • 效果图: 代码: #include<Windows.h> #include<iostream> #include<vector> #include<time.h> using namespace std; #define BLOCKMAXSIZE 409600//每次读取内存...//每次将读取的...
  • Sunday算法的思想和BM算法中的坏字符思想非常类似。差别只是在于Sunday算法在匹配失败之后,是取目标串中当前和Pattern字符串对应的部分后面一个位置的字符来做坏字符匹配,写了个小例子来实现以下这个算法
  • 字符串匹配算法之Sunday算法C++实现
  • [TOC] ...今天在尝试用Python编写KMP的时候,无意中看到Sunday算法,该算法的编写比BoyerMoore简单,也比BoyerMoore快,更是胜过KMP,这里就把这三种方法总结一下。KMP算法关于KMP算法,我是直接看的
  • 针对Sunday匹配算法在首字符和正文存在大量重复,使得其平均执行效率降低这一问题,提出了一种改进的Sunday算法。首先将重复的首字符压缩为一个字符,然后使用压缩后的字符串和正文进行匹配,若匹配成功,对成功匹配的...
  • Sunday算法(字符串匹配-)
  • Sunday算法流程与代码

    千次阅读 2017-01-01 14:06:05
    Sunday算法: 用map记录较短字符串中,每个字符出现的最后一个位置。 两个游标,i,j。初始为0。一个index指向往后数第一个未重合的字符。 1,当l_str[i] == s_str[j] i++,j++; 2, 不相等: 2.1:去map中...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 67,232
精华内容 26,892
关键字:

sunday