Это сложный вопрос. Выполнение различий означает нахождение минимального расстояния редактирования между двумя файлами. То есть минимальное количество изменений, которое вы должны сделать, чтобы преобразовать один файл в другой. Это эквивалентно нахождению самой длинной общей подпоследовательности строк между двумя файлами, и это является основой для различных программ сравнения. Самая длинная распространенная проблема подпоследовательности хорошо известна, и вы сможете найти решение для динамического программирования в Google.
Проблема с подходом динамического программирования состоит в том, что это O (n ^ 2). Таким образом, он очень медленный для больших файлов и непригоден для больших двоичных строк. Сложной частью при написании программы diff является оптимизация алгоритма для вашей проблемной области, чтобы вы получили разумную производительность (и приемлемые результаты). В статье «Алгоритм сравнения дифференциальных файлов» Ханта и Макилроя дается хорошее описание ранней версии утилиты Unix diff.