Поиск алгоритма для сравнения текста, который обнаруживает и может группировать похожие строки

Question

Я нахожусь в процессе написания инструмента сравнения текста для сравнения двух похожих файлов исходного кода.

Есть много таких инструментов "diff", но мой должен быть немного улучшен:

Если он обнаружит, что набор строк не совпадает с обеих сторон (т. Е. В обоих файлах), он должен не только выделить эти строки, но и выделить отдельные изменения в этих строках (здесь я называю это сравнение между строками).

Пример моего несколько работающего решения:

альтернативный текст http://files.tempel.org/tmp/diff_example.png

То, что он в настоящее время делает, это берет набор несовпадающих линий и запускает их отдельные символы еще раз через дифференциал, производя розовую подсветку.

Однако второй набор несоответствий, содержащий «оригинал 2», требует дополнительной работы: здесь были добавлены первые две правые строки («добавленная строка a / b»), а третья строка является измененной версией левая сторона. Я хочу, чтобы мое программное обеспечение обнаружило эту разницу между вероятным изменением и новой строкой.

Глядя на этот простой пример, я довольно легко могу обнаружить этот случай:

С таким алгоритмом, как Левенштейн, я мог бы найти, что из всех правых строк в наборе от 3 до 5, строка 5 лучше всего соответствует левой строке 3, поэтому я мог бы вычесть, что строки 3 и 4 справа были добавлены, и выполнить межстрочное сравнение в левой строке 3 и правой строке 5.

Пока все хорошо. Но я все еще застрял в том, как превратить это в более общий алгоритм для этой цели.

В более сложной ситуации набор различных линий может иметь добавленные линии с обеих сторон с несколькими близко совпадающими линиями между ними. Это становится довольно сложным:

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

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

Обновление

Я должен признать, что я даже не понимаю, как работает алгоритм LCS. Я просто передаю ему два массива строк, и получается список последовательностей, которые не совпадают. Я в основном использую код здесь: http://www.incava.org/projects/java/java-diff

Глядя на код, я нахожу одну функцию, равную (), которая отвечает за указание алгоритму, совпадают ли две строки или нет. Исходя из того, что предложил Павел, мне интересно, это место, где я бы внес изменения. Но как? Эта функция возвращает только логическое значение, а не относительное значение, которое может идентифицировать качество соответствия. И я не могу просто использовать фиксированный рацион Левенштейна, который бы решал, считается ли подобная линия по-прежнему равной или нет - мне нужно что-то самоопределяющееся для всего набора рассматриваемых линий.

Итак, что я в основном говорю, так это то, что я до сих пор не понимаю, где бы я применил нечеткое значение, относящееся к относительному сходству линий, которые (точно) не совпадают.

Answer 1

Расстояние Левенштейна основано на понятии «сценарий редактирования», который преобразует одну строку в другую. Он очень тесно связан с алгоритмом 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 году в статье под названием «Улучшенный алгоритм сопоставления». биологические последовательности ». К сожалению, я не могу найти никаких ссылок на бесплатный полный текст статьи - но есть много полезных руководств, которые вы можете найти, прибегая к помощи «выравнивания последовательностей» и «штрафов за аффинные пробелы».

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

Какое все это имеет отношение к вашей проблеме? Если вы используете алгоритм Гото для отдельных персонажей с подходящим штрафом за пробел (получено с помощью нескольких эмпирических тестов), вы должны найти значительное уменьшение количество ужасных линий, как в приведенном вами примере.

Вопросы эффективности

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

Answer 2

Вот одно из возможных решений, которое только что заставил меня осознать:

Мой оригинальный подход был таким:

1. Разделите текст на отдельные строки и используйте алгоритм LCS, чтобы определить, где находятся блоки несоответствующих строк.
2. Используйте какой-нибудь умный алгоритм (о чем этот вопрос), чтобы выяснить, какие из этих строк близко совпадают, то есть сказать, что эти строки были изменены между ревизиями.
3. Снова сравнивайте эти близко совпадающие строки, используя LCS, помечая несоответствующие строки как совершенно новые.

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

1. То же, что и выше.
2. Возьмите правый и левый блок несовпадающих строк, объедините эти строки и токенизируйте их (либо в языковые токены / слова, либо просто в отдельные символы)
3. Применение алгоритма LCS к двум массивам токенов.

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

Так что, хотя этот подход не предоставит такую ​​подробную информацию об изменениях, как было в моем первоначальном намерении, он все же улучшит результаты по сравнению с тем, с чем я начал вчера, когда писал этот вопрос.

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

Answer 3

С таким алгоритмом, как Левенштейн, я мог бы найти, что из всех правых строк в наборе от 3 до 5, строка 5 лучше всего соответствует левой строке 3, поэтому я мог бы вычесть, что строки 3 и 4 справа были добавлены выполнить межстрочное сравнение в левой строке 3 и правой строке 5.

После того, как вы его определили, используйте тот же алгоритм , чтобы определить, какие линии в этих двух цепях соответствуют друг другу. Но вам нужно сделать небольшую модификацию. Когда вы использовали алгоритм для сопоставления одинаковых линий, эти строки могли совпадать или не совпадать, поэтому в ячейку таблицы, которую вы использовали, добавляли 0 или 1.

При сравнении строк в одном фрагменте некоторые из них "более равны", чем другие (например, Оруэлла). Таким образом, они могут добавить действительное число от 0 до 1 в ячейку, учитывая, какая последовательность соответствует наилучшим на данный момент.

Чтобы вычислить эту метрику (от 0 до 1), вы можете применить к каждой паре строк, с которыми вы сталкиваетесь ... верно, тот же алгоритм снова (на самом деле, вы уже делали это, когда выполняли first проход алгоритма Левенштейна). Это вычислит длину LCS, отношение которой к средней длине двух строк будет значением метрики.

Или вы можете позаимствовать алгоритм у одного из инструментов сравнения. Например, vimdiff может выделить нужные вам совпадения.