Python 中字符串相似程度的百分比

Question

我不知道如何做一个程序，给出相同长度的两个字符串的相似程度的百分比。

例如，对于abcd和abce，它应该给出 75%。

顺序很重要，我不希望它给我abcd，dcab有 100%。

我知道Levenshtein模块可以做到这一点，但我想要一个可以做到这一点的程序。

Answer 1

>>> from difflib import SequenceMatcher
>>> SequenceMatcher(None, 'abcd', 'abce').ratio()
0.75

阅读文档了解更多信息。 您可以阅读文档中的描述以弄清楚如何自己执行此操作，但您最终将从头开始编写某种对齐算法。

Answer 2

相似这个词有不同的上下文，但看看你的例子，我肯定，你正在寻找

Match% = 2* Longest_Common_Substring(a, b) / (len(a) + len(b)) * 100

只需谷歌搜索最长的公共子字符串，你一定会找到大量的Python实现。

来自维基教科书的一个这样的Python实现：算法实现/字符串/最长的公共子字符串如下

def longest_common_substring(s1, s2):
    m = [[0] * (1 + len(s2)) for i in xrange(1 + len(s1))]
    longest, x_longest = 0, 0
    for x in xrange(1, 1 + len(s1)):
        for y in xrange(1, 1 + len(s2)):
            if s1[x - 1] == s2[y - 1]:
                m[x][y] = m[x - 1][y - 1] + 1
                if m[x][y] > longest:
                    longest = m[x][y]
                    x_longest = x
            else:
                m[x][y] = 0
    return s1[x_longest - longest: x_longest]

用相似性函数包装它，结果符合您的期望

>>> def similarity(s1, s2):
     return 2. * len(longest_common_substring(s1, s2)) / (len(s1) + len(s2)) * 100
>>> similarity("abcd","abce")
75.0
>>> similarity("abcd","dcba")
25.0

Answer 3

假设 s1 和 s2 具有相同的长度：

from numpy import mean
mean([s1[i]==s2[i] for i in xrange(len(s1))])

Answer 4

这个怎么样：

>>> a = list('abce')
>>> b = list('abcd')
>>> ( 100 - (sum(i != j for i, j in zip(a, b)) / float(len(a))) * 100 )
75.0
>>> a = list('abce')
>>> b = list('bdce')
>>> ( 100 - (sum(i != j for i, j in zip(a, b)) / float(len(a))) * 100 )
50.0
>>>

Answer 5

维

基百科有用于Levenshtein_distance或编辑距离的伪代码这是一个简单的算法。如果您遇到困难，您为什么不尝试一下并提出具体问题。