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

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

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

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

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

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

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

Існують різні підходи при вирішенні даної задачі. Один з них — повний перебір. Ми порівнюємо кожен елемент рядка X з кожним елементом рядка Y, тобто ${\displaystyle 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₂) зводиться до підзадач наступним чином:

${\displaystyle 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.}$

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

Очевидно, що час роботи алгоритму буде ${\displaystyle \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 

Джерела

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

Примітки