Вычисление редакционного расстояния


    Редакционное расстояние, или расстояние Левенштейна — метрика, позволяющая определить «схожесть» двух строк — минимальное количество операций вставки одного символа, удаления одного символа и замены одного символа на другой, необходимых для превращения одной строки в другую. В статье излагается метод вычисления редакционного расстояния при использовании небольшого объема памяти, без существенной потери скорости. Данный подход может быть применен для больших строк (порядка 105 символов, т.е. фактически для текстов) при получении не только оценки «схожести», но и последовательности изменений для перевода одной строки в другую.

    Небольшая формализация

    Пусть имеется две строки S1 и S2. Мы хотим перевести одну в другую (пусть первую во вторую, легко показать, что операции симметричны), используя следующие операции:
    • I: Вставка символа в произвольное место;
    • D: Удаление символа с произвольной позиции;
    • R: Замена символа на другой.

    Тогда d(S1,S2) — минимальное количество операций I/D/R для перевода S1 в S2, а редакционное предписание — перечисление операций для перевода с их параметрами.

    Задача легко решается алгоритмом Вагнера — Фишера, однако для восстановления редакционного предписания потребуется O(|S1|*|S2|) ячеек памяти. Вкратце излагаю сам алгоритм, так как «оптимизация» основывается на нем.

    Алгоритм Вагнера — Фишера

    Искомое расстояние формируется через вспомогательную функцию D(M,N), находящую редакционное расстояние для подстрок S1[0..M] и S2[0..N]. Тогда полное редакционное расстояние будет равно расстоянию для подстрок полной длины: d(S1,S2) = DS1,S2(M,N).

    Самоочевидным фактом, является то, что:

    D(0,0) = 0.

    Действительно, пустые строки и так совпадают.

    Также, ясны значения для:

    D(i, 0) = i;
    D(0, j) = j.

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

    В общем случае чуть сложнее:

    D(i,j) = D(i-1,j-1), если S1[i] = S2[j],
    иначе D(i,j) = min( D(i-1,j), D(i,j-1), D(i-1,j-1) ) + 1.

    В данном случае, мы выбираем, что выгоднее: удалить символ (D(i-1,j)), добавить (D(i,j-1)), или заменить (D(i-1,j-1)).

    Нетрудно понять, что алгоритму получения оценки не требуется памяти больше чем два столбца, текущий (D(i,*)) и предыдущий (D(i-1,*)). Однако в полном объеме матрица нужна для восстановления редакционного предписания. Начиная из правого нижнего угла матрицы (M,N) мы идем в левый верхний, на каждом шаге ища минимальное из трёх значений:
    • если минимально (D(i-1, j) + 1), добавляем удаление символа S1[i] и идём в (i-1, j);
    • если минимально (D(i, j-1) + 1), добавляем вставку символа S1[i] и идём в (i, j-1);
    • если минимально (D(i-1, j-1) + m), где m = 1, если S1[i] != S2[j], иначе m = 0; после чего идём в (i-1, j-1) и добавляем замену если m = 1.
    Здесь (i, j) — клетка матрицы, в которой мы находимся на данном шаге. Если минимальны два из трёх значений (или равны все три), это означает, что есть 2 или 3 равноценных редакционных предписания.

    В итоге потребуется O(|S1|*|S2|) времени и O(|S1|*|S2|) памяти.

    Общие доводы

    Предпосылкой создания данного метода является простой факт: в условиях реальных систем память дороже времени. Действительно, для строк длиной в 216 символов нужно порядка 232 вычислительных операций (что при современных мощностях ляжет в пределах десяти секунд вычислений) и 232 же памяти, что в большинстве случаев уже больше размера физической памяти машины.

    Идея, как использовать линейный объем памяти (2*|S1|) для оценки расстояния лежит на поверхности, осталось грамотно перенести ее на вычисление редакционного предписания.

    Метод встречного расчета (алгоритм Хиршберга)

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

    S1 = ACGTACGTACGT,
    S2 = AGTACCTACCGT.

    Похожи, не правда ли? Но и переписать одну в другую «на глаз» не так очевидно. Буквы, кстати, выбраны не случайно — это азотистые основания (A,T,G,C), компоненты ДНК: метод оценки редакционного расстояния активно применяется в биологии для оценки мутаций.

    Тогда исходная не заполненная матрица будет выглядеть (именно выглядеть, хранить мы будем только необходимые данные) следующим образом:



    В каждой клетке должно стоять значение редакционного расстояния.

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



    При заполнении мы не будем хранить предыдущие столбцы, двигаясь слева направо, сверху вниз, по мере вычисления значений D(i,j) значения D(i-1,j) можно удалять:



    Аналогично, заполним правую часть разбиения. Здесь будем двигаться справа налево, сверху вниз:



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



    Что означает это совмещение? Мы попытались совместить первую строку с первой половиной второй строки, затем первую строку с второй половиной строки. Сумма позволяет получить количество операций изменения первой строки, чтобы привести ее к конкатенации первой и второй половины второй строки (то есть к второй строке)… это значит что мы получили значение редакционного расстояния! Но, рано радоваться, ибо этого результата можно было достичь и проще (вышеописанный метод).

    Однако, посмотрев на картинку под другим углом (буквально), мы получили еще один существенный факт: теперь мы знаем как «разрезать» первую строку на две половины, чтобы соответствующие пары дали нам редакционное расстояние: d(S11,S21) + d(S12,S22) = d(S1,S2). Строка (в матрице), в которой расположен минимум и есть искомое разбиение S1, и это разбиение отправляется в выдачу редакционного предписания.

    Аналогично будем делить задачу уже для получившихся подстрок S11 и S21 (и вторую пару тоже не забудем):



    Завершим подразделение когда не останется ни одной подстроки S1 длины больше 1.



    Получим список разбиений, где каждая подстрока S1 (смотреть по вертикали) дает минимальную оценку изменений относительно соответствующей подстроки S2 (по горизонтали).



    Для удобства я раскрасил отметки цветами: зеленый означает посимвольное совпадение строк в выбранных позициях, синим необходимость замены, а красным — удаления или добавления. Нетрудно заметить, что «красные» кружки находятся в той же строке/столбце (задачка внимательным: объяснить из чего это следует).

    В более удобной форме результат может быть записан так (красные штрихи — соответствие символов, сдвиги обозначены черными горизонтальными):



    Анализ алгоритма

    Память: для каждого шага потребуется запоминать не более чем один столбец d(i,*) и набор разбиений S1. Итого O(|S1| + |S2|). То есть вместо квадратичного объема мы получаем линейный.

    Время: каждое разбиение S[0..N] по столбцу t порождает обработку подстрок S[0..t] и S[t..N]. Всего разбиений N. При обработке каждого разбиения (S1[i..j], S1[k..n]) требуется (j — i) x (n — k) операций. Суммируя оценку худших случаев для подстрок получаем в итоге 2 * |S1| * |S2| операций. Время работы алгоритма осталось квадратичным, хоть и изменилась мультипликативная константа.

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

    [*] Википедия: алгоритм Хиршберга.
    Поделиться публикацией

    Комментарии 19

      +3
      Было бы неплохо упомянуть автора алгоритма (D.S. Hirschberg) и источник.
        +1
        да, спасибо большое! пытался найти информацию об авторстве «метода встречного расчета», но это была кривая дорожка…
        +2
        Стоит отметить, что в случае естественных текстов предпочитают чуть расширенную версию: расстояние Дамерау-Левенштейна. Оно добавляет в список возможных операций транспозиции — перестановку двух соседних символов. Алгоритм, правда, несколько усложняется (просто добавить четвертый случай «если» недостаточно).

        Дамерау показал, что перестановки соседних символов, пропуск символа, добавление нового символа, и ошибка в символе составляют 80% человеческих ошибок при наборе текстов. Таким образом, эту меру похожести слов можно отлично использовать в текстовых редакторах.
          0
          Да, это полезное замечание. В целом, и метод встречного расчета не становится сложнее, достаточно при рекурсивном подразделении рассматривать оба варианта перестановок последних символов на полученных подстроках — ухудшит время в два раза.
          0
          Хорошо расписано, спасибо.
          Добавлю, что не только для текста можно использовать это расстояние, а, к примеру, для распознавания жестов мыши, о чем правда где-то на хабре уже писали.
            +4
            Банальное табличное динамическое программирование.
              +1
              В есть ли готовые библиотеки позволящие сравнивать строки на «близость»?
              0
              А можно как-то из этого алгоритма получить diff?
                0
                Думаю, да — просто сравниваем не символы, а строки (например, хэшами) файла.
                  0
                  Собственно, так обычно diff-ы и работают (в tortoiseHG — точно): ищут Левенштейна, но в качестве «символов» выступают отдельные строки.
                    0
                    именно. а затем, после выполнения синхронизации строк производится сравнения между несовпадающими строками в соответствующих блоках уже посимвольно.

                    хотя вот майкрософтовская утилита fc (file compare) работает как-то по-другому и иногда дает очень странные результаты.
                      0
                      затем, после выполнения синхронизации строк производится сравнения между несовпадающими строками в соответствующих блоках уже посимвольно.

                      Ни разу не видел такого поведения. Обычно даже при добавлении пробела в конец строки просто считают, что изменилась вся строка, и не символ в ней. Или Вы имеете в виду способ хранения этих изменений во внутренностях репозитория? Тогда такое поведение вполне оправдано :).
                  +2
                  когда уже свежий Кнут выйдет? )
                  у него вроде целый том о строках планируется…
                    +1
                    Большое спасибо за статью.
                      0
                      Очень интересная статья, все разжевано и по полочкам разложено!
                      Еще один способ сэкономить память — упаковать нуклеотиды в биты.
                      Тогда в 1 байт войдет 4 нуклеотида (по 2 бита каждый) против 1 или 2 байт на один нуклеотид (в зависимости от кодировки)… Ну и битовые операции сдвига и сравнения по определению быстрее :)
                        0
                        Мне кажется, у Вас в статье закралась ошибка. При склеивании решений Вы считаете сумму в колонке, соответствующей центральному символу, а нужно считать сумму «на стыке». Т.е. у Вас на первом шаге рассматриваются подзадачи (S1[0,6], S2) и (S1[6,11], S2), где буква C (зелёный столбец) входит в обе подзадачи. Склеивание таких решений не всегда работает корректно.

                        Рассмотрим такой пример:
                        S1 = ABYCAKZ
                        S2 = ABYZAKZ
                        Первая подзадача была бы такой: (ABYC, ABYZAKZ) и (CAKZ, ABYZAKZ).
                        Важно, что C входит в обе «половинки» первой строки, как это показано на Вашей картинке.
                        Теперь посмотрим на колонку соответствующую C.
                        Не сложно проверить, что в строке соответствующей Z будет достигнут минимум суммы стоимостей для следующих пар строк: (ABYX, ABYZ) и (XAKZ, ZAKZ).
                        Стоимость первой — 1, стоимость второй — 1. Суммарная стоимость — 2.
                        При этом оптимальное выравнивание
                        ABYXAKZ
                        ABYZAKZ
                        имеет стоимость 1, т.е. стоимость оптимального выравнивания мы не получили.
                        Это происходит из-за того, что Вы дважды посчитали одно и то же редактирование.
                        В оригинальном решении строки делятся пополам без общих символов и склеиваются на стыке строк.

                        Поправьте меня, если я не прав.
                          0
                          Посмотрел ещё раз на Вашу картинку внимательнее. Видимо, проблема в том, что правая синяя часть у Вас сдвинута на 1 вверх и 1 влево (у вас в правой части 4 нуля на диагонали, а должно быть три). Похоже, что за счёт сдвига у Вас получается правильное решение, но неправильная картинка: например, в ячейке (10,10) стоит ноль, а должна стоять единица.
                            0
                            (вместо C нужно читать X)

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

                          Самое читаемое