Ответ 1
Никто еще не обратился к этому какое-то время, поэтому я возьму на него удар. Это все чисто теоретико-высший уровень, поскольку я не читал статью об оригинальном алгоритме терпения.
Алгоритмы 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-es, мы разбиваем проблему на "редактирование не общего префикса, сохранение общей последовательности и редактирование не общего суффикса": теперь мы вычисляем две матрицы динамического программирования, но для небольших проблем, поэтому он идет быстрее. (И, конечно же, мы можем рефинансировать префикс и суффикс. Если бы у нас был файл размером ~ 4k, и мы обнаружили, что ~ 2k полностью без изменений, в общих строках около середины, оставляя строки ~ 0.5k вверху и ~ 1.5k внизу, мы можем проверить, что длинные общие подпоследовательности в вершинах размером ~ 0.5k "имеют разницу", а затем в ~ 1.5k "дно имеет разницу".)
LCS плохо работает и, следовательно, приводит к ужасным различиям, когда "общие подпоследовательности" представляют собой тривиальные строки, такие как }, которые имеют множество совпадений, но не очень важно. Вариант терпения diff просто отбрасывает эти строки из начального вычисления LCS, так что они не являются частью "общей подпоследовательности". Это делает оставшиеся матрицы большими, поэтому вы должны быть терпеливыми.: -)
В результате терпение diff не помогает здесь, потому что наша проблема не имеет ничего общего с общими подпоследовательностями. На самом деле, даже если мы полностью отбросили LCS и просто сделали одну большую матрицу, мы все равно получили бы нежелательный результат. Наша проблема заключается в том, что стоимость удаления:
- * Функция foo description.
- */
-функция foo() {}
-
-/**
Код>
(и ничего не вставлять) является тот же как стоимость удаления:
<Предварительно > <код > -/** - * Описание функции foo. - */ -функция foo() {} - Код >Стоимость одного из них - это просто "удалить 5 символов". Даже если мы взвешиваем каждый символ - делаем непустые строки "более дорогими" для удаления, чем пустые строки - стоимость остается той же: мы удаляем пять строк в конце.
Вместо этого нам нужен способ взвешивания строк на основе "визуальной кластеризации": короткие строки на краю дешевле удалить, чем короткие строки в середине, Эвристика уплотнения добавила к Git 2.9 попытка сделать это после факта. Это, по-видимому, по крайней мере немного ошибочно (только пустые строки подсчитываются, и они должны фактически существовать, а не просто подразумеваться путем достижения края). Возможно, было бы лучше сделать взвешивание во время заполнения матрицы (если предположить, что осталось после устранения LCS, действительно идет полная матрица динамического программирования). Однако это нетривиально.