欢迎访问智唯网络!专业H5响应式营销型网站建设、百度seo优化、网络推广服务!
营销之道 干货分享
了解企业新动态,分享前沿的营销推广干货,成长路上,我们携手同行
优化推广News

KMP算法-关键词搜索完整匹配与部分匹配

发布时间:2017:09:06 22:05:27 | 已阅: | 作者:智唯小编 | 来源:智唯网络 | 共 0 条评论

扫一扫
手机访问

本文共有6503个文字,预计阅读时间17分钟
导语
网站SEO查询工具是网站优化、关键词排名、关键词优化必备的站长SEO工具:快速诊断网站seo排名状况,给出合理的网站优化建议,快速提升网站关键词优化排名!

KMP检索词算法(搜索词及部分匹配值)如下图如示:

KMP算法-关键词搜索完整匹配与部分匹配
一开始我一直以为单个字符进行计算,后来经过查询资料发现我错了,每个字符下面记录的部分匹配值不是这单个字符的值,而是从开头字符到此字符这个字符串的值,这样说可能有点抽象,下面以上图为例详细介绍一下

为了方便说明这里把搜索词记为:P={ABCDABD}

1,P[0]表示“A”,其完全前后缀都是空,所以其部分匹配值为0
2,P[1]表示“AB”,其完全前缀为{空,A},完全后缀为{B,空},前后缀中只有空相同,所以AB(即P[1])的匹配值为0
3,P[2]表示“ABC”,其完全前缀为{空,A,AB},完全后缀为{BC,B,空},前后缀中只有空相同,所以ABC(即P[2])的匹配值为0
4,P[3]表示“ABCD”,其完全前缀为{空,A,AB,ABC},完全后缀为{BCD,CD,D,空},前后缀中只有空相同,所以ABCD(即P[3])的匹配值为0
5,P[4]表示“ABCDA”,其完全前缀为{空,A,AB,ABC,ABCD},完全后缀为{BCDA,CDA,DA,A,空},前后缀中都有{A}长度为1,所以ABCDA(即P[4])的匹配值为1
6,P[5]表示“ABCDAB”其完全前缀为{空,A,AB,ABC,ABCD,ABCDA},完全后缀为{BCDAB,CDAB,DAB,AB,B,空},前后缀中都有{AB}长度为2,所以ABCDAB(即P[5])的匹配值为2
7,P[6]表示“ABCDABD”其完全前缀为{空,A,AB,ABC,ABCD,ABCDA,ABCDAB},完全后缀为{BCDABD,CDABD,DABD,ABD,BD,D,空},前后缀中只有空相同,所以ABCDABD(即P[6])的匹配值为0

说明:

P[i]表示能匹配的字符串,部分匹配值计算的是能匹配的字符串对应该的值,例如上面的P[5]表示的是如果匹配了字符串“ABCDAB”,则这个字符串对应的部分匹配值为2,而不是第二个字符B的部分匹配值
为了方便操作,字符串的部分匹配值都对应到字符串的最后一个字符,这样即方便记录也方便查询


另外,

"部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度,这个已经在阮总的文件中解释,这里再强调一点,其前后缀都是表示完全前后缀,即不包含自身的前缀或者后缀。

做网络营销的都应该知道,竞价推广是网络营销的首选手段,而要做好中国市场的广告竞价推广就必须要了解百度竞价。细心研究过百度竞价对网站业绩提升是有很大的帮助。今天我就借助马海祥博客的平台跟大家浅谈一下百度竞价,首先我们先谈一下百度竞价中的四种关键词匹配方式:短语匹配、广泛匹配、精确匹配和否定匹配。

KMP算法-关键词搜索完整匹配与部分匹配

百度竞价的匹配方式组成:

短语匹配:匹配条件是搜索关键词完全包含推广关键词,而且包含的部分与推广关键词字面完全一致时(顺序不变,无间隔)才触发,用于比较精确的匹配限制。短语匹配将限制只有网民搜索那些仅在字面上与关键词高度相关的搜索词时才能展现对应的推广信息。

例如:在短语匹配情况下,推广关键词“牛奶”与“购买牛奶”、“婴儿牛奶”、“牛奶价格”匹配,而与“牛奶米粉”不匹配。

优势:与精确匹配相比更为灵活且能获得更多的潜在客户访问,与广泛匹配相比则有更强的针对性且可能有更高的转化率。

