Сравнение расстояния строки на основе предварительно вычисленных хэшей

Question

У меня есть большой список (более 200 000) строк, которые я хотел бы сравнить с данной строкой.Данная строка вставляется пользователем, поэтому она может быть немного неправильной.

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

Мой вопрос: существует ли уже что-то подобное?Конечно, было бы что-то, что позволило бы мне избежать бега Левенштейна на каждой строке в списке?

Или, может быть, есть третий вариант, о котором я еще не подумал?

Answer 1

Похоже, вы хотите использовать какой-то нечеткий хэш. Есть много доступных хеш-функций, которые могут делать такие вещи. Классический старый алгоритм « SOUNDEX » может даже работать.

Еще одна мысль - если вы оцениваете, что вероятность неправильной записи низкая, то вы можете получить прямой удар 99,9% времени, возвращаясь к SOUNDEX, который может поймать 90% оставшихся случаев, а затем поиск по всему списку за оставшиеся 0,01% времени.

Также стоит проверить это обсуждение: Как найти наилучшее нечеткое совпадение для строки в большой базе данных