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

Этот весьма общий результат имеет место также для вычисления взвешенного расстояния редактирования и локального сходства (см. раздел «Применение»). Для случая расстояния редактирования и использования RAM-модели с единичной стоимостью можно получить лучший результат. С одной стороны, можно применить «метод четырех русских», который предварительно вычисляет все возможные блоки (подматрицы C) размера <math>t \times t</math> для <math>t = O(log_{\sigma} \; n)</math> и затем поблочно вычисляет матрицу [9]. С другой стороны, каждую ячейку матрицы C можно представить при помощи константного числа бит (поскольку она может отличаться от соседних ячеек на ± 1) таким образом, чтобы можно был охранить и обрабатывать несколько ячеек при помощи одного машинного слова [10]. Эта техника называется ''битовым параллелизмом'' и предполагает использование машинных слов длиной <math>\Theta (log \; n)</math> бит.

'''Теорема 3 (Масек и Паттерсон, 1980 [9]; Майерс, 1999 [10]). Существуют решения с временем выполнения <math>O(n + mn / log_{\sigma} \; n)^2)</math> и <math>O(n + mn /log \; n)</math> в наихудшем случае для задачи ASM с использованием взвешенного расстояния редактирования.'''

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