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

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

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

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

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


string distance hash compare precompute
person Brad    schedule 12.08.2010    source источник

Ответы (1)


arrow_upward
3
arrow_downward

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

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

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

person mikera    schedule 12.08.2010