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

Последний результат для расстояния редактирования [4] демонстрирует время O(n) в случае, если k достаточно мало <math>(k = O(m^{1/4)})</math>. Можно также получить время O(n) для расстояний редактирования с единичной стоимостью за счет экспоненциального дополнительного члена в m или k. Количество разных столбцов в матрице C не зависит от n, так что переход от одного возможного столбца к следующему может быть предварительно вычислен при помощи конечного автомата.

'''Теорема 7 (Чанг и Марр, 1994 [3]). Существует решение с временем выполнения <math>\Theta(n(k + log_{\sigma} \; m)/m)</math> в среднем случае для задачи ASM с использованием расстояния редактирования с единичной стоимостью.'''

Нетрудно доказать нижнюю границу как расширение границы Яо для точного сравнения строк [15]. Нижняя граница была достигнута в той же статье [3] для <math>k/m < 1/3 - O(1 / \sqrt{\sigma})</math>. Позднее она была улучшена до <math>k/m < 1/2 - O(1 / \sqrt{\sigma})</math> [6] с использованием несколько отличающейся идеи. Данный подход заключается в вычислении минимального расстояния для сопоставления любой возможной текстовой подстроки (блока) длины <math>(log_{\sigma} \; m)</math> в P. Затем текстовое окно поблочно сканируется в обратном направлении с добавлением этим заранее вычисленных минимальных расстояний. Если до окончания сканирования всего окна они превышают значение k, тогда никакое вхождение P с k ошибками не может содержать отсканированный блок и окно можно безопасно сдвинуть поверх отсканированных блоков, продвигаясь по T. Это пример алгоритма ''фильтрации'', который отбрасывает большинство текстовых областей и применяет алгоритм ASM только к тем областям, которые не могут быть отброшены.

Данный результат дословно применим и к indel-расстоянию. Для расстояния Хэмминга достигается та же сложность, однако граница на k/m улучшается до <math>1 - 1 / \sqrt{\sigma}</math>. Отметим, что при достижении предельного значения k/m средняя сложность уже составляет <math>\Theta(n)</math>. Неясно, для какого предела k/m можно получить среднее линейное время выполнения.