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

Question

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

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

Спасибо.

Answer 1

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

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

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

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

Answer 2

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

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

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

Answer 3

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

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

Answer 4

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

Answer 5

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

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

E. Майерс, `` O (ND) Разница Алгоритм и его вариации, ''
Algorithmica 1, 2 (1986), 251-266.

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

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

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

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

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

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

Mike

Answer 6

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

Cf. также этот ответ .

Answer 7

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

Answer 8

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

Answer 9

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

Answer 10

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

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