Найдовша загальна підпослідовність: Python, C++ Приклад

⚡ Розумний підсумок

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

  • 📘 Основна концепція: Функція «Найдовша спільна підпослідовність» повертає найдовший упорядкований набір символів, що зустрічається в обох вхідних рядках, зберігаючи при цьому їхній початковий відносний порядок.
  • ???? Наївний підхід: Метод грубої сили перераховує кожну підпослідовність першого рядка та перевіряє її на відповідність другому, виконуючи експоненціальний час O(n·2^m).
  • 🔁 Рекурсивний метод: Рекурсивне правило збігається з останніми символами або рекурсивно виконується для менших підрядків, але перераховує перекриття.ping підзадачі неодноразово.
  • 🧮 Динамічне програмування: Двовимірна dp таблиця кешує результати підзадачі, даючи чистий розв'язок O(m·n) з допоміжним простором O(m·n).
  • 🐍 Мовне покриття: Цілковита Python та C++ Реалізації демонструють як рекурсивну базову лінію, так і мемоізовану таблицю dp для практичного використання.
  • 🌐 Реальні застосування: Найдовша спільна підпослідовність забезпечує інструменти для вирівнювання послідовностей, перевірки на плагіат, корекції орфографії та біоінформатичне вирівнювання послідовностей ДНК та білків.

Найдовша загальна підпослідовність

Що таке найдовша спільна підпослідовність?

Найдовша спільна підпослідовність (НСП) означає, що вам буде задано два рядки, шаблони або послідовності об'єктів. Серед цих двох послідовностей або рядків вам потрібно знайти найдовшу підпослідовність елементів в одному порядку, присутню в обох рядках або шаблонах.

Приклад

Наприклад, надано два рядки. Припустимо, що:

Шаблон_1 = “RGBGARGA”
Шаблон_2 = «BGRARG»

  • З шаблону pattern_1 можна створювати послідовності типу «RGB», «RGGA», «RGAR». Для створення послідовності потрібно зберегти відносне положення кожного символу в рядку.
  • З шаблону pattern_2 ми можемо створювати послідовності типу «BGR», «BRAG», «RARG». Послідовності можна створювати, якщо вони зберігають відносну позицію вихідного рядка.

Термін відносне розташування означає порядок.

Наприклад, «BRG» є коректною послідовністю, оскільки «B» з’явилася першою, потім «R» і лише потім «G» у вихідному рядку pattern_2. Однак, якщо послідовність має вигляд «RBRG», вона некоректна, оскільки у вихідному рядку (pattern_2) «B» йде першою.

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

У нас є два варіанти пошуку найдовшої спільної підпослідовності з заданих двох послідовностей або масивів.

  • Наївний метод
  • Рішення для динамічного програмування: найдовша загальна підпослідовність також відома як LCS.

Наївне рішення має більшу часову складність і не є оптимальним рішенням. Використовуючи рішення динамічного програмування (DP), ми долаємо проблему складності.

Наївний метод

Наївний метод — це простий підхід до проблеми, незалежно від часової складності та інших факторів оптимізації. У більшості випадків він складається з «грубої сили», кількох циклів та рекурсивних викликів. Термін «груба сила» означає перебір усіх можливих шаблонів для заданої проблеми.

Приклад

З наведеного вище прикладу pattern1 і pattern2 припустимо, що pattern1 має довжину m, а pattern2 має довжину n. Щоб перевірити всі можливі випадки, нам потрібно оцінити кожну можливу підпослідовність шаблону1 з шаблоном2.

Ось простий рядок із 4 літер «ABCD». Наприклад, нам потрібно створити послідовність з «ABCD». Ми можемо або взяти символ, або ні. Це означає, що для кожного символу у нас є два варіанти:

  • Символ буде додано до підпослідовності.
  • Символ не буде додано до підпослідовності.

Тут зображення показують усі послідовності, які ми можемо створити з рядка «ABCD».

Послідовності наївного методу ABCD

Послідовність з 1 символу:

Послідовності окремих символів наївного методу

