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赋值语句后逗号的作用分析

本文实例讲述了Python赋值语句后逗号的作用。分享给大家供大家参考。具体分析如下: IDLE 2.6.2 >>> a = 1 >>> b =...

Tensorflow的可视化工具Tensorboard的初步使用详解

Tensorflow的可视化工具Tensorboard的初步使用详解

当使用Tensorflow训练大量深层的神经网络时,我们希望去跟踪神经网络的整个训练过程中的信息,比如迭代的过程中每一层参数是如何变化与分布的,比如每次循环参数更新后模型在测试集与训练集...

在Python中使用HTMLParser解析HTML的教程

如果我们要编写一个搜索引擎,第一步是用爬虫把目标网站的页面抓下来,第二步就是解析该HTML页面,看看里面的内容到底是新闻、图片还是视频。 假设第一步已经完成了,第二步应该如何解析HTML...

Python 共享变量加锁、释放详解

Python 共享变量加锁、释放详解

一、共享变量 共享变量:当多个线程访问同一个变量的时候。会产生共享变量的问题。 例子: import threading sum = 0 loopSum = 1000000 def...

Python用zip函数同时遍历多个迭代器示例详解

前言 本文主要介绍的是Python如何使用zip函数同时遍历多个迭代器,文中的版本为Python3,zip函数是Python内置的函数。下面话不多说,来看详细的内容。 应用举例...