Как эффективно найти все нечеткие совпадения между набором терминов и списком предложений?

Question

У меня есть список предложений (например, «Это примерное предложение») и глоссарий терминов (например, «предложение», «примерное предложение») и нужно найти все термины, которые соответствуют предложению с отсечкой на некоторых Левенштейн.

Как я могу сделать это достаточно быстро? Разделение предложений, использование FTS для поиска слов, которые появляются в терминах и фильтрации терминов по отношениям, но это довольно медленно. Прямо сейчас я использую sphinxsearch + python-Levelshtein, есть ли лучшие инструменты?

Будет ли обратный поиск: соответствие FTS условиям в предложении быстрее?

Answer 1

Если скорость является реальной проблемой, и если ваш глоссарий терминов не будет часто обновляться, по сравнению с количеством поисковых запросов, которое вы хотите сделать, вы можете посмотреть что-то вроде Levenshtein Automaton. Я не знаю ни одной библиотеки python, которая ее поддерживает, но если вам это действительно нужно, вы можете реализовать ее самостоятельно. Чтобы найти все возможные пути, потребуется некоторое динамическое программирование.

Если вам просто нужно сделать это, просто пройдите по глоссарию и проверьте каждый на каждое слово в строке. Это должно дать вам ответ в полиномиальное время. Если вы используете многоядерный процессор, вы можете получить некоторое ускорение, выполнив его in parallel.