Послідовності з 2 символів:

Двосимвольні послідовності наївного методу

Послідовності з 3 символів:

Наївний метод трисимвольних послідовностей

З наведеної вище діаграми видно 14 послідовностей. Якщо не брати жодної літери, тобто порожній рядок, загальна кількість послідовностей становитиме 15. Більше того, рядок «ABCD» сам по собі є послідовністю. Отже, загальна кількість послідовностей дорівнює 16.

Отже, з «ABCD» можна згенерувати 2^4 або 16 підпослідовностей. Потім рядок довжиною m матиме повну підпослідовність 2^m.

Для кожної підпослідовності нам потрібно перевірити її для всього шаблону2. Це займе O(n) часу. O(n) означає функцію складності, яка обчислює час, необхідний для виконання.

Отже, загальна часова складність стає O(n*2^m). Для прикладу, який ми розглянули вище, значення m=8 та n=5.

Ось кроки наївного методу:

Крок 1) Візьміть послідовність з шаблону1.
Крок 2) Зіставте послідовність з кроку 1 зі шаблоном 2.
Крок 3) Якщо збігається, то збережіть підпослідовність.
Крок 4) Якщо у шаблоні 1 залишилося більше послідовностей, то знову перейдіть до кроку 1.
Крок 5) Вивести найдовшу підпослідовність.

Оптимальна підструктура

Термін «оптимальна підструктура» означає, що оптимальне рішення можна знайти шляхом розв'язання підзадач. Наприклад, у наведеному вище прикладі ми маємо шаблон1 та шаблон2.

Крок 1) Візьміть перші два символи з кожного шаблону.

Крок 2) Візьміть третій-п’ятий символи з кожного шаблону.

Крок 3) Продовжуйте аналогічно з іншими символами.

Рекурсивна структура задачі LCS

Рекурсивна структура задачі LCS

Ми знаходимо НСК (довжину НСК) для підрядка (рядка, згенерованого з вихідного рядка). Потім ми ведемо запис довжини НСК підрядків.

Ось ще одна цікава властивість перекриттяping підпроблемиКажуть, що проблема має перекриття.ping підзадачі, якщо постановку задачі можна розбити на невеликі підзадачі та використовувати кілька разів у програмі.

На діаграмі нижче показано, що рекурсивний алгоритм кілька разів викликав функцію з одним і тим же параметром.

Оптимальне перекриття підструктуриping підзадачі

Наприклад, розгляньте дерево рекурсії. У темному полі ви можете помітити перекриття.ping підзадачі. («RG», «RA»), («RG», «R») та інші викликаються кілька разів.

Щоб оптимізувати це, ми маємо підхід Динамічне програмування (ДП).

Рекурсивний метод найдовшої спільної підпослідовності

Графік, показаний вище, є рекурсивним методом. Кожна рекурсивна функція має базовий випадок для переривання рекурсії або початку повернення зі свого стеку.

Для цієї реалізації ми використовуватимемо базовий випадок. Отже, алгоритм виглядає наступним чином:

  • Якщо всі елементи перед останнім елементом мають збіг, то збільшують довжину на одиницю та повертають.
  • Передайте два шаблони до функції та візьміть максимальне значення, яке повертається.
  • Якщо один шаблон має нульову довжину, то у нас немає підпослідовності для порівняння. У цьому випадку повертає 0. Це базовий випадок рекурсії.

Псевдо Code:

def lcs:
    input: pattern_1, pattern_2, len_1, len_2
    if len_1 or len_2 is zero:
        return 0
    if pattern_1[len_1 - 1] equals pattern_2[len_2 - 1]:
        return 1 + lcs(pattern_1, pattern_2, len_1 - 1, len_2 - 1)
    else:
        return max(lcs(pattern_1, pattern_2, len_1 - 1, len_2),
                   lcs(pattern_1, pattern_2, len_1, len_2 - 1))

