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

本文实例讲述了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程序设计有所帮助。

赞 (0)

相关推荐

  • js 获取中文拼音,Select自动匹配字母获取值的代码

    复制代码 代码如下: <script type="text/javascript"> var key2code = {65:"a",66:"b",67:"c",68:"d",69:"e",70:"f",71:"g",72:"h",73:"i",74:"j", 75:"

  • js正则表达式匹配数字字母下划线等

    1.一个正则表达式,只含有汉字.数字.字母.下划线不能以下划线开头和结尾: ^(?!_)(?!.*?_$)[a-zA-Z0-9_\u4e00-\u9fa5]+$ 其中: ^ 与字符串开始的地方匹配 (?!_) 不能以_开头 (?!.*?_$) 不能以_结尾 [a-zA-Z0-9_\u4e00-\u9fa5]+ 至少一个汉字.数字.字母.下划线 $ 与字符串结束的地方匹配 放在程序里前面加@,否则需要\\进行转义 @"^(?!_)(?!.*?_$)[a-zA-Z0-9_\u4e00-\u9fa5]

  • JS 正则表达式（学习笔记2）匹配网址url参数

    . 匹配除换行符的任意字符 \w 匹配字母,数字,下划线,汉字 \s 匹配任意空白符 \d 匹配数字 ^ 匹配字符开始位置 $ 匹配字符结束位置 * 重复零次或更多次 + 重复一次或更多次 ? 重复零次或一次 {n} 重复N次 {n,} 重复N次或更多次 {n,m} 重复N次或m次url参数匹配的问题 var str="http://ladjkfldfjlfjlafjlfk/-1-1.html?sdlfjsdlkfjsdlfjo";//这是一个url //要求把URL里面-1.html

  • JS仿百度搜索自动提示框匹配查询功能

    1. 添加动态加载css文件 不需要引入css css全部在JS动态生成.2. 不需要额外的标签 只需要一个input输入框 并且默认指定一个class类名为 "inputElem" 当然也可以自己配置参数 还需要一个当前父级容器增加一个默认类名 parentCls(也可以自己配置),因为输入框匹配值后需要一个隐藏域 所以需要隐藏域增加一个class "hiddenCls" 当然也支持自己配置参数. 如下代码: 复制代码 代码如下: <div class=&q

  • js 正则表达式学习笔记之匹配字符串

    js 正则表达式学习笔记之匹配字符串

    今天看了第5章几个例子,有点收获,记录下来当作回顾也当作分享. 关于匹配字符串问题,有很多种类型,今天讨论 js 代码里的字符串匹配.(因为我想学完之后写个语法高亮练手,所以用js代码当作例子) 复制代码 代码如下: var str1 = "我是字符串1哦,快把我取走", str2 = "我是字符串2哦,快把我取走"; 比如这样一个字符串,匹配起来很简单 /"[^"]*"/g 即可.   PS: 白色截图是 chrome 34 控制台中

  • js实现带搜索功能的下拉框实时搜索实时匹配

    js实现带搜索功能的下拉框实时搜索实时匹配

    1. 当select输入框中每输入一点内容的时候,在option中找出与内容匹配的选项显示在option的前面选项中. 2. 如何获取每次输入的内容,当keyup的时候触发函数. 问题:select标签中可以输入内容吗?(解决:另一篇文章可选择和输入的下拉列表框 ) 3. 如何获得输入框中的内容?(解决,在输入框上添加onkeyup时间触发的函数用js获得) 4. 如何匹配?(解决) 4.1 如何获得所有option中的内容?(解决) 复制代码 代码如下: function getSelectT

  • js正则表达式之$1$2$3$4$5$6$7$8$9属性，返回子匹配的结果

    功能:$1-$9存放着正则表达式中最近的9个正则表达式的匹配结果,这些结果按照子匹配的出现顺序依次排列. 基本语法RegExp.$n 注意:这些属性是静态的,除了replace中的第二个参数可以省略RegExp之外,其他地方使用都要加上RegExp. 案例讲解:demo1 复制代码 代码如下: <html> <script language="javascript" type="text/javascript"> //创建要进行匹配的字符串

  • Java/Js下使用正则表达式匹配嵌套Html标签

    Java/Js下使用正则表达式匹配嵌套Html标签

    通用 HTML 标签区配正则 最近看网站日志,发现有人在博客上转了我不知道几年前写的一个匹配 HTML 标签的正则,刚好最近也在做一些相关的事情,顿时来了兴趣.就拿回来改改,成了下面这样,可能会有一些 case 遗漏,欢迎修改,已知在内嵌 <script> 复杂内容的处理能力较弱,不过对纯 HTML 来说已经够用,拿来做一些分析工具还是不错滴. 复制代码 代码如下: <script type="text/javascript"> var str = "

  • 仿百度的关键词匹配搜索示例

    复制代码 代码如下: <!DOCTYPE html> <html> <head> <meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> <title>关键词匹配搜索仿百度</title> <meta name="description" content=" 内容介绍不超过10

  • 1秒50万字!js实现关键词匹配

    1秒50万字!js实现关键词匹配

    在论坛和聊天室这样的场景里,为了保证用户体验,我们经常需要屏蔽很多不良词语.对于单个关键词查找,自然是indexOf.正则那样的方式效率比较高.但对于关键词较多的情况下,多次重复调用indexOf.正则的话去匹配全文的话,性能消耗非常大.由于目标字符串通常来说体积都比较大,所以必须要保证一次遍历就得到结果.根据这样的需求,很容易就想到对全文每个字符依次匹配的方式.比如对于这段文字:"Mike Jordan had said "Just do IT", so Mark has

随机推荐