Никто еще не обращался к этому какое-то время, поэтому я попробую. Это все чисто теоретическое, так как я не читал статью об оригинальном алгоритме терпения.
Алгоритмы LCS (самая длинная общая подпоследовательность) предназначены для сокращения времени, затрачиваемого на поиск решения с минимальным расстоянием редактирования. Стандартное (динамическое программирование) решение — O(MN), где M — количество символов в исходной строке, а N — количество символов в целевой строке. В нашем случае «символы» — это строки, а «строка» — это набор строк, а не строк с символами (где символы были бы, например, кодами ASCII). Мы просто заполняем матрицу M x N «стоимости редактирования»; когда мы закончим, мы произведем фактическое редактирование, проследив минимальный путь назад через результирующую матрицу. См. https://jlordiales.me/2014/03/01/dynamic-programming-edit-distance/ для примера. (Веб-страница, найденная через поиск Google: я не имел к этому никакого отношения, кроме как просканировать ее на высокой скорости на предмет правильности. Вроде правильно. :-))
На самом деле вычисление этой матрицы довольно затратно для больших файлов, поскольку M и N — это количество строк исходного кода (обычно примерно одинаковое): файл ~4k строк дает ~16M элементы в матрице, которые должны быть заполнены полностью, прежде чем мы сможем проследить минимальный обратный путь. Более того, сравнение «символов» уже не так тривиально, как сравнение символов, поскольку каждый «символ» представляет собой полную строку. (Обычный трюк состоит в том, чтобы хешировать каждую строку и вместо этого сравнивать хэши во время генерации матрицы, а затем перепроверять во время обратной трассировки, заменяя «сохранить неизменный символ» на «удалить исходный и вставить новый», если хеш ввел нас в заблуждение. при наличии коллизий хэшей: мы можем получить немного неоптимальную последовательность редактирования, но она практически никогда не будет ужасной.)
LCS изменяет матричный расчет, замечая, что сохранение длинных общих подпоследовательностей («сохранить все эти строки») почти всегда приводит к большому выигрышу. Найдя несколько хороших LCS-ов, мы разбиваем задачу на «отредактировать нестандартный префикс, сохранить общую последовательность и отредактировать необычный суффикс»: теперь мы вычисляем две матрицы динамического программирования, а для мелких задач, так дело идет быстрее. (И, конечно же, мы можем выполнить рекурсию по префиксу и суффиксу. Если бы у нас был файл длиной ~4 тыс. строк, и мы нашли бы ~2 тыс. полностью неизмененных общих строк в середине, оставив ~0,5 тыс. строк вверху и ~1,5 тыс. внизу, мы можем проверить наличие длинных общих подпоследовательностей в ~0,5 тыс. строк «вверху есть отличие», а затем снова в ~1,5 тыс. строк «внизу есть отличие».)
LCS работает плохо и, таким образом, приводит к ужасным различиям, когда «общие подпоследовательности» представляют собой тривиальные строки, такие как }, которые имеют много совпадений, но на самом деле не имеют отношения к делу. Вариант терпеливый diff просто отбрасывает эти строки из начального вычисления LCS, чтобы они не были частью "общей подпоследовательности". Это делает оставшиеся матрицы больше, поэтому вы должны быть терпеливы. :-)
В результате терпение diff здесь не поможет, потому что наша проблема не имеет ничего общего с общими подпоследовательностями. На самом деле, даже если бы мы полностью отказались от LCS и просто сделали одну большую матрицу, мы все равно получили бы нежелательный результат. Наша проблема в том, что стоимость удаления:
- * Function foo description.
- */
-function foo() {}
-
-/**
(и ничего не вставлять) то же самое, что и стоимость удаления:
-/**
- * Function foo description.
- */
-function foo() {}
-
Стоимость любого из них - просто «удалить 5 символов». Даже если мы взвесим каждый символ — сделаем непустые строки «более дорогими» для удаления, чем пустые строки — стоимость останется прежней: в конце мы удаляем те же пять строк.
Вместо этого нам нужен какой-то способ взвешивания линий на основе «визуальной кластеризации»: короткие строки на краю удалять дешевле, чем короткие строки посередине. Эвристика уплотнения, добавленная в Git 2.9, пытается сделать это постфактум. Это очевидно, по крайней мере, немного ошибочно (учитываются только пустые строки, и они должны действительно существовать, а не просто подразумеваться, достигая края). Возможно, было бы лучше выполнить взвешивание во время заполнения матрицы (при условии, что то, что осталось после устранения LCS, действительно проходит через полную матрицу динамического программирования). Однако это нетривиально.
person
torek
schedule
20.10.2016