Реалізація в C++

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int lcs(string pattern_1, string pattern_2, int len_1, int len_2) {
  if (len_1 == 0 || len_2 == 0)
    return 0;
  if (pattern_1[len_1 - 1] == pattern_2[len_2 - 1]) {
    return 1 + lcs(pattern_1, pattern_2, len_1 - 1, len_2 - 1);
  } else {
    return max(lcs(pattern_1, pattern_2, len_1 - 1, len_2), lcs(pattern_1, pattern_2, len_1, len_2 - 1));
  }
}
int main() {
  string pattern_1, pattern_2;
  pattern_1 = "RGBGARGA";
  pattern_2 = "BGRARG";
  cout<<"Length of LCS is: "<<lcs(pattern_1, pattern_2, pattern_1.size(), pattern_2.size())<<endl;
}

вихід:

Length of LCS is: 5

Реалізація в Python

def lcs(pattern_1, pattern_2, len_1, len_2):
    if len_1 == 0 or len_2 == 0:
        return 0
    if pattern_1[len_1 - 1] == pattern_2[len_2 - 1]:
        return 1 + lcs(pattern_1, pattern_2, len_1 - 1, len_2 - 1)
    else:
        return max(lcs(pattern_1, pattern_2, len_1 - 1, len_2),
                   lcs(pattern_1, pattern_2, len_1, len_2 - 1))

pattern_1 = "RGBGARGA"
pattern_2 = "BGRARG"
print("Length of LCS is: ", lcs(pattern_1, pattern_2, len(pattern_1), len(pattern_2)))

вихід:

Length of LCS is:  5

Метод динамічного програмування найдовшої спільної підпослідовності (LCS)

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

Ми використовуватимемо 2D-масив з розмірами mxn, де m та n – довжини шаблонів pattern1 та pattern2. Для 2D масив, ми можемо використовувати структури даних List у Python або векторні/масивні структури даних у C++.

Псевдо Code для LCS з використанням DP:

LCS(pattern_1, pattern_2):
    m = length of pattern_1 + 1
    n = length of pattern_2 + 1
    dp[n][m]
    for i in range 0 to n + 1:
        for j in range 0 to m + 1:
            if i or j equals to 0:
                dp[i][j] = 0
            else if pattern_1[i] == pattern_2[j]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[n][m]

Ось таблична LCS, яка використовується як структура даних 2D-масиву для підходу динамічного програмування.

Метод динамічного програмування LCS 2D таблиці

Давайте обговоримо логіку, яку ми тут використовували. Кроки такі:

Крок 1) Якщо i або j дорівнює нулю, ми беремо порожній рядок з двох заданих рядків і намагаємося знайти спільні підпослідовності. Однак, оскільки підрядок, який ми беремо, порожній, довжина підпослідовності дорівнює 0.

Крок 2) Якщо два символи збігаються, ми присвоїмо значення індексу (i,j), збільшуючи попередньо обчислене НСК, яке присутнє в індексі (i-1,j-1) (з попереднього рядка).

Крок 3) Якщо воно не збігається, то ми візьмемо максимальне значення НСК двох суміжних індексів. Таким чином, нам потрібно заповнити всі значення в 2D-масиві.

Крок 4) Нарешті, ми повернемо значення останньої клітинки 2D-масиву.

По суті, всі значення у 2D-масиві містять довжину спільних підпослідовностей. Серед них остання комірка містить довжину найдовшої спільної підпослідовності.

Реалізація в C++