劣势:获得的展示次数介于广泛匹配与精确匹配之间,转化率没有精确匹配高。

广泛匹配:匹配条件是搜索关键词完全包含推广关键词,允许包含部分字面顺序颠倒或有间隔,是最宽泛的匹配方式,也是默认的匹配方式。系统有可能对匹配条件进行延伸,扩展至关键词的同义词、近义词、相关词、以及包含关键词的短语等。

例如:在广泛匹配情况下,推广关键词“牛奶”可能与“牛奶米粉”匹配。

优势:是一种既进行高针对性的投放、又接触广泛受众群体的有效方法,能够为客户带去更多的潜在用户访问。

劣势:点击访问的针对性不足,转化率不如精确匹配和短语匹配。有可能会带来大量点击,触发较多的点击消费。

精确匹配:匹配条件是在搜索关键词与推广关键词二者字面完全一致时才触发的限定条件,用于精确严格的匹配限制。使用精确匹配时,若搜索词中包含其他词语,或搜索词与关键词的词语顺序不同,均不会展现对应的创意。

例如:精确匹配时,推广关键词“培训”与“培训价格”或“seo培训”不匹配,仅在有人搜索“培训”时推广信息才被触发,这样可以对展现条件进行完全的控制。

优势:可获得最具针对性的点击访问,转化率较高。

劣势:会降低创意的展示次数,获得潜在客户的范围较窄。

否定匹配:与短语匹配和广泛匹配相配合使用,对于一些可能被匹配但与推广意图不相符合的关键词可以添加到否定匹配关键词表中来阻止对应推广信息的触发。可以选择其反面或非经营业务类的词作为否定关键词。

例如:商户只做英语培训,不做日语培训,则可以选择“日语”作为否定词。商户还可以在统计报告中的“搜索词报告”中找出与业务无关的关键词,将其设置为否定词。

优势:使客户在通过广泛匹配和短语匹配获得更多潜在用户访问的同时,通过滤除不能为客户带去潜在客户访问的不必要展现,降低转化成本,提高投资回报率。

劣势:设置否定关键词后,将降低关键词的展现概率,即获得潜在客户关注的概率降低。

KMP算法-关键词搜索完整匹配与部分匹配

每个关键词的短语匹配和广泛匹配都可以视为对一组词的选定,并可以通过否定匹配进行校正。合理的运用关键词的匹配,对于提高推广效果,降低推广成本起到很好的作用。

竞价匹配模式——马海祥博客知识点扩展

问:广泛匹配怎么用啊?会不会让我白花钱啊?

答:广泛匹配是关键词的一种匹配模式,它能够最大范围的帮助您覆盖潜在目标客户,让您展现在更多潜在客户面前。与此同时,您不必担心因覆盖范围过大而产生缺乏针对性的访问,因为搜索推广提供了搜索词统计报告和否定匹配的功能。

首先,您可以通过搜索词统计报告查看网民是通过哪些搜索词访问到自己的。将不适合展现您推广结果的搜索词,直接通过搜索推广独有的否定匹配功能,进行排除即可。同时,进一步洞悉哪些关键词价值高,更符合网民的搜索习惯,从而,进一步优化和丰富您的推广内容。

通过将广泛匹配、搜索词统计报告和否定匹配三种功能的结合使用,循环优化,一定能使您的推广效果价值最大化。这也正是搜索推广功能所独具的优势,让您的推广更科学更合理

问:为什么搜索某个我没提交的词,我的关键词也出现了?广泛匹配默认是什么都不加,而客户提交关键词的时候就是习惯什么都不加,你们就是利用这个来赚客户不知情的钱。(为什么没有人提醒我有广泛匹配这个情况啊?我多花了好多没用的钱,你们怎么解释!)

答:广泛匹配可以最大范围的覆盖潜在目标客户,是一种既能高针对性投放,又能广泛接触受众的方式。使用广泛匹配可以增加您展现的机会,提升您的品牌知名度。在新建计划、单元、撰写创意、提交关键词的过程中,提交关键词页面的下方,对于各种匹配方式和设置方式都有明确提示的。

如果您觉得解释的不够详尽,也可以马海祥博客本文中上面介绍来了解各种匹配方式,以选择最适合的方式进行推广。

问:如果我发现不相关的搜索词展现了我的结果,怎么办?

策略:黄金组合持续优化。

