Пошук найдовшої спільної підпослідовності

Приклад порівняння двох версій файлу на основі їх найдовшої спільної підпослідовності (чорний)

Пошук найдовшої спільної підпослідовності (англ. longest common subsequence, LCS) — це завдання пошуку послідовності, яка є підпослідовністю кількох послідовностей (зазвичай — двох). Часто завдання визначається як пошук всіх найбільших спільних підпослідовностей. Ця задача відрізняється від пошуку найдовшого спільного підрядка: на відміну від підрядків, підпослідовності не повинні займати суміжні позиції в оригінальних послідовностях. Це класична задача інформатики, яка має застосування, зокрема, в задачі порівняння текстових файлів (утиліта diff), а також у біоінформатиці.

Підпослідовність можна отримати з деякої послідовності, якщо видалити з неї деяку множину елементів (можливо, порожню). Наприклад, BCDB є підпослідовністю послідовності ABCDBAB. Також вона буде підпослідовністю послідовності XBXCDXBX. Послідовність Z є спільною підпослідовність послідовностей X і Y, якщо Z є підпослідовністю як X, так і Y. Потрібно для двох послідовностей X і Y знайти спільну підпослідовність найбільшої довжини. Зауважимо, що таких підпослідовностей може бути кілька.

Вирішення задачі

Порівняємо два методи рішення: повний перебір і динамічне програмування.

Повний перебір

Існують різні підходи при вирішенні даної задачі. Один з них — повний перебір. Ми порівнюємо кожен елемент рядка X з кожним елементом рядка Y, тобто $2^{n}$ — час роботи такого алгоритму.

Метод динамічного програмування

		A	B	C	B
	0	0	0	0	0
D	0	← 0	← 0	← 0	← 0
C	0	← 0	← 0	↖ 1	← 1
B	0	← 0	↖ 1	← 1	↖ 2
A	0	↖ 1	← 1	← 1	↑ 2

Спочатку знайдемо довжину найбільшої підпослідовності. Припустимо, ми шукаємо рішення для випадку (n₁, n₂), де n₁, n₂ — довжина першого та другого рядків. Нехай вже існують рішення для всіх підзадач (m₁, m₂), менших заданої. Тоді задача (n₁, n₂) зводиться до підзадач наступним чином:

$f(n_{1},n_{2})=\left\{{\begin{array}{ll}0,&n_{1}=0\lor n_{2}=0\\f(n_{1}-1,n_{2}-1)+1,&s[n_{1}]=s[n_{2}]\\max(f(n_{1}-1,n_{2}),f(n_{1},n_{2}-1)),&s[n_{1}]\neq s[n_{2}]\end{array}}\right.$

Тепер повернемося до задачі побудови підпослідовності. Для цього в наявний алгоритм для кожної задачі додають запам'ятовування тих підзадач, через які вона вирішується. Наступною дією, починаючи з останнього елемента, піднімаємося до початку за напрямками, заданим першим алгоритмом, і записуємо символи в кожній позиції. Це і буде відповіддю в цій задачі.

Очевидно, що час роботи алгоритму буде $\mathrm {O} \,(n_{1}\cdot n_{2})$^{[джерело?]}.

Реалізація алгоритму

С++

    string getLongestCommonSubsequence(const string& a, const string& b)
    {
        vector<vector<int> > max_len;
        max_len.resize(a.size() + 1);
        for(int i = 0; i <= static_cast<int>(a.size()); i++)
            max_len[i].resize(b.size() + 1);
        for(int i = static_cast<int>(a.size()) - 1; i >= 0; i--)
        {
            for(int j = static_cast<int>(b.size()) - 1; j >= 0; j--)
            {
                if(a[i] == b[j])
                {
                    max_len[i][j] = 1 + max_len[i+1][j+1];
                }
                else
                {
                    max_len[i][j] = max(max_len[i+1][j], max_len[i][j+1]);
                }
            }
        }
        string res;
        for(int i = 0, j = 0; max_len[i][j] != 0 && i < static_cast<int>(a.size()) && j < static_cast<int>(b.size()); )
        {
            if(a[i] == b[j])
            {
                res.push_back(a[i]);
                i++;
                j++;
            }
            else
            {
                if(max_len[i][j] == max_len[i+1][j])
                    i++;
                else
                    j++;
            }
        }
        return res;
    }

Ruby

#>> a = "aaaaabbbb34354354345"
#>> b = "abbb34aaabbbb"
#>> longest_common_subsequence(a, b)
#=> "aaaabbbb"
  def longest_common_subsequence(a, b)
    max_len = Array.new(a.size + 1, 0)
    max_len.map! {Array.new(b.size + 1, 0)}

    (a.size - 1).downto(0) do |i|
      (b.size - 1).downto(0) do |j|
        if a[i] == b[j]
          max_len[i][j] = 1 + max_len[i+1][j+1]
        else
          max_len[i][j] = [max_len[i+1][j], max_len[i][j+1]].max
        end
      end
    end

    res = ""
    i = 0
    j = 0
    while max_len[i][j] != 0 && i < a.size && j < b.size
      if a[i] == b[j]
        res << a[i]
        i += 1
        j += 1
      else
        if max_len[i][j] == max_len[i+1][j]
          i += 1
        else
          j += 1
        end
      end
    end

    res
  end

Python

def lcs(a, b):
    n, m = len(a) + 1, len(b) + 1
    f = [[0] * m for i in range(n)]
    for i in range(1, n):
        for j in range(1, m):
            f[i][j] = f[i-1][j-1] + 1 if a[i-1] == b[j-1] else max(f[i-1][j], f[i][j-1])

    i, j = len(a), len(b)
    res = ''
    while f[i][j] > 0:
        if f[i][j] == f[i][j-1]:
            j -= 1
        elif f[i][j] == f[i-1][j]:
            i -= 1
        else:
            res = a[i-1] + res
            i -= 1
            j -= 1
    return res

Джерела

• Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. 4.1 Задача пошуку найбільшого підмасиву. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN 0-262-03384-4.