-4

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

例如，forabcd和abce它应该给出 75%。

abcd订单很重要，我不希望它给了我dcab100％。

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

4

5 回答 5

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

阅读文档以获取更多信息。你可以阅读文档中的描述来弄清楚如何自己做，但你最终会从头开始编写某种对齐算法。

于 2013-12-22T04:37:36.283 回答
1

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

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

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

Wikibook 中的一种这样的 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
于 2013-12-22T04:40:09.620 回答
0

这个怎么样：

>>> 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
>>>
于 2013-12-22T04:35:26.713 回答
0

维基百科有Levenshtein_distance 或 Edit Distance的伪代码， 这是一个简单的算法。如果您遇到困难，为什么不试一试并提出具体问题。

于 2013-12-22T04:35:53.577 回答
0

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

from numpy import mean
mean([s1[i]==s2[i] for i in xrange(len(s1))])
于 2013-12-22T04:31:34.607 回答