是否有任何字符串距離算法沒有考慮到單詞的順序？

以下算法未提供所需結果(在該示例中,所需結果應為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的排列創建了一個函數,它接受所有可能的單詞編譯并比較字符串并輸出最大值.結果令人滿意,但是當我必須比較數百萬個名字時,整個程序真的很慢.

可以做的其他事情是對單詞進行排序,例如：

' '.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'(我就是其中之一).用這種方式我們就失去了這個’匹配’.

是否有任何字符串距離算法比較單詞而不考慮單詞的順序？或者是否有建議如何有效地實現所需的功能？