Редакційна відстань, або відстань Лівенштейна - метрика, що дозволяє визначити «схожість» двох рядків - мінімальну кількість операцій вставки одного символу, видалення одного символу і заміни одного символу на інший, необхідних для перетворення одного рядка на інший. У статті викладається метод обчислення редакційної відстані при використанні невеликого об'єму пам'яті, без істотної втрати швидкості. Цей підхід може бути застосований для великих рядків (близько 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| операцій. Час роботи алгоритму залишився квадратичним, хоч і змінилася мультиплікативна константа.
Отже, ми вирішили завдання, використовуючи лінійну кількість пам'яті і незначно втратили в швидкості, що в даному випадку можна вважати успіхом.
[*] Вікіпедія: алгоритм Хіршберга.