Инструменты разработчика · Сравнение текста
Как функция Text Diff находит измененные строки: LCS и алгоритм Майерса
· Как это работает
разница текста алгоритмы рабочий процесс разработчика
Объясняет идею самой длинной общей подпоследовательности, лежащую в основе линейного сравнения, и почему алгоритм Майерса сделал его достаточно быстрым, чтобы его можно было запустить мгновенно, даже на вкладке браузера.
Два файла, один вопрос: какие строки сохранились? — сравнение кадров как поиск самого длинного отрезка строк, общего для обеих версий, а не совпадающих номеров строк.
Две ревизии не поставляются с метками, указывающими, какие строки сохранились. ToolAcre сначала разбивает каждый текст на упорядоченный список, затем ищет длинную подпоследовательность, появляющуюся в обоих списках в одном и том же порядке. Линии за пределами этого общего позвоночника становятся скорее дополнениями или удалениями, чем предполагаемыми модификациями.
Результат содержит исходные однозначные позиции для обеих сторон. Неизменный ряд имеет число с каждой стороны, удаление только слева, а добавление только справа. Такой учет делает отображаемую историю доступной для просмотра, даже если повторяющиеся строки дают более одного правдоподобного совпадения.
Почему diff работает со строками, а не с символами — как разделение по символам новой строки превращает текст в последовательность сопоставимых единиц и почему это заставляет прозу вести себя иначе, чем код
Реализация рассматривает полную строку как единицу сравнения. Таким образом, границы новой строки формируют результат: редактирование одного слова внутри абзаца, хранящегося в одной строке, заменяет всю эту строку, в то время как та же самая проза, организованная предложение за предложением, может изолировать гораздо меньшую область.
Сравнение строк — это не анализ символов, скрытый за другим дисплеем. `splitLines` создает массивы, а таблица LCS сравнивает один ключ строки с другим. Такая предсказуемая степень детализации подходит для исходных файлов и файлов конфигурации, но не позволяет выделить точные буквы, измененные внутри совпадающей замены.
Самая длинная общая подпоследовательность простыми словами — раскрывает идею LCS на пятистрочном примере и показывает, как все, что находится за пределами подпоследовательности, становится вставкой или удалением.
Представьте себе левые линии A, B, C, D, E и правые линии A, C, E. A, C и E образуют упорядоченную общую подпоследовательность. B и D выходят за его пределы, поэтому результат сообщает о двух удалениях и трех неизмененных строках без необходимости связывания удаленной строки с заменой.
В таблице для каждой оставшейся пары позиций записана наилучшая доступная общая длина. Реконструкция идет вперед через эти ценности. Равные клавиши продвигают обе стороны; в противном случае большее соседнее значение решает, следует ли выполнить удаление слева или добавление справа.
Алгоритм Майерса и почему скорость имеет значение — без формул объясняет, как отслеживание самого короткого сценария редактирования обеспечивает быстрое сравнение файлов с тысячами строк.
В книге имя Майерс, но `diff.js` явно реализует простое динамическое программирование наибольшей общей подпоследовательности. В его комментарии указано время и память O(n·m) для отличающейся середины. Утверждение Майерса или поведения «кратчайшего графа редактирования» означало бы замену кода, который фактически поставляется, знакомым алгоритмом.
ToolAcre ограничивает эту стоимость до распределения. Одинаковые префиксы и суффиксы удаляются линейными проходами, и каждая из отличающихся средних строк может содержать не более 2,000 строк. Матрица представляет собой `Uint32Array`; задокументированный наихудший разрешенный квадрат занимает около шестнадцати мегабайт, а не неограниченные значения в коробочках.
ToolAcre использует таблицу LCS, а не алгоритм Майерса, указанный в схеме.
Сравните журнал изменений, содержащий «Добавленный поиск», «Фиксированный экспорт» и «Обновленную справку», с версией, в которой сохраняются первая и третья записи, но вставляются «Добавленные фильтры» перед последней. Общие записи закрепляют путь, «Фиксированный экспорт» удаляется и добавляется «Добавленные фильтры».
Алгоритм не называет эту пару модифицированной строкой. Его словарь строк равен только добавлению и удалению, поэтому текстовая замена выглядит как одно удаление, за которым следует одно добавление. В сводке эти операции подсчитываются отдельно и помечаются как идентичные только тогда, когда оба счетчика равны нулю.
Почему два правильных различия могут выглядеть по-разному: показано, как связи между одинаково короткими сценариями редактирования объясняют, почему один инструмент винит пустую строку, а другой — закрывающую скобку.
Повторяющиеся или взаимозаменяемые строки могут создавать несколько общих подпоследовательностей одинаковой длины. ToolAcre разрешает одну ничью, предпочитая удаление, когда значения двух соседних таблиц равны. Другая правильная реализация может сначала выбрать дополнение и представить выравнивание, выглядящее по-другому, с той же стоимостью редактирования.
Вот почему пустая строка или закрывающая скобка могут отображаться прикрепленными к разным фрагментам в разных инструментах. Расхождение не означает автоматически, что сравнение потеряло содержание. Прочтите исходные номера строк и окружающие их неизмененные строки, прежде чем рассматривать различия в представлении как конкурирующие фактические утверждения.
Что это не охватывает: семантическое или структурное сравнение, обнаружение перемещения и выделение на уровне слов выходят за рамки того, что вычисляет строковый дифф.
Ничто в этом пути не анализирует синтаксические деревья, не распознает переименованные идентификаторы, не помечает перемещенные блоки и не понимает смысл текста. Перемещенный абзац нарушает требование общего порядка и может отображаться один раз как удаленный и один раз как добавленный. Инструмент также не вычисляет выделение на уровне символов или слов внутри строк.
Эти упущения являются границами, а не скрытыми режимами. Используйте рецензента, знающего язык, для семантических утверждений и контроля версий для истории слияний. Text diff отвечает на более узкий вопрос о том, чем отличаются две упорядоченные последовательности строк, а затем позволяет человеку интерпретировать, важны ли эти текстовые изменения.
Вывод: что на самом деле означают выделенные строки — кратко описано, как читать разницу строк как кратчайшую историю изменений и как функция сравнения текста ToolAcre запускает это на вашей вкладке, не загружая ничего.
Прочитайте зеленые и красные строки как одно объяснение, полученное из LCS, а не как доказательство намерений автора. Обрезка префиксов и суффиксов меняет объем работы, но не окончательный учет строк. Исходный текст остается в каждой строке, даже если параметры регистра или пробелов предоставляют более свободные ключи для сопоставления.
Сравнение выполняется через импортированные модули браузера и отображается с текстовыми узлами DOM; на пути инструмента нет конечной точки преобразования. Попробуйте пример из пяти строк, поменяйте стороны местами и загрузите выходные данные в форме патча, чтобы увидеть, как направление меняет добавления на удаления, не изобретая семантики.