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

Question

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

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

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

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

Answer 1

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

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

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