Последовательное приближенное сравнение строк: различия между версиями

Этот весьма общий результат имеет место также для вычисления взвешенного расстояния редактирования и локального сходства (см. раздел «Применение»). Для случая расстояния редактирования и использования RAM-модели с единичной стоимостью можно получить лучший результат. С одной стороны, можно применить «метод четырех русских», который предварительно вычисляет все возможные блоки (подматрицы C) размера t x t для t = O(logcr n) и затем поблочно вычисляет матрицу [9]. С другой стороны, каждую ячейку матрицы C можно представить при помощи константного числа бит (поскольку она может отличаться от соседних ячеек на ± 1) таким образом, чтобы можно был охранить и обрабатывать несколько ячеек при помощи одного машинного слова [10]. Эта техника называется битовым параллелизмом и предполагает использование машинных слов длиной © (log n) бит.

Для расстояний редактирования с единичной стоимостью сложность может зависеть от k, а не от m, поскольку для нетривиальных задач k < m и обычно k составляет небольшую часть m (или даже k = o(m)). Классическая техника [ ] вычисляет матрицу С путем обработки за константное время диагоналей C[i + d; j + d], 0 < d < s, вдоль  которых значения ячеек не изменяются. Это можно сделать при помощи предварительной обработки суффиксных деревьев T и P для ответа на запросы о самых низких общих предках.

Теорема 4 (Ландау и Вишкин, 1989 [ ]). Существует решение с временем выполнения O(mn) в наихудшем случае для задачи ASM с использованием расстояния редактирования с единичной стоимостью.