Разностный алгоритм O(ND) для C#
Данная статья посвящена сравнению текстовых файлов и лучшему и самому известному алгоритму нахождения различий между ними.
Введение
Данная статья посвящена сравнению текстовых файлов и лучшему и самому известному алгоритму нахождения различий между ними. Исходный код, находящийся в загрузке, реализует маленький класс с простым в применении интерфейсом прикладного программирования (API), выполняющим эту работу. Он должен быть в вашей коллекции алгоритмов.
Кроме класса, реализующего алгоритм, еще есть пример веб-приложения, сравнивающего два файла и генерирующего вывод HTML с объединенным и окрашенным документом.
Впервые алгоритм был опубликован Евгением Майером 20 лет назад под названием "Разностный алгоритм O(ND) и его вариации". В его статье дано абстрактное рекурсивное определение алгоритма с использованием псевдокода, требующего перевода на существующий язык программирования.
В интернете есть много общедоступных реализаций данного алгоритма на C, Java и Lisp. Перед написанием версии на C# было выяснено, что почти все эти реализации взяты из одного источника (GNU diffutils), доступного по (несвободной) открытой лицензии GNU, и поэтому не могут использоваться как исходный код для коммерческого или свободно распространяемого приложения без ограничений лицензии GNU.
Есть очень старые реализации на C, использующие другие (худшие) эвристические алгоритмы. Microsoft также опубликовал исходный код разностного инструмента (WinDiff), использующего древовидные структуры. Также прямой перенос из исходника C в C# непрост, потому что в типичных решениях C есть много арифметических операций с указателями, и требовалась управляемое решение. В результате проверки многих исходников не было найдено приемлемое решение, написанное для платформы .NET.
Не был нужен быстродействующий разностный инструмент. По мере необходимости производительность будет настраиваться. Также в исходном коде были оставлены указания по этому предмету.
Как алгоритм работает (кратко)
• Сравнение символов двух огромных текстовых файлов тяжело реализуется и является медленным. Сравнивать числа гораздо проще, поэтому сначала вычисляются уникальные числа для всех текстовых строк. Если текстовые строки одинаковы, то вычисляются одинаковые числа.
• Перед вычислением этих чисел надо рассмотреть несколько вариантов, полезных для текста: удаление пробелов и сравнение без учета регистра.
• Сам основной алгоритм будет сравнивать два массива чисел, и подготовка осуществляется в закрытом методе DiffCodes и с использованием Hashtable.
• Методы – DiffText и DiffInts.
• Ядро алгоритма построено на базе двух методов:
o LCS: Это реализация «разделяй и властвуй» алгоритма самой длинной общей подпоследовательности.
o SMS: Этот алгоритм находит самую короткую среднюю змею.
• Оригинальный алгоритм был изменен для повышения быстродействия. Оригинальный алгоритм описан с помощью рекурсивного подхода и сравнивает индексированные нулями последовательности, и передает части этих последовательностей как параметры. Извлечение подмассивов и их соединение сильно нагружает процессор и память. Чтобы избежать копирования этих последовательностей как массивов, используемые массивы вместе с нижней и верхней границами передаются, пока последовательности не копируются постоянно. Эти обстоятельства усложняют функции LCS и SMS.
• Был добавлен некоторый код в функцию LCS, чтобы получать быстрый отклик на подмассивы, которые одинаковы, полностью удалены или вставлены вместо рекурсивного анализа их вплоть до отдельного числа.
• Результат сохраняется в двух массивах, помечаемых на измененные (удаленные или вставленные) строки в двух массивах данных, затем эти биты анализируются для выработки массива объектов, описывающих найденные различия.
• Прочитайте оригинальную статью, если хотите узнать больше.
Интерфейс прикладного программирования (API)
Для использования данной функциональности надо лишь вызвать один из методов DiffText. Все они принимают пару строк и возвращают массив элементов, описывающих вставки и удаления между двумя строками. Не сообщается об "изменениях". Зато можно найти "вставленную" и "удаленную" пару.
DiffText(string TextA, string TextB)
Находит различие между двумя текстами, сравнивая по текстовым строкам без преобразования. Возвращает массив элементов, содержащих различия.
DiffText(string TextA, string TextB, bool trimSpace, bool ignoreSpace, bool ignoreCase)
Находит различие между двумя текстами, сравнивая по текстовым строкам с некоторыми дополнительными преобразованиями. Возвращает массив элементов, содержащих различия.
Diff(int[] ArrayA, int[] ArrayB)
Находит различие между двумя массивами целых чисел. Возвращает массив элементов, содержащих различия.
Пример приложения для алгоритма
Пример – маленькое веб-приложение, вычисляющее разницу между двумя текстовыми файлами и выводящее результат на экран с помощью HTML.
Чтобы установить пример, надо создать веб-проект и скопировать все файлы из zip-архива в каталог. Реализация алгоритма содержится в классе "diff.cs".
Дополнительные возможные оптимизации (если нужна скорость)
(Первое правило: не делай этого; второе: не делай этого пока.)
Массивы DataA и DataB передаются как параметры, но вообще не меняются после создания, поэтому их можно использовать как члены класса во избежание затрат на параметры. В SMS есть много граничной арифметики в циклах for-D и for-k, которую можно делать путем увеличения и уменьшения локальных переменных. Массивы DownVector и UpVector всегда создаются и уничтожаются при каждом вызове SMS. Можно повторно использовать их при передаче их членам класса.
Проблемы безопасности веб-приложения
• Использование этой реализации веб-сайта позволяет клиентам просмотреть весь исходный код вашего веб-сайта. Не используйте его в неизменном виде на общедоступном сервере.
• Надо реализовать проверку параметров и разрешать выводить различия только для файлов, которые можно вывести на экран (текстовых файлов).
Встроенная самопроверка
Класс имеет встроенную самопроверку, работающую без изменения кода. Если вы скомпилируете diff и отладите файлы класса вместе, то получите файл EXE, проверяющий несколько простых ситуаций различий, использовавшихся для обнаружения ошибок в версиях 1 и 2 (как правило, OutOfArrayBounds).
Команда компиляции:
csc /target:exe /out:diffTest.exe /debug /d:SELFTEST Diff.cs Debug.cs