Техника хэширования для строк с расстоянием редактирования 2

Question

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

Answer 1

Я вызываю на ваш вопрос так:

Представьте себе, что у меня есть двойные значения, как 7.3 и 8.5, и я хочу, чтобы они имели один и тот же хэш. Вы сразу спросите, должны ли 9.1, а затем 10.0, а затем 10.4, а затем 10.8 и т. Д., Тоже получить тот же хэш, не так ли? Поскольку 9.1 приблизилось к 8.5, поскольку 8.5 - 7.3.

Так что для чисел вы разделились бы на [0; 1 [, [1; 2 [и т. Д. И присваивать один и тот же хэш каждому разделу. Каким будет аналоговый способ разбиения строк?

Таким образом, вам нужно найти различные области, которые могут быть определены представителями, а затем генерировать хеш на основе ближайшего представителя. Вы могли бы выбрать представителей «", "a", "aa", "aaa" и т. Д. И вернуть некоторый хэш представителя, который равен NEXT данному значению, где NEXT может быть определено расстоянием Левенштейна или простой строкой длина.

В целом, я думаю, вы ошибаетесь и должны объяснить свою первоначальную проблему в первую очередь. Хэш не предназначен для вычисления какого-либо значимого адреса кластера или номера раздела значения.