#include<iostream>
using namespace std;
int lcs(string pattern_1, string pattern_2) {
  int m = pattern_1.size();
  int n = pattern_2.size();
  // dp will store solutions as the iteration goes on
  int dp[n + 1][m + 1];
  for (int i = 0; i < n + 1; i++) {
    for (int j = 0; j < m + 1; j++) {
      if (i == 0 || j == 0) {
        dp[i][j] = 0;
      } else if (pattern_2[i - 1] == pattern_1[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }
  return dp[n][m];
}
int main() {
  string pattern_1 = "RGBGARGA";
  string pattern_2 = "BGRARG";
  cout<<"Length of LCS: "<<lcs(pattern_1, pattern_2)<<endl;
}

вихід:

Length of LCS: 5

Реалізація в Python

def lcs(pattern_1, pattern_2):
    m = len(pattern_1)
    n = len(pattern_2)
    # dp will store solutions as the iteration goes on
    dp = [[None] * (n + 1) for item in range(m + 1)]
    for i in range(m + 1):
        for j in range(n + 1):
            if i == 0 or j == 0:
                dp[i][j] = 0
            elif pattern_1[i - 1] == pattern_2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

pattern_1 = "RGBGARGA"
pattern_2 = "BGRARG"
print("Length of LCS: ", lcs(pattern_1, pattern_2))

вихід:

Length of LCS: 5

Отже, обидва рядки мають найдовшу спільну підпослідовність довжиною 5.

Коротко кажучи, у методі DP ми просто обчислюємо кожне завдання один раз. У рекурсивному методі може бути перекриття.ping підзадачі.

У цьому алгоритмі динамічного програмування ми використовуємо двовимірну матрицю. Буде подано два рядки (припустимо, що обидва мають довжину n). Тоді необхідний простір у масиві становить nx n. Якщо рядки достатньо великі, нам знадобиться оптимізована для пам’яті версія рішення DP.

Спрощена логіка, яка була використана в коді:

  • Оголошення двовимірного масиву DP[m][n].
  • Заповніть перший рядок і перший стовпець масиву DP 0.
  • Візьміть i та j для ітерації.
  • Якщо pattern1[i] дорівнює pattern2[j], тоді оновлюємо DP[i][j] = DP[i-1][j-1] + 1.
  • Якщо pattern1[i] не дорівнює pattern2[j], то DP[i][j] буде максимальним значенням між DP[i-1][j] та DP[i][j-1].
  • Продовжуйте, доки i та j не досягнуть m та n.
  • Останній елемент, DP[m-1][n-1], міститиме довжину.

Тут він адресується як DP[m-1][n-1], оскільки індекс масиву починається з 0.

Поширені запитання

Конвеєри машинного навчання використовують LCS як ознаку подібності в класифікації тексту, оцінці послідовності до послідовності та детекторах плагіату коду. Він також лежить в основі метрик у стилі BLEU та ROUGE, які оцінюють згенерований текст порівняно з вихідними даними.

Так. Помічники ШІ-кодування, такі як GitHub Copilot та GPT, можуть створювати рекурсивні та динамічні версії LCS у Python, C++або JavaВони також можуть додавати мемоізацію, виводити фактичну підпослідовність або перетворювати код в ітераційну форму на запит.

Підрядок має бути безперервним, тоді як підпослідовність має лише зберігати порядок. Для «ABCDE» «ACD» є коректною підпослідовністю, але не підрядком, тоді як «BCD» є і підрядком, і підпослідовністю.

Версія динамічного програмування виконується за час та простор O(m·n), де m та n – довжини двох вхідних послідовностей. Проста рекурсивна версія виконується за експоненціальний час O(2^(m+n)) у найгіршому випадку.

LCS забезпечує роботу утиліт для порівняння файлів, злиття Git, вирівнювання послідовностей ДНК та білків у біоінформатиці, виявлення плагіату, перевірку орфографії та інструменти синхронізації даних, які повинні зберігати спільний порядок записів.

Стандартна таблиця вимагає O(m·n) простору. Дворядкова оптимізація зменшує простір до O(min(m, n)), коли потрібна лише довжина, хоча для реконструкції фактичної підпослідовності все одно потрібна повна таблиця.

Так, чиста рекурсія працює для коротких рядків, але переобчислює ті самі підзадачі багато разів і стає непрактичною після 20-25 символів. Додавання мемоізації або таблиці DP відновлює tracпродуктивність столу.

Так. Ідея DP поширюється на k послідовностей з використанням k-вимірної таблиці з O(n^k) часом та простором. Цей варіант зустрічається в інструментах для багатофайлового різнення та вирівнювання множинних послідовностей у біоінформатиці.

Підсумуйте цей пост за допомогою: