当需要字符串之间的近似比较时，基本的Levenshtein距离会有所帮助。它测量等于另一个字符串所需的字符串修改量：
"aaaa" vs "aaab" => 1
"abba" vs "aabb" => 2
"aaaa" vs "a" => 3
使用Dictionary<T, U>时，可以提供自定义IEqualityComparer<T>。可以将列文施泰因距离实现为IEqualityComparer<string>：
public class LevenshteinStringComparer : IEqualityComparer<string>
{
private readonly int _maximumDistance;
public LevenshteinStringComparer(int maximumDistance)
=> _maximumDistance = maximumDistance;
public bool Equals(string x, string y)
=> ComputeLevenshteinDistance(x, y) <= _maximumDistance;
public int GetHashCode(string obj)
=> 0;
private static int ComputeLevenshteinDistance(string s, string t)
{
// Omitted for simplicity
// Example can be found here: https://www.dotnetperls.com/levenshtein
}
}
所以我们可以使用模糊字典：
var dict = new Dictionary<string, int>(new LevenshteinStringComparer(2));
dict["aaa"] = 1;
dict["aab"] = 2; // Modify existing value under "aaa" key
// Only one key was created:
dict.Keys => { "aaa" }
完成所有这些设置后，您可能已经注意到我们没有在LevenshteinStringComparer中实现适当的GetHashCode，字典将非常感谢。作为关于哈希代码的一些经验法则，我会使用：
- 不相等的对象不应具有相同的哈希代码
- 相等的对象必须具有相同的哈希代码
我能想象到的遵循这些规则的唯一可能的哈希函数是一个常数，就像在给定的代码中实现的那样。不过这不是最佳选择，但是当我们开始例如采用字符串的默认哈希时，aaa和aab最终会得到不同的哈希，即使它们是平等的。进一步思考，这意味着所有可能的字符串都必须具有相同的哈希值。
我说的对吗？为什么当我为比较器使用带有哈希冲突的默认字符串哈希函数时，字典的性能会变得更好？这不应该使字典中的哈希桶无效吗？
public int GetHashCode(string obj)
=> obj.GetHashCode();
我认为没有一个哈希函数可以在您的情况下工作。
问题是您必须仅根据签名值分配存储桶，而您无法知道之前添加了什么。但是被散列项目的 Levenshtein 距离可以是从 0 到"无穷大"的任何距离，唯一重要的是它与什么进行比较。因此，您无法满足哈希函数的第二个条件(使相等的对象具有相同的哈希代码(。
另一个参数"伪证明">是当您想要最大距离为 2并且字典中已经有两个项目时，它们的相互距离为 3。如果随后添加一个字符串，该字符串与第一项的距离为 2，与第二项的距离为 1，您将如何决定它应该与哪个项目匹配？它满足您对这两个项目的最大值，但它可能应该与第二个而不是第一个匹配。但是对字典的内容一无所知，你就不知道如何正确地散列它。
对于第二个问题 - 使用默认string.GetHashCode()方法确实可以提高性能，但它会破坏相等比较器的功能。如果在示例代码上测试此解决方案，可以看到dict现在将包含两个键。这是因为GetHashCode返回了两个不同的哈希代码，所以没有冲突，dict现在有两个存储桶，您的Equals方法甚至没有执行。
我可以理解模糊查找。但不是模糊存储。为什么在为"aab"赋值时要覆盖"aaa"？ 如果您想要的只是模糊查找，那么拥有一个普通的字典不是更好吗，该字典具有扩展名来执行模糊查找，例如......
public static class DictionaryExtensions
{
public static IEnumerable<T> FuzzyMatch<T>(this IDictionary<string, T> dictionary, string key, int distance = 2)
{
IEqualityComparer<string> comparer = new LevenshteinStringComparer(distance);
return dictionary
.Keys
.Where(k => comparer.Equals(k, key))
.Select(k => dictionary[k]);
}
}
这与其说是答案，不如说是评论。 为了回答您的问题，如果您考虑以下示例...
"abba" vs "cbbc" => 2
"cddc" vs "cbbc" => 2
"abba" vs "cddc" => 4
你明白这里的要点了吗？ 即显然，以下内容不可能是真的
abba == cbbc &&
cddc == cbbc &&
abba != cddc
唯一严格的规则是，如果对象相等，那么它们应该具有相同的哈希码，这可以通过返回 0 来保证。在这种情况下，您始终回退到等于。
列文施泰因距离可以归一化为1.0。
唯一的问题是结果取决于添加项目的顺序，一些相似的值最终可能会出现在不同的存储桶中。在单词大多彼此"相距很远"的情况下，这是可以的，它允许您降低标准，例如Better、Beter、Beetter、Knowledge、Programming。
如果先应用某些聚类分析算法并使用聚类作为键，结果会更好。