Алгоритм текстового различия - PullRequest
42 голосов
/ 28 сентября 2008

Мне нужен алгоритм, который может сравнивать два текстовых файла и выделять их различие и (даже лучше!) Может вычислять их различие осмысленным способом (например, два одинаковых файла должны иметь показатель сходства выше, чем два разнородных файла со словом «подобное» определено в нормальных терминах). Звучит легко для реализации, но это не так.

Реализация может быть на C # или Python.

Спасибо.

Ответы [ 11 ]

0 голосов
/ 21 декабря 2009

Один метод, который я использовал для другой функциональности, чтобы вычислить, сколько данных было новым в измененном файле, возможно, будет работать и для вас.

У меня есть реализация diff / patch C #, которая позволяет мне взять два файла, предположительно старую и новую версию одного и того же файла, и вычислить «разницу», но не в обычном смысле этого слова. По сути, я вычисляю набор операций, которые я могу выполнить со старой версией, чтобы обновить ее до того же содержимого, что и у новой версии.

Чтобы использовать это для первоначально описанной функциональности, чтобы увидеть, сколько данных было новым, я просто пробежался по операциям, и для каждой операции, которая дословно скопировала из старого файла, имел 0-фактор, и каждую операцию, которая вставленный новый текст (распространяемый как часть патча, так как его не было в старом файле) имел 1-фактор. Все персонажи получили эту фабрику, которая дала мне длинный список нулей и единиц.

Все, что мне тогда нужно было сделать, это подсчитать 0 и 1. В моем случае, с моей реализацией, небольшое число 1 по сравнению с 0 означало бы, что файлы очень похожи.

Эта реализация также будет обрабатывать случаи, когда в измененный файл были вставлены копии из старого файла не по порядку или даже дубликаты (т. Е. Вы копируете деталь из начала файла и вставляете ее около дна), так как они оба будут копиями одной и той же оригинальной части из старого файла.

Я экспериментировал с взвешиванием копий, чтобы первая копия учитывалась как 0, а последующие копии тех же символов имели прогрессивно более высокие коэффициенты, чтобы придать операции копирования / вставки некоторый «новый фактор», но я так и не закончил это как проект был свернут.

Если вам интересно, мой код diff / patch доступен в моем хранилище Subversion.

...