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

以下算法不给所期望的结果（在该例子中，所希望的结果应该是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”他们的名字（我是其中之一）的情况。通过这种方式，我们正在放弃这场'比赛'。

是否有任何字符串距离算法比较单词并且没有考虑单词的顺序？还是有一个建议如何有效地实现所需的功能？

来源

2016-02-14 Mpizos Dimitris

我只想输入字符串到功能的排序版本。 – ChaiNunes

字符串是否总是包含相同数量的字？ –

不，但我很好奇，如果它的单词数量相同，什么会减少计算量？ –

尝试转换为小写，然后排序。你用原始字符串排序的问题是python看到大写字母顺序更高。（如果你要为Levenshtein距离，空间不应该是一个问题）

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

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

来源

2016-02-14 18:48:48 Valkyrie

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

来源

2016-02-14 21:45:10

更仔细地阅读你的问题，我明白你想要一个功能dist（“A B”，“B A”）== 0，这个解决方案不提供。 –

尝试fuzzywuzzy

安装：

与秩序

pip install fuzzywuzzy 
pip install python-Levenshtein

使用未无所谓：

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

来源

2016-09-12 17:37:01 Roman

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

回答

相关问题