答:广泛匹配是关键词的一种匹配模式,它能够最大范围的帮助您覆盖潜在目标客户,让您展现在更多潜在客户面前。与此同时,您不必担心因覆盖范围过大而产生缺乏针对性的访问,因为搜索推广提供了搜索词统计报告和否定匹配的功能。首先,您可以通过搜索词统计报告查看网民是通过哪些搜索词访问到自己的。将不适合展现您推广结果的搜索词,直接通过搜索推广独有的否定匹配功能,进行排除即可。同时,进一步洞悉哪些关键词价值高,更符合网民的搜索习惯,从而,进一步优化和丰富您的推广内容。

通过将广泛匹配、搜索词统计报告和否定匹配三种功能的结合使用,持续优化,一定能使您的推广效果价值最大化。这也正是搜索推广功能所独具的优势,让您的推广更科学更合理。

问:现在都是广泛匹配了,是不是就提核心词就行了?

策略:词少影响推广效果,引导使用工具提词;

答:关键词参加广泛匹配后,它能够最大范围的帮助您覆盖潜在目标客户,让您展现在更多潜在客户面前,但是如果只提交核心词,缩小提词范围从整体推广来看还是会影响您的覆盖范围和推广效果。

所以建议,您可以通过搜索词报告和关键词推荐工具,查找提交具备商业性的关键词,并参与广泛匹配,会让您的推广结果获得更多有针对性的关注,从而取得更好的推广效果。

问:否定关键词怎么设置呢?怎么选择合适的否定关键词啊?

答:在选词阶段,您可根据企业的产品特性,排查出推荐工具所推荐的低质词汇,并将这些词设置为否定关键词就可以实现否定匹配了;您也可以通过搜索推广新增的“搜索词统计报告”,来排查那些不符合需求的词,直接将其设置为否定关键词即可。



 

在文本编辑中,我们经常要在一段文本中某个特定的位置找出 某个特定的字符或模式。
由此,便产生了字符串的匹配问题。
本文由简单的字符串匹配算法开始,经Rabin-Karp算法,最后到KMP算法,教你从头到尾彻底理解KMP算法。

来看算法导论一书上关于此字符串问题的定义:
假设文本是一个长度为n的数组T[1...n],模式是一个长度为m<=n的数组P[1....m]。
进一步假设P和T的元素都是属于有限字母表Σ.中的字符。

KMP算法-关键词搜索完整匹配与部分匹配

依据上图,再来解释下字符串匹配问题。目标是找出所有在文本T=abcabaabcaabac中的模式P=abaa所有出现。
该模式仅在文本中出现了一次,在位移s=3处。位移s=3是有效位移。

 

一、简单的字符串匹配算法

简单的字符串匹配算法用一个循环来找出所有有效位移,
该循环对n-m+1个可能的每一个s值检查条件P[1....m]=T[s+1....s+m]。

NAIVE-STRING-MATCHER(T, P)
1 n ← length[T]
2 m ← length[P]
3 for s ← 0 to n - m
4     do if P[1 ‥ m] = T[s + 1 ‥ s + m]          
      //对n-m+1个可能的位移s中的每一个值,比较相应的字符的循环必须执行m次。
5           then print "Pattern occurs with shift" s

KMP算法-关键词搜索完整匹配与部分匹配

简单字符串匹配算法,上图针对文本T=acaabc 和模式P=aab。
上述第4行代码,n-m+1个可能的位移s中的每一个值,比较相应的字符的循环必须执行m次。
所以,在最坏情况下,此简单模式匹配算法的运行时间为O((n-m+1)m)。

 

--------------------------------

下面我再来举个具体例子,并给出一具体运行程序:
对于目的字串target是banananobano,要匹配的字串pattern是nano,的情况,

下面是匹配过程,原理很简单,只要先和target字串的第一个字符比较,
如果相同就比较下一个,如果不同就把pattern右移一下,
之后再从pattern的每一个字符比较,这个算法的运行过程如下图。
//index表示的每n次匹配的情形。

KMP算法-关键词搜索完整匹配与部分匹配

 

#include<iostream>
#include<string>
using namespace std;
int match(const string& target,const string& pattern)
{
    int target_length = target.size();
    int pattern_length = pattern.size();
    int target_index = 0;
    int pattern_index = 0;
    while(target_index < target_length && pattern_index < pattern_length)
    {
        if(target[target_index]==pattern[pattern_index])
        {
            ++target_index;
            ++pattern_index;
        }
        else
        {
            target_index -= (pattern_index-1); 
            pattern_index = 0;
        }
    }
    if(pattern_index == pattern_length)
    {
        return target_index - pattern_length;
    }
    else
    {
        return -1;
    }
}
int main()
{
    cout<<match("banananobano","nano")<<endl;
    return 0;
}

//运行结果为4。

 

上面的算法进间复杂度是O(pattern_length*target_length),
我们主要把时间浪费在什么地方呢,
观查index =2那一步,我们已经匹配了3个字符,而第4个字符是不匹配的,这时我们已经匹配的字符序列是nan,

此时如果向右移动一位,那么nan最先匹配的字符序列将是an,这肯定是不能匹配的,
之后再右移一位,匹配的是nan最先匹配的序列是n,这是可以匹配的。

如果我们事先知道pattern本身的这些信息就不用每次匹配失败后都把target_index回退回去,
这种回退就浪费了很多不必要的时间,如果能事先计算出pattern本身的这些性质,
那么就可以在失配时直接把pattern移动到下一个可能的位置,
把其中根本不可能匹配的过程省略掉,
如上表所示我们在index=2时失配,此时就可以直接把pattern移动到index=4的状态,
kmp算法就是从此出发。

 

二、KMP算法

1、 覆盖函数(overlay_function)

覆盖函数所表征的是pattern本身的性质,可以让为其表征的是pattern从左开始的所有连续子串的自我覆盖程度。
比如如下的字串,abaabcaba

KMP算法-关键词搜索完整匹配与部分匹配

 

由于计数是从0始的,因此覆盖函数的值为0说明有1个匹配,对于从0还是从来开始计数是偏好问题,

具体请自行调整,其中-1表示没有覆盖,那么何为覆盖呢,下面比较数学的来看一下定义,比如对于序列

a0a1...aj-1 aj

 

要找到一个k,使它满足

a0a1...ak-1ak=aj-kaj-k+1...aj-1aj

而没有更大的k满足这个条件,就是说要找到尽可能大k,使pattern前k字符与后k字符相匹配,k要尽可能的大,
原因是如果有比较大的k存在,而我们选择较小的满足条件的k,
那么当失配时,我们就会使pattern向右移动的位置变大,而较少的移动位置是存在匹配的,这样我们就会把可能匹配的结果丢失。

比如下面的序列,

KMP算法-关键词搜索完整匹配与部分匹配

 

在红色部分失配,正确的结果是k=1的情况,把pattern右移4位,如果选择k=0,右移5位则会产生错误。
计算这个overlay函数的方法可以采用递推,可以想象如果对于pattern的前j个字符,如果覆盖函数值为k

a0a1...ak-1ak=aj-kaj-k+1...aj-1aj
则对于pattern的前j+1序列字符,则有如下可能
⑴     pattern[k+1]==pattern[j+1] 此时overlay(j+1)=k+1=overlay(j)+1
⑵     pattern[k+1]≠pattern[j+1] 此时只能在pattern前k+1个子符组所的子串中找到相应的overlay函数,h=overlay(k),如果此时pattern[h+1]==pattern[j+1],则overlay(j+1)=h+1否则重复(2)过程.

 

下面给出一段计算覆盖函数的代码:

#include<iostream>
#include<string>
using namespace std;
void compute_overlay(const string& pattern)
{
    const int pattern_length = pattern.size();
    int *overlay_function = new int[pattern_length];
    int index;
    overlay_function[0] = -1;
    for(int i=1;i<pattern_length;++i)
    {
        index = overlay_function[i-1];
        //store previous fail position k to index;
        
        while(index>=0 && pattern[i]!=pattern[index+1])
        {
            index = overlay_function[index];
        }
        if(pattern[i]==pattern[index+1])
        {
            overlay_function[i] = index + 1;  
        }
        else
        {
            overlay_function[i] = -1;
        }
    }
    for(i=0;i<pattern_length;++i)
    {
        cout<<overlay_function[i]<<endl;
    }
    delete[] overlay_function;
}
int main()
{
    string pattern = "abaabcaba";
    compute_overlay(pattern);
    return 0;
}


运行结果为:

-1
-1
0
0
1
-1
0
1
2
Press any key to continue

-------------------------------------

 

2、kmp算法
     有了覆盖函数,那么实现kmp算法就是很简单的了,我们的原则还是从左向右匹配,但是当失配发生时,我们不用把target_index向回移动,target_index前面已经匹配过的部分在pattern自身就能体现出来,只要动pattern_index就可以了。

当发生在j长度失配时,只要把pattern向右移动j-overlay(j)长度就可以了。

 如果失配时pattern_index==0,相当于pattern第一个字符就不匹配,
这时就应该把target_index加1,向右移动1位就可以了。

 

ok,下图就是KMP算法的过程(红色即是采用KMP算法的执行过程):

 

 

KMP算法-关键词搜索完整匹配与部分匹配

 

ok,最后给出KMP算法实现的c++代码:

#include<iostream>
#include<string>
#include<vector>
using namespace std;

int kmp_find(const string& target,const string& pattern)
{
    const int target_length = target.size();
    const int pattern_length = pattern.size();
    int * overlay_value = new int[pattern_length];
    overlay_value[0] = -1;
    int index = 0;
    for(int i=1;i<pattern_length;++i)
    {
        index = overlay_value[i-1];
        while(index>=0 && pattern[index+1]!=pattern[i])
        {
            index  = overlay_value[index];
        }
        if(pattern[index+1]==pattern[i])
        {
            overlay_value[i] = index +1;
        }
        else
        {
            overlay_value[i] = -1;
        }
    }
    //match algorithm start
    int pattern_index = 0;
    int target_index = 0;
    while(pattern_index<pattern_length&&target_index<target_length)
    {
        if(target[target_index]==pattern[pattern_index])
        {
            ++target_index;
            ++pattern_index;
        }
        else if(pattern_index==0)
        {
            ++target_index;
        }
        else
        {
            pattern_index = overlay_value[pattern_index-1]+1;
        }
    }
    if(pattern_index==pattern_length)
    {
        return target_index-pattern_index;
    }
    else
    {
        return -1;
    }
    delete [] overlay_value;
}

int main()
{
    string source = " annbcdanacadsannannabnna";
    string pattern = " annacanna";
    cout<<kmp_find(source,pattern)<<endl;
    return 0;
}
//运行结果为 -1.

 

三、kmp算法的来源
    kmp如此精巧,那么它是怎么来的呢,为什么要三个人合力才能想出来。其实就算没有kmp算法,人们在字符匹配中也能找到相同高效的算法。这种算法,最终相当于kmp算法,只是这种算法的出发点不是覆盖函数,不是直接从匹配的内在原理出发,而使用此方法的计算的覆盖函数过程序复杂且不易被理解,但是一但找到这个覆盖函数,那以后使用同一pattern匹配时的效率就和kmp一样了,其实这种算法找到的函数不应叫做覆盖函数,因为在寻找过程中根本没有考虑是否覆盖的问题。

    说了这么半天那么这种方法是什么呢,这种方法是就大名鼎鼎的确定的有限自动机(Deterministic finite state automaton DFA),DFA可识别的文法是3型文法,又叫正规文法或是正则文法,既然可以识别正则文法,那么识别确定的字串肯定不是问题(确定字串是正则式的一个子集)。对于如何构造DFA,是有一个完整的算法,这里不做介绍了。在识别确定的字串时使用DFA实在是大材小用,DFA可以识别更加通用的正则表达式,而用通用的构建DFA的方法来识别确定的字串,那这个overhead就显得太大了。

    kmp算法的可贵之处是从字符匹配的问题本身特点出发,巧妙使用覆盖函数这一表征pattern自身特点的这一概念来快速直接生成识别字串的DFA,因此对于kmp这种算法,理解这种算法高中数学就可以了,,但是如果想从无到有设计出这种算法是要求有比较深的数学功底的。

如何建站:
建网站需要准备哪些资料 如何购买域名空间 协助备案 成功案例 真实见证 建站类型有哪些 收费标准 建站流程 制作周期 改版美化 提升有户体验 [建站必看]源码内容交付 联系客服 专业建站

看了这篇文章的人还看了

专业建站 免费排名(有什么疑问的请留言或咨询在线客服)
  • 全部评论(0
    还没有评论,快来抢沙发吧!

上一篇:SEO优化需杜绝链接买卖行为

下一篇:和云无限一起探索SEO站内优化的八大要素

  • 同行价格

    统一报价,无隐形消费

  • 金牌服务

    一对一专属顾问,7*24小时金牌服务

  • 售后无忧

    完善售后,客服经理全程跟进

建站优化二维码
建站优化二维码

截屏,微信识别二维码

微信号:13825575516

(点击微信号复制,添加好友)

优化二维码打开微信