Дистанция по Ливеншейну не совсем подходит для решения этой задачи, поскольку очень трудоёмко сравнивать каждую фразу с каждой другой фразой из текста. Надо использовать хеширование
примерное решение по пунктам:
*токенайзером преобразуем текст в поток лексем
* приводим каждое слово к основе.. либо стеммером (что очень грубо), либо используя какую-нибудь морфологическую библиотеку
*далее для каждого слова выяснем группу синонимов, к которой оно принадлежит. Для определения синонимов можно использовать WordNet, поскольку у него большое покрытие, однако там может не быть некоторых современных слов
*далее хешируем (hashing) все фразы (остаётся открытым вопрос, что мы считаем фразами. можно вообще считать фразами все n-граммы (последовательности n слов)). Делаем это с учётом "дырок" (т.к. называемый insensitive hashing), т.е. у нас будет хеш для фразы "? went for a walk", "She ? for a walk", "She went ? a walk", итп
* ну и дальше уже более подробно работаем с множествами похожих фраз с совпадающими хешами
** за кадром остался вопрос в предобработке текста.. надо выкинуть все знаки препинания и, возможно, стоп слова
..было бы желание и средства, а сделать можно всё что угодно :)
