如何确定数组中哪个字符串与给定字符串最相似？

Question

给定一个字符串，

string name = "Michael";

我希望能够评估数组中哪个字符串最相似：

string[] names = new[] { "John", "Adam", "Paul", "Mike", "John-Michael" };

我想为用户创建一条消息：“我们找不到'Michael'，但是'John-Michael'很接近。这是您的意思吗？” 我该如何做出这个决定？

- Michael Hedgpeth

---

你需要知道的是，string[] names = 这个语句已经包含了创建新数组的操作，所以你不需要再使用 new[]。 - Gabe

请定义“相似”。那一个例子并不能完全说明问题。 - H H

我对算法做出这种决定感到满意。如果答案是“Mike”或“John-Michael”，我也没问题。我只是想要一个能提供有意义建议的东西。 - Michael Hedgpeth

Answer 1

通常使用编辑距离/ Levenshtein distance 来比较哪个单词最接近，基于需要删除、添加或更改的数量来转换一个单词为另一个单词。

这里有一篇文章提供了C#的通用实现 here。

- BrokenGlass

---

+1，但我也建议如果用户在名称中发现非字母字符，最好沿着该字符拆分名称，否则与John-Michael相比，Levenshtein距离可能太大，而与Mike或其他名称相比。 - Kiril

@Lirik，你可以对编辑距离进行各种更改，以适应特定的问题，例如指定添加和替换不同的权重（而不是 1/1/1）——如果增加了替换的权重，算法将“更喜欢”添加/删除，这将涵盖你刚刚提供的示例。 - BrokenGlass

Answer 2

以下是使用Levenshtein距离算法的示例结果：

EditDistance["Michael",#]&/@{"John","Adam","Paul","Mike","John-Michael"}
{6,6,5,4,5}  

使用Smith-Waterman相似性测试，您将获得以下结果：

SmithWatermanSimilarity["Michael",#]&/@{"John","Adam","Paul","Mike","John-Michael"}
{0.,0.,0.,2.,7.} 

祝好运！

- Dr. belisarius

---

介绍这两种不同的相似性测试非常棒，这正是我所需要的。再加上其他答案，我得到了我需要的东西。谢谢！ - Michael Hedgpeth

@Michael 你可以对两者进行加权平均来优化你的目的。祝你好运！ - Dr. belisarius