Машек і Патерсон [Masek, Paterson, 1980] застосували до процедури обчислення відстані між рядками Вагнера і Фішера підхід 'чотирьох російських' (Арлазарова, Дініца, Кронрода і Фараджева [Arlazarov, Dinic, Kronrod, Faradzev, 1970]) і отримали алгоритм, що виконується за час O (n 2 / log n). Він і описаний нижче.
Матриця відстаней d розбивається на сукупність квадратних підматриць з перекриваються крайніми векторами. Подматріца (i, j, p) визначається як подматріца розмірності (p + 1) * (p + 1), лівим верхнім елементом якої є di, j. З визначення (11) входів матриці d видно, що значення подматріци (i, j, p) виводяться з її відповідних подстрок x (i + 1, i + p) і y (j + 1, j + p) і початкових векторів, тобто, її верхнього рядка (di, j. di, j + 1, ... di, j + p) і лівого стовпчика (di, j. di + 1, j. di + p, j).
На першому етапі алгоритму обчислюються значення кінцевих векторів, тобто нижнього рядка і правого стовпчика, для всіх можливих підматриць (i, j, p) будь-якої матриці d для даних алфавіту і функції ціни. Це вимагає перерахування всіх підматриць, для чого потрібні списки всіх комбінацій можливих подстрок і початкових векторів. Щоб перелічити всі можливі подстроки довжини p, ми повинні вважати, що алфавіт кінцевий. Крім того, спроби перерахувати всі можливі початкові вектора можуть бути заборонені. Однак, обмеження цін редагування таким чином, щоб вони стали інтегральними множителями деяких дійсних чисел призведе до того, що вони стануть всього лише кінцевим числом різниць між послідовними значеннями d для всіх матриць відстаней, що використовують один і той же алфавіт і функцію ціни. Набагато практичніше використовувати ці різниці, ніж абсолютні значення. Визначаючи крок як різниця між будь-якими двома горизонтально або вертикально суміжними елементами матриць, приходимо до наступного слідству правила (11) обчислення di, j:
Кожну підматрицю можна, таким чином, вивести за відповідними підрядками x (i + 1, i + p) і y (j + 1, j + p), початкового значення di, j. і початковим векторах - верхньому рядку (di, j + 1 - di, j. di, j + p - di, j + p-1) і на одну (di + 1, j - di, j. ..., di + p , j - di + p-1, j). Перерахування всіх можливих підматриць може бути досягнуто перерахуванням всіх пар рядків довжини p над кінцевим алфавітом C, і всіх пар векторів кроку довжини p.
Алгоритм для обчислення всіх підматриць наведено на малюнку 17. Рядки довжини p і вектора кроку довжини p перераховуються в алфавітному порядку, припускаючи фіксоване впорядкування на C і на кінцевому безлічі можливих значень кроку. Подматріца кроку обчислюється для кожної пари рядків u і v, і кожної пари векторів початкового кроку T і L, відповідно до (42). Щоб полегшити подальше просування, процедура store зберігає вектори кінцевого етапу B і R, подматріци, визначеної u, v. T і L. У процедурі обчислюються дві матриці кроків: V містить значення вертикального кроку, а H - горизонтального.
Малюнок 17. Обчислення подматріци в методі Машека-Патерсона
Так як самий внутрішній цикл виконується постійне час і повторюється рівно p 2 раз для кожної пари рядків і векторів кроку, кожна подматріца обчислюється за час O (p 2). Число пар рядків довжини p над алфавітом одно 2p. Якщо s - потужність цієї множини можливих значень кроку, яке ми будемо вважати кінцевим, то все є s 2p різних пар векторів кроку довжини p. Таким чином, всього є (s *) 2p різних підматриць, що в цілому дає час обробки O (p 2 (s * 2p).
Раніше ми оголосили, що при обмеженнях на функцію ціни безліч можливих значень кроку є кінцевим. Розглянемо це твердження ближче. З правила для di, j і граничних умов (11) - (12) можна бачити, що значення кроку обмежені, незалежно від того, які рядки розглядаються:
Функцію ціни називають розрідженій. якщо кожен член безлічі цінових ваг, а саме, є цілим множником деякої константи r. Для кінцевих алфавітів можна показати, що, якщо функція ціни є розрідженій, то безліч отриманих в матриці значень кроку є кінцевим незалежно від конкретних рядків, що підтверджує зроблене раніше твердження.
Малюнок 18. Обчислення відстані по Машека-Патерсону
w (,) = 0 w (,) = 0 w (a,) = w (a,) a w (, b) = w (, b)) b
Фактичну послідовність редагування мінімальної ціни можна отримати за допомогою методу, близькому до перебору з поверненнями Вагнера і Фішера. Необхідні для цього відстані редагування можна отримати або перевичісляя подматріци, через які проходить шлях оптимального редагування, або зберігаючи заповнені подматріци під час попередніх обчислень. Останній підхід дозволяє визначати послідовність редагування по заповненим матрицями P і Q і заздалегідь обчисленим подматріца за лінійний час і вимагає O (n log 2 n) пам'яті для зберігання підматриць. Зверніть увагу, що матриці P і Q вимагають по (1 + m / p) * (1 + n / p) * p осередків кожна, що становить O (n 2 / log n). Таким чином, всього при цьому методі потрібно O (n 2 / log n) пам'яті.
Цей алгоритм можна також застосувати до задачі знаходження lcs (x, y), використовуючи функцію ціни, що задається (15). Взаємозв'язок між d (x, y) і | l (x, y) |, що задається виразом (16), дозволяє потім обчислити довжину lcs за час O (n 2 * log n). Саму lcs можна отримати за допомогою методу, схожого на використовуваний для отримання оптимальної послідовності редагування.
Було показано, що обчислення відстаней між рядками за допомогою цього методу асимптотично швидше, ніж квадратичний метод Вагнера і Фішера. Однак, на практиці реальний виграш можна отримати тільки для дуже довгих рядків. Щоб проілюструвати це, Машек і Патерсон [Masek, Patterson, 1983] вирахували, що для бінарного алфавіту і цінової функції відстані редагування, краща ефективність досягається тільки для рядків, довжина яких перевищує 262 418.