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

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'

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

我创建了一个函数，使用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”（我就是其中之一）。使用这种方式我们失去了这个“匹配”。是否有任何字符串距离算法可以比较单词而不考虑单词顺序？或者有没有建议如何高效实现所需的功能？

- Mpizos Dimitris

---

我只需将字符串的排序版本输入函数即可。 - ChaiNunes

这些字符串是否始终包含相同数量的单词？ - Tomer Levinboim

不是，但我很好奇如果单词数量相同的情况下有什么能够减少计算量？ - Mpizos Dimitris

我试图更好地理解这个问题。如果你有兴趣加速计算，你应该考虑使用pypy或cython进行计算。 - Tomer Levinboim

该函数用于使用pyspark对RDD进行“映射”。 - Mpizos Dimitris

Answer 1

尝试使用fuzzywuzzy。

安装：

pip install fuzzywuzzy
pip install python-Levenshtein

无论顺序如何使用：

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

- Roman

Answer 2

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

- Tomer Levinboim

---

仔细阅读您的问题后，我理解您想要一个函数 dist("A B", "B A") == 0，而这个解决方案并没有提供。 - Tomer Levinboim

Answer 3

尝试将字符串转换为小写，然后进行排序。使用原始字符串进行排序的问题在于Python将大写字母视为顺序中更高的字符。（如果您正在计算Levenshtein距离，则空格不应该是一个问题）

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

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

- Valkyrie