Хеш-функция словаря для нечетких поисков

Когда требуется аппроксимированное сравнение между строками, основное расстояние Левенштейна может помочь. Он измеряет количество модификаций строки, необходимых для того, чтобы равняться другой строке: 

"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" }

Имея все это настроено, вы, возможно, заметили, что мы не реализовали надлежащее GetHashCode в LevenshteinStringComparer, что было бы очень ценно в словаре. В качестве некоторого правила больших пальцев относительно хэш-кодов я бы использовал:

  • неодинаковые объекты не должны иметь одинаковый хэш-код
  • равные объекты должны иметь одинаковый хэш-код

Единственная возможная хэш-функция, следующая этим правилам, которую я могу себе представить, - это постоянное число, точно так же, как реализовано в данном коде. Это не является оптимальным, хотя, но когда мы начинаем, например, брать по умолчанию хэш строки, то aaa и aab будут иметь разные хэши, даже если они обрабатываются как равные. Думая далее, это означает, что все возможные строки должны иметь один и тот же хэш.

Я не ошибаюсь? и почему производительность словаря становится лучше, когда я использую строковую хэш-функцию по умолчанию с хэш-коллизиями для нашего компаратора? не должно ли это сделать хэш-ведра внутри словаря недействительными? 

public int GetHashCode(string obj)
    => obj.GetHashCode();
2 4
c# hashtable fuzzy-search

2 ответа:

Я не думаю, что существует функция хэширования, которая могла бы работать в вашем случае.

Проблема заключается в том, что вы должны назначить ведро только на основе значения signle, в то время как вы не можете знать, что было добавлено раньше. Но левенштейновское расстояние хэшируемого элемента может быть любым от 0 до" бесконечности", важно только то, с чем его сравнивают. Следовательно, вы не можете выполнить второе условие функции хэширования (чтобы одинаковые объекты имели одинаковый хэш-код).

Еще один аргументом "псевдозащиты" будет ситуация, когда вы хотите максимальное расстояние 2, и у вас уже есть два элемента в словаре, которые имеют взаимное расстояние 3. Если затем вы добавите строку, которая имеет расстояние 2 от первого элемента и расстояние 1 от второго элемента, как вы решите, какому элементу она должна соответствовать? Он удовлетворяет вашему максимуму для обоих пунктов, но он, вероятно, должен соответствовать второму, а не первому. Но Не зная ничего о содержании словаря, вы не можете знать, как правильно его хэшировать.

Для второго вопроса-использование метода по умолчанию string.GetHashCode() действительно улучшает производительность, но разрушает функциональность вашего компаратора равенства. Если вы протестируете это решение на своем примере кода, то увидите, что dict теперь будет содержать два ключа. Это потому, что GetHashCode вернул два разных хэш-кода, так что не было никакого конфликта и dict теперь имеет два ведра и ваш Equals метод даже не был выполнен.

2

Я могу понять нечеткий поиск. Но не нечеткое хранилище. Почему вы хотите перезаписать "aaa "при назначении значения для"aab"? Если все, что вам нужно, - это нечеткий поиск, не лучше ли иметь нормальный словарь, который имеет расширение для выполнения нечеткого поиска, например...

public static class DictionaryExtensions
{
    private static IEqualityComparer<string> _comparer = new LevenshteinStringComparer(distance);

    public static IEnumerable<T> FuzzyMatch<T>(this IDictionary<string, T> dictionary, string key, int distance = 2)
    {
        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