Есть ли подобный алгоритм, который обрабатывает движущийся блок строк?

Программа diff в своих различных воплощениях разумно хороша при вычислении разницы между двумя текстовыми файлами и выражении ее более компактно, чем отображение обоих файлов полностью. Он показывает разницу как последовательность вставленных и удаленных фрагментов строк (или в некоторых случаях измененных строк, но это эквивалентно удалению, за которым следует вставка). Эта же или очень похожая программа или алгоритм используется patch и системами управления версиями для минимизации хранения, необходимого для представления различий между двумя версиями одного и того же файла. Обсуждается алгоритм здесь и здесь.

Но он падает, когда в файл перемещаются блоки текста.

Предположим, что у вас есть следующие два файла: a.txt и b.txt (представьте, что они представляют собой сотни строк длиной, а не только 6):

a.txt   b.txt
-----   -----
1       4
2       5
3       6
4       1
5       2
6       3

diff a.txt b.txt показывает это:

$ diff a.txt b.txt 
1,3d0
< 1
< 2
< 3
6a4,6
> 1
> 2
> 3

Изменение от a.txt до b.txt может быть выражено как "Возьмите первые три строки и переместите их в конец", но diff показывает полное содержимое перемещенного фрагмента строк дважды, упуская возможность для краткого описания этого большого изменения.

Обратите внимание, что diff -e показывает блок текста только один раз, но это потому, что он не отображает содержимое удаленных строк.

Существует ли вариант алгоритма diff, который (a) сохраняет diff способность представлять вставки и удаления и (b) эффективно представляет перемещенные блоки текста без необходимости показывать их все содержимое?

Ответ 1

Поскольку вы попросили алгоритм, а не приложение, посмотрите "Проблема с коррекцией строк и строк при перемещении блоков" Уолтер Тичи. Есть и другие, но это оригинал, поэтому вы можете искать документы, которые ссылаются на него, чтобы найти больше.

В статье цитируется статья Пола Хеккеля "Техника выделения различий между файлами" (упомянутая в этом ответе на этот вопрос) и упоминает об этом алгоритме:

Хеккель [3] указал на аналогичные проблемы с методами LCS и предложил линейный алгоритм для обнаружения движения блоков. Алгоритм выполняется адекватно если в строках имеется несколько повторяющихся символов. Однако алгоритм дает при прочих равных условиях. Например, учитывая две строки aabb и bbaa, Алгоритм Геккеля не может обнаружить какую-либо общую подстроку.

Ответ 2

Следующий способ способен обнаруживать перемещения блоков:

Пол Хеккель: метод изоляции различий между файлами
Сообщения ACM 21 (4): 264 (1978)
http://doi.acm.org/10.1145/359460.359467 (доступ ограничен)
Зеркало: http://documents.scribd.com/docs/10ro9oowpo1h81pgh1as.pdf (открытый доступ)

wikEd diff - это бесплатная библиотека diff JavaScript, которая реализует этот алгоритм и улучшает его. Он также включает в себя код для компиляции текстового вывода с вставками, удалениями, перемещенными блоками и исходными позициями блоков, вставленными в новую текстовую версию. Подробную информацию см. на странице проекта или подробном комментарии. Для тестирования вы также можете использовать онлайн-демонстрацию .

Ответ 3

Наши инструменты Smart Differencer делают именно это при вычислении различий между исходными текстами двух программ на одном языке программирования. Различия сообщаются в терминах структур программы (идентификаторы, выражения, операторы, блоки) с точностью до номера строки/столбца и с точки зрения правдоподобных операций редактирования (удаление, вставка, перемещение, копирование [выше и выше запроса OP для простой "копии" ) ], rename-identifier-in-block).

Для SmartDifferencers требуется структурированный артефакт (например, язык программирования), поэтому он не может сделать это для произвольного текста. (Мы могли бы определить структуру как "просто строки текста", но не думали, что это будет особенно ценно по сравнению со стандартным diff).

Ответ 4

Вот очерк того, что может сработать. Игнорируйте вставки/удаления в настоящее время для ясности.

Это, по-видимому, состоит в том, чтобы определить лучшую блокировку, похожую на сжатие текста. Мы хотим найти общую подстроку двух файлов. Один из вариантов состоит в том, чтобы построить обобщенное дерево суффикса и итеративно взять максимальную общую подстроку, удалить ее и повторить до тех пор, пока не будет подстроки некоторого размера $s $. Это можно сделать с помощью дерева суффикса в O (N ^ 2) времени (https://en.wikipedia.org/wiki/Longest_common_substring_problem#Suffix_tree). Жадное принятие максимума представляется оптимальным (как функция сжимаемых символов), так как взятие символьной последовательности из другой подстроки означает добавление одинакового числа символов в другое место.

Каждая подстрока затем заменяется символом для этого блока и отображается один раз в виде словаря.

$ diff a.txt b.txt 
1,3d0
< $
6a4,6
> $

 $ = 1,2,3

Теперь нам нужно повторно ввести поведение типа diff. Простой (возможно, неоптимальный) ответ состоит в том, чтобы просто запустить алгоритм дифференциала, опустить весь текст, который не будет выводиться в исходном diff, и запустить описанный выше алгоритм.

Ответ 5

SemanticMerge, инструмент "семантический scm", упомянутый в этом комментарии к одному из других ответов, включает в себя "семантический diff", который обрабатывает перемещение блока строк (для поддерживаемых языков программирования). Я не нашел подробностей об алгоритме, но, возможно, сам алгоритм diff не является особенно интересным, поскольку он полагается на вывод отдельного анализа файлов исходного кода языка программирования. Здесь представлена документация SemanticMerge по реализации (внешнего) парсера языка, которая может пролить свет на то, как работают ее отличия:

Внешние парсеры - SemanticMerge

Я тестировал его только сейчас, и его различие является фантастическим. Это значительно лучше, чем тот, который я выпустил, используя демо алгоритм, упомянутый в этом ответе (и этот diff был намного лучше, чем тот, который был создан с помощью Git default diff алгоритм), и я подозреваю, что все еще лучше, чем тот, который может быть вызван алгоритмом, упомянутым в этом ответе.

Ответ 6

Git 2.16 (Q1 2018) представит другую возможность, проигнорировав некоторые заданные перемещенные строки.

"git diff" выучил вариант алгоритма "--patience", которому пользователь может указать, какая "уникальная" строка будет использоваться в качестве фиксирующих точек.

См. совершить 2477ab2 (27 ноября 2017 г.) Джонатан Тан (jhowtan).
^{(слияние Junio C Hamano - gitster - в commit d7c6c23, 19 декабря 2017 г.)}

diff: поддерживать линию привязки

Научите diff новый алгоритм, который пытается предотвратить появление пользовательских строк в качестве удаления или добавления в конечном результате.
Конечный пользователь может использовать это, указав "--anchored=<text>" один или несколько раз при использовании команд Git, таких как "diff" и "show".

Документация для git diff теперь читает:

--anchored=<text>:
Сгенерируйте diff, используя алгоритм "привязанный diff".

Эта опция может быть указана более одного раза.

Если строка существует как для источника, так и для адресата, существует только один раз и начинается с этого текста, этот алгоритм пытается предотвратить его появление в качестве удаления или добавления в выход. Он использует внутренний алгоритм "терпения".

Смотрите примеры для некоторых примеров:

pre post
 a   c
 b   a
 c   b

обычно, c перемещается для создания наименьшего разности.
Но:

 git diff --no-index --anchored=c pre post

Diff будет a.