Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

3.2. Алгоритм diff

3.2.1. Команда git diff

Важной частью распределённой системы контроля версий (СКВ) git [36] является средство сравнения разных версий изменившегося файла, позволяющее отследить, какие именно фрагменты файла были изменены. В этом разделе рассмотрим команду git diff, а затем реализуем её упрощённый вариант на основе модифицированного расстояния Левенштейна.

Основой git diff является алгоритм, решающий задачу вычисления наибольшей общей подпоследовательности (Longest Common Subsequence, LCS). Известно множество алгоритмов для решения задачи LCS, различающихся по своим характеристикам. В git поддерживаются такие алгоритмы, как Patience, Minimal, Histogram, Myers, причём по умолчанию используется алгоритм Myers [36]. Мы реализуем простейший из diff-алгоритмов, основанный на модифицированном расстоянии Левенштейна, в котором, в отличие от расстояния Левенштейна [37], нет операции замены символа.

Начнём работу с создания нового репозитория, воспользовавшись для этого командой git init, и добавим в созданный репозиторий новый файл fib.py, содержащий функцию для вычисления чисел Фибоначчи, реализованную на языке Python. После этого добавим файл fib.py в область индексирования при помощи команды git add fib.py и выведем список изменений, внесённых в репозиторий.

Выводом команды git diff --cached является содержимое файла fib.py, каждая строка которого помечена знаком «+», поскольку файл fib.py ранее отсутствовал в репозитории. Сделаем новый коммит:

~$ mkdir repo
~$ cd repo
~/repo$ echo "def fib(n):
>     fibs = [0, 1]
>     for _ in range(n):
>         fibs.append(fibs[-1] + fibs[-2])
>     return fibs[-2]" > fib.py
~/repo$ git init
Initialized empty Git repository in /home/artyom/Github/repo/.git/
~/repo$ git add fib.py
~/repo$ git diff --cached
diff --git a/fib.py b/fib.py
new file mode 100644
index 0000000..719362a
--- /dev/null
+++ b/fib.py
@@ -0,0 +1,5 @@
+def fib(n):
+    fibs = [0, 1]
+    for _ in range(n):
+        fibs.append(fibs[-1] + fibs[-2])
+    return fibs[-2]
~/repo$ git commit -m "Initial commit"
[master (root-commit) bb07669] Initial commit
 1 file changed, 5 insertions(+)
 create mode 100644 fib.py

Реализованный в записанной в файл fib.py функции fib алгоритм вычисления \(n\)-го числа Фибоначчи сейчас имеет пространственную сложность \(O(n)\), поскольку для вычисления \(n\)-го числа необходимо создать список fibs, содержащий n + 2 вычисленных чисел.

Улучшим функцию fib, заменив список fibs на 2 переменные, в которых находятся 2 числа Фибоначчи, вычисленных последними – пространственная сложность исправленного алгоритма составит \(O(1)\).

Обновим файл fib.py, добавим его в область индексирования и выведем список внесённых в файл изменений при помощи команды git diff --cached:

~/repo$ echo "def fib(n):
>     a, b = 0, 1
>     for _ in range(n):
>         a, b = b, a + b
>     return a" > fib.py
~/repo$ git add .
~/repo$ git diff --cached
diff --git a/fib.py b/fib.py
index 719362a..34ac5a2 100644
--- a/fib.py
+++ b/fib.py
@@ -1,5 +1,5 @@
 def fib(n):
-    fibs = [0, 1]
+    a, b = 0, 1
     for _ in range(n):
-        fibs.append(fibs[-1] + fibs[-2])
-    return fibs[-2]
+        a, b = b, a + b
+    return a

Каждая строка выведенного в консоль содержимого файла fib.py помечена знаком «+», помечена знаком «-» или не помечена вовсе. Команда git diff расставляет метки на основе выявленной разницы между старым содержимым изменённого файла и его новым содержимым – добавленная в изменённый файл строка помечается знаком «+», удалённая строка помечается знаком «-», а строки, оставленные без изменений, не помечаются.

Исходя из вывода утилиты git diff можно сделать вывод, что для преобразования функции fib в её улучшенный вариант потребовалось удалить 3 строки с кодом, обрабатывающим список вычисленных чисел Фибоначчи fibs, и добавить 3 строки с кодом для работы с переменными a и b, содержащими 2 числа, вычисленных последними.

3.2.2. Расстояние Левенштейна

Теперь попробуем реализовать утилиту, аналогичную git diff, на основе модифицированного редакционного расстояния, предложенного в 1965 г. советским и российским математиком В.И. Левенштейном [37].

В работе [37] исследовались вопросы передачи двоичной информации с исправлением ошибок, однако расстояние Левенштейна сегодня применяется и для сравнения последовательностей из символов, отличных от нулей и единиц.

Расстояние Левенштейна может быть определено как минимальное число операций замены, вставки и удаления символов, необходимых для преобразования одной последовательности символов в другую.

Расстояние Левенштейна можно определить как:

$$ f(\text{a}, \text{b}, i, j) = \begin{cases} \max(i, j), & \text{если } i = 0 \text{ или } j = 0, \\ f(\text{a}, \text{b}, i-1, j-1), & \text{если } \text{a}_i = \text{b}_j, \\ 1 + \min \left( \begin{array}{} f(\text{a}, \text{b}, i, j-1), \\ f(\text{a}, \text{b}, i-1, j), \\ f(\text{a}, \text{b}, i-1, j-1) \end{array} \right), & \text{если } \text{a}_i \neq \text{b}_j. \end{cases} $$ (4)

В формуле (4) \(\text{a}\) и \(\text{b}\) – это сравниваемые последовательности символов, \(i\) – это номер символа в последовательности \(\text{a}\), \(j\) – номер символа в последовательности \(\text{b}\). Номера 1-х символов в последовательностях \(\text{a}\) и \(\text{b}\) равны 1, начальным значением \(i\) является длина \(\text{a}\), начальным значением \(j\) является длина \(\text{b}\).

Если номер символа \(i\) в формуле (4) равен 0, то это значит, что в \(\text{a}\) больше не осталось символов, и чтобы превратить пустую последовательность в \(\text{b}\), необходимо выполнить \(j\) операций вставки символа в \(\text{a}\). Если номер символа \(j\) в формуле (4) равен 0, то необходимо выполнить \(i\) операций удаления символа из \(\text{a}\), поскольку в \(\text{b}\) больше не осталось символов. Если символ \(\text{a}_i\), имеющий номер \(i\) в последовательности \(\text{a}\), равен символу \(\text{b}_j\), то необходимо уменьшить номера символов \(i\) и \(j\) без увеличения значения расстояния Левенштейна.

Если символы \(\text{a}_i\) и \(\text{b}_j\) не равны друг другу, то редакционное расстояние по формуле (4) всегда увеличивается на 1, после чего необходимо или вставить в \(\text{a}\) символ из \(\text{b}\), или удалить из \(\text{a}\) символ, присутствующий в \(\text{b}\), или заменить символ \(\text{a}_i\) на символ \(\text{b}_j\) – выбирается действие, которое приводит к наименьшему редакционному расстоянию.

Попробуем реализовать утилиту командной строки для вычисления расстояния Левенштейна на языке Python по формуле (4).

Поместим в файл diff.py следующий код:

import sys
from functools import cache

@cache
def diff(a, b, i=0, j=0):
    if i == len(a):
        return len(b) - j
    if j == len(b):
        return len(a) - i
    if a[i] == b[j]:
        return diff(a, b, i + 1, j + 1)
    return 1 + min(
        diff(a, b, i, j + 1),
        diff(a, b, i + 1, j),
        diff(a, b, i + 1, j + 1))

print(diff(sys.argv[1], sys.argv[2]))

Для удобства при сравнении последовательностей будем двигаться не от последних символов в \(\text{a}\) и \(\text{b}\) к первым, как в формуле (4), а от первых символов к последним. Для вычисления длин последовательностей воспользуемся стандартной функцией len.

Для ускорения вычислений значений рекурсивной функции diff мы воспользовались механизмом запоминания промежуточных результатов, применив к реализованной функции декоратор cache из модуля functools [12].

Проверим работу программы, попробовав вычислить из командной строки редакционное расстояние:

~$ python diff.py столб слон
3
~$ python diff.py стол слон
2
~$ python diff.py слон слон
0

Легко убедиться в корректности работы функции diff, вручную вычислив расстояние Левенштейна между строками, использованными в качестве примеров, по формуле (4). Например, для преобразования строки «столб» в строку «слон» необходимо выполнить 3 действия – из первой строки удалить последний символ «б», заменить 2-й символ «т» на «л», заменить 4-й символ «л» на «н». Расстояние Левенштейна между строками «столб» и «слон» равно 3.

3.2.3. diff на основе расстояния Левенштейна

Модифицируем реализованный алгоритм вычисления расстояния Левенштейна следующим образом: операцию замены одного символа на другой преобразуем в последовательность операций удаления старого символа и добавления нового путём исключения в формуле (4) из аргументов функции min 3-го выражения, соответствующего замене символа.

Кроме того, теперь функция diff будет работать не с последовательностями символов, а с последовательностями строк. Результатом её работы станет не численное значение редакционного расстояния, а список пар, содержащих метку строки и саму строку – тем самым мы добавим в нашу утилиту командной строки diff.py поддержку вывода меток для отличающихся строк, как в выводе команды git diff.

Для операции добавления строки меткой является символ «+», для операции удаления – символ «-», а операция замены в модифицированном расстоянии Левенштейна не поддерживается:

import sys
from functools import cache

@cache
def diff(a, b, i=0, j=0):
    if i == len(a):
        return [('+', b[x]) for x in range(j, len(b))]
    if j == len(b):
        return [('-', a[x]) for x in range(i, len(a))]
    if a[i] == b[j]:
        return [(' ', a[i])] + diff(a, b, i + 1, j + 1)
    return min(
        [('+', b[j])] + diff(a, b, i, j + 1),
        [('-', a[i])] + diff(a, b, i + 1, j),
        key=len)

with open(sys.argv[1]) as file:
    a = tuple(file.readlines())

with open(sys.argv[2]) as file:
    b = tuple(file.readlines())

for op, line in diff(a, b):
    print(op, line.rstrip())

В обновлённой функции diff, как и в git diff, метки указываются только для добавленных строк и для удалённых строк, а строки, оставшиеся без изменений, никак не помечаются. Списки кортежей, состоящих из метки строки и самой строки, генерируются при помощи списковых включений [12] и склеиваются при помощи оператора сложения списков.

При помощи функции open мы открываем на чтение 2 файла, пути к которым передаются как аргументы командной строки. Кортежи, состоящие из строк, содержащихся в файлах с указанными именами, подаются на вход функции diff. Результат работы diff выводится построчно в stdout.

Сравним результат работы обновлённой утилиты diff.py с результатом работы команды git diff. Для этого создадим файл fib.py, содержащий реализацию алгоритма вычисления \(n\)-го числа Фибоначчи с пространственной сложностью \(O(n)\), а также файл fib_new.py, содержащий реализацию улучшенного алгоритма с пространственной сложностью \(O(1)\). После этого выведем на экран различия между 2 файлами с кодом на Python при помощи утилиты diff.py и команды git diff:

~$ echo "def fib(n):
>     fibs = [0, 1]
>     for _ in range(n):
>         fibs.append(fibs[-1] + fibs[-2])
>     return fibs[-2]
>" > fib.py
~$ echo "def fib(n):
>     a, b = 0, 1
>     for _ in range(n):
>         a, b = b, a + b
>     return a
>" > fib_new.py
~$ git diff --no-index fib.py fib_new.py
diff --git a/fib.py b/fib_new.py
index 719362a..34ac5a2 100644
--- a/fib.py
+++ b/fib_new.py
@@ -1,5 +1,5 @@
 def fib(n):
-    fibs = [0, 1]
+    a, b = 0, 1
     for _ in range(n):
-        fibs.append(fibs[-1] + fibs[-2])
-    return fibs[-2]
+        a, b = b, a + b
+    return a
~$ python diff.py fib.py fib_new.py
  def fib(n):
+     a, b = 0, 1
-     fibs = [0, 1]
      for _ in range(n):
+         a, b = b, a + b
+     return a
-         fibs.append(fibs[-1] + fibs[-2])
-     return fibs[-2]

Опция --no-index команды git diff позволяет найти различия между файлами, находящимися вне git-репозитория.

Вывод нашей утилиты diff.py, основанной на модифицированном расстоянии Левенштейна, в котором, в отличие от [37], нет операции замены, похож на вывод команды git diff. Однако, сначала выводятся добавленные строки с меткой «+», и только после них – удалённые строки с меткой «-». Кроме того, отсутствует заголовок, содержащий имена сравниваемых файлов и номера строк.

3.2.4. Упражнения

Задача 1. Оцените diff-алгоритмы, такие как Patience, Minimal, Histogram, Myers [36], с точки зрения различия получаемых результатов на конкретных примерах. Какой алгоритм Вы считаете предпочтительным и почему?

Задача 2. Детально сравните работу реализованной утилиты diff.py и команды git diff с diff-алгоритмом, используемым в git diff по умолчанию. Объясните различия в выводе. Исправьте реализацию diff.py, чтобы добиться идентичного поведения.

Задача 3. С использованием функции расстояния Левенштейна можно получить последовательность команд редактирования, которые превращают исходную последовательность в результат. Это может помочь компактно хранить данные – для измененной версии файла мы храним только команды, которые производят эти изменения.

Реализуйте генератор кода, который из исходной последовательности создаёт последовательность-результат с помощью минимального числа операций вставки, замены и удаления. Пример работы такого генератора, реализованного на Python:

~$ python diff-gen.py "достаток" "остаточный"
x[7] = y[9]
x.insert(7, y[8])
x.insert(7, y[7])
x.insert(7, y[6])
del x[0]

Задача 4. Реализуйте графический интерфейс для утилиты diff.py. В графическом интерфейсе должна поддерживаться подсветка как удалённых и добавленных строк, так и отличающихся символов в старой и новой строке. Постарайтесь сделать графический интерфейс похожим графический интерфейс приложения GitHub Desktop, показанный на рис. 27.

Рисунок 27. Графический интерфейс GitHub Desktop

Задача 5. Добавьте поддержку вывода результатов работы утилиты diff.py в формате HTML. Постарайтесь сделать результат похожим на графический интерфейс, показанный на рис. 27.