Нечеткий поиск по миллионам строк с пользовательской функцией расстояния

Question

У меня есть большой пул коротких струн и пользовательская функция расстояния (скажем, расстояние Дамерау – Левенштейна).

Вопрос: Каково современное решение для получения лучших N строк из пула в соответствии с заданным расстоянием?

Я ищу как теоретический подход к этой проблеме, так и кодированную реализацию (Java, Python и т. Д.).

Answer 1

Прямой подход состоит в том, чтобы перебрать все строки, рассчитать расстояние для каждой и сохранить только лучшее N, пока вы перебираете.

Если вам нужно много выполнять эту задачу, вам следует подумать, сможете ли вы найти оценку верхней / нижней границы для затрат, которая может быть рассчитана намного быстрее, чем ваша функция реальных затрат. Например, предварительно рассчитайте все n-граммы (например, 3-граммы) для ваших строк. или, может быть, сравнение разницы в длине может дать нижнюю границу для расстояния. чем вы можете пропустить расчет расстояния для всех строк, у которых нижнее граничное расстояние больше, чем ваше текущее расстояние n-го наилучшего совпадения.