Алгоритм разницы текста

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

Реализация может быть в c # или python.

Благодарю.

11 Solutions collect form web for “Алгоритм разницы текста”

В Python есть difflib , как и другие предложили.

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

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

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

Google-Diff-матч-патч

В настоящее время доступны Java, JavaScript, C ++ и Python. Независимо от языка, каждая библиотека имеет тот же API и те же функции. Все версии также имеют комплектные испытательные жгуты.

Neil Fraser: Diff Strategies – для комментариев теории и реализации

Посмотрите на difflib . (Python)

Это позволит рассчитать различия в различных форматах. Тогда вы могли бы использовать размер контекста diff как показатель того, как разные два документа?

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

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

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

Э. Майерс, «Алгоритм разностных уравнений O (ND) и его вариации»,
Алгоритмика 1, 2 (1986), 251-266.

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

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

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

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

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

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

Майк

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • Внедрение API DiffMatchPatch от Google для Python 2/3
  • Алгоритм обнаружения похожих документов в скрипте python
  • Как распечатать сравнение двух многострочных строк в унифицированном формате diff?
  • Как программно объединить текстовые файлы с потенциальными конфликтами (ala git или svn и т. Д.)?
  • Сравнить фрагменты XML?
  • Создать довольно diff html в Python
  • Разнообразный JSON
  • как определить, была ли изменена веб-страница
  • Python - лучший язык программирования в мире.