TheFuzz是一个用python实现Levenshtein距离的包，在某些情况下，当你希望两个不同的字符串被认为是相同的时，它带有一些帮助函数来提供帮助。例如:

>>> fuzz.ratio("fuzzy wuzzy was a bear", "wuzzy fuzzy was a bear")
    91
>>> fuzz.token_sort_ratio("fuzzy wuzzy was a bear", "wuzzy fuzzy was a bear")
    100

解决方案#1:内置Python

使用difflib中的SequenceMatcher

优点: 本机python库，不需要额外的包。 缺点:太有限了，有很多其他的字符串相似度的好算法。

例子

>>> from difflib import SequenceMatcher
>>> s = SequenceMatcher(None, "abcd", "bcde")
>>> s.ratio()
0.75

解决方案#2:水母库

这是一个非常好的图书馆，覆盖面广，问题少。 它支持: - Levenshtein距离 -达默罗-利文斯坦距离 ——Jaro Distance - Jaro-Winkler距离 -匹配评级方法比较 -汉明距离

优点: 易于使用，支持的算法的范围，测试。 缺点:不是本地库。

例子:

>>> import jellyfish
>>> jellyfish.levenshtein_distance(u'jellyfish', u'smellyfish')
2
>>> jellyfish.jaro_distance(u'jellyfish', u'smellyfish')
0.89629629629629637
>>> jellyfish.damerau_levenshtein_distance(u'jellyfish', u'jellyfihs')
1

我想你们可能在寻找一种描述字符串之间距离的算法。这里有一些你可以参考的:

汉明距离 Levenshtein距离 Damerau-Levenshtein距离 Jaro-Winkler距离

如上所述，有许多指标可以定义字符串之间的相似性和距离。我将给出我的5美分，通过展示一个Jaccard与Q-Grams相似的例子和一个编辑距离的例子。

库

from nltk.metrics.distance import jaccard_distance
from nltk.util import ngrams
from nltk.metrics.distance  import edit_distance

Jaccard相似

1-jaccard_distance(set(ngrams('Apple', 2)), set(ngrams('Appel', 2)))

我们得到:

0.33333333333333337

还有苹果和芒果

1-jaccard_distance(set(ngrams('Apple', 2)), set(ngrams('Mango', 2)))

我们得到:

0.0

编辑距离

edit_distance('Apple', 'Appel')

我们得到:

2

最后,

edit_distance('Apple', 'Mango')

我们得到:

5

q - grams上的余弦相似度(q=2)

另一个解决方案是使用textdistance库。我将提供一个余弦相似度的例子

import textdistance
1-textdistance.Cosine(qval=2).distance('Apple', 'Appel')

我们得到:

0.5

Python3.6 + = 没有导入图书馆 在大多数情况下工作良好

在堆栈溢出，当你试图添加一个标签或发布一个问题，它会带来所有相关的东西。这是如此方便，正是我正在寻找的算法。因此，我编写了一个查询集相似度过滤器。

def compare(qs, ip):
    al = 2
    v = 0
    for ii, letter in enumerate(ip):
        if letter == qs[ii]:
            v += al
        else:
            ac = 0
            for jj in range(al):
                if ii - jj < 0 or ii + jj > len(qs) - 1: 
                    break
                elif letter == qs[ii - jj] or letter == qs[ii + jj]:
                    ac += jj
                    break
            v += ac
    return v


def getSimilarQuerySet(queryset, inp, length):
    return [k for tt, (k, v) in enumerate(reversed(sorted({it: compare(it, inp) for it in queryset}.items(), key=lambda item: item[1])))][:length]
        


if __name__ == "__main__":
    print(compare('apple', 'mongo'))
    # 0
    print(compare('apple', 'apple'))
    # 10
    print(compare('apple', 'appel'))
    # 7
    print(compare('dude', 'ud'))
    # 1
    print(compare('dude', 'du'))
    # 4
    print(compare('dude', 'dud'))
    # 6

    print(compare('apple', 'mongo'))
    # 2
    print(compare('apple', 'appel'))
    # 8

    print(getSimilarQuerySet(
        [
            "java",
            "jquery",
            "javascript",
            "jude",
            "aja",
        ], 
        "ja",
        2,
    ))
    # ['javascript', 'java']

解释

compare takes two string and returns a positive integer. you can edit the al allowed variable in compare, it indicates how large the range we need to search through. It works like this: two strings are iterated, if same character is find at same index, then accumulator will be added to a largest value. Then, we search in the index range of allowed, if matched, add to the accumulator based on how far the letter is. (the further, the smaller) length indicate how many items you want as result, that is most similar to input string.

这是我想到的:

import string

def match(a,b):
    a,b = a.lower(), b.lower()
    error = 0
    for i in string.ascii_lowercase:
            error += abs(a.count(i) - b.count(i))
    total = len(a) + len(b)
    return (total-error)/total

if __name__ == "__main__":
    print(match("pple inc", "Apple Inc."))