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

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'

但是这里姓名和姓氏的信息丢失了,不会有"稳定"的结果.

我创建了一个使用permutationsfrom 的函数,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

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

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

然后使用该.index()方法获取子串位置。（您也可以使用这个使用模块并使其更加可变的答案）re