python通过BF算法实现关键词匹配的方法

yipeiwu_com6年前Python基础

本文实例讲述了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中用PIL库批量给图片加上序号的教程

Python中用PIL库批量给图片加上序号的教程

女友让我给她论文的图片上加上字母序号,本来觉得是个很简单的事情,但那个白底黑字的圆圈序号却难住了我, 试了几个常用的软件,都不行。 后来用 PS + 动作,倒是能搞出来,不过也不容易,正...

基于Python实现对PDF文件的OCR识别

基于Python实现对PDF文件的OCR识别

最近在做一个项目的时候,需要将PDF文件作为输入,从中输出文本,然后将文本存入数据库中。为此,我找寻了很久的解决方案,最终才确定使用tesseract。所以不要浪费时间了,我们开始吧。...

利用Python脚本实现ping百度和google的方法

Ping服务 ping 是基于 XML_RPC 标准协议的更新通告服务,用于Blog把内容更新快速通知给搜索引擎,以便搜索引擎及时进行抓取和更新。 计算机就相当于 RPC Client...

flask中主动抛出异常及统一异常处理代码示例

flask中主动抛出异常及统一异常处理代码示例

本文主要介绍的是flask中主动抛出异常及统一异常处理的相关内容,具体如下。 在开发时,后台出现异常 ,但不想把异常显示给用户或者要统一处理异常时,可以使用abort主动抛出异常,再捕获...

Python切片操作深入详解

本文实例讲述了Python切片操作。分享给大家供大家参考,具体如下: 我们基本上都知道Python的序列对象都是可以用索引号来引用的元素的,索引号可以是正数由0开始从左向右,也可以是负数...