精华内容
下载资源
问答
  • python 字符串相似度计算,距离算法

    千次阅读 2018-09-10 10:39:59
    字符串相似度最常见的办法就是:把一个字符串通过插入、删除或替换为另一个字符串,所需要的最少编辑次数,这种就是编辑距离(edit distance)度量方法,也称为Levenshtein距离。海明距离是编辑...

    字符串的相似性比较应用场合很多,像拼写纠错、文本去重、上下文相似性等,判断2个文字列的相似度的多少,合理使用的话就可以实现Google、百度等搜索引擎中的 ‘你是不是要找‘XX’’ 的功能了。

    字符串相似度最常见的办法就是:把一个字符串通过插入、删除或替换为另一个字符串,所需要的最少编辑次数,这种就是编辑距离(edit distance)度量方法,也称为Levenshtein距离。海明距离是编辑距离的一种特殊情况,只计算等长情况下替换操作的编辑次数,只能应用于两个等长字符串间的距离度量。其他常用的度量方法还有 Jaccard distance、J-W距离(Jaro–Winkler distance)、余弦相似性(cosine similarity)、欧氏距离(Euclidean distance)等

    import difflib
    import Levenshtein
    
    str1 = "未来资金还款来源主要包括上市公司分红"
    str2 = "未来还款资金来源主要包括个人日常收入"
    
    # 1. difflib
    seq = difflib.SequenceMatcher(None, str1, str2)
    ratio = seq.ratio()
    print('difflib similarity1: ', ratio)
    #返回的结果超过0.6就算很相似。目前做近义词词典就是借助相似度自动化来实现。
    
    # difflib 去掉列表中不需要比较的字符
    seq = difflib.SequenceMatcher(lambda x: x in '主要', str1, str2)
    ratio = seq.ratio()
    print('difflib similarity2: ', ratio)
    
    #2. hamming距离,str1和str2长度必须一致,描述两个等长字串之间对应位置上不同字符的个数
    sim = Levenshtein.hamming(str1, str2)
    print('hamming similarity: ', sim)
    
    # 3. 编辑距离,描述由一个字串转化成另一个字串最少的操作次数,在其中的操作包括 插入、删除、替换
    sim = Levenshtein.distance(str1, str2)
    print('Levenshtein similarity: ', sim)
    
    # 4.计算莱文斯坦比
    sim = Levenshtein.ratio(str1, str2)
    print('Levenshtein.ratio similarity: ', sim)
    
    # 5.计算jaro距离
    sim = Levenshtein.jaro(str1, str2)
    print('Levenshtein.jaro similarity: ', sim)
    
    # 6. Jaro–Winkler距离
    sim = Levenshtein.jaro_winkler(str1, str2)
    print('Levenshtein.jaro_winkler similarity: ', sim)

    输出 

    difflib similarity1:  0.5555555555555556
    difflib similarity2:  0.5555555555555556
    hamming similarity:  10
    Levenshtein similarity:  10
    Levenshtein.ratio similarity:  0.5555555555555556
    Levenshtein.jaro similarity:  0.7222222222222222
    Levenshtein.jaro_winkler similarity:  0.7777777777777778

    ref:https://blog.csdn.net/qq_37788558/article/details/78780785

    https://blog.csdn.net/xiaodongxiexie/article/details/78221271

    https://blog.csdn.net/u013055678/article/details/52695280

    https://blog.csdn.net/u010454729/article/details/46559845(推荐)

    https://blog.csdn.net/yixianfeng41/article/details/61917158

    展开全文
  • python判断字符串相似度

    千次阅读 2019-08-23 10:55:05
    参考Python 字符串相似性的几种度量方法 安装python-Levenshtein 直接去官网下载适合自己系统的python-Levenshtein.whl文件,进入文件目录,安装,...测试字符串相似度算法 参考了上述链接的代码 # -*- coding: utf...

    参考Python 字符串相似性的几种度量方法

    安装python-Levenshtein

    直接去官网下载适合自己系统的python-Levenshtein.whl文件,进入文件目录,安装,如我的

    pip install python_Levenshtein-0.12.0-cp37-cp37m-win_amd64.whl
    

    测试字符串相似度算法

    参考了上述链接的代码

    # -*- coding: utf-8 -*-
    
    import difflib
    # import jieba
    import Levenshtein
    
    str1 = "我的骨骼雪白 也长不出青稞"
    str2 = "雪的日子 我只想到雪中去si"
    
    # 1. difflib
    seq = difflib.SequenceMatcher(None, str1,str2)
    ratio = seq.ratio()
    print('difflib similarity1: ', ratio)
    
    # difflib 去掉列表中不需要比较的字符
    seq = difflib.SequenceMatcher(lambda x: x in ' 我的雪', str1,str2)
    ratio = seq.ratio()
    print('difflib similarity2: ', ratio)
    
    # 2. hamming距离,str1和str2长度必须一致,描述两个等长字串之间对应位置上不同字符的个数
    # sim = Levenshtein.hamming(str1, str2)
    # print 'hamming similarity: ', sim
    
    # 3. 编辑距离,描述由一个字串转化成另一个字串最少的操作次数,在其中的操作包括 插入、删除、替换
    sim = Levenshtein.distance(str1, str2)
    print('Levenshtein similarity: ', sim)
    
    # 4.计算莱文斯坦比
    sim = Levenshtein.ratio(str1, str2)
    print('Levenshtein.ratio similarity: ', sim)
    
    # 5.计算jaro距离
    sim = Levenshtein.jaro(str1, str2 )
    print('Levenshtein.jaro similarity: ', sim)
    
    # 6. Jaro–Winkler距离
    sim = Levenshtein.jaro_winkler(str1 , str2 )
    print('Levenshtein.jaro_winkler similarity: ', sim)
    

    输出结果为

    difflib similarity1: 0.14814814814814814
    difflib similarity2: 0.0
    Levenshtein similarity: 13
    Levenshtein.ratio similarity: 0.14814814814814814
    Levenshtein.jaro similarity: 0.4061355311355312
    Levenshtein.jaro_winkler similarity: 0.4061355311355312

    展开全文
  • /usr/bin/env python def levenshtein(a,b): "Calculates the Levenshtein distance between a and b." n, m = len(a), len(b) if n > m: # Make sure n <= m, to use O(min(n,m)) spa...
    #!/usr/bin/env python
    
    def levenshtein(a,b):
        "Calculates the Levenshtein distance between a and b."
        n, m = len(a), len(b)
        if n > m:
            # Make sure n <= m, to use O(min(n,m)) space
            a,b = b,a
            n,m = m,n
            
        current = range(n+1)
        for i in range(1,m+1):
            previous, current = current, [i]+[0]*n
            for j in range(1,n+1):
                add, delete = previous[j]+1, current[j-1]+1
                change = previous[j-1]
                if a[j-1] != b[i-1]:
                    change = change + 1
                current[j] = min(add, delete, change)
                
        return current[n]
    def levenshtein_distance(first, second):
        """Find the Levenshtein distance between two strings."""
        if len(first) > len(second):
            first, second = second, first
        if len(second) == 0:
            return len(first)
        first_length = len(first) + 1
        second_length = len(second) + 1
        distance_matrix = [range(second_length) for x in range(first_length)]
        for i in range(1, first_length):
            for j in range(1, second_length):
                deletion = distance_matrix[i-1][j] + 1
                insertion = distance_matrix[i][j-1] + 1
                substitution = distance_matrix[i-1][j-1]
                if first[i-1] != second[j-1]:
                    substitution += 1
                distance_matrix[i][j] = min(insertion, deletion, substitution)
    
        return distance_matrix[first_length-1][second_length-1]
    
    
    if __name__=="__main__":
        #from sys import argv
        first = "abcabcaa"
        second = "cbsaaecaa"
        print levenshtein(first,second)
        print levenshtein_distance(first,second)
    
    

     

    展开全文
  • # -*- coding: utf8 -*- #字符串相似度算法 #!/usr/bin/env python __author__ = 'Administrator' def levenshtein(a,b): "Calculates the Levenshtein distance between a and b." n, m = len(a), len(b) if
    # -*- coding: utf8 -*-
    #字符串相似度算法
    #!/usr/bin/env python
    __author__ = 'Administrator'
    
    
    def levenshtein(a,b):
        "Calculates the Levenshtein distance between a and b."
        n, m = len(a), len(b)
        if n > m:
            # Make sure n <= m, to use O(min(n,m)) space
            a,b = b,a
            n,m = m,n
        current = range(n+1)
        for i in range(1,m+1):
            previous, current = current, [i]+[0]*n
            for j in range(1,n+1):
                add, delete = previous[j]+1, current[j-1]+1
                change = previous[j-1]
                if a[j-1] != b[i-1]:
                    change = change + 1
                current[j] = min(add, delete, change)
        return current[n]
    
    def levenshtein_distance(first, second):
        """Find the Levenshtein distance between two strings."""
        if len(first) > len(second):
            first, second = second, first
        if len(second) == 0:
            return len(first)
        first_length = len(first) + 1
        second_length = len(second) + 1
        distance_matrix = [range(second_length) for x in range(first_length)]
        for i in range(1, first_length):
            for j in range(1, second_length):
                deletion = distance_matrix[i-1][j] + 1
                insertion = distance_matrix[i][j-1] + 1
                substitution = distance_matrix[i-1][j-1]
                if first[i-1] != second[j-1]:
                    substitution += 1
                distance_matrix[i][j] = min(insertion, deletion, substitution)
        return distance_matrix[first_length-1][second_length-1]
    
    
    


    levenshtein_distance(字符串相似度算法):

               所谓levenshtein distance即将一个字符串转换成另一个字符串所需要的最少修改次数,一般包括对字符的3种操作:1、删除。2、修改。3、增加。

              如‘天通苑’和‘天通西苑’的度为1,执行一次插入操作。

     

    展开全文
  • 2019独角兽企业重金招聘Python工程师标准>>> ...
  • 参考:http://www.merriampark.com/ld.htm#WHATIS http://en.wikipedia.org/wiki/Levenshtein_distance    * Java  * C++  * Visual Basic ... * Python Java代码   Java public
  • 2019独角兽企业重金招聘Python工程师标准>>> ...
  • 参考:http://www.merriampark.com/ld.htm#WHATIS ... * Java * C++ * Visual Basic * Python [code="java"] Java public class Dist...
  • Levenshtein算法python也是用的这个对比字符串相似度的,还不错
  • 2019独角兽企业重金招聘Python工程师标准>>> ...
  • 计算字符串变换相等的最小操作代价 2020远景智能计算字符串相似度计算字符串变换相等的最小操作代价题目描述:输入描述:输出描述:示例:思路:算法介绍示例代码:代码输出:2020远景智能在线笔试 计算字符串的相似度...
  • python字符串相似度 tdebatty likeity的Python3.x实现 一个实现不同字符串相似度和距离度量的库。 当前实现了十二种算法(包括Levenshtein编辑距离和同级,Jaro-Winkler,最长公共子序列,余弦相似性等)。 查看...
  • 安装python-Levenshtein模块 pip install python-Levenshtein 使用python-Levenshtein模块 import Levenshtein ...算法说明 1). Levenshtein.hamming(str1, str2) 计算汉明距离。要求str1和st...
  • 最近因为工作需要,使用Python实现了常用的字符串相似度算法,一共超过十种。列举如下: Levenshtein NormalizedLevenshtein WeightedLevenshtein DamerauLevenshtein OptimalStringAlignment Jarowinkler ...
  • 之前有说过最长公共子序列的问题,类似的还有一个两个字符串相似度的问题。  所谓相似度就是指一个字符串要至少通过多少次变化(插入一个新字符,删除一个字符,替换一个字符)才能变成另一个字符串。  在python...
  • 计算字符串相似度的一些方法

    千次阅读 2018-09-30 12:10:11
    产品出了一个奇怪的需求,想通过字符串相似度取匹配城市= =(当然,最后证实通过字符串相似度取判断两个字符串是不是一个城市是不对的!!!) 这里就记录一下我计算字符串(英文字符串)相似度的方法吧~ 参考文档: ...
  • 字符串相似度

    2018-02-04 17:58:03
    最近在做算法作业,需要比较两个字符串相似度,并且返回相同的元素所占的百分比。 如果让我自己做的话,思路是把两个字符串分别转化为列表,然后在列表中解决掉。 [python] view plain copy ...
  • Python计算字符串相似度

    万次阅读 2017-02-28 14:20:36
    字符串相似度算法以及有很多资料了。最常见的理解就是:把一个字符串通过插入、删除或替换这样的编辑操作,变成另外一个字符串,所需要的最少编辑次数。AKA,两个字符串之间的距离。解这样一个问题,可以使用穷举...
  • 2019独角兽企业重金招聘Python工程师标准>>> ...
  • 稍微翻了一下github,在字符串相似度方面现成的开源rust轮子不多,一个手数的过来,而且质量普遍不算很高(无脑递归,或者直接将jaro_winkler的p因子固定为0.1,前者仅是运行性能层面的不足,而后者则会导致运算结果...
  • 文章目录自然语言处理系列二十八文本相似度算法字符串编辑距离Python代码实现总结 自然语言处理系列二十八 文本相似度算法 在自然语言处理中,我们经常需要判定两个东西是否相似。比如,在微博的热点话题推荐那里,...
  • #!/user/bin/env python # -*- coding: utf-8 -*- class arithmetic(): ... def __init__(self): ... ''' 【编辑距离算法】 【levenshtein distance】 【字符串相似度算法】 ''' def...
  • BK树或者称为Burkhard-...在构建BK树之前,我们需要定义一种用于比较字符串相似度的度量方法。通常都是采用编辑距离(Levenshtein Distance),这是一种用于表示两个字符串相互转换需要进行的最少编辑步数。 在...
  • 主要方法有:编辑距离、余弦相似度、模糊相似度百分比 1、编辑距离 def levenshtein(first, second): ''' 编辑距离算法(LevD... returns: 两个字符串的编辑距离 int ''' if len(first) &amp;gt; len(se...
  • 短文本相似度算法(distance.py) 基于分词后单词: edit_similar(str1,str2):编辑距离相似度,输入为分词后的两个句子的列表,返回值为两者相似度。 cos_sim(str1, str2):余弦相似度,输入为分词后的两个句子的列表...

空空如也

空空如也

1 2 3 4
收藏数 61
精华内容 24
关键字:

python字符串相似度算法

python 订阅