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

#java #поиск #нечеткий_поиск

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

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

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

Ответы

Ответ 1

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


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



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


получим


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



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


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