Самая длинная общая проблема подпоследовательности - Longest common subsequence problem

Сравнение двух ревизий файла примера на основе их самой длинной общей подпоследовательности (черный)

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

Например, рассмотрим последовательности (ABCD) и (ACBAD). У них есть 5 общих подпоследовательностей длины 2: (AB), (AC), (AD), (BD) и (CD); 2 общих подпоследовательности длины 3: (ABD) и (ACD); и больше не общие подпоследовательности. Итак, (ABD) и (ACD) - их самые длинные общие подпоследовательности.

Сложность

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

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

Для случая двух последовательностей из n и m элементов время работы подхода динамического программирования составляет O ( n × m ). Для произвольного количества входных последовательностей подход динамического программирования дает решение в

Существуют методы с меньшей сложностью, которые часто зависят от длины LCS, размера алфавита или того и другого.

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

Решение для двух последовательностей

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

Префиксы

Префикс S п из S определяется как первые п символов S . Например, префиксы S = (AGCA):

S 0 = ()
S 1 = (А)
S 2 = (AG)
S 3 = (АРУ)
S 4 = (AGCA).

Пусть LCS ( X , Y ) функция , которая вычисляет самую длинную подпоследовательность , общие для X и Y . У такой функции есть два интересных свойства.

Первая недвижимость

LCS ( X ^ A , Y ^ A ) = LCS ( X , Y ) ^ A для всех строк X , Y и всех символов A , где ^ обозначает конкатенацию строк. Это позволяет упростить вычисление LCS для двух последовательностей, заканчивающихся одним и тем же символом. Например, LCS («BANANA», «ATANA») = LCS («BANAN», «ATAN») ^ «A», продолжение для остальных общих символов, LCS («BANANA», «ATANA») = LCS (« БАН »,« АТ ») ^« АНА ».

Вторая собственность

Если A и B - разные символы ( AB ), то LCS (X ^ A, Y ^ B) - одна из строк максимальной длины в наборе { LCS ( X ^ A , Y ), LCS ( X , Y ^ B )}, для всех строк X , Y .

Например, LCS («ABCDEFG», «BCDGK») - самая длинная строка среди LCS («ABCDEFG», «BCDG») и LCS («ABCDEF», «BCDGK»); если оба оказались одинаковой длины, один из них мог быть выбран произвольно.

Чтобы реализовать недвижимость, различают два случая:

  • Если LCS («ABCDEFG», «BCDGK») заканчивается на «G», то последний «K» не может быть в LCS, следовательно, LCS («ABCDEFG», «BCDGK») = LCS («ABCDEFG», «BCDG ").
  • Если LCS («ABCDEFG», «BCDGK») не заканчивается на «G», то последняя «G» не может быть в LCS, следовательно, LCS («ABCDEFG», «BCDGK») = LCS («ABCDEF», «БЦДГК»).

Функция LCS определена

Пусть две последовательности определены следующим образом: и . В префиксы являются ; префиксы есть . Позвольте представить набор самой длинной общей подпоследовательности префиксов и . Этот набор последовательностей дается следующим.

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

Пример работы

Будет найдена самая длинная подпоследовательность, общая для R = (GAC) и C = (AGCAT). Поскольку функция LCS использует «нулевой» элемент, удобно определять нулевые префиксы, которые пусты для этих последовательностей: R 0 = Ø; и C 0 = Ø. Все префиксы помещаются в таблице с C в первой строке ( что делает его с olumn заголовка) и R в первом столбце ( что делает его г вл заголовок).

Струны LCS
Ø А грамм C А Т
Ø Ø Ø Ø Ø Ø Ø
грамм Ø
А Ø
C Ø

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

LCS ( R 1 , C 1 ) определяется путем сравнения первых элементов в каждой последовательности. G и A не совпадают, поэтому эта LCS получает (используя «второе свойство») самую длинную из двух последовательностей, LCS ( R 1 , C 0 ) и LCS ( R 0 , C 1 ). Согласно таблице, оба они пусты, поэтому LCS ( R 1 , C 1 ) также пуст, как показано в таблице ниже. Стрелки указывают, что последовательность исходит как из ячейки выше, LCS ( R 0 , C 1 ), так и из ячейки слева, LCS ( R 1 , C 0 ).

LCS ( R 1 , C 2 ) определяется путем сравнения G и G. Они совпадают, поэтому G добавляется к верхней левой последовательности, LCS ( R 0 , C 1 ), которая равна (Ø), что дает (ØG), что есть (G).

Для LCS ( R 1 , C 3 ) G и C не совпадают. Последовательность выше пуста; один слева содержит один элемент G. Если выбрать самый длинный из них, LCS ( R 1 , C 3 ) будет (G). Стрелка указывает налево, поскольку это самая длинная из двух последовательностей.

LCS ( R 1 , C 4 ) также есть (G).

LCS ( R 1 , C 5 ) также есть (G).

Ряд "G" завершен
Ø А грамм C А Т
Ø Ø Ø Ø Ø Ø Ø
грамм Ø Ø (ГРАММ) (ГРАММ) (ГРАММ) (ГРАММ)
А Ø
C Ø

Для LCS ( R 2 , C 1 ) A сравнивается с A. Два элемента совпадают, поэтому A добавляется к Ø, давая (A).

Для LCS ( R 2 , C 2 ), A и G не совпадают, поэтому самый длинный из LCS ( R 1 , C 2 ), который равен (G), и LCS ( R 2 , C 1 ), который равен (A ), используется. В этом случае каждый из них содержит по одному элементу, поэтому данной LCS даны две подпоследовательности: (A) и (G).

Для LCS ( R 2 , C 3 ) A не соответствует C. LCS ( R 2 , C 2 ) содержит последовательности (A) и (G); LCS ( R 1 , C 3 ) - это (G), который уже содержится в LCS ( R 2 , C 2 ). В результате LCS ( R 2 , C 3 ) также содержит две подпоследовательности, (A) и (G).

Для LCS ( R 2 , C 4 ) A соответствует A, которое добавляется в верхнюю левую ячейку, давая (GA).

Для LCS ( R 2 , C 5 ) A не соответствует T. При сравнении двух последовательностей (GA) и (G) самая длинная - (GA), поэтому LCS ( R 2 , C 5 ) - (GA).

Завершенные ряды "G" и "A"
Ø А грамм C А Т
Ø Ø Ø Ø Ø Ø Ø
грамм Ø Ø (ГРАММ) (ГРАММ) (ГРАММ) (ГРАММ)
А Ø (А) (А) и (G) (А) и (G) (GA) (GA)
C Ø

Для LCS ( R 3 , C 1 ), C и A не совпадают, поэтому LCS ( R 3 , C 1 ) получает самую длинную из двух последовательностей (A).

Для LCS ( R 3 , C 2 ) C и G не совпадают. И LCS ( R 3 , C 1 ), и LCS ( R 2 , C 2 ) имеют один элемент. В результате LCS ( R 3 , C 2 ) содержит две подпоследовательности (A) и (G).

Для LCS ( R 3 , C 3 ), C и C совпадают, поэтому C добавляется к LCS ( R 2 , C 2 ), который содержит две подпоследовательности, (A) и (G), что дает (AC) и (GC ).

Для LCS ( R 3 , C 4 ) C и A не совпадают. Объединение LCS ( R 3 , C 3 ), которое содержит (AC) и (GC), и LCS ( R 2 , C 4 ), которое содержит (GA), дает в общей сложности три последовательности: (AC), (GC) , и (GA).

Наконец, для LCS ( R 3 , C 5 ) C и T не совпадают. В результате LCS ( R 3 , C 5 ) также содержит три последовательности: (AC), (GC) и (GA).

Заполненная таблица LCS
Ø А грамм C А Т
Ø Ø Ø Ø Ø Ø Ø
грамм Ø Ø (ГРАММ) (ГРАММ) (ГРАММ) (ГРАММ)
А Ø (А) (А) и (G) (А) и (G) (GA) (GA)
C Ø (А) (А) и (G) (AC) и (GC) (AC) и (GC) и (GA) (AC) и (GC) и (GA)

Конечный результат состоит в том, что последняя ячейка содержит все самые длинные подпоследовательности, общие для (AGCAT) и (GAC); это (AC), (GC) и (GA). В таблице также показаны самые длинные общие подпоследовательности для каждой возможной пары префиксов. Например, для (AGC) и (GA) самые длинные общие подпоследовательности - это (A) и (G).

Подход с отслеживанием

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

Сохранение длины, а не последовательностей
Ø А грамм C А Т
Ø 0 0 0 0 0 0
грамм 0 0 1 1 1 1
А 0 1 1 1 2 2
C 0 1 1 2 2 2

Фактические подпоследовательности выводятся с помощью процедуры «трассировки», которая следует по стрелкам назад, начиная с последней ячейки в таблице. Когда длина уменьшается, последовательности должны иметь общий элемент. Если в ячейке показаны две стрелки, возможно несколько путей. Ниже представлена ​​таблица для такого анализа с номерами, окрашенными в ячейки, длина которых собирается уменьшиться. Жирные числа обозначают последовательность (GA).

Пример трассировки
Ø А грамм C А Т
Ø 0 0 0 0 0 0
грамм 0 0 1 1 1 1
А 0 1 1 1 2 2
C 0 1 1 2 2 2

Отношение к другим проблемам

Для двух строк и длина кратчайшей общей суперпоследовательности связана с длиной LCS соотношением

Расстояние редактирования, когда разрешены только вставка и удаление (без замены) или когда стоимость замены в два раза превышает стоимость вставки или удаления, составляет:

Код для решения динамического программирования

Вычисление длины LCS

Приведенная ниже функция принимает в качестве входных последовательностей X[1..m]и Y[1..n]вычисляет LCS между X[1..i]и Y[1..j]для всех 1 ≤ i ≤ mи 1 ≤ j ≤ nи сохраняет ее в C[i,j]. C[m,n]будет содержать длину LCS Xи Y.

function LCSLength(X[1..m], Y[1..n])
    C = array(0..m, 0..n)
    for i := 0..m
        C[i,0] = 0
    for j := 0..n
        C[0,j] = 0
    for i := 1..m
        for j := 1..n
            if X[i] = Y[j]
                C[i,j] := C[i-1,j-1] + 1
            else
                C[i,j] := max(C[i,j-1], C[i-1,j])
    return C[m,n]

В качестве альтернативы можно использовать мемоизацию .

Пример на C #

static int[,] LcsLength(string a, string b)
{
    int[,] C = new int[a.Length + 1, b.Length + 1]; // (a, b).Length + 1
    for (int i = 0; i < a.Length; i++)
        C[i, 0] = 0;
    for (int j = 0; j < b.Length; j++)
        C[0, j] = 0;
    for (int i = 1; i <= a.Length; i++)
        for (int j = 1; j <= b.Length; j++)
        {
            if (a[i - 1] == b[j - 1])//i-1,j-1
                C[i, j] = C[i - 1, j - 1] + 1;
            else
                C[i, j] = Math.Max(C[i, j - 1], C[i - 1, j]);
        }
    return C;
}

Чтение LCS

Следующая функция отслеживает выбор, сделанный при вычислении Cтаблицы. Если последние символы в префиксах равны, они должны быть в LCS. Если нет, то проверьте , что дало наибольший ЛСК хранения и , и сделать такой же выбор. Просто выберите один, если они одинаковой длины. Вызовите функцию с помощью и . i=mj=n

function backtrack(C[0..m,0..n], X[1..m], Y[1..n], i, j)
    if i = 0 or j = 0
        return ""
    if  X[i] = Y[j]
        return backtrack(C, X, Y, i-1, j-1) + X[i]
    if C[i,j-1] > C[i-1,j]
        return backtrack(C, X, Y, i, j-1)
    return backtrack(C, X, Y, i-1, j)

Пример на C #

string Backtrack(int[,] C, char[] aStr, char[] bStr, int x, int y)
{
    if (x == 0 | y == 0)
        return "";
    if (aStr[x - 1] == bStr[y - 1]) // x-1, y-1
        return backtrack(C, aStr, bStr, x - 1, y - 1) + aStr[x - 1]; // x-1
    if (C[x, y - 1] > C[x - 1, y])
        return backtrack(C, aStr, bStr, x, y - 1);
    return backtrack(C, aStr, bStr, x - 1, y);
}

Считывание всех LCS

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

function backtrackAll(C[0..m,0..n], X[1..m], Y[1..n], i, j)
    if i = 0 or j = 0
        return {""}
    if X[i] = Y[j]
        return {Z + X[i] for all Z in backtrackAll(C, X, Y, i-1, j-1)}
    R := {}
    if C[i,j-1] ≥ C[i-1,j]
        R := backtrackAll(C, X, Y, i, j-1)
    if C[i-1,j] ≥ C[i,j-1]
        R := R ∪ backtrackAll(C, X, Y, i-1, j)
    return R

Распечатать разницу

Эта функция будет возвращаться назад через матрицу C, и напечатать различия между двумя последовательностями. Обратите внимание, что вы получите другой ответ, если обменяете и <, с >и ниже.

function printDiff(C[0..m,0..n], X[1..m], Y[1..n], i, j)
    if i >= 0 and j >= 0 and X[i] = Y[j]
        printDiff(C, X, Y, i-1, j-1)
        print "  " + X[i]
    else if j > 0 and (i = 0 or C[i,j-1] ≥ C[i-1,j])
        printDiff(C, X, Y, i, j-1)
        print "+ " + Y[j]
    else if i > 0 and (j = 0 or C[i,j-1] < C[i-1,j])
        printDiff(C, X, Y, i-1, j)
        print "- " + X[i]
    else
        print ""

Пример

Пусть будет « » и будет « ». Самая длинная общая подпоследовательность между и - « ». Приведенная ниже таблица , созданная функцией , показывает длины самых длинных общих подпоследовательностей между префиксами и . В строке и столбце показана длина LCS между и . XMJYAUZMZJAWXUMJAUCLCSLength

0 1 2 3 4 5 6 7
Ø M Z J А W Икс U
0 Ø 0 0 0 0 0 0 0 0
1 Икс 0 0 0 0 0 0 1 1
2 M 0 1 1 1 1 1 1 1
3 J 0 1 1 2 2 2 2 2
4 Y 0 1 1 2 2 2 2 2
5 А 0 1 1 2 3 3 3 3
6 U 0 1 1 2 3 3 3 4
7 Z 0 1 2 2 3 3 3 4

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

Оптимизация кода

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

Уменьшите набор проблем

Матрица C в наивном алгоритме растет квадратично с длиной последовательностей. Для двух последовательностей из 100 элементов потребуется матрица из 10 000 элементов и выполнить 10 000 сравнений. В большинстве реальных случаев, особенно при обнаружении различий и исправлений исходного кода, начало и конец файлов редко меняются, и почти наверняка не оба одновременно. Если в середине последовательности изменились только несколько элементов, начало и конец можно удалить. Это снижает не только требования к памяти для матрицы, но и количество необходимых сравнений.

function LCS(X[1..m], Y[1..n])
    start := 1
    m_end := m
    n_end := n
    trim off the matching items at the beginning
    while start ≤ m_end and start ≤ n_end and X[start] = Y[start]
        start := start + 1
    trim off the matching items at the end
    while start ≤ m_end and start ≤ n_end and X[m_end] = Y[n_end]
        m_end := m_end - 1
        n_end := n_end - 1
    C = array(start-1..m_end, start-1..n_end)
    only loop over the items that have changed
    for i := start..m_end
        for j := start..n_end
            the algorithm continues as before ...

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

Сократите время сравнения

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

Преобразовать строки в хеши

Для уменьшения размера строк в последовательностях можно использовать хеш-функцию или контрольную сумму . То есть для исходного кода, в котором средняя строка составляет 60 или более символов, хэш или контрольная сумма для этой строки может иметь длину от 8 до 40 символов. Кроме того, случайный характер хэшей и контрольных сумм гарантирует, что сравнения будут сокращаться быстрее, поскольку строки исходного кода редко меняются в начале.

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

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

Уменьшите необходимое пространство

Если требуется только длина LCS, матрицу можно легко уменьшить до матрицы или до вектора (более разумно), поскольку для подхода динамического программирования нужны только текущий и предыдущий столбцы матрицы. Алгоритм Хиршберга позволяет построить саму оптимальную последовательность за то же квадратичное время и линейные пространственные ограничения.

Дальнейшие оптимизированные алгоритмы

Существует несколько алгоритмов, которые работают быстрее, чем представленный подход динамического программирования. Один из них - алгоритм Ханта – Шимански , который обычно выполняется во времени (для ), где - количество совпадений между двумя последовательностями. Для задач с ограниченным размером алфавита можно использовать метод четырех русских , чтобы сократить время работы алгоритма динамического программирования на логарифмический коэффициент.

Поведение на случайных строках

Начиная с Chvátal & Sankoff (1975) , ряд исследователей исследовали поведение самой длинной общей длины подпоследовательности, когда две заданные строки выбираются случайным образом из одного и того же алфавита. Когда размер алфавита постоянный, ожидаемая длина LCS пропорциональна длине двух строк, а константы пропорциональности (в зависимости от размера алфавита) известны как константы Хватала – Санкоффа . Их точные значения неизвестны, но верхняя и нижняя границы их значений были доказаны, и известно, что они растут обратно пропорционально квадратному корню из размера алфавита. Было показано, что упрощенные математические модели самой длинной общей проблемы подпоследовательности контролируются распределением Трейси – Уидома .

Смотрите также

использованная литература

внешние ссылки