用于模糊查找的字典哈希函数

Question

当需要对字符串进行近似比较时，基本的 Levenshtein Distance 可以提供帮助。它测量等于另一个字符串所需的字符串修改量：

"aaaa" vs "aaab" => 1
"abba" vs "aabb" => 2
"aaaa" vs "a"    => 3

使用 Dictionary<T, U> 时，可以提供自定义 IEqualityComparer<T>。可以将 Levenshtein 距离实现为 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();

Answer 1

我认为没有适用于您的情况的哈希函数。

问题是你只能根据一个单值分配桶，而你不知道之前添加了什么。但是被散列的项目的 Levenshtein 距离可以是 0 到 "infinity" 之间的任何值，唯一重要的是它与什么进行比较。因此你不能满足哈希函数的第二个条件（让相同的对象具有相同的哈希码）。

另一个论点 "pseudo-proof" 是这样的情况，当你想要 最大距离 2 而你已经有 字典中的两个项目，它们的相互距离为 3。如果你然后添加一个字符串，它与第一个项目的距离为 2，与第二个项目的距离为 1，你将如何决定它应该匹配哪个项目？它满足您对两个项目的最大值，但它可能应该与第二个而不是第一个匹配。但是对字典的内容一无所知，你就不知道如何正确散列它。

对于第二个问题 - 使用默认的 string.GetHashCode() 方法确实提高了性能，但它破坏了相等比较器的功能。如果您在示例代码上测试此解决方案，您会看到 dict 现在将包含两个键。这是因为 GetHashCode 返回了两个不同的哈希码，所以没有冲突，dict 现在有两个桶，你的 Equals 方法甚至没有执行。

Answer 2

我能理解模糊查找。但不是模糊存储。为什么要在为 "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

用于模糊查找的字典哈希函数

Dictionary hash function for fuzzy lookups

c#

dictionary

hash

hashtable

fuzzy-search