У меня есть база данных из ~ 150 000 слов и шаблон (любое отдельное слово), и я хочу получить все слова из базы данных, у которой расстояние Дамерау-Левенштейна между ним и шаблоном меньше заданного числа . Мне нужно сделать это очень быстро. Какой алгоритм вы могли бы предложить? Если нет хорошего алгоритма определения расстояния Дамерау-Левенштейна, то можно будет приветствовать и расстояние Левенштейна.
Спасибо за помощь.
P.S. Я не собираюсь использовать SOUNDEX.
Я бы начал с функции SQL для вычисления расстояния Левенштейна (в T-SQl или .Net) (да, я человек MS ...) с параметром максимального расстояния, который вызовет ранний выход.
Затем эту функцию можно использовать для сравнения вашего ввода с каждой строкой, чтобы проверить расстояние и перейти к следующему, если он превышает пороговое значение.
Я также думал, что вы можете, например, установить максимальное расстояние равным 2, а затем отфильтровать все слова, длина которых больше 1, а первая буква отличается. С индексом это может быть немного быстрее.
Вы также можете ярлыком вернуть все строки, которые идеально подходят (индексация ускорит это), поскольку на самом деле для вычисления расстояния Левенштейна, равного 0, потребуется больше времени.
Просто мысли ....
Я не думаю, что вы можете вычислить такую функцию без фактического перечисления всех строк.
Итак, решения следующие:
Решение, которое мне пришло в голову, могло бы заключаться в том, чтобы хранить базу данных в отсортированном наборе (например, std::set в C ++), поскольку мне кажется, что строки, отсортированные лексикографически, будут хорошо сравниваться. Чтобы аппроксимировать положение данной строки в set, используйте std::upper_bound в строке, затем перебирайте набор наружу от найденной позиции в обоих направлениях, вычисляя расстояние по мере продвижения, и останавливайтесь, когда оно падает ниже определенного порога. У меня такое чувство, что это решение, вероятно, будет соответствовать только строкам с одним и тем же начальным символом, но если вы используете алгоритм для проверки орфографии, то это ограничение является обычным или, по крайней мере, неудивительным.
Изменить: если вы ищете оптимизацию самого алгоритма, этот ответ не имеет значения.
Я использовал KNIME для нечеткого сопоставления строк и получил очень быстрые результаты. В нем также очень легко создавать визуальные рабочие процессы. Просто установите бесплатную версию KNIME с https://www.knime.org/, затем используйте "String Distance" и Узлы «Поиск по сходству» для получения результатов. Я прикрепил сюда небольшой рабочий процесс с нечетким соответствием smaple (входные данные поступают сверху, а шаблоны для поиска в данном случае - снизу): 
Я бы порекомендовал изучить Ankiro.
Я не уверен, что он соответствует вашим требованиям к точности, но он быстрый.
