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

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

一种方法是按字母顺序排列字符串，然后再使用上述算法：

^{pr2}$

但这里的姓名和姓氏信息丢失，不会有“稳定”的结果。在

我创建了一个函数，使用来自itertools的permutations，它接受所有可能的单词编译，并比较字符串并输出最大值。结果是令人满意的，但整个过程是非常缓慢的，当我要比较数以百万计的名字。在

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

' '.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

试着转换成小写，然后排序。使用原始字符串排序的问题是python认为大写字母的顺序更高。（如果你要去levenshtein distance，空间应该不是问题）

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

然后使用.index()方法来获得子字符串的位置。（您也可以使用this answer，它使用re模块并使其更加可变）

Answer 2

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

Answer 3

尝试fuzzywuzzy

安装：

pip install fuzzywuzzy
pip install python-Levenshtein

使用顺序不重要：

^{pr2}$