4551
правка
Последовательное приближенное сравнение строк: различия между версиями
Перейти к навигации
Перейти к поиску
Последовательное приближенное сравнение строк (посмотреть исходный код)
Версия от 15:59, 29 марта 2019
, 29 марта 2019→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 68: | Строка 68: | ||
'''Теорема 7 (Чанг и Марр, 1994 [3]). Существует решение с временем выполнения <math>\Theta(n(k + log_{\sigma} \; m)/m)</math> в среднем случае для задачи ASM с использованием расстояния редактирования с единичной стоимостью.''' | '''Теорема 7 (Чанг и Марр, 1994 [3]). Существует решение с временем выполнения <math>\Theta(n(k + log_{\sigma} \; m)/m)</math> в среднем случае для задачи ASM с использованием расстояния редактирования с единичной стоимостью.''' | ||
Нетрудно доказать нижнюю границу как расширение границы Яо для точного сравнения строк [15]. Нижняя граница была достигнута в той же статье [3] для k/m < 1/3 — О(1/у/ст). Позднее она была улучшена до k/m < 1/2 - O(l/^/a) [ ] с использованием несколько отличающейся идеи. Данный подход заключается в вычислении минимального расстояния для сопоставления любой возможной текстовой подстроки (блока) длины O(\oga m) в P. Затем текстовое коно поблочно сканируется в обратном направлении с добавлением этим заранее вычисленных минимальных расстояний. Если до окончания сканирования всего окна они превышают значение k, тогда никакое вхождение P с k ошибками не может содержать отсканированный блок и окно можно безопасно сдвинуть поверх отсканированных блоков, продвигаясь по T. Это пример алгоритма фильтрации, который отбрасывает большинство текстовых областей и применяет алгоритм ASM только к тем областям, которые не могут быть отброшены. | |||
Теорема 8 (Фредриксон и Наварро, 2004 [6]). Существует оптимальное в среднем решение для задачи ASM с использованием расстояния редактирования для любого k/m < —e, Д = 1/2 — J y 2—е/л/а | |||
Данный результат дословно применим и к indel-расстоянию. Для расстояния Хэмминга достигается та же сложность, однако граница на k/m улучшается до 1 — l/ст. Отметим, что при достижении предельного значения k/m средняя сложность уже составляет 0{n). Неясно, для какого предела k/m можно получить среднее линейное время выполнения. | |||
== Применение == | |||