近似字符串匹配
我知道这个问题已被问了很多时间。 我想要一个关于哪种算法适合近似字符串匹配的建议。
该应用程序专门用于公司名称匹配,而不是其他任何内容。
最大的挑战可能是公司的名称部分和简短的命名部分示例:1。companyA pty ltd vs companyA pty。 LTD。 vs companyA 2. WES工程与WES工程(极为罕见)
你认为Levenshtein编辑距离是否足够?
我正在使用C#
此致,Max
您可以使用各种字符串距离指标。
我会推荐Jaro-Winkler 。 与编辑距离不同,其中比较结果是以离散的编辑单位,JW为您提供0-1的分数。 它特别适合专有名称。 另外看看这个漂亮的教程和这个问题。
我没有使用过C#,但是我在网上发现了JW的一些实现:
Impl 1 (如果查看文件列表,它们也有DOT NET版本)
Impl 2
如果你想做一些更复杂的匹配,你可以尝试对公司名称中常见的单词forms进行一些自定义规范化,例如ltd/limited, inc/incorporated, corp/corporation
以解决不区分大小写,缩写等问题。如果你计算的方式
distance (normalize("foo corp."), normalize("FOO CORPORATION") )
你应该得到的结果是0而不是14(如果你计算levenshtein编辑距离,这将是你得到的)。
是的,Levenshtein距离适合这个。 它将适用于您至少列出的所有人。
你也可以使用Soundex ,但我认为你不需要它。
在这些简单的例子中,只删除所有非字母数字字符会给你一个匹配,并且是最简单的方法,因为你可以预先计算每一侧的数据,然后进行直线等于匹配,这将比交叉乘法并计算编辑距离。
我已在另一个问题中提供了我的答案。
https://stackoverflow.com/a/30120166/2282794
我已经研究过具有类似名称匹配要求的大型系统,您已经讨论过了。 名称匹配不是很简单,名字和姓氏的顺序可能不同。 简单模糊名称匹配算法在这种情况下失败。
如果我们只是想谈谈近似字符串匹配算法,那么有很多。 其中很少是:Jaro-Winkler,编辑距离(Levenshtein),Jaccard相似度,Soundex / Phonetics算法等。一个简单的谷歌搜索将给我们所有的细节。 您可以在C#中实现所有这些function
反讽是,当你尝试匹配两个给定的输入字符串时,它们可以工作。 理论上可以说明模糊或近似字符串匹配的工作方式。
然而,严重低估的一点是,我们如何在生产环境中使用相同的。 并不是每个我知道谁在寻找近似字符串匹配算法的人都知道如何在生产环境中解决这个问题。
我可能刚刚谈到了特定于Java的Lucene,但也有针对.Net的Lucene。