精华内容
下载资源
问答
  • Python实现列表匹配

    万次阅读 2018-06-09 22:40:00
    每个文章对应一个list,里面包含着[文件名,分词1,分词2...我们认为交集元素数目最多的最匹配,一样多的情况下,分词的序号(例如分词1、分词3、分词10的1、3、10)代表着其重要性,计算他们的和,越小则优先级最高。

    注:此为项目之前所作利用Python实现文档的分词及词频统计的后续工作,主要做推荐所用。该代码相比普适性不强,只是针对项目所需编写。下面是链接:python3.6实现文档词频统计 - CSDN博客

    https://blog.csdn.net/yanjiaxin1996/article/details/80629597

    摘要:每个文章对应一个list,里面包含着[文件名,分词1,分词2,。。。。,分词15],。要进行文章的最佳匹配与推荐,思路是以15个分词作为特征,进行list与list之间的交集运算。我们认为交集元素数目最多的最匹配,一样多的情况下,分词的序号(例如分词1、分词3、分词10的1、3、10)代表着其重要性,计算他们的和,越小则优先级最高。

    难点的详细解释放在代码后面。

    环境:win10+pycharm2018.1+Python3.6

    第三方库:无

    输入:python3.6实现文档词频统计 - CSDN博客 最后生成的 分词结果汇总.txt

    输入文件示例(不必一致,只是为了运行结果说明):

    PTA.docx,节点,题目,存储,输出,算法,做法,路径,循环,集合,时间,数据,元素,最小,数组,两个
    高级程序设计语言.docx,方法,对象,类型,变量,语句,数组,int,Java,执行,String,实例,数据,循环,声明,引用
    计算机组成原理复习纲要.docx,中断,方式,地址,CPU,周期,指令,程序,执行,设备,寄存器,寻址,DMA,数据,主存,接口
    离散数学合子童.docx,运算,关系,元素,系统,生成,代数,同态,函数,排列,单位,映射,盒子,原理,递推,an
    软件工程内部终版.docx,系统,测试,需求,设计,过程,开发,软件,功能,模型,描述,故障,活动,对象,关系,时间
    山软智库_计算机网络_1-41.txt,发送,数据,网络,协议,接收,传输,连接,信号,服务,智库,山软,地址,信道,TCP,主机
    数据库_可编辑.docx,属性,事务,关系,数据,索引,元组,记录,查询,连接,实体,函数,Ti,依赖,搜索,数据库
    智库内部编辑版_操作系统概念.docx,进程,系统,文件,内存,磁盘,线程,程序,调度,资源,用户,执行,访问,等待,时间,地址1
    面向对象开发技术(1).doc,对象,方法,public,继承,接口,模式,子类,定义,抽象,实例,void,类型,父类,属性,new
    数据结构复习纲要见解.doc,元素,节点,链表,数组,操作,插入,搜索,描述,路径,删除,二叉树,时间,排序,遍历,位置
    Alpha_1_操作系统概念_16-20.txt,进程,调度,程序,PCB,系统,CPU,状态,执行,内存,fork,创建,3.1,信息,上下文,切换
    Alpha_1_操作系统概念_61-70.txt,内存,页表,地址,进程,逻辑,空间,分配,分页,碎片,大小,偏移量,长度,寄存器,作业,吉鹏

    代码:

    fr = open("分词结果汇总.txt")
    data = []
    for line in fr:
        line = line.replace("\n", "")
        data.append(line.split(","))
    fr.close()
    
    #把标签list转化合并为string,并加在每篇文章的最后一列
    def list2String():
        for i in range(len(data)):
            string = ""
            for j in range(1,len(data)-1):
                string=string+data[i][j]
            data[i].append(string)
    
        print (data)
    
    #python 两个list 求交集,并集,差集 - CSDN博客  https://blog.csdn.net/bitcarmanlee/article/details/51622263
    #获取两个list的交集 返回值是list
    def intersection(listA,listB):
        #求交集的两种方式
        retA = [i for i in listA if i in listB]
        # retB = list(set(listA).intersection(set(listB)))
        return retA
    #获取两个list的并集 返回值是list
    def union(listA,listB):
        #求并集
        retC = list(set(listA).union(set(listB)))
        return retC
    #获取两个list的补集 返回值是list
    def complement(listA,listB):
        #求差集,在B中但不在A中
        retD = list(set(listB).difference(set(listA)))
        return retD
    
    #获取权重最小的序号index
    def getMinIndex(list):
        min=100
        if(len(list)==1):
            index=0
        else:
            for i in range(len(list)):
                if (list[i] < min):
                    min = list[i]
                    index = i
        return index
    
    #寻找与其最相似的文章
    def findSimilarity(singleDataAsList):
        # 生成包含匹配数目最多的文章的列表。如[[7, '进程', '内存'], [10, '进程', '内存']]
        allresult = [["初始值"]]
        max = -1
        for i in range(len(data)):
            if (data[i]!=singleDataAsList): #不能与自身比较
                a = data[i]
                intersectionResult = intersection(a,singleDataAsList)
                print (intersectionResult)
                if (len(intersectionResult) > max and len(intersectionResult) != 0):  # and len(intersectionResult)!=0
                    max = len(intersectionResult)
                    allresult.pop()
                    intersectionResult.insert(0, i)
                    allresult.append(intersectionResult)
                elif (len(intersectionResult) == max):
                    intersectionResult.insert(0, i)
                    allresult.append(intersectionResult)
    
        # 生成相应的列表的权重 如[5, 10]
        allweight = [0] * len(allresult)
        for i in range(len(allresult)):
            for j in range(1, len(allresult[i])):
                for k in range(len(data[allresult[i][0]])):
                    if (data[allresult[i][0]][k] == allresult[i][j]):
                        allweight[i] = allweight[i] + k
    
        print (allresult)
        print (allweight)
    
        minIndex = getMinIndex(allweight)
        title = data[allresult[minIndex][0]][0]
    
        print ("最匹配的文章是:" + title)
    
    b=data[-1]  #以最后一篇文章示例
    findSimilarity(b)

    运行结果不生成文件,只打印信息,如图所示:


    因为我们是拿最后一篇文章来做例子的,最后一篇文章是截取的操作系统内存部分章节的内容。那么理应我们得到的最匹配的文字是操作系统的文档。结果证明与预想的符合,该推荐还是有一定意义的。

    评价总结:

    推荐效果:所做测试不是很多,但效果尚可接受,均与预想符合。

    耗时:非常短,大约一秒就可完成。采用列表匹配后大大节省了时间。

    重点解释:

    1.为什么用列表匹配,而不用建立稀疏矩阵,计算cos等常规方法?

    因为文档对于实际项目是未知的,所以无法确定的文档的分词会产生什么结果,所以无法建立一些预定的分词。其次由于分词的多样行,即使我们预先定义好一些同义词和近义词,仍然是一个巨大的分词库。这样势必会导致产生的文档*分词的矩阵极其稀疏,当文档数目达到一定量时,运算耗时会成指数增长。考虑到时间因素,不得已放弃常规方法。

    采用list匹配,优化的部分在于省去一些本不必要的计算,比如两篇文档的交集本就为0或者为1(代指很少),这种根本无需进行cos计算,因为根本不可能是最优结果。所以用list匹配先求出交集,在交集最多的几个候选集里再次计算。这样虽然比计算cos相似度在精确度方面有不足,但是大大节约了运算时间和资源,性价比较高。

    2.如何进行列表匹配?

    一开始想到的是最基础的设置几个for循环,但对于for循环要慎重考虑。毕竟当文档数目很多后,for循环是指数增长的罪魁祸首。后来查阅一些资料,在一篇博客里发现不错的解决方案。

    python 两个list 求交集,并集,差集 - CSDN博客  https://blog.csdn.net/bitcarmanlee/article/details/51622263

    里面提供了两种方法,选用其中一种即可。(代码注释里有解释,可看代码)

    3.对于交集数目同样的文档怎么进一步划分?

    首先要明确,有同样数目的交集,并不代表相似程度就一样。回过头来捋一捋,我们假定分词代表着文章的内容,词频越高代表性越强。我们的list里面也是按词频的大小排序的。所以有同样元素数目的交集,元素的代表性(词频)也是不一样的,这就是我们二次筛选的依据。即利用分词的序号(例如分词1、分词3、分词10的1、3、10)来模拟词频,模拟重要性。


    如上图所示,这三篇文章的分词的交集的重要度的和分别是13,5,10。前面的2,7,10是文章序号。数目越小,重要性越高。故第7篇文章最符合,根据前面的序号(7)匹配到文章名,输出最后的结果。


    展开全文
  • python 字典快速匹配

    万次阅读 2018-07-03 10:20:41
    有时候我们在生成模型的时候,会出现在一个好 几十万 的字典 dict 里面匹配数据,但往往这种方法造成的时间损耗是巨大的。 比如以下代码: # word_index 就是有几十万数据的词汇字典 # post 就是分词后的文档 for...

    有时候我们在生成模型的时候,会出现在一个好 几十万 的字典 dict 里面匹配数据,但往往这种方法造成的时间损耗是巨大的。

    比如以下代码:

    # word_index 就是有几十万数据的词汇字典
    # post 就是分词后的文档
    for w in post.split(" "):
        if w in word_index.keys():
            word_model.append(word_index[w])
    

    这种方法往往是非常耗时的,但我们可以使用 pandas 模块实现这个快速匹配的问题,示例如下

    # -*- coding:utf-8 -*-
    import pandas as pd
    # 词汇字典
    ss = {"a":1,"b":2,"c":3,"d":4,"e":5}
    
    # 文档分词
    uu = ["a","c","f","d","b","h","e"]
    
    # 将文档分词转换成 DF
    article = pd.DataFrame({"word":uu})
    
    # 将词汇字典也转换成 DF
    wordid = pd.DataFrame({"word":[s[0] for s in ss.items()],"id":[s[1] for s in ss.items()]})
    # 对字典设置索引
    wordid.set_index("word")
    
    # 进行匹配
    df_inner = pd.merge(article,wordid,how = "inner")
    print list(df_inner["id"])
    

    更多的关于 pandas 的用法:https://blog.csdn.net/liufang0001/article/details/77856255

    展开全文
  • opencv+python实现图像匹配----模板匹配、特征点匹配

    万次阅读 多人点赞 2019-02-12 16:30:46
    文章目录模板匹配与特征匹配python的版本及依赖的库的安装opencv+python模板匹配[^1]匹配材料Template Matchingopencv+python特征匹配[^2]匹配材料BFMatching描述特征点--运行结果不精确基于FLANN的匹配器(FLANN ...

    模板匹配与特征匹配

    • 模板匹配:模板匹配是一种最原始、最基本的模式识别方法,研究某一特定对象物的图案位于图像的什么地方,进而识别对象物,这就是一个匹配问题。它是图像处理中最基本、最常用的匹配方法。模板匹配具有自身的局限性,主要表现在它只能进行平行移动,若原图像中的匹配目标发生旋转或大小变化,该算法无效。
    • 特征匹配:所谓特征匹配(FBM),就是指将从影像中提取的特征作为共轭实体,而将所提特征属性或描述参数(实际上是特征的特征,也可以认为是影像的特征)作为匹配实体,通过计算匹配实体之间的相似性测度以实现共轭实体配准的影像匹配方法。在匹配目标发生旋转或大小变化时,该算法依旧有效。

    python的版本及依赖的库的安装

    #版本python 3.7.1
    pip install numpy==1.15.3
    pip install matplotlib==3.0.1
    pip install opencv-python==3.4.2.16
    pip install opencv-contrib-python==3.4.2.16
    

    opencv+python模板匹配1

    匹配材料

    • 目标图片:target.jpg
      target
    • 模板图片:template.jpg
      template

    模板匹配Template Matching----单目标匹配

    #opencv模板匹配----单目标匹配
    import cv2
    #读取目标图片
    target = cv2.imread("target.jpg")
    #读取模板图片
    template = cv2.imread("template.jpg")
    #获得模板图片的高宽尺寸
    theight, twidth = template.shape[:2]
    #执行模板匹配,采用的匹配方式cv2.TM_SQDIFF_NORMED
    result = cv2.matchTemplate(target,template,cv2.TM_SQDIFF_NORMED)
    #归一化处理
    cv2.normalize( result, result, 0, 1, cv2.NORM_MINMAX, -1 )
    #寻找矩阵(一维数组当做向量,用Mat定义)中的最大值和最小值的匹配结果及其位置
    min_val, max_val, min_loc, max_loc = cv2.minMaxLoc(result)
    #匹配值转换为字符串
    #对于cv2.TM_SQDIFF及cv2.TM_SQDIFF_NORMED方法min_val越趋近与0匹配度越好,匹配位置取min_loc
    #对于其他方法max_val越趋近于1匹配度越好,匹配位置取max_loc
    strmin_val = str(min_val)
    #绘制矩形边框,将匹配区域标注出来
    #min_loc:矩形定点
    #(min_loc[0]+twidth,min_loc[1]+theight):矩形的宽高
    #(0,0,225):矩形的边框颜色;2:矩形边框宽度
    cv2.rectangle(target,min_loc,(min_loc[0]+twidth,min_loc[1]+theight),(0,0,225),2)
    #显示结果,并将匹配值显示在标题栏上
    cv2.imshow("MatchResult----MatchingValue="+strmin_val,target)
    cv2.waitKey()
    cv2.destroyAllWindows()
    

    运行结果:
    MatchResult
    可以看到显示的min_val的值为0.0,说明完全匹配。

    模板匹配Template Matching----多目标匹配

    • 目标图片:target.jpg
      多目标匹配目标图片
    #opencv模板匹配----多目标匹配
    import cv2
    import numpy
    #读取目标图片
    target = cv2.imread("target.jpg")
    #读取模板图片
    template = cv2.imread("template.jpg")
    #获得模板图片的高宽尺寸
    theight, twidth = template.shape[:2]
    #执行模板匹配,采用的匹配方式cv2.TM_SQDIFF_NORMED
    result = cv2.matchTemplate(target,template,cv2.TM_SQDIFF_NORMED)
    #归一化处理
    #cv2.normalize( result, result, 0, 1, cv2.NORM_MINMAX, -1 )
    #寻找矩阵(一维数组当做向量,用Mat定义)中的最大值和最小值的匹配结果及其位置
    min_val, max_val, min_loc, max_loc = cv2.minMaxLoc(result)
    #绘制矩形边框,将匹配区域标注出来
    #min_loc:矩形定点
    #(min_loc[0]+twidth,min_loc[1]+theight):矩形的宽高
    #(0,0,225):矩形的边框颜色;2:矩形边框宽度
    cv2.rectangle(target,min_loc,(min_loc[0]+twidth,min_loc[1]+theight),(0,0,225),2)
    #匹配值转换为字符串
    #对于cv2.TM_SQDIFF及cv2.TM_SQDIFF_NORMED方法min_val越趋近与0匹配度越好,匹配位置取min_loc
    #对于其他方法max_val越趋近于1匹配度越好,匹配位置取max_loc
    strmin_val = str(min_val)
    #初始化位置参数
    temp_loc = min_loc
    other_loc = min_loc
    numOfloc = 1
    #第一次筛选----规定匹配阈值,将满足阈值的从result中提取出来
    #对于cv2.TM_SQDIFF及cv2.TM_SQDIFF_NORMED方法设置匹配阈值为0.01
    threshold = 0.01
    loc = numpy.where(result<threshold)
    #遍历提取出来的位置
    for other_loc in zip(*loc[::-1]):
        #第二次筛选----将位置偏移小于5个像素的结果舍去
        if (temp_loc[0]+5<other_loc[0])or(temp_loc[1]+5<other_loc[1]):
            numOfloc = numOfloc + 1
            temp_loc = other_loc
            cv2.rectangle(target,other_loc,(other_loc[0]+twidth,other_loc[1]+theight),(0,0,225),2)
    str_numOfloc = str(numOfloc)
    #显示结果,并将匹配值显示在标题栏上
    strText = "MatchResult----MatchingValue="+strmin_val+"----NumberOfPosition="+str_numOfloc
    cv2.imshow(strText,target)
    cv2.waitKey()
    cv2.destroyAllWindows()
    

    运行结果:
    多目标匹配运行结果

    opencv+python特征匹配2

    匹配材料

    • 目标图片:target.jpg
      target

    • 模板图片:template_adjst.jpg
      template_adjst

    BFMatching描述特征点–运行结果不精确

    #opencv----特征匹配----BFMatching
    import cv2
    from matplotlib import pyplot as plt
    #读取需要特征匹配的两张照片,格式为灰度图。
    template=cv2.imread("template_adjust.jpg",0)
    target=cv2.imread("target.jpg",0)
    orb=cv2.ORB_create()#建立orb特征检测器
    kp1,des1=orb.detectAndCompute(template,None)#计算template中的特征点和描述符
    kp2,des2=orb.detectAndCompute(target,None) #计算target中的
    bf = cv2.BFMatcher(cv2.NORM_HAMMING,crossCheck=True) #建立匹配关系
    mathces=bf.match(des1,des2) #匹配描述符
    mathces=sorted(mathces,key=lambda x:x.distance) #据距离来排序
    result= cv2.drawMatches(template,kp1,target,kp2,mathces[:40],None,flags=2) #画出匹配关系
    plt.imshow(result),plt.show() #matplotlib描绘出来
    

    基于FLANN的匹配器(FLANN based Matcher)描述特征点

    # 
    '''
    基于FLANN的匹配器(FLANN based Matcher)
    1.FLANN代表近似最近邻居的快速库。它代表一组经过优化的算法,用于大数据集中的快速最近邻搜索以及高维特征。
    2.对于大型数据集,它的工作速度比BFMatcher快。
    3.需要传递两个字典来指定要使用的算法及其相关参数等
    对于SIFT或SURF等算法,可以用以下方法:
    index_params = dict(algorithm = FLANN_INDEX_KDTREE, trees = 5)
    对于ORB,可以使用以下参数:
    index_params= dict(algorithm = FLANN_INDEX_LSH,
                       table_number = 6, # 12   这个参数是searchParam,指定了索引中的树应该递归遍历的次数。值越高精度越高
                       key_size = 12,     # 20
                       multi_probe_level = 1) #2
    '''
    import cv2 as cv
    from matplotlib import pyplot as plt
    queryImage=cv.imread("template_adjust.jpg",0)
    trainingImage=cv.imread("target.jpg",0)#读取要匹配的灰度照片
    sift=cv.xfeatures2d.SIFT_create()#创建sift检测器
    kp1, des1 = sift.detectAndCompute(queryImage,None)
    kp2, des2 = sift.detectAndCompute(trainingImage,None)
    #设置Flannde参数
    FLANN_INDEX_KDTREE=0
    indexParams=dict(algorithm=FLANN_INDEX_KDTREE,trees=5)
    searchParams= dict(checks=50)
    flann=cv.FlannBasedMatcher(indexParams,searchParams)
    matches=flann.knnMatch(des1,des2,k=2)
    #设置好初始匹配值
    matchesMask=[[0,0] for i in range (len(matches))]
    for i, (m,n) in enumerate(matches):
    	if m.distance< 0.5*n.distance: #舍弃小于0.5的匹配结果
    		matchesMask[i]=[1,0]
    drawParams=dict(matchColor=(0,0,255),singlePointColor=(255,0,0),matchesMask=matchesMask,flags=0) #给特征点和匹配的线定义颜色
    resultimage=cv.drawMatchesKnn(queryImage,kp1,trainingImage,kp2,matches,None,**drawParams) #画出匹配的结果
    plt.imshow(resultimage,),plt.show()
    

    运行结果:
    MatchResult

    基于FLANN的匹配器(FLANN based Matcher)定位图片

    #基于FLANN的匹配器(FLANN based Matcher)定位图片
    import numpy as np
    import cv2
    from matplotlib import pyplot as plt
     
    MIN_MATCH_COUNT = 10 #设置最低特征点匹配数量为10
    template = cv2.imread('template_adjust.jpg',0) # queryImage
    target = cv2.imread('target.jpg',0) # trainImage
    # Initiate SIFT detector创建sift检测器
    sift = cv2.xfeatures2d.SIFT_create()
    # find the keypoints and descriptors with SIFT
    kp1, des1 = sift.detectAndCompute(template,None)
    kp2, des2 = sift.detectAndCompute(target,None)
    #创建设置FLANN匹配
    FLANN_INDEX_KDTREE = 0
    index_params = dict(algorithm = FLANN_INDEX_KDTREE, trees = 5)
    search_params = dict(checks = 50)
    flann = cv2.FlannBasedMatcher(index_params, search_params)
    matches = flann.knnMatch(des1,des2,k=2)
    # store all the good matches as per Lowe's ratio test.
    good = []
    #舍弃大于0.7的匹配
    for m,n in matches:
        if m.distance < 0.7*n.distance:
            good.append(m)
    if len(good)>MIN_MATCH_COUNT:
        # 获取关键点的坐标
        src_pts = np.float32([ kp1[m.queryIdx].pt for m in good ]).reshape(-1,1,2)
        dst_pts = np.float32([ kp2[m.trainIdx].pt for m in good ]).reshape(-1,1,2)
        #计算变换矩阵和MASK
        M, mask = cv2.findHomography(src_pts, dst_pts, cv2.RANSAC, 5.0)
        matchesMask = mask.ravel().tolist()
        h,w = template.shape
        # 使用得到的变换矩阵对原图像的四个角进行变换,获得在目标图像上对应的坐标
        pts = np.float32([ [0,0],[0,h-1],[w-1,h-1],[w-1,0] ]).reshape(-1,1,2)
        dst = cv2.perspectiveTransform(pts,M)
        cv2.polylines(target,[np.int32(dst)],True,0,2, cv2.LINE_AA)
    else:
        print( "Not enough matches are found - %d/%d" % (len(good),MIN_MATCH_COUNT))
        matchesMask = None
    draw_params = dict(matchColor=(0,255,0), 
                       singlePointColor=None,
                       matchesMask=matchesMask, 
                       flags=2)
    result = cv2.drawMatches(template,kp1,target,kp2,good,None,**draw_params)
    plt.imshow(result, 'gray')
    plt.show()
    

    运行结果:
    FLANN匹配定位

    参考资料

    1.opencv英文版文档大全
    2.opencv中文网、论坛
    3.opencv的版本不对可能出现的一个错误


    1. 模板匹配英文版教程–opencv–version:3.4.2
      模板匹配中文版教程–opencv–version:2.3.2 ↩︎

    2. FLANN特征点匹配英文版教程–opencv–version:3.4.2
      FLANN特征点匹配中文版教程–opencv–version:2.3.2 ↩︎

    展开全文
  • Python实现多模匹配——AC自动机

    千次阅读 2020-02-10 13:23:32
    Python实现多模匹配——AC自动机 目标:学习AC自动机,多模匹配。 要求:尽可能用纯Python实现,提升代码的扩展性。 一、什么是AC自动机? AC自动机,Aho-Corasick automaton,该算法在1975年产生于贝尔...

                                                          Python实现多模匹配——AC自动机

     

    目标:学习AC自动机,多模匹配。

    要求:尽可能用纯Python实现,提升代码的扩展性。

     

    一、什么是AC自动机?

            AC自动机,Aho-Corasick automaton,该算法在1975年产生于贝尔实验室,是著名的多模匹配算法。要学会AC自动机,我们必 须知道什么是Trie,也就是字典树。Trie树,又称单词查找树或键树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。

                                                                                                                                                                                               ——摘自百度百科

    二、AC自动机用来做什么?

            一个常见的例子就是给出n个单词,再给出一段包含m个字符的文章,让你找出有多少个单词在文章里出现过。要搞懂AC自动机,先得有模式树(字典树)Trie和KMP模式匹配算法的基础知识。AC自动机算法分为3步:构造一棵Trie树,构造失败指针和模式匹配过程。

            如果你对KMP算法了解的话,应该知道KMP算法中的next函数(shift函数或者fail函数)是干什么用的。KMP中我们用两个指针i和j分别表示,A[i-j+ 1..i]与B[1..j]完全相等。也就是说,i是不断增加的,随着i的增加j相应地变化,且j满足以A[i]结尾的长度为j的字符串正好匹配B串的前 j个字符,当A[i+1]≠B[j+1],KMP的策略是调整j的位置(减小j值)使得A[i-j+1..i]与B[1..j]保持匹配且新的B[j+1]恰好与A[i+1]匹配,而next函数恰恰记录了这个j应该调整到的位置。同样AC自动机的失败指针具有同样的功能,也就是说当我们的模式串在Trie上进行匹配时,如果与当前节点的关键字不能继续匹配,就应该去当前节点的失败指针所指向的节点继续进行匹配。

     

    三、AC自动机的Python安装

    安装过这个包的朋友,相信都遇到过各种坑。

    1、pip安装

    官网:https://pypi.org/project/pyahocorasick/。源码下载:

    安装方式:pip install pyahocorasick(python3),但尝试过的朋友会发现,这个包需要C编译器,如果自己的电脑中没有安装C编译器,是安装不成功的。pip install ahocorasick(python2)也无法安装。具体报错代码:

    pip install pyahocorasick
    
    Collecting pyahocorasick
      Using cached https://files.pythonhosted.org/packages/f4/9f/f0d8e8850e12829eea2e778f1c90e3c53a9a799b7f412082a5d21cd19ae1/pyahocorasick-1.4.0.tar.gz
    Building wheels for collected packages: pyahocorasick
      Running setup.py bdist_wheel for pyahocorasick ... error
      Complete output from command /anaconda3/bin/python -u -c "import setuptools, tokenize;__file__='/private/var/folders/jd/6t6rh0991m72k_vxp02p7f440000gn/T/pip-install-_tg58exd/pyahocorasick/setup.py';f=getattr(tokenize, 'open', open)(__file__);code=f.read().replace('\r\n', '\n');f.close();exec(compile(code, __file__, 'exec'))" bdist_wheel -d /private/var/folders/jd/6t6rh0991m72k_vxp02p7f440000gn/T/pip-wheel-rbzdosp6 --python-tag cp37:
      running bdist_wheel
      running build
      running build_ext
      building 'ahocorasick' extension
      creating build
      creating build/temp.macosx-10.7-x86_64-3.7
      gcc -Wno-unused-result -Wsign-compare -Wunreachable-code -DNDEBUG -g -fwrapv -O3 -Wall -Wstrict-prototypes -I/anaconda3/include -arch x86_64 -I/anaconda3/include -arch x86_64 -DAHOCORASICK_UNICODE= -I/anaconda3/include/python3.7m -c pyahocorasick.c -o build/temp.macosx-10.7-x86_64-3.7/pyahocorasick.o
      xcrun: error: invalid active developer path (/Library/Developer/CommandLineTools), missing xcrun at: /Library/Developer/CommandLineTools/usr/bin/xcrun
      error: command 'gcc' failed with exit status 1
      
      ----------------------------------------
      Failed building wheel for pyahocorasick
      Running setup.py clean for pyahocorasick
    Failed to build pyahocorasick
    Installing collected packages: pyahocorasick
      Running setup.py install for pyahocorasick ... error
        Complete output from command /anaconda3/bin/python -u -c "import setuptools, tokenize;__file__='/private/var/folders/jd/6t6rh0991m72k_vxp02p7f440000gn/T/pip-install-_tg58exd/pyahocorasick/setup.py';f=getattr(tokenize, 'open', open)(__file__);code=f.read().replace('\r\n', '\n');f.close();exec(compile(code, __file__, 'exec'))" install --record /private/var/folders/jd/6t6rh0991m72k_vxp02p7f440000gn/T/pip-record-5oyl9c1l/install-record.txt --single-version-externally-managed --compile:
        running install
        running build
        running build_ext
        building 'ahocorasick' extension
        creating build
        creating build/temp.macosx-10.7-x86_64-3.7
        gcc -Wno-unused-result -Wsign-compare -Wunreachable-code -DNDEBUG -g -fwrapv -O3 -Wall -Wstrict-prototypes -I/anaconda3/include -arch x86_64 -I/anaconda3/include -arch x86_64 -DAHOCORASICK_UNICODE= -I/anaconda3/include/python3.7m -c pyahocorasick.c -o build/temp.macosx-10.7-x86_64-3.7/pyahocorasick.o
        xcrun: error: invalid active developer path (/Library/Developer/CommandLineTools), missing xcrun at: /Library/Developer/CommandLineTools/usr/bin/xcrun
        error: command 'gcc' failed with exit status 1
        
        ----------------------------------------
    Command "/anaconda3/bin/python -u -c "import setuptools, tokenize;__file__='/private/var/folders/jd/6t6rh0991m72k_vxp02p7f440000gn/T/pip-install-_tg58exd/pyahocorasick/setup.py';f=getattr(tokenize, 'open', open)(__file__);code=f.read().replace('\r\n', '\n');f.close();exec(compile(code, __file__, 'exec'))" install --record /private/var/folders/jd/6t6rh0991m72k_vxp02p7f440000gn/T/pip-record-5oyl9c1l/install-record.txt --single-version-externally-managed --compile" failed with error code 1 in /private/var/folders/jd/6t6rh0991m72k_vxp02p7f440000gn/T/pip-install-_tg58exd/pyahocorasick/

    如果直接下载Github中的源码,在使用ahocorasick.Automaton()函数会报错。那怎么办?

    个人尝试着安装ahocorasick-python,官网:https://pypi.org/project/ahocorasick-python/,GitHub源码:源码

    但是结果发现Mac/Linux系统可以使用,Win10不行?瞬间无语了。demo环境用的是win10。

     

    2、解决方案

    网上查找了一些解决方案,主要包括三种:

    (1)老老实实地装C编译器;

    (2)python使用esmre代替ahocorasick实现ac自动机多模匹配

    (3)个人改写ahocorasick——Python下的ahocorasick实现快速的关键字匹配

     

    四、ahocorasick的Python代码

    1、Python2代码:

    # python2
    # coding=utf-8
    
    KIND = 16
    
    class Node():
        static = 0
    
        def __init__(self):
            self.fail = None
            self.next = [None] * KIND
            self.end = False
            self.word = None
            Node.static += 1
    
    
    class AcAutomation():
        def __init__(self):
            self.root = Node()
            self.queue = []
    
        def getIndex(self, char):
            return ord(char)  # - BASE
    
        def insert(self, string):
            p = self.root
            for char in string:
                index = self.getIndex(char)
                if p.next[index] == None:
                    p.next[index] = Node()
                p = p.next[index]
            p.end = True
            p.word = string
    
        def build_automation(self):
            self.root.fail = None
            self.queue.append(self.root)
            while len(self.queue) != 0:
                parent = self.queue[0]
                self.queue.pop(0)
                for i, child in enumerate(parent.next):
                    if child == None: continue
                    if parent == self.root:
                        child.fail = self.root
                    else:
                        failp = parent.fail
                        while failp != None:
                            if failp.next[i] != None:
                                child.fail = failp.next[i]
                                break
                            failp = failp.fail
                        if failp == None: child.fail = self.root
                    self.queue.append(child)
    
        def matchOne(self, string):
            p = self.root
            for char in string:
                index = self.getIndex(char)
                while p.next[index] == None and p != self.root: p = p.fail
                if p.next[index] == None:
                    p = self.root
                else:
                    p = p.next[index]
                if p.end: return True, p.word
            return False, None
    
    
    class UnicodeAcAutomation():
        def __init__(self, encoding='utf-8'):
            self.ac = AcAutomation()
            self.encoding = encoding
    
        def getAcString(self, string):
            string = bytearray(string.encode(self.encoding))
            ac_string = ''
            for byte in string:
                ac_string += chr(byte % 16)
                ac_string += chr(byte / 16)
            # print ac_string
            return ac_string
    
        def insert(self, string):
            if type(string) != unicode:
                raise Exception('UnicodeAcAutomation:: insert type not unicode')
            ac_string = self.getAcString(string)
            self.ac.insert(ac_string)
    
        def build_automation(self):
            self.ac.build_automation()
    
        def matchOne(self, string):
            if type(string) != unicode:
                raise Exception('UnicodeAcAutomation:: insert type not unicode')
            ac_string = self.getAcString(string)
            retcode, ret = self.ac.matchOne(ac_string)
            if ret != None:
                s = ''
                for i in range(len(ret) / 2):
                    tmp = chr(ord(ret[2 * i]) + ord(ret[2 * i + 1]) * 16)
                    s += tmp
                ret = s.decode('utf-8')
            return retcode, ret
    
    
    def main():
        ac = UnicodeAcAutomation()
        ac.insert(u'丁亚光')
        ac.insert(u'好吃的')
        ac.insert(u'好玩的')
        ac.build_automation()
    
        print(ac.matchOne(u'hi,丁亚光在干啥'))
        print(ac.matchOne(u'ab'))
        print(ac.matchOne(u'不能吃饭啊'))
        print(ac.matchOne(u'饭很好吃,有很多好好的吃的,'))
        print(ac.matchOne(u'有很多好玩的'))
    
    
    if __name__ == '__main__':
        main()

    输出:

    (True, u'\u4e01\u4e9a\u5149')
    (False, None)
    (False, None)
    (False, None)
    (True, u'\u597d\u73a9\u7684')

    可能很多朋友习惯了Python3,这里提供个人修改后的代码(主要是编码格式的修改)


    2、Python3

    # python3
    # coding=utf-8
    
    KIND = 16
    
    class Node():
        static = 0
    
        def __init__(self):
            self.fail = None
            self.next = [None] * KIND
            self.end = False
            self.word = None
            Node.static += 1
    
    
    class AcAutomation():
        def __init__(self):
            self.root = Node()
            self.queue = []
    
        def getIndex(self, char):
            return ord(char)  # - BASE
    
        def insert(self, string):
            p = self.root
            for char in string:
                index = self.getIndex(char)
                if p.next[index] == None:
                    p.next[index] = Node()
                p = p.next[index]
            p.end = True
            p.word = string
    
        def build_automation(self):
            self.root.fail = None
            self.queue.append(self.root)
            while len(self.queue) != 0:
                parent = self.queue[0]
                self.queue.pop(0)
                for i, child in enumerate(parent.next):
                    if child == None: continue
                    if parent == self.root:
                        child.fail = self.root
                    else:
                        failp = parent.fail
                        while failp != None:
                            if failp.next[i] != None:
                                child.fail = failp.next[i]
                                break
                            failp = failp.fail
                        if failp == None: child.fail = self.root
                    self.queue.append(child)
    
        def matchOne(self, string):
            p = self.root
            for char in string:
                index = self.getIndex(char)
                while p.next[index] == None and p != self.root: p = p.fail
                if p.next[index] == None:
                    p = self.root
                else:
                    p = p.next[index]
                if p.end: return True, p.word
            return False, None
    
    
    class UnicodeAcAutomation():
        def __init__(self, encoding='utf-8'):
            self.ac = AcAutomation()
            self.encoding = encoding
    
        def getAcString(self, string):
            string = bytearray(string.encode(self.encoding))
            ac_string = ''
            for byte in string:
                ac_string += chr(byte % 16)
                ac_string += chr(byte // 16)
            return ac_string
    
        def insert(self, string):
            if type(string) != str:
                raise Exception('StrAcAutomation:: insert type not str')
            ac_string = self.getAcString(string)
            self.ac.insert(ac_string)
    
        def build_automation(self):
            self.ac.build_automation()
    
        def matchOne(self, string):
            if type(string) != str:
                raise Exception('StrAcAutomation:: insert type not str')
            ac_string = self.getAcString(string)
            retcode, ret = self.ac.matchOne(ac_string)
            if ret != None:
                s = ''
                for i in range(len(ret) // 2):
                    s += chr(ord(ret[2 * i]) + ord(ret[2 * i + 1]) * 16)
                ret = s.encode("latin1").decode('utf-8')
            return retcode, ret
    
    
    def main():
        ac = UnicodeAcAutomation()
        ac.insert('丁亚光')
        ac.insert('好吃的')
        ac.insert('好玩的')
        ac.build_automation()
        print(ac.matchOne('hi,丁亚光在干啥'))
        print(ac.matchOne('ab'))
        print(ac.matchOne('不能吃饭啊'))
        print(ac.matchOne('饭很好吃,有很多好好的吃的,'))
        print(ac.matchOne('有很多好玩的'))
    
    
    if __name__ == '__main__':
    

    输出:

    (True, '丁亚光')
    (False, None)
    (False, None)
    (False, None)
    (True, '好玩的')

     

    总结:ahocorasick个人改写的方法还有很多,比如根据ahocorasick-python的源码进行改写。其中ahocorasick-python的核心源码如下。

    # coding:utf-8
    # write by zhou
    # revised by zw
    
    class Node(object):
        """
        节点的抽象
        """
        def __init__(self, str='', is_root=False):
            self._next_p = {}
            self.fail = None
            self.is_root = is_root
            self.str = str
            self.parent = None
    
        def __iter__(self):
            return iter(self._next_p.keys())
    
        def __getitem__(self, item):
            return self._next_p[item]
    
        def __setitem__(self, key, value):
            _u = self._next_p.setdefault(key, value)
            _u.parent = self
    
        def __repr__(self):
            return "<Node object '%s' at %s>" % \
                   (self.str, object.__repr__(self)[1:-1].split('at')[-1])
    
        def __str__(self):
            return self.__repr__()
    
    
    class AhoCorasick(object):
        """
        Ac自动机对象
        """
        def __init__(self, *words):
            self.words_set = set(words)
            self.words = list(self.words_set)
            self.words.sort(key=lambda x: len(x))
            self._root = Node(is_root=True)
            self._node_meta = {}
            self._node_all = [(0, self._root)]
            _a = {}
            for word in self.words:
                for w in word:
                    _a.setdefault(w, set())
                    _a[w].add(word)
    
            def node_append(keyword):
                assert len(keyword) > 0
                _ = self._root
                for _i, k in enumerate(keyword):
                    node = Node(k)
                    if k in _:
                        pass
                    else:
                        _[k] = node
                        self._node_all.append((_i+1, _[k]))
                    self._node_meta.setdefault(id(_[k]),set())
                    if _i >= 1:
                        for _j in _a[k]:
                            if keyword[:_i+1].endswith(_j):
                                self._node_meta[id(_[k])].add((_j, len(_j)))
                    _ = _[k]
                else:
                    if _ != self._root:
                        self._node_meta[id(_)].add((keyword, len(keyword)))
    
            for word in self.words:
                node_append(word)
            self._node_all.sort(key=lambda x: x[0])
            self._make()
    
        def _make(self):
            """
            构造Ac树
            :return:
            """
            for _level, node in self._node_all:
                if node == self._root or _level <= 1:
                    node.fail = self._root
                else:
                    _node = node.parent.fail
                    while True:
                        if node.str in _node:
                            node.fail = _node[node.str]
                            break
                        else:
                            if _node == self._root:
                                node.fail = self._root
                                break
                            else:
                                _node = _node.fail
    
        def search(self, content, with_index=False):
            result = set()
            node = self._root
            index = 0
            for i in content:
                while 1:
                    if i not in node:
                        if node == self._root:
                            break
                        else:
                            node = node.fail
                    else:
                        for keyword, keyword_len in self._node_meta.get(id(node[i]), set()):
                            if not with_index:
                                result.add(keyword)
                            else:
                                result.add((keyword, (index - keyword_len + 1, index + 1)))
                        node = node[i]
                        break
                index += 1
            return result
    
    
    if __name__ == '__main__':
        ac = AhoCorasick("abc", 'abe', 'acdabd', 'bdf', 'df', 'f', 'ac', 'cd', 'cda')
        print(ac.search('acdabdf', True))
    

    输出:

    {('cd', (1, 3)), ('acdabd', (0, 6)), ('df', (5, 7)), ('f', (6, 7)), ('bdf', (4, 7)), ('cda', (1, 4)), ('ac', (0, 2))}

     

    参考文献:

    1、AC自动机的python实现

    2、70行Python实现AC自动机

    3、序列比对(二十六)——精准匹配之KMP算法、Trie树以及AC自动机

    4、关于AC自动机的思考

    展开全文
  • 用于快速查找近似字符串匹配,比方说拼写纠错,或模糊查找,当搜索”aeek”时能返回与其最相似的字符串”seek”和”peek”。 在构建BK树之前,我们需要定义一种用于比较字符串相似度的度量方法。通常都是采用编辑...
  • 如何实现字符串的匹配 题目描述: 给定主字符串 S 与模式字符串 P,判断 P 是否是 S 的子串,如果是,那么找出 P 在 S 中第一次出现的下标。 逐个比较: def match(s,p): if s==None or p==None: print('参数不合理...
  • python实现的多字典的最大正向匹配算法,针对于中医药物数据,对方剂中的“药物组成”属性提取出该字段的包含了那些药物
  • 讲在前面的话,KMP算法是字符串中匹配快速算法,时间复杂度为O(m+n) 。KMP算法的核心思想主要通过分析前面字符串的信息的来滑动匹配字符串,避免当不匹配时像传统匹配算法回溯到匹配字符串的开头,而当不匹配时...
  • OpenCV - 特征匹配Python实现

    千次阅读 2019-07-31 14:48:56
    蛮力( Brute-Force)匹配 Brute-Force匹配非常简单,首先在第一幅图像中选取一个关键点然后依次与第二幅图像的每个关键点进行(描述符)距离测试,最后返回距离最近的关键点. 对于BF匹配器,首先我们必须使用cv2....
  • 傅立叶变换与图像特征定位与模板匹配 ...使用傅立叶变换实现图像卷积可以参考这里:数字图像处理与Python实现-快速傅立叶变换(FFT)实现图像快速卷积。 2.实现步骤 第一步:对图像进行和所械匹配的模板进行傅立
  • Python快速编程入门课后习题答案

    万次阅读 多人点赞 2019-11-24 13:03:43
    五、程序分析题 第十二章 一、选择题 二、判断题 三、填空题 四、简答题 END 前言 本文整理了填空、选择、判断等一些课后习题答案,具体的编程题可以见:Python快速编程入门课后程序题答案。 第一章 一、填空题 ...
  • Python 使用Opencv实现图像特征检测与匹配

    万次阅读 多人点赞 2018-06-13 11:36:58
    本人新书《玩转Python网络爬虫》,可在天猫、京东等商城搜索查阅,项目深入浅出,适合爬虫初学者或者是已经有一些网络爬虫编写经验,但希望更加全面、深入理解Python爬虫的开发人员。 ———-欢迎加入学习交流QQ...
  • 使用Python查找大数据文件中与目标数据匹配的行数据。 代码实现如下: import win32api,win32con import win32ui # #coding=utf-8 import os, time, sys, re #reload(sys) win32api.MessageBox(0, "Select the...
  • 我们知道Excel有一个match函数,可以做数据匹配。 比如要根据人名获取成绩 ...但是如何用python实现这一点呢,我写了一个函数,非常好用,分享给大家。 这个函数考虑到了匹配多个字段,多个sheet。
  • python pandas数据匹配 merge函数

    千次阅读 2019-09-01 09:06:19
    python中pandas数据匹配常用merge函数,其实merge函数就类似于excel中的vlookup hlookup lookup,最近excel又出了一个逆天的xlookup函数,默默地推荐一下,嘿嘿 转载自:...
  • 利用FuzzyWuzzy库匹配字符串1. 背景前言2. FuzzyWuzzy库介绍2.1 安装2.1 fuzz模块2.1.1 简单匹配(Ratio)2.1.2 非完全匹配(Partial Ratio)2.1.3 忽略顺序匹配(Token Sort Ratio)2.1.4 去重子集匹配(Token Set ...
  • 在生活中常常遇到两组元素多对多匹配而又数目有限的情况,我们需要对其进行最大匹配数的分配,使效率最大化。例如,有一组压缩气缸和一组压缩活塞,每一个型号的压缩气缸有一个固定的内径大小,每一个型号的压缩活塞...
  • python openCV学习——快速的图像匹配

    千次阅读 2019-10-30 19:53:00
    由于最近工作中需要用到图像快速图像匹配的事情,在此做一下学习记录。 主要是两个,一个是图像相似度计算,一个是图像模板匹配。 我的学习背景 之前的博客介绍过关于GAutomator的应用。但是GA只是提供一些基于游戏...
  • 对于字符串的查找,我想在爬虫的时候是十分苦恼的,想要找到子串的具体位置,我想大多数人眼睛都会看花; 时间久了之后我们会发现字符串的查找并不是...针对Python语言,我们使用re模块来实现; import re re.search(r
  • Python快速实现实时人脸活体检测

    千次阅读 2020-06-27 16:23:51
    为解决上述问题,小编实现一种基于眨眼检测的人脸活体检测算法,该算法可以通过摄像头实时工作,来区分是正常人脸还是照片。 算法原理具体步骤如下: 在网络摄像头生成的每个帧中检测人脸。 对于每个检测到的脸,...
  • 文章目录1、SIFT1.1、sift的定义1.2、sift算法介绍1.3、特征检测1.4、特征匹配2、python实现2.1、准备工作2.2、代码实现2.3、运行结果 1、SIFT 1.1、sift的定义 SIFT,即尺度不变特征变换(Scale-invariant feature ...
  • 最近有朋友问可否编程来减轻表格整理工作量,今儿我们就通过实例来实现 Python 对表格的自动化整理。首先我们有这么一份数据表 source.csv:我们要做的是从上表中提取数据,来生成一份符合以下要求的表格:按照以下...
  • 详解KMP及其Python实现

    千次阅读 2019-03-03 10:34:49
    详解KMP及其Python实现 一、 KMP是什么 KMP算法是一种改进的字符串匹配算法。KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数,函数...
  • 今天,我们用Python实现简单的人脸识别技术! Python里,简单的人脸识别有很多种方法可以实现,依赖于python胶水语言的特性,我们通过调用包可以快速准确的达成这一目的。这里介绍的是准确性比较高的一种。 欲直接...
  • Python语言对图像实现快速的掩模运算编译环境介绍掩模代码运行结果原图掩模模板处理结果结论 编译环境 编程语言:Python IDE:PyCharm2017 介绍 图像掩模是用选定的图像、图形或物体、对待处理的图像(全部或局部)...
  • opencv-python 特征匹配

    千次阅读 2020-05-05 09:04:40
    使用 OpenCV 中的蛮力(Brute-Force)匹配和 FLANN 匹配 蛮力(Brute-Force)匹配基础 蛮力匹配器很简单。首先在第一幅图像中选取一个关键点然后依次与第二幅图像的每个关键点进行(描述符)距离测试,最后返回距离...
  • 双目测距理论及其python实现

    万次阅读 多人点赞 2019-09-03 23:19:09
    --> 立体校正(含消除畸变) --> 立体匹配 --> 视差计算 --> 深度计算/3D坐标计算 下面将分别阐述每一个步骤并使用opencv-python实现。本篇博客将偏重实践一些,理论方面的论述会比较少,但也会尽量写的通俗易懂...
  • AprilTag详解-Python实现

    千次阅读 热门讨论 2020-08-07 23:42:29
    文章目录一、AprilTag简介二、AprilTag原理三、AprilTag图像生成四、OpenMV实现五、pupil-apriltags六、Python代码实现 一、AprilTag简介 AprilTag是一个视觉基准系统,可用于多种任务,包括增强现实,机器人和相机...
  • 经常需要数据时,难以寻找,或者收集困难,利用开放数据接口,实现股票数据快速收集与下载,可以下载股票、财务、基础数据等,股票金融工具。 编程语言 强大组合:Python + PySide2 PySide2已经很强大了,完全可以...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 50,795
精华内容 20,318
关键字:

python实现快速匹配

python 订阅