Словарь хэш-функции для нечетких поисков - PullRequest
Новая
       7

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

0 голосов
/ 05 июля 2018

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

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

0 голосов
/ 05 июля 2018

Я могу понять нечеткий поиск. Но не нечеткое хранение. Почему вы хотите перезаписать «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 голосов
/ 05 июля 2018

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

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

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

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

...