В проекте есть требование, чтобы мы сравнили два текста (update1, update2) и разработали алгоритм, чтобы определить, сколько слов и сколько предложений изменилось.
Есть ли алгоритмы, которые я могу использовать?
Я даже не ищу код. Если я знаю алгоритм, я могу написать его на Java.
Обычно это достигается путем нахождения Самая длинная общая подпоследовательность (обычно называемая проблемой LCS). Вот как работают инструменты, такие как diff. Конечно, diff - ориентированный на линию инструмент, и это звучит так, как ваши потребности несколько отличаются. Тем не менее, я предполагаю, что вы уже создали способ сравнения слов и предложений.
Алгоритм сравнения последовательностей О (NP) используется движком дифференциации subversion.
Для вашей информации, есть реализация с различными языками программирования самостоятельно на следующей странице github.
Может быть полезен какой-то вариант diff, например wdiff
Если вы решите разработать свой собственный алгоритм, вам придется обратиться к ситуации, когда предложение было вставлено. Например, для следующих двух документов:
The men are bad. I hate the men
и
The men are bad. John likes the men. I hate the men
Ваш инструмент должен уметь следить за тем, чтобы во втором, I hate the men не был заменен на John likes the men, но вместо этого был нетронутым, и перед ним появилось новое предложение. то есть он должен сообщать о введении предложения, а не об изменении четырех слов, за которым следует новое предложение.
Конкретным алгоритмом, используемым diff и большинством других утилит сравнения, является Eugene Myer O (ND) Разностный алгоритм и его вариации. Его реализация на Java доступна в пакете java-diff-utils.
Вот две статьи, которые описывают другие алгоритмы сравнения текста, которые обычно должны выводить "лучше" (например, меньшие, более значимые) различия:
В первой статье цитируется вторая и упоминается об ее алгоритме:
Хеккель [3] указал на аналогичные проблемы с методами LCS и предложил линейный алгоритм для обнаружения движения блоков. Алгоритм выполняется адекватно если в строках имеется несколько повторяющихся символов. Однако алгоритм дает при прочих равных условиях. Например, учитывая две строки aabb и bbaa, Алгоритм Геккеля не может обнаружить какую-либо общую подстроку.
Первая статья была упомянута в этом ответе и вторая в этом ответе, как для аналогичного Вопрос:
Трудность возникает при эффективном сравнении больших файлов и хорошей производительности. Поэтому я внедрил вариацию алгоритма diff Myers O (ND), который работает довольно хорошо и точно (и поддерживает фильтрацию на основе регулярного выражения):
Алгоритм можно проверить здесь: becke.ch сравнить инструмент веб-приложения
И немного больше информации на домашней странице: инструмент сравнения becke.ch