Текстовый алгоритм различия
Исключение нулевого указателя генерируется, когда приложение пытается использовать null в случае, когда требуется объект. К ним относятся:
- Вызов метода экземпляра объекта
null. - Доступ или изменение поля объекта
null. - Принимая длину
null, как если бы это был массив. - Доступ или изменение слотов
null, как если бы это был массив. - Бросок
nullкак будто это было значение Throwable.
Приложения должны бросать экземпляры этого класса, чтобы указать на другие незаконные использования объекта null.
Ссылка: http://docs.oracle.com/javase/8/docs/api/java/lang/NullPointerException.html
10 ответов
В Python, существует difflib, равно как и другие предложили.
difflib предложения класс SequenceMatcher , который может использоваться, чтобы дать Вам отношение подобия. Функция в качестве примера:
def text_compare(text1, text2, isjunk=None):
return difflib.SequenceMatcher(isjunk, text1, text2).ratio()
Я могу рекомендовать смотреть на код и статьи Neil Fraser:
, В настоящее время доступный в Java, JavaScript, C++ и Python. Независимо от языка каждая библиотека показывает тот же API и ту же функциональность. Все версии также имеют ремни безопасности комплексного испытания.
Neil Fraser: Различные Стратегии - для теории и примечаний реализации
Взгляд difflib. (Python)
, Который вычислит diffs в различных форматах. Вы могли тогда использовать размер разности контекста как мера того, как различные два документа?
Базар содержит альтернативный алгоритм различия, названный разность терпения (существует больше информации в комментариях, что страница), который, как утверждают, лучше, чем традиционный различный алгоритм. Файл 'patiencediff.py' в распределении базара является простым фронтэндом командной строки.
При необходимости в более прекрасной гранулярности, чем строки можно использовать расстояние Левенштейна. Расстояние Левенштейна является простой мерой о том, как к подобным двум текстам.
можно также использовать его для извлечения журналов редактирования, и может очень мелкомодульная разность, подобная этому на страницах истории редактирования ТАК. Предупредите, хотя то расстояние Левенштейна может быть вполне ЦП - и интенсивно использующий память для вычисления, таким образом с помощью difflib, поскольку предложенный Douglas Leder, скорее всего, собирается быть быстрее.
Cf. также этот ответ .
Мое текущее понимание - то, что лучшим решением проблемы Самого короткого сценария редактирования (SES) является метод "средней змеи" Myers с Хиршбергом линейное улучшение пространства.
алгоритм Myers описан в:
E. Myers, ''O (ND) Алгоритм Различия и Его Изменения'',
Algorithmica 1, 2 (1986), 251-266.
утилита разности GNU использует алгоритм Myers.
"счет подобия", о котором Вы говорите, называют "расстоянием редактирования" в литературе, которая является количеством вставок или удаляет необходимый для преобразования одной последовательности в другой.
Примечание, что много людей процитировали алгоритм расстояния Левенштейна, но то есть, хотя легкий для реализации, не оптимальное решение, поскольку это неэффективно (требует использования возможно огромной n*m матрицы) и не предоставляет "сценарий редактирования", который является последовательностью редактирований, которые могли использоваться для преобразования одной последовательности в другой и наоборот.
Для хорошего Myers / взгляд реализации Хиршберга на:
http://www.ioplex.com/~miallen/libmba/dl/src/diff.c
конкретная библиотека, в которой это содержится, больше не сохраняется, но к моему знанию сам diff.c модуль все еще корректен.
Mike
Существует много метрик расстояния, поскольку paradoja упомянул, что существует расстояние Левенштейна, но существует также NYSIIS и Soundex. С точки зрения реализаций Python я использовал py-editdist и ADVAS прежде. Оба хороши в том смысле, что Вы возвращаете единственное число как счет. Проверьте ADVAS сначала, он реализует набор алгоритмов.
Как указано, используйте difflib. Как только у Вас есть вывод diffed, можно найти расстояние Левенштейна из различных строк для предоставления "значения" того, насколько отличающийся они.
Один метод, который я использовал для другой функциональности, чтобы подсчитать, сколько данных было новым в измененном файле, возможно, также может сработать для вас.
У меня есть C # реализация diff / patch, которая позволяет мне использовать два файла, предположительно старая и новая версия одного и того же файла, и вычисляют «разницу», но не в обычном смысле этого слова. В основном я рассчитываю набор операций, которые я могу выполнить со старой версией, чтобы обновить ее, чтобы она имела то же содержимое, что и новая версия.
Чтобы использовать это для первоначально описанной функциональности, чтобы увидеть, сколько данных было новым, я просто выполнял операции, и для каждой операции, которая дословно копировалась из старого файла с нулевым коэффициентом, и каждой операции, которая вставляла новый текст (распространяется как часть патча, так как он не выполнялся в старом файле) имел 1-фактор. Всем персонажам была предоставлена эта фабрика, которая дала мне в основном длинный список из 0 и 1.
Все, что мне оставалось сделать, это подсчитать 0 и 1. В вашем случае с моей реализацией меньшее количество единиц по сравнению с нулем означало бы, что файлы очень похожи.
Эта реализация также будет обрабатывать случаи, когда в измененный файл были вставлены копии из старого файла не по порядку, или даже дубликаты (т. е. вы копируете часть с начала файла и вставляете ее ближе к низу), поскольку они обе будут копиями одной и той же исходной части из старого файла.
Я экспериментировал с взвешиванием копий, так что первая копия засчитывалась как 0, а последующие копии тех же символов имели прогрессивно более высокие коэффициенты, чтобы придать операции копирования / вставки некоторый «новый коэффициент»,
Можно использовать решение для самой длинной общей последовательности (LCS) . См. также обсуждение возможных путей оптимизации этого решения.
.