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

Question

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

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

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

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

Answer 1

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

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

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