Быстрое получение нечетких строк из базы данных

Question

У меня есть база данных ~ 150 000 слов и шаблон (любое слово), и я хочу получить все слов из базы данных, в которой расстояние между ним и Дамерау-Левенштейном шаблон меньше заданного числа. Мне нужно сделать это очень быстро. Какой алгоритм вы могли бы предложить? Если нет хорошего алгоритма для расстояния Дамерау-Левенштейн, то только расстояние Левенштина будет приветствоваться.

Благодарим за помощь.

P.S. Я не буду использовать SOUNDEX.

Answer 1

Я бы начал с функции SQL, чтобы вычислить расстояние Левенштейна (в T-SQl или .Net) (да, я человек MS ...) с максимальным параметром расстояния, который приведет к раннему выходу.

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

Я также думал, что вы могли бы, например, установить максимальное расстояние до 2, а затем отфильтровать все слова, длина которых больше 1, в то время как первая буква отличается. С индексом это может быть немного быстрее.

Вы также могли бы ярлык, чтобы вернуть все строки, которые идеально матчей (индексация будет ускорить этот процесс), поскольку они будут на самом деле займет больше времени, чтобы вычислить расстояние Левенштейна 0.

Просто некоторые мысли ....

Answer 2

Я бы порекомендовал посмотреть Ankiro.

Я не уверен, что он соответствует вашим требованиям точности, но быстро.

Answer 3

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

1. Сделать это очень быстро перечисление (но это на самом деле не масштабировать)
2. фильтра начальные варианты как-то (индекс в письме, по крайней мере, х общие буквы)
3. Используйте альтернативный (индексируемый) алгоритм, такой как N-граммы (однако у меня нет деталей о качестве результата ngrams по сравнению с расстоянием DL).

Answer 4

Решение от верхней части головы может быть, чтобы сохранить базу данных в упорядоченном множестве (например, std::set в C++), как мне кажется, что строки, упорядоченные лексикографически бы сравнить хорошо. Чтобы аппроксимировать позицию данной строки в set, используйте строку std::upper_bound в строке, затем проведите по множеству по направлению от найденной позиции в обоих направлениях, вычисляя расстояние по ходу и остановитесь, когда он опустится ниже определенного порога. У меня такое ощущение, что это решение, вероятно, будет соответствовать только строкам с одним и тем же стартовым символом, но если вы используете алгоритм проверки орфографии, то это ограничение является общим или, по крайней мере, неудивительным.

Редактировать: Если вы ищете оптимизацию самого алгоритма, этот ответ не имеет значения.

Answer 5

Я использовал KNIME для нечеткого соответствия строк и получил очень быстрые результаты.В нем также очень легко создавать визуальные рабочие процессы. Просто установите бесплатную версию KNIME от https://www.knime.org/, затем используйте узлы «String Distance» и «Search Search», чтобы получить ваши результаты. Я приложил небольшой нечеткий рабочий процесс согласования smaple здесь (входные данные поступают из верхних и шаблонов для поиска приходят из нижней части в данном случае):