Есть ли алгоритм сравнения, который сохраняет владение линией

Question

Моя цель - создать скрипт для отслеживания точки, в которую была добавлена ​​линия, даже если линия впоследствии была изменена или перемещена (оба из них путают традиционные сценарии vcs 'обвиняют'. Я провел небольшое второстепенное исследование (см. внизу), но не нашел ничего полезного. У меня есть концепция того, как действовать, но время выполнения было бы ужасным (с учетом факториала).

Две отсутствующие функции - это отслеживание строк, отредактированных по месту, отдельно от удаления и добавления этой строки, и отслеживание перемещения целых функций, поэтому они находятся в разных областях. Для тех, кто имеет опыт работы с diff, но не знаком с терминологией, подпоследовательность представляет собой непрерывную группу из + или - строк с типом: delete (все -), add (все +) ) или replace (комбинация). Мне нужно больше информации о шагах и edit-in-place строках, на которые смутно ссылаются записи в c2: DiffAlgorithm (абзац начинается с «Мой любимый режим»). Кто-нибудь знает, что это? (кажется, основано на Tichy, см. внизу.)

---

Вот дополнительная информация о двух отсутствующих функциях:

1. нет понятия об изменении строки (четвертый тип, что-то вроде edit-in-place). В этом блоке родительским элементом для «bc» является «b», но «d» является новым и не является потомком «b»:

 a
-b
+bc
+d

Обходной путь для этого не слишком сложен, если позиция правок одинакова (только расширенная версия markup_instraline_changes, но сравнивает расстояние редактирования на всех равных по размеру подмножествах старого и нового линии.

2. нет концепции "перемещения" кода, который сохраняет владение строками, например эта разница не должна изменять владельца "линии", хотя ее позиция меняется.

 a
-line
 c
+line

Это может быть сделано таким же образом, но с гораздо худшим временем выполнения (вместо проверки только отдельных блоков, помеченных как «заменить», вам нужно будет проверить расстояние Левенштейна между всеми добавленными по всем удаленным линиям) и с вероятными ложными срабатываниями (некоторые, например, пробелы, не имеющие отношения к моей проблеме).

Исследования, которые я провел: чтение о сопоставлении гештальт-паттернов (Ratcliff и Obershelp, используется в difflib Python) и O (ND) Разностный алгоритм и его варианты (EW Myers ).

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

Answer 1

Я думаю, что идея о том, какой объем редактирования можно выполнить, оставаясь потомком какой-то ранее написанной строки, очень субъективна и основана на контексте, с которыми компьютер не может работать. Я думаю, вам нужно было бы указать какое-то настраиваемое минимальное сходство строк в вашей программе ... Другая проблема заключается в том, что вполне возможно, чтобы две одинаковые строки были написаны совершенно независимо (например, увеличивая значение некоторой переменной) , и это будет довольно распространенным явлением, поэтому желаемый алгоритм не будет действительно давать правдивую или полезную информацию о строке довольно часто.

Я хотел бы предложить алгоритм для этого, хотя (который делает тонны, мы надеемся, очевидные предположения, кстати), так что здесь идет:

Convert both texts to lists of lines
Copy the lists and Strip all whitespace from inside of each line
Delete blank lines from both lists
Repeat
   Do a Levenshtein distance from the old to new lists ...
    ... keeping all intermediate data
   Find all lines in the new text that were matched with old lines
      Mark the line in both new/old original lists as having been matched
      Delete the line from the new text (the copy)
   Optional: If some matched lines are in a contiguous sequence ...
    ... in either original text assign them to a grouping as well!
Until there is nothing left but unmatchable lines in the new text
Group together sequences of unmatched lines in both old and new texts ...
 ... which are contiguous in the original text
   Attribute each with the line match before and after
Run through all groups in old text
   If any match before and after attributes with new text groups for each
    //If they are inside the same area basically
      Concatenate all the lines in both groups (separately and in order)
         Include a character to represent where the line breaks are
      Repeat
         Do a Levenshtein distance on these concatenations
         If there are any significantly similar subsequences found
          //I can't really define this but basically a high proportion
          //of matches throughout all lines involved on both sides
            For each matched subsequence
               Find suitable newline spots to delimit the subsequence
               Mark these lines matched in the original text
                //Warning splitting+merging of lines possible
                //No 1-to-1 correspondence of lines here!
               Delete the subsequence from the new text group concat
               Delete also from the new text working list of lines
      Until there are no significantly similar subsequences found
Optional: Regroup based on remaining unmatched lines and repeat last step
 //Not sure if there's any point in trying that at the moment
Concatenate the ENTIRE list of whitespaced-removed lines in the old text
Concatenate the lines in new text also (should only be unmatched ones left)
 //Newline character added in both cases
Repeat
   Do Levenshtein distance on these concatenations
   Match similar subsequences in the same way as earlier on
    //Don't need to worry deleting from list of new lines any more though
    //Similarity criteria should be a fair bit stricter here to avoid
    // spurious matchings.  Already matched lines in old text might have 
    // even higher strictness, since all of copy/edit/move would be rare
While you still have matchings

//Anything left unmatched in the old text is deleted stuff
//Anything left unmatched in the new text is newly written by the author
Print out some output to show all the comparing results!

Что ж, надеюсь, вы сможете понять основы того, что я имею в виду, с этим полностью непроверенным алгоритмом. Сначала найдите очевидные совпадения и дословно переместите куски уменьшающегося размера, затем сравните вещи, которые могут быть похожими, затем найдите что-нибудь похожее, но и измененное, и перемещенное: возможно, просто совпадение.

Что ж, если вы попытаетесь реализовать это, скажите мне, как это работает, и какие детали вы изменили, и какие присваивания вы сделали различным задействованным переменным ... Я ожидаю, что будут некоторые тестовые случаи, когда это будет работать блестяще и другие, где это просто бездонная неудача из-за некоторого массивного недосмотра. Идея состоит в том, что большинство вещей будет сопоставлено до того, как вы попадете в неэффективный последний цикл, и, действительно, предыдущий

Answer 2

Вы, кажется, заинтересованы в отслеживании происхождения, проблема отслеживания, откуда появилась линия.

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

В качестве слабой замены можно посмотреть на последовательность изменений исходного кода из хранилища и восстановить «правдоподобную» историю изменений. Это то, что вы делаете, предлагая использовать «diff». Как вы заметили, diff не понимает идеи «перемещения» или «копирования».

SD Smart Differencer инструменты сравнивают исходный текст, анализируя текст в соответствии с языком, в котором он находится, обнаруживая структуры кода и вычисляя наименьшие левенские различия с точки зрения конструкций языка программирования (идентификаторов, выражений, операторы, блоки, классы, ...) и операторы редактирования абстрактов «вставить», «удалить», «скопировать», «переместить» и «переименовать идентификатор в области видимости». Они выдают разнородный вывод, немного богаче, потому что говорят строку / столбец -> строка / столбец с различными операциями редактирования.

Очевидно, что правки «переместить» и «скопировать» наиболее интересны для вас с точки зрения отслеживания определенных строк (ну, конечно, конкретных языковых конструкций). Наш опыт показывает, что код также проходит много копий и редактирований, что, я подозреваю, вас не удивит.

Эти инструменты находятся в бета-версии и в настоящее время доступны для COBOL, Java и C #. Множество других языков находятся в канале, потому что SmartDifferencer построен поверх инфраструктуры, параметризованной языком, DMS Software Reengineering Toolkit , которая содержит довольно много уже существующих надежных грамматик языка.