Алгоритм разницы текста
https://stackoverflow.com/questions/145607
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Мне нужен алгоритм, который может сравнить два текстовых файла и выделить их разницу и (даже лучше!) Может вычислить их разницу осмысленным образом (например, два похожих файла должны иметь показатель сходства выше, чем два разных файла, со словом «похожие» определяется в обычных терминах).Звучит легко реализовать, но это не так.
Реализация может быть на C# или Python.
Спасибо.
Решение
В Python есть разница в библиотеке, как и другие предлагали.
difflib предлагает SequenceMatcher класс, который можно использовать для определения коэффициента сходства.Пример функции:
def text_compare(text1, text2, isjunk=None):
return difflib.SequenceMatcher(isjunk, text1, text2).ratio()
Другие советы
Я могу порекомендовать взглянуть на код и статьи Нила Фрейзера:
В настоящее время доступны в Java, JavaScript, C ++ и Python.Независимо от языка, каждая библиотека имеет одинаковый API и одинаковую функциональность.Все версии также имеют комплексные тестовые жгуты.
Нил Фрейзер:Стратегии различия - для теории и замечаний по реализации
Посмотри на разница в библиотеке.(Питон)
Это позволит рассчитать различия в различных форматах.Затем вы могли бы использовать размер разницы контекста как меру того, насколько различаются два документа?
Базар содержит альтернативный разностный алгоритм, называемый терпение разница (дополнительная информация есть в комментариях на этой странице), что, как утверждается, лучше, чем традиционный алгоритм сравнения.Файл «patiencediff.py» в базовом дистрибутиве представляет собой простой интерфейс командной строки.
Насколько я понимаю, лучшим решением проблемы кратчайшего сценария редактирования (SES) является метод «средней змеи» Майерса с уточнением линейного пространства Хиршберга.
Алгоритм Майерса описан в:
Э.Майерс, «Алгоритм разности O (ND) и его вариации»,
Алгоритмика 1, 2 (1986), 251-266.
Утилита GNU diff использует алгоритм Майерса.
«Показатель сходства», о котором вы говорите, в литературе называется «расстоянием редактирования», которое представляет собой количество вставок или удалений, необходимых для преобразования одной последовательности в другую.
Обратите внимание, что ряд людей цитировали алгоритм расстояния Левенштейна, но он, хотя и прост в реализации, не является оптимальным решением, поскольку он неэффективен (требует использования, возможно, огромной матрицы n*m) и не предоставляет «сценария редактирования». ", то есть последовательность изменений, которые можно использовать для преобразования одной последовательности в другую и наоборот.
Для хорошей реализации Майерса/Хиршберга посмотрите:
http://www.ioplex.com/~miallen/libmba/dl/src/diff.c
Конкретная библиотека, в которой он содержится, больше не поддерживается, но, насколько мне известно, сам модуль diff.c все еще работает.
Майк
Если вам нужна более тонкая детализация, чем у линий, вы можете использовать расстояние Левенштейна.Расстояние Левенштейна — это прямой показатель того, насколько похожи два текста.
Вы также можете использовать его для извлечения журналов изменений и получения очень детальных различий, аналогичных тем, что есть на страницах истории изменений SO.Однако имейте в виду, что вычисление расстояния Левенштейна может потребовать значительных ресурсов процессора и памяти, поэтому использование difflib, как предположил Дуглас Ледер, скорее всего, будет быстрее.
См.также этот ответ.
Существует ряд метрик расстояния, как упоминалось в Парадохе, есть расстояние Левенштейна, но есть также НИСИИС и Саундекс.Что касается реализаций Python, я использовал py-editdist и АДВАС до.Оба хороши в том смысле, что в качестве результата вы получаете одно число.Сначала проверьте ADVAS, он реализует кучу алгоритмов.
Как уже говорилось, используйте difflib.Получив дифференциальный вывод, вы можете найти Расстояние Левенштейна различных строк, чтобы дать «значение» того, насколько они различаются.
Вы можете использовать решение проблемы самой длинной общей подпоследовательности (LCS).См. также обсуждение возможных способов оптимизации этого решения.
Один метод, который я использовал для другой функциональности, — для расчета количества новых данных в измененном файле, возможно, подойдет и вам.
У меня есть реализация различий/исправлений C#, которая позволяет мне взять два файла, предположительно старую и новую версию одного и того же файла, и вычислить «разницу», но не в обычном смысле этого слова.По сути, я рассчитываю набор операций, которые я могу выполнить над старой версией, чтобы обновить ее, чтобы она имела то же содержимое, что и новая версия.
Чтобы использовать это для первоначально описанной функциональности, чтобы увидеть, сколько данных было новым, я просто пробежал операции, и для каждой операции, которая дословно копировала из старого файла, которая имела 0-фактор, и для каждой операции, которая вставляла новый текст (распространялся как часть патча, так как в старом файле его не было) имел 1-фактор.Все символы были переданы в эту фабрику, что дало мне, по сути, длинный список из 0 и 1.
Все, что мне тогда нужно было сделать, это подсчитать 0 и 1.В вашем случае, в моей реализации, небольшое количество единиц по сравнению с нулями будет означать, что файлы очень похожи.
Эта реализация также будет обрабатывать случаи, когда измененный файл вставляет копии старого файла не по порядку или даже дубликаты (т.вы копируете часть из начала файла и вставляете ее внизу), поскольку они оба будут копиями одной и той же исходной части из старого файла.
Я экспериментировал с взвешиванием копий так, чтобы первая копия считалась 0, а последующие копии тех же символов имели все более высокие коэффициенты, чтобы придать операции копирования/вставки некоторый «новый коэффициент», но я так и не закончил ее, поскольку проект был свернут.
Если вам интересно, мой код различий/исправлений доступен в моем репозитории Subversion.
Взгляните на Нечеткий модуль.Он имеет быстрые (написанные на C) алгоритмы для soundex, NYSIIS и двойного метафона.
Хорошее введение можно найти по адресу: http://www.informit.com/articles/article.aspx?p=1848528
