字符串相似度算法

Question

我有两个字符串(它们最终会成为一个简单数据库中的描述)，假设它们是：

1. 字符串A: “苹果橙子椰子青柠吉米自助餐”
2. 字符串B: “汽车自行车滑板”

我需要的是，一个函数将以“椰子”作为输入，并输出“字符串A”。

我们可能存在大小写不同的问题，并且拼写有时可能不完全正确。目标是实现“快而脏”的搜索。

是否有任何 .net(或第三方) 或推荐的“相似算法”可以对字符串进行比较，以便检查输入是否有一个“相当接近的片段”，并返回它？我的数据库顶多只有50个条目。

- greggorob64

---

汉明距离？Soundex？ - Marc B

Levenshtein距离是一种用来度量两个字符串之间差异程度的算法，它定义为将一个字符串转换为另一个字符串所需进行的最少单字符编辑操作次数（插入、删除、替换）。 - Oded

我现在正在尝试Levenshtein算法。我想我正在寻找建议，因为我的目标是仅使用整个字符串的片段。尝试所有算法并选择最佳算法可能是我应该采取的方法。 - greggorob64

https://dev59.com/1HVD5IYBdhLWcg3wHnsX#1095806... 该答案中的链接已失效，请在此处获取该产品：http://sourceforge.net/projects/simmetrics/files/。 - Joel Coehoorn

@KonradRudolph：看起来他们有一个（旧的）.NET版本在这里：http://sourceforge.net/projects/simmetrics/files/simmetrics.NET%20and%20amp_%20phonetics.NET/ - Chris Sinclair

Answer 1

你正在搜索的是两个字符串之间的编辑距离。有很多实现方法 - 这里有一个来自Stack Overflow的实现。

由于你只搜索字符串的一部分，所以你需要的是一个局部最优匹配，而不是通过该方法计算的全局匹配。

这被称为局部比对问题，再次使用几乎相同的算法很容易解决 - 唯一改变的是初始化（我们不惩罚出现在搜索字符串之前的任何内容）和选择最优值（我们不惩罚出现在搜索字符串之后的任何内容）。

- Konrad Rudolph

---

我想我找到了解决方案，我将使用Levenshtein算法。由于我的大多数数据都是简单的空格分隔，所以我只需将我的字符串与数据库条目的空格分隔版本进行比较，并将最高的单词作为结果。 - greggorob64