计算两个字符串之间距离的算法

Question

有没有不考虑单词顺序的字符串距离算法？

以下算法未给出所需结果（在该示例中，所需结果应为 1）：

import jaro
jaro.jaro_winkler_metric(u'Michael Jordan',u'Jordan Michael')
>>>0.47

import Levenshtein
Levenshtein.ratio('Michael Jordan', 'Jordan Michael')
>>>0.5

from difflib import SequenceMatcher
SequenceMatcher(None, 'Michael Jordan', 'Jordan Michael').ratio()
>>>0.5

实现此目的的一种方法是按字母顺序排列字符串，然后使用上述算法：

''.join(sorted('Michael Jordan'))
>>>' JMaacdehilnor'

''.join(sorted('Jordan Michael'))
>>>' JMaacdehilnor'

但是这里姓名的信息丢失了，并且不会有“稳定”的结果。

我创建了一个函数，使用

permutations

中的

itertools

，它获取所有可能的单词编译并比较字符串并输出最大值。结果令人满意，但当我必须比较数百万个名字时，整个过程真的很慢。

还可以做的事情是对单词进行排序，例如：

' '.join(sorted('Michael Jordan'.split()))
>>>'Jordan Michael'
' '.join(sorted('Jordan Michael'.split()))
>>>'Jordan Michael'

似乎是减少计算量的好方法和简单方法，但我们丢失了一些敏感情况。示例：

name1 = ' '.join(sorted('Bizen Dim'.split()))
>>>'Bizen Dim'
name2 = ' '.join(sorted('Dim Mpizen'.split()))
>>>'Dim Mpizen'

SequenceMatcher(None, name1, name2).ratio()
>>>  0.55

这两个名字是相同的，因为有些情况下人们将他们的名字从“b”“翻译”为“mp”（我就是其中之一）。使用这种方式我们就会输掉这场“比赛”。

是否有任何字符串距离算法可以比较单词并且不考虑单词的顺序？或者有什么建议如何有效地实现所需的功能？

Answer 1

尝试fuzzywuzzy

安装：

pip install fuzzywuzzy
pip install python-Levenshtein

使用顺序无关紧要：

from fuzzywuzzy import fuzz

fuzz.token_sort_ratio(u'Michael Jordan',u'Jordan Michael')

>>100

Answer 2

尝试转换为小写，然后排序。使用原始字符串排序的问题是 python 认为大写字母的顺序较高。 （如果你想要编辑距离，空间不应该成为问题）

>>> ''.join(sorted('Michael Jordan'.lower()))
' aacdehijlmnor'

然后使用

.index()

方法获取子串位置。 （您还可以使用 this 答案，它使用

re

模块并使其更加可变）

Answer 3

您可以对两个字符串进行标记（例如，使用 NLTK 标记器），计算每个单词对之间的距离并返回所有距离的总和。