c# - 近似字符串匹配

Question

我知道这个问题已经被问了很多次了。我想要一个关于哪种算法适合近似字符串匹配的建议。

该应用程序专门用于公司名称匹配，仅此而已。

最大的挑战可能是公司名称部分和简称部分示例： 1. companyA pty ltd vs companyA pty。有限公司 vs companyA 2. WES Engineering vs WES Engineering（极少出现）

您认为 Levenshtein Edit Distance 是否足够？

我正在使用 C#

问候，马克斯

score 14 · Accepted Answer

您可以使用各种字符串距离指标。

我会推荐Jaro-Winkler。与比较结果以离散的编辑单位为单位的编辑距离不同，JW 为您提供 0-1 分数。它特别适用于专有名称。另请查看这个不错的教程和这个 SO question。

我没有使用过 C#，但这里有一些我在网上找到的 JW 实现：

Impl 1 （如果您查看文件列表，他们也有 DOT NET 版本）

如果您想做更复杂的匹配，您可以尝试对公司名称中常见的单词形式进行一些自定义规范化，例如ltd/limited, inc/incorporated, corp/corporation考虑不区分大小写、缩写等。这样，如果您计算

distance (normalize("foo corp."), normalize("FOO CORPORATION") )

你应该得到的结果是 0 而不是 14（如果你计算了 levenshtein 编辑距离，你会得到这个结果）。

score 1 · Accepted Answer

是的，Levenshtein 距离适用于此。它至少适用于您列出的所有人。

您也可以使用Soundex，但我认为您不需要它。

score 1 · Accepted Answer

在这些简单的示例中，只需删除所有非字母数字字符即可获得匹配，并且是最容易做到的，因为您可以预先计算每一侧的数据，然后进行直接等于匹配，这将比交叉乘法和计算编辑距离。

score 0 · Accepted Answer

我已经在另一个问题中提供了答案。

我曾在具有类似名称匹配要求的大型系统上工作过，就像您谈到的那样。名称匹配不是很简单，名字和姓氏的顺序可能不同。在这种情况下，简单的模糊名称匹配算法会惨遭失败。

如果我们只是想谈谈近似字符串匹配算法，那么还有很多。其中很少有：Jaro-Winkler、编辑距离（Levenshtein）、Jaccard 相似度、基于 Soundex/Phonetics 的算法等。一个简单的谷歌搜索就能为我们提供所有细节。您可以在 C# 中实现所有这些

具有讽刺意味的是，当您尝试匹配两个给定的输入字符串时，它们会起作用。理论上可以，并演示模糊或近似字符串匹配的工作方式。

然而，严重低估的一点是，我们如何在生产环境中使用它。并不是我认识的每个正在寻找近似字符串匹配算法的人都知道他们如何在生产环境中解决同样的问题。

我可能刚刚谈到了特定于 Java 的 Lucene，但也有 .Net 的 Lucene。

4 回答 4