Книга: Фундаментальные алгоритмы и структуры данных в Delphi

Поиск различий между двумя файлами

Поиск различий между двумя файлами

Рассмотрим следующую задачу. Имеются две версии исходного файла, одна из которых - более поздняя, содержащая ряд изменений. Как выяснить различия между этими двумя файлами? Какие строки были добавлены, а какие удалены? Какие строки изменились?

Существует множество программ, выполняющих подобные функции. В их числе и программа diff, которую можно считать прародительницей всех программ сравнения файлов. Пакет Microsoft Windows SDK содержит программу, названную WinDiff. Программа Visual SourceSafe, поставляемая компанией Microsoft, также предоставляет функцию, которая позволяет выбрать две версии файла, хранящиеся в базе данных, и просмотреть различия между ними.

-------

Этот раздел адресован только тем программистам, которые работают в 32-разрядной среде. Рассмотренный здесь алгоритм является рекурсивным и интенсивно использует программный стек. Delphi1 не поддерживает достаточно большой стек, чтобы с его помощью можно было реализовать этот алгоритм даже для сравнительно умеренных по размеров файлов.

-------

Потратим несколько минут, и попытаемся определить требуемый для выполнения этой задачи алгоритм. Раньше я уже пытался сделать это, что оказалось достаточно трудно. Кое-что можно упростить сразу: изменение строки можно считать удалением старой строки и вставкой новой. Мы не будем углубляться в проблемы семантики, пытаясь выяснить, насколько сильно изменилась строка. Мы всего лишь будем рассматривать все изменения в текстовом файле как набор удаленных строк и набор вставленных новых строк.

Оглавление книги