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

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