python通过BF算法实现关键词匹配的方法
作者:chongq 时间:2022-10-19 03:56:37
本文实例讲述了python通过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))
希望本文所述对大家的Python程序设计有所帮助。
标签:python,算法,匹配
0
投稿
猜你喜欢
python 装饰器重要在哪
2023-12-30 12:13:29
WEB设计经验-来自Microsoft
2008-05-15 07:30:00
MySQL数据库搜索中的大小写敏感性
2008-11-24 12:44:00
python 可视化库PyG2Plot的使用
2022-10-14 05:22:17
Oracle动态交叉表生成
2010-07-27 12:55:00
超链“确认”对话框confirm
2008-05-16 11:42:00
Python中最大递归深度值的探讨
2021-01-16 14:21:21
Python中使用matplotlib模块errorbar函数绘制误差棒图实例代码
2022-11-09 17:01:42
python常用函数random()函数详解
2022-08-04 18:17:21
python多线程超详细详解
2023-08-09 09:10:23
Python 动态导入对象,importlib.import_module()的使用方法
2023-01-24 01:48:47
python中defaultdict方法的使用详解
2022-06-25 05:07:09
asp长文章分页显示思路
2007-08-23 13:54:00
Python中的文本相似度的计算方法总结
2021-02-08 08:40:37
Python从列表推导到zip()函数的5种技巧总结
2023-07-31 00:57:11
python中类和实例如何绑定属性与方法示例详解
2022-01-02 07:22:12
MSSQL数据库还原图解教程
2009-01-12 17:58:00
Django渲染Markdown文章目录的方法示例
2021-03-31 05:12:07
escape,encodeURI,encodeURIComponent函数比较
2008-01-27 11:19:00
FrontPage 2000主页设计问与答
2008-08-02 12:37:00