Поиск алгоритма для текстовой разности, которая обнаруживает и может сгруппировать подобные строки
Я нахожусь в процессе записи различного текстового инструмента для сравнения двух подобных файлов исходного кода.
Вокруг существует много таких "различных" инструментов, но мой должен быть немного улучшен:
Если это найдет, что ряду строк не соответствуют с обеих сторон (т.е. в обоих файлах), то это должно не только выделить те строки, но также и выделить отдельные изменения в этих строках (я называю это межстрочное сравнение здесь).
Пример моего несколько рабочего решения:
сопроводительный текст http://files.tempel.org/tmp/diff_example.png
То, что это в настоящее время делает, должно взять ряд несогласованных линий и выполнения их единственных символов через различный алгоритм еще раз, произведя розовое выделение.
Однако второй набор несоответствий, содержа "оригинал 2", требует большего количества работы: Здесь, первые две правильных строки ("добавленная строка a/b") были добавлены, в то время как третья строка является измененной версией левой стороны. Я хочу, чтобы мое программное обеспечение обнаружило это различие между вероятным изменением и вероятной новой строкой.
При рассмотрении этого простого примера я могу скорее легко обнаружить этот случай:
С алгоритмом, таким как Levenshtein, я мог найти Levenshtein в порядке строками в наборе 3 - 5, строка 5 соответствий, оставленных строку 3 лучших, таким образом я мог вычесть это, строки 3 и 4 справа были добавлены и выполняют межстрочное сравнение на левой строке 3 и правильной строке 5.
Пока все хорошо. Но я все еще застреваю с тем, как превратить это в более общий алгоритм с этой целью.
В более сложной ситуации ряд различных строк мог иметь добавленные строки с обеих сторон с несколькими тесно промежуточными согласующими отрезками длинной линии. Это становится довольно сложным:
Я должен был бы соответствовать не только первой строке слева к лучшему справа, но наоборот также, и так далее со всеми другими строками. В основном я должен соответствовать каждой строке слева против всех справа. В худшем случае это могло бы создать даже пересечения, так, чтобы это больше не было легко ясно, какие строки были недавно вставлены и которые были просто изменены (Примечание: Я не хочу иметь дело с возможными перемещенными строками в таком блоке, если это на самом деле не упростило бы алгоритм).
Несомненно, это никогда не будет прекрасным, но я пытаюсь получить его лучше, чем это теперь. Ценятся любые предложения, которые являются не также theoerical, а скорее практичны (я не хорошие понимающие абстрактные алгоритмы).
Обновление
Я должен признать, что даже не понимаю, как алгоритм LCS работает. Я просто подаю его два массива строк, и прибывает, списку которого последовательности не соответствуют. Я в основном использую код отсюда: http://www.incava.org/projects/java/java-diff
Рассмотрение кода, я нахожу одну функцию равной (), который ответственен за сообщение алгоритма, соответствуют ли две строки или нет. На основе какой предложенный Pavel, интересно, является ли это местом, где я внес бы изменения. Но как? Эта функция только возвращает булевскую переменную - не относительное значение, которое могло определить качество соответствия. И я не могу, просто использовал фиксированную порцию Levenshtein, которая решит, считают ли подобную строку все еще равной или не - мне будет нужно что-то, что это самопринимает ко всему набору рассматриваемых строк.
Так, что я в основном говорю, то, что я все еще не понимаю, где я применил бы нечеткое значение, которое касается относительного подобия строк, которые (точно) не соответствуют.
3 ответа
С помощью такого алгоритма, как Левенштейн, я смог найти, что из всех правых строк в наборе от 3 до 5, строка 5 лучше всего соответствует левой строке 3, таким образом, я мог вычесть, что строки 3 и 4 справа были добавлены, и выполните межстрочное сравнение для левой строки 3 и правой строки 5.
После того, как вы его определили, используйте тот же алгоритм, чтобы определить, какие строки в этих двух промежутках соответствуют друг другу. Но вам нужно внести небольшие изменения. Когда вы использовали алгоритм для сопоставления одинаковых строк, строки могли совпадать или не совпадать, поэтому в ячейку таблицы, которую вы использовали, добавлялось либо 0, либо 1.
При сравнении строк в одном фрагменте некоторые из них «более равны», чем другие (например, по Оруэллу). Таким образом, они могут добавить к ячейке действительное число от 0 до 1, учитывая, какая последовательность на данный момент подходит лучше всего.
Чтобы вычислить эту метрику (от 0 до 1), вы можете применить к каждой паре строк, с которыми вы сталкиваетесь ... верно, тот же алгоритм снова (на самом деле, вы уже делали это, когда выполняли first проход алгоритма Левенштейна). Это вычислит длину LCS, отношение которой к средней длине двух строк будет значением метрики.
Или вы можете позаимствовать алгоритм из одного из инструментов сравнения. Например, vimdiff может выделить нужные вам совпадения.
Вот одно возможное решение, которое кто-то другой только что заставил меня осознать:
Мой оригинальный подход был следующим:
- Разделите текст на отдельные строки и используйте LCS алгоритм для определения того, где находятся блоки несовпадающих строк.
- Используйте какое-нибудь умное алго (о котором идет речь в этом вопросе), чтобы выяснить, какие из этих строк близко совпадают, т.е. чтобы сказать, что эти строки были изменены между ревизиями.
- Снова сравните эти близко совпадающие строки построчно, используя LCS, и пометьте несовпадающие строки как совершенно новые.
Хотя это позволило бы лучше визуально отобразить изменения при сравнении ревизий исходного кода, теперь я обнаружил, что обычно достаточно гораздо более простого подхода. Он работает следующим образом:
- То же самое, что и выше.
- Возьмите правый и левый блок несовпадающих строк, сконцентрируйте эти строки и подпишите их (либо на токены/слова, специфичные для языка, либо только на отдельные символы)
- Применяйте алгоритм LCS на двух массивах токенов.
Может быть, те, кто ответил на мой первоначальный вопрос, предположили, что я знал, что должен делать это постоянно, но я так сильно сосредоточился на сравнении по строкам, что мне не пришло в голову применить LCS к набору строк, объединив их, вместо того, чтобы обрабатывать их по строке за строкой.
Таким образом, хотя этот подход и не дает такой подробной информации об изменениях, как это было изначально задумано, он все же улучшает результаты по сравнению с тем, с чего я начинал вчера, когда писал этот вопрос.
Я оставлю этот вопрос открытым еще на некоторое время - возможно, кто-то другой, прочитав все это, все же сможет дать полный ответ (Павел и random_hacker предложили несколько предложений, но это еще не полное решение - в любом случае, спасибо за полезные комментарии).
Расстояние Левенштейна основано на понятии "скрипт редактирования", который преобразует одну строку в другую. Это очень тесно связано с алгоритмом Needleman-Wunsch, используемым для выравнивания последовательностей ДНК путем вставки символов разрыва, в котором мы ищем выравнивание, которое максимизирует оценку во времени O(nm), используя динамическое программирование. Точные совпадения между символами увеличивают оценку, а несовпадения или вставленные символы разрыва уменьшают оценку. Пример выравнивания AACTTGCCA и AATGCGAT:
AACTTGCCA-
AA-T-GCGAT
(6 matches, 1 mismatch, 3 gap characters, 3 gap regions)
Можно подумать, что верхняя строка - это "начальная" последовательность, которую мы превращаем в "конечную" последовательность снизу. Каждый столбец, содержащий внизу символ пробела - - это удаление, каждый столбец с - сверху - это вставка, а каждый столбец с различными (не пробелами) символами - подстановка. В приведенном выше выравнивании 2 удаления, 1 вставка и 1 подстановка, поэтому расстояние Левенштейна равно 4.
Вот еще одно выравнивание тех же строк, с тем же самым расстоянием Левенштейна:
AACTTGCCA-
AA--TGCGAT
(6 matches, 1 mismatch, 3 gap characters, 2 gap regions)
Но обратите внимание, что хотя имеется одинаковое количество разрывов, но на один разрыв меньше -. Так как биологические процессы чаще создают большие промежутки, чем несколько отдельных, то биологи предпочитают такое выравнивание -- и пользователи Вашей программы тоже. Это достигается путем также штрафования количества областей разрыва в баллах, которые мы вычисляем. Алгоритм O(nm) для выполнения этого для строк длиной n и m был дан Гото в 1982 году в работе под названием "Улучшенный алгоритм согласования биологических последовательностей". К сожалению, я не могу найти никаких ссылок на свободный полный текст статьи -- но есть много полезных уроков, которые можно найти, погуглив "выравнивание последовательностей" и "аффинное наказание за пробелы".
В общем, различные варианты весов совпадений, несовпадений, разрывов и разрывов дают разные выравнивания, но любой отрицательный результат по разрывным областям предпочтет выравнивание снизу вверх, а не сверху.
Какое отношение все это имеет к вашей проблеме? Если вы используете алгоритм Гото на отдельных персонажах с подходящим штрафом за разрыв (полученный с помощью нескольких эмпирических тестов), вы должны обнаружить значительное уменьшение количества ужасно выглядящих выравниваний, как в приведенном вами примере.
Учет эффективности
В идеале, вы можете просто сделать это на символах и полностью игнорировать строки, так как аффинное удаление будет работать для кластеризации изменений в блоках, охватывающих многие строки, где это возможно. Но из-за большего времени работы, возможно, более реалистичным будет сделать первый проход по строкам, а затем перезапустить алгоритм по символам, используя в качестве входа все строки, которые не идентичны. По этой схеме любой общий блок одинаковых строк может быть обработан путем сжатия его в один "символ" с завышенным весом совпадения, что позволяет исключить появление "пересечений".