Алгоритм сравнения текста

Question

У нас в проекте есть требование, чтобы мы сравнили два текста (update1, update2) и разработали алгоритм, чтобы определить, сколько слов и предложений изменилось.

Существуют ли алгоритмы?что я могу использовать?

Я даже не ищу код.Если я знаю алгоритм, я могу написать его на Java.

Answer 1

Обычно это достигается путем нахождения самой длинной общей подпоследовательности (обычно называемой проблемой LCS).Вот как работают такие инструменты, как diff.Конечно, diff - это инструмент, ориентированный на строки, и кажется, что ваши потребности несколько иные.Однако я предполагаю, что вы уже создали какой-то способ сравнения слов и предложений.

Answer 2

Алгоритм сравнения Subversion использует алгоритм сравнения последовательностей O (NP) .

К вашему сведению, на следующей странице github есть мои собственные реализации с различными языками программирования.

https://github.com/cubicdaiya/onp

Answer 3

Может быть полезен некоторый вариант 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, но вместо этого не тронут, и перед ним вставлено новое предложение.то есть он должен сообщать о вставке предложения, а не об изменении четырех слов, за которым следует новое предложение.

Answer 4

Вот две статьи, которые описывают другие алгоритмы сравнения текста, которые обычно должны выводить «лучшие» (например, меньшие, более значимые) различия:

• Tichy, Walter F., «The Stringисправления цепочки при перемещении блоков "(1983).Информатика Технические отчеты.Документ 378.
• Пол Хекель, «Методика изоляции различий между файлами», сообщения ACM, апрель 1978 г., том 21, номер 4

Первая статья цитирует вторую и упоминает об этом алгоритме:

Геккель [3] указал на аналогичные проблемы с методами LCS и предложил алгоритм линейного извлечения для обнаружения перемещений блоков.Алгоритм работает адекватно, если в строках мало повторяющихся символов.Тем не менее, алгоритм дает плохие результаты в противном случае.Например, учитывая две строки aabb и bbaa , алгоритм Геккеля не может обнаружить какую-либо общую подстроку.

Первая статья упоминалась в этот ответ и второй в этот ответ , оба на аналогичный вопрос SO:

• Существует ли алгоритм сравнения, который обрабатывает движущийся блок строк?- Переполнение стека

Answer 5

Конкретным алгоритмом, используемым diff и большинством других утилит сравнения, является Eugene Myer's O (ND) Разностный алгоритм и его вариации .Его реализация на Java доступна в пакете java-diff-utils .

Answer 6

Трудность возникает при эффективном сравнении больших файлов с хорошей производительностью.Поэтому я реализовал разновидность алгоритма сравнения Myers O (ND), который работает довольно хорошо и точно (и поддерживает фильтрацию на основе регулярного выражения):

Алгоритм можно протестировать здесь: becke.ch сравнитьинструмент веб-приложения

И немного больше информации на домашней странице: becke.ch сравнить инструмент