智能字符串比较

Question

我正在寻找一个允许两个字符串进行智能比较的库/类.最好它会给出两个字符串相似的百分比.我正在比较公司名称,在不同存储库中记录的地址,因此在名称中有许多拼写错误或不一致.

要比较的示例字符串:

 "Good Company Ltd." vs. "GoodCompany" 
 "Baker Street 2" vs. "Baker Str. 2" 

如果我得到相似百分比的结果,那么这可以是这种数据的智能合并的输入.

你知道任何能够进行这种智能字符串比较的好库吗？

Answer 1

在这种情况下,Levenshtein不合适."Good Company Ltd"和"GoodCompany"如果修剪的距离= 3,而"Good Company Ltd"和"Food Company Ltd"的距离为1,但意义完全不同.我建议使用Metaphone或Double Metaphone算法.

使用在线metaphone比较器的结果是:

Good Company Ltd = KTKMPNLTT
GoodCompany = KTKMPN
Food Company Ltd = FTKMPNLTT
GoodCompanyLLC = KTKMPNLK

这样,你知道GoodCompany,Good Company Ltd和GoodCompanyLLC是相似的,而Food Company拼写错误或完全不相关(KTKMPN包含无论是在KTKMPNLTT和KTKMPNLK而不是在FTKMPNLTT).

你看这里的其他算法的比较.

Answer 2

您可能想要寻找Levenshtein Distance实施.它显示了使两个字符串相等所需的插入/删除和替换的字符数.

这是一篇关于C#中实现Levenshtein Distance和其他文本比较算法的库的文章:用于文本算法的.NET库？.

但是我认为你必须使用一些方法组合,因为使用Levenshtein会告诉你'Good Company Ltd.' 更类似于'Bad Company Ltd.' 而不是'GoodCompany'.

也许你必须通过扩展'str'来做一些预处理.到'街'并删除'有限公司' 作为字符串比较的"无意义"词.

更新1

Francesco De Lisi 建议使用Phonetic算法.看起来它们更适合比较拼错的名字.您仍然需要将地址拆分为拼音/非拼音部分(如建筑物编号)并单独进行比较.

更新2

至于地址比较,这篇文章建议使用Google Maps API用于此目的,另一篇文章讨论地址解析.我猜Google可以产生可靠的结果,因为他们有一个街道地址数据库,可以找到最正确的街道名称拼写.如果没有正确的街道/公司名称列表,您可能会遇到一些不正确的奇怪名称,但是许多不同的正确名称将与它类似.

Answer 3

您正在寻找的是Levenshtein距离(维基百科):

...... Levenshtein距离是用于测量两个序列之间差异的字符串度量.非正式地,两个单词之间的Levenshtein距离是将一个单词改为另一个单词所需的单字符编辑(插入,删除,替换)的最小数量.