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

Нетрудно доказать нижнюю границу как расширение границы Яо для точного сравнения строк [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 только к тем областям, которые не могут быть отброшены.

'''Теорема 8 (Фредриксон и Наварро, 2004 [6]). Существует оптимальное в среднем решение для задачи ASM с использованием расстояния редактирования для любого k/m'''