python 通过 BF 算法实现关键词匹配, BF 算法, 即暴风 (Brute Force) 算法, 是普通的模式匹配算法, BF 算法的思想就是将目标串 S 的第一个字符与模式串 T 的第一个字符进行匹配, 若相等, 则继续比较 S 的第二个字符和 T 的第二个字符; 若不相等, 则比较 S 的第二个字符和 T 的第一个字符, 依次比较下去, 直到得出最后的匹配结果. BF 算法是一种蛮力算法.
- #!/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
算法思想: 目标串 t 与模式串 p 逐词比较, 若对应位匹配, 则进行下一位比较; 若不相同, p 右移 1 位, 从 p 的第 1 位重新开始比较.
算法特点: 整体移动方向: 可认为在固定的情况下, p 从左向右滑动; 匹配比较时, 从 p 的最左边位开始向右逐位与 t 串中对应位比较. p 的滑动距离为 1, 这导致 BF 算法匹配效率低(相比其他算法, 如: BM,KMP, 滑动没有跳跃).
该算法的时间复杂度为 O(len(t)*len(p)), 空间复杂度为 O(len(t)+len(p))
文章参考: https://www.py.cn/faq/python/10459.html
来源: http://www.bubuko.com/infodetail-3100840.html