Люди, использующие системы контроля версий исходного кода (SVN, Mercurial, Git и т.п.), наверняка часто пользуются возможностью сравнения версий файлов для просмотра внесенных пользователями изменений. Существует множество независимых программ сравнения версий (WinMerge, BeyondCompare и др.). При сравнении версий, как правило, две версии файла показываются рядом друг с другом таким образом, чтобы одинаковые (неизменившиеся) части документов были расположены напротив друг друга, а изменившиеся (добавленные и удаленные) выделяются соответствующим цветом.
Уверен, многим было бы интересно узнать, какие алгоритмы могут использоваться для реализации такого сравнения.
В качестве простейшего случая рассмотрим сравнение простых текстовых (plain text) файлов.
Текстовый файл — это набор строк (а точнее абзацев) текста. Абзац — это строка символов, заканчивающая символами конца строки и перевода каретки (в Windows) или только одним символом конца строки (в Unix/Linux). Не будем отвлекаться на то, что символы могут быть представлены различными кодировками и будем считать, что мы имеем дело с однобайтной ASCII. Задача сравнения версий такого файла заключается в определении того, какие абзацы не изменились, а какие изменились, были удалены или добавлены.
Большинство алгоритмов сравнения файлов основаны на алгоритме поиска самой длинной совпадающей подпоследовательности (LCS, Longest Common Subsequence). Действительно, самая длинная общая подпоследовательность символов двух файлов можно считать неизменившейся частью, а все остальные участки (в зависимости от их принадлежности к одной из версий) являются удаленными (если они принадлежат старой версии) или добавленными (если принадлежат новой). Существует несколько реализаций алгоритма LCS, вычислительная сложность которых варьируется от полиномиальной (прямо пропорциональной длинам сравниваемых подпоследовательностей) до логарифмической. Данные алгоритмы также очень требовательны к памяти. Становится понятно, что использовать посимвольное представление документов в таких условиях нереально. Удобнее в качестве единиц сравнения использовать абзацы. Их можно сравнивать «как есть», т.е. непосредственно как строки, но в целях оптимизации удобнее их прохэшировать и сравнивать хэши, а к самим строкам обращаться только в случае совпадения хэшей (т.к. от коллизий при хэшировании никто не застрахован).
Таким образом, первый этап алгоритма сравнения заключается в загрузке списка абзацев документов в память (да, нам действительно придется загрузить оба сравниваемых документа целиком в память), их хэшировании и применении к полученным хэшам алгоритма поиска наибольшей общей совпадающей подпоследовательности (LCS). На выходе данного этапа мы получим информацию о гарантированно неизменившихся (т.е. совпадающих) участках документов. Все остальные участки являются изменившимися. Если изменившемуся участку из старой версии соответствует пустой участок в новой версии, значит этот участок был удален. Если изменившемуся участку новой версии соответствует пустой участок в старой версии, значит этот участок был добавлен.
Сложнее дело обстоит с измененными участками, присутствующими и в старой, и в новой версии. Например, между двумя совпадающими участками может располагаться изменившийся участок, который в старой версии составлял два абзаца, а в новой — три. Равных (совпадающих) абзацев среди этих пяти абзацев нет. Если остановиться на этом шаге, можно просто при показе пользователю выделить эти группы абзацев целиком как измененные и переложить задачу анализа подробных изменений на пользователя. Но можно поступить хитрее. Можно рассчитать оптимальное соответствие для абзацев измененного участка, чтобы точно знать, какой которому соответствует. Для оценки «похожести» каждой пары абзацев можно применить алгоритм расчета так называемой «дистанции редактирования» (или расстояния Левенштейна). Дистанция редактирования — это минимальное количество операций вставки, удаления и замены одного символа на другой, необходимых для превращения одной строки в другую. Вычислив дистанцию редактирования между каждой парой абзацев измененного участка, мы можем применить метод динамического программирования для вычисления оптимального соответствия между абзацами измененного участка. Самым неоптимальным вариантом размещения при этом является тот, когда все абзацы измененного участка в старой версии считаются удаленными, а все абзацы новой версии — добавленными (т.е. никто никому не соответствует). Все остальные варианты размещения будут более оптимальны. Применив метод динамического программирования (как именно его можно в данном случае применить, напишу в другом посте) можно найти самый оптимальный вариант соответствия. Теперь мы уже точно знаем, какой абзац измененного участка какому соответствует и сможем применить алгоритм сравнения (на этот раз уже посимвольный) для вычисления точных изменений внутри абзаца.
Если уважаемым читателям интересны подробности и особенности реализации алгоритмов поиска наибольшей общей подпоследовательности, дистанции редактирования и применения метода динамического программирования для вычисления оптимального соответствия группы изменившихся абзацев (последний алгоритм я считаю своего рода моим ноу-хау), просьба писать об этом в комментариях, и я напишу об этом более подробные посты (каждый из этих алгоритмов сам по себе очень интересен и заслуживает отдельного поста).
Уверен, многим было бы интересно узнать, какие алгоритмы могут использоваться для реализации такого сравнения.
В качестве простейшего случая рассмотрим сравнение простых текстовых (plain text) файлов.
Текстовый файл — это набор строк (а точнее абзацев) текста. Абзац — это строка символов, заканчивающая символами конца строки и перевода каретки (в Windows) или только одним символом конца строки (в Unix/Linux). Не будем отвлекаться на то, что символы могут быть представлены различными кодировками и будем считать, что мы имеем дело с однобайтной ASCII. Задача сравнения версий такого файла заключается в определении того, какие абзацы не изменились, а какие изменились, были удалены или добавлены.
Большинство алгоритмов сравнения файлов основаны на алгоритме поиска самой длинной совпадающей подпоследовательности (LCS, Longest Common Subsequence). Действительно, самая длинная общая подпоследовательность символов двух файлов можно считать неизменившейся частью, а все остальные участки (в зависимости от их принадлежности к одной из версий) являются удаленными (если они принадлежат старой версии) или добавленными (если принадлежат новой). Существует несколько реализаций алгоритма LCS, вычислительная сложность которых варьируется от полиномиальной (прямо пропорциональной длинам сравниваемых подпоследовательностей) до логарифмической. Данные алгоритмы также очень требовательны к памяти. Становится понятно, что использовать посимвольное представление документов в таких условиях нереально. Удобнее в качестве единиц сравнения использовать абзацы. Их можно сравнивать «как есть», т.е. непосредственно как строки, но в целях оптимизации удобнее их прохэшировать и сравнивать хэши, а к самим строкам обращаться только в случае совпадения хэшей (т.к. от коллизий при хэшировании никто не застрахован).
Таким образом, первый этап алгоритма сравнения заключается в загрузке списка абзацев документов в память (да, нам действительно придется загрузить оба сравниваемых документа целиком в память), их хэшировании и применении к полученным хэшам алгоритма поиска наибольшей общей совпадающей подпоследовательности (LCS). На выходе данного этапа мы получим информацию о гарантированно неизменившихся (т.е. совпадающих) участках документов. Все остальные участки являются изменившимися. Если изменившемуся участку из старой версии соответствует пустой участок в новой версии, значит этот участок был удален. Если изменившемуся участку новой версии соответствует пустой участок в старой версии, значит этот участок был добавлен.
Сложнее дело обстоит с измененными участками, присутствующими и в старой, и в новой версии. Например, между двумя совпадающими участками может располагаться изменившийся участок, который в старой версии составлял два абзаца, а в новой — три. Равных (совпадающих) абзацев среди этих пяти абзацев нет. Если остановиться на этом шаге, можно просто при показе пользователю выделить эти группы абзацев целиком как измененные и переложить задачу анализа подробных изменений на пользователя. Но можно поступить хитрее. Можно рассчитать оптимальное соответствие для абзацев измененного участка, чтобы точно знать, какой которому соответствует. Для оценки «похожести» каждой пары абзацев можно применить алгоритм расчета так называемой «дистанции редактирования» (или расстояния Левенштейна). Дистанция редактирования — это минимальное количество операций вставки, удаления и замены одного символа на другой, необходимых для превращения одной строки в другую. Вычислив дистанцию редактирования между каждой парой абзацев измененного участка, мы можем применить метод динамического программирования для вычисления оптимального соответствия между абзацами измененного участка. Самым неоптимальным вариантом размещения при этом является тот, когда все абзацы измененного участка в старой версии считаются удаленными, а все абзацы новой версии — добавленными (т.е. никто никому не соответствует). Все остальные варианты размещения будут более оптимальны. Применив метод динамического программирования (как именно его можно в данном случае применить, напишу в другом посте) можно найти самый оптимальный вариант соответствия. Теперь мы уже точно знаем, какой абзац измененного участка какому соответствует и сможем применить алгоритм сравнения (на этот раз уже посимвольный) для вычисления точных изменений внутри абзаца.
Если уважаемым читателям интересны подробности и особенности реализации алгоритмов поиска наибольшей общей подпоследовательности, дистанции редактирования и применения метода динамического программирования для вычисления оптимального соответствия группы изменившихся абзацев (последний алгоритм я считаю своего рода моим ноу-хау), просьба писать об этом в комментариях, и я напишу об этом более подробные посты (каждый из этих алгоритмов сам по себе очень интересен и заслуживает отдельного поста).
