清华大佬耗费三个月吐血整理的几百G的资源,免费分享!....>>>
python通过BF算法实现关键词匹配
算法思想:目标串t与模式串p逐词比较,若对应位匹配,则进行下一位比较;若不相同,p右移1位,从p的第1位重新开始比较。
算法特点:整体移动方向:可认为在固定的情况下,p从左向右滑动;匹配比较时,从p的最左边位开始向右逐位与t串中对应位比较。p的滑动距离为1,这导致BF算法匹配效率低(相比其他算法,如:BM,KMP,滑动没有跳跃)。
该算法的时间复杂度为O(len(t)*len(p)),空间复杂度为O(len(t)+len(p))
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | #!/usr/bin/python # -*- coding: UTF-8 # filename BF import time """ t="this is a big apple,this is a big apple,this is a big apple,this is a big apple." p="apple" """ t = "为什么叫向量空间模型呢?其实我们可以把每个词给看成一个维度,而词的频率看成其值(有向),即向量,这样每篇文章的词及其频率就构成了一个i维空间图,两个文档的相似度就是两个空间图的接近度。假设文章只有两维的话,那么空间图就可以画在一个平面直角坐标系当中,读者可以假想两篇只有两个词的文章画图进行理解。" p = "读者" i = 0 count = 0 start = time.time() while (i < = len(t) - len(p)): j = 0 while (t[i] = = p[j]): i = i + 1 j = j + 1 if j = = len(p): break elif (j = = len(p) - 1 ): count = count + 1 else : i = i + 1 j = 0 print count print time.time() - start |
算法特点:整体移动方向:可认为在固定的情况下,p从左向右滑动;匹配比较时,从p的最左边位开始向右逐位与t串中对应位比较。p的滑动距离为1,这导致BF算法匹配效率低(相比其他算法,如:BM,KMP,滑动没有跳跃)。
该算法的时间复杂度为O(len(t)*len(p)),空间复杂度为O(len(t)+len(p))