Нечеткий поиск подстроки в строке

429

07 февраля 2017, 19:49

Здравствуйте. Необходимо реализовать на Java поиск подстроки в строке. Т.е. строка "Разница между родившимися и умершими" должна быть найдена в строке "Разность между числом родившихся и числом умерших за определенное время (например, за один год) называют естественным приростом населения."

А строка "Ивановыми" должна быть найдена в строке "Иванов - древнейший житель города"

Необходим лишь ответ - есть ли что-то похожее в строке. Посоветуйте что-нибудь, желательно уже реализованное на Java.

Answer 1

Грубо говоря это делается в 3 шага:

Разбиваем строку на лексемы/слова
Полученные лексемы прогоняем через Apache Lucene c русской морфологией - в итоге получаем список лексем очищенный от падежных/родовых и прочих морфологичечких признаков характерных для великого могучего, то есть вместо:

Разность между числом родившихся и числом умерших за определенное время

получим

Разница между число родить и число умереть за определенный время

Далее для этих лексем вычисляем хэш функцию умеющую выдавать близкие значения хэша для похожих слов - например SimHash или что-то вроде упомянутого Левенштейна

Остальное надеюсь объяснять не надо.