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

Посмотрите на дифлиб. (Python)

Это позволит вычислить различия в различных форматах. Затем вы можете использовать размер контекста diff как меру различий между двумя документами?

Если вам нужна более мелкая детализация, чем линии, вы можете использовать расстояние Левенштейна. Расстояние Левенштейна - это прямая мера того, насколько похожи два текста. Вы также можете использовать его для извлечения журналов редактирования и очень детального сравнения, аналогичного тому, что на страницах истории редактирования SO. Однако имейте в виду, что расстояние Левенштейна может потребовать значительных ресурсов процессора и памяти для вычисления, поэтому использование diffflib, как предположил Дуглас Ледер, скорее всего, будет быстрее.

Ср. также этот ответ.

Как уже говорилось, используйте difflib. После того, как у вас есть дифференцированный вывод, вы можете найти Расстояние Левенштейна различных строк, чтобы дать «значение» того, насколько они различны.

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

Могу порекомендовать взглянуть на код и статьи Нила Фрейзера:

Google-diff-match-patch

Currently available in Java, JavaScript, C++ and Python. Regardless of language, each library features the same API and the same functionality. All versions also have comprehensive test harnesses.

Нил Фрейзер: разные стратегии - за теорию и примечания по реализации

Существует ряд показателей расстояния, как упоминалось в парадодже, есть расстояние Левенштейна, но есть также NYSIIS и Soundex. Что касается реализаций Python, я раньше использовал py-editdist и ADVAS. Оба они хороши в том смысле, что вы получаете одно число в качестве результата. Сначала ознакомьтесь с ADVAS, он реализует множество алгоритмов.

В Python есть дифлиб, как предлагали и другие.

difflib предлагает класс SequenceMatcher, который можно использовать для определения коэффициента сходства. Пример функции:

def text_compare(text1, text2, isjunk=None):
    return difflib.SequenceMatcher(isjunk, text1, text2).ratio()

В настоящее время я понимаю, что лучшим решением проблемы сценария кратчайшего редактирования (SES) является метод Майерса "средней змейки" с уточнением линейного пространства Хиршберга.

Алгоритм Майерса описан в:

E. Myers, ``An O(ND) Difference Algorithm and Its Variations,''
Algorithmica 1, 2 (1986), 251-266.

Утилита GNU diff использует алгоритм Майерса.

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

Обратите внимание, что ряд людей цитировал алгоритм расстояния Левенштейна, но он, хотя и легко реализуемый, не является оптимальным решением, поскольку он неэффективен (требует использования, возможно, огромной матрицы n * m) и не предоставляет сценарий редактирования "- последовательность изменений, которые можно использовать для преобразования одной последовательности в другую и наоборот.

Для хорошей реализации Майерса / Хиршберга посмотрите:

http://www.ioplex.com/~miallen/libmba/dl/src/diff.c

Конкретная библиотека, в которой он содержится, больше не поддерживается, но, насколько мне известно, сам модуль diff.c все еще верен.

Майк

Вы можете использовать решение проблемы самой длинной общей подпоследовательности (LCS). См. Также обсуждение возможных способов оптимизации этого решения.

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

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

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

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

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

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

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

Взгляните на модуль Нечеткое. Он имеет быстрые (написанные на C) алгоритмы на основе soundex, NYSIIS и двойного метафона.

Хорошее введение можно найти по адресу: http://www.informit.com/articles/article.aspx?p=1848528