Мне нужен алгоритм, который может сравнивать два текстовых файла и выделять их разницу и (даже лучше!) может рассчитать их различие значимым образом (например, два похожих файла должны иметь оценку подобия выше, чем два несходных файла, со словом "аналогичный", определенный в нормальных терминах). Это звучит легко реализовать, но это не так.
Реализация может быть в С# или python.
Спасибо.
В Python есть difflib, как и другие.
difflib предлагает класс SequenceMatcher, который можно использовать, чтобы дать вам коэффициент подобия. Пример функции:
def text_compare(text1, text2, isjunk=None):
return difflib.SequenceMatcher(isjunk, text1, text2).ratio()
Я могу порекомендовать взглянуть на код и статьи Нила Фрейзера:
В настоящее время доступно на Java, JavaScript, С++ и 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 использует алгоритм Майерса.
"Схожесть", о которой вы говорите, называется "расстоянием редактирования" в литературе, которое представляет собой количество вставок или удалений, необходимых для преобразования одной последовательности в другую.
Обратите внимание, что ряд людей процитировал алгоритм расстояния Левенштейна, но это легко реализовать, а не оптимальное решение, поскольку оно неэффективно (требует использования, возможно, огромной матрицы n * m) и не обеспечивает "edit script", который представляет собой последовательность изменений, которые могут быть использованы для преобразования одной последовательности в другую и наоборот.
Для хорошей реализации Майерса/Хиршберга:
http://www.ioplex.com/~miallen/libmba/dl/src/diff.c
Конкретная библиотека, в которой она содержится внутри, больше не поддерживается, но, насколько мне известно, сам модуль diff.c по-прежнему верен.
Mike
Если вам нужна более тонкая гранулярность, чем линии, вы можете использовать расстояние Левенштейна. Расстояние Левенштейна - это прямолинейная мера того, как аналогичные два текста. Вы также можете использовать его для извлечения журналов редактирования и может иметь очень мелкомасштабный diff, аналогичный тому, который находится на страницах истории изменений SO. Будьте осторожны, хотя расстояние Левенштейна может быть достаточно вычислительным и интенсивным для вычисления, поэтому использование difflib, как предположил Дуглас Ледер, скорее всего будет быстрее.
Cf. также этот ответ.
Существует несколько показателей расстояния, так как парадоджа упоминает о расстоянии Левенштейна, но есть также NYSIIS и Soundex. Что касается реализаций Python, я использовал py-editdist и ADVAS. Оба хороши в том смысле, что вы получаете один номер назад, как счет. Сначала проверьте ADVAS, он реализует кучу алгоритмов.
Как указано, используйте difflib. После того, как вы получите разный выход, вы можете найти расстояние Левенштейна разных строк, чтобы дать "ценность" того, насколько они различны.
Вы можете использовать решение проблемы с наибольшей общей субпоследовательностью (LCS). См. Также обсуждение возможных путей оптимизации этого решения.
Один метод, который я использовал для другой функции, чтобы вычислить, сколько данных было новым в модифицированном файле, возможно, может работать и на вас.
У меня есть реализация С# diff/patch, которая позволяет мне взять два файла, предположительно старую и новую версию того же самого файла, и вычислить "разницу", но не в обычном смысле этого слова. В основном я вычисляю набор операций, которые я могу выполнить на старой версии, чтобы обновить его до того же содержимого, что и новая версия.
Чтобы использовать это для первоначально описанной функции, чтобы увидеть, сколько данных было новым, я просто выполнял операции и для каждой операции, скопированной из старого файла дословно, которая имела 0-фактор и каждую операцию, которая вставленный новый текст (распространяемый как часть патча, поскольку он не встречался в старом файле) имел 1-фактор. Все символы получили этот factory, который дал мне в основном длинный список 0 и 1.
Все, что я тогда должен был сделать, это подсчет очков 0 и 1. В вашем случае с моей реализацией небольшое число 1 по сравнению с 0 будет означать, что файлы очень похожи.
Эта реализация также будет обрабатывать случаи, когда модифицированный файл вставлял копии из старого файла из строя или даже дублировал (т.е. копировал часть с начала файла и вставлял ее в нижней части), поскольку они оба будут копиями одной и той же оригинальной части из старого файла.
Я экспериментировал с взвешивающими копиями, так что первая копия подсчитывалась как 0, а последующие копии тех же символов имели прогрессивно более высокие коэффициенты, чтобы придать операции копирования/вставки некоторый "новый фактор", но я никогда не заканчивал это как проект был отменен.
Если вам интересно, мой код diff/patch доступен из моего репозитория Subversion.
Взгляните на модуль Fuzzy. Он имеет быстрые (написанные на C) алгоритмы для soundex, NYSIIS и двух-метафонов.
Хорошее введение можно найти по адресу: http://www.informit.com/articles/article.aspx?p=1848528