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

Существует немало расширений задачи ASM, особенно в вычислительной биологии. К примеру, можно заменить полные подстроки другими (''обобщенное расстояние редактирования''), поменять символы в строке (''сравнение строк с заменами или транспозициями''), выполнить обращение подстрок (''расстояние обращений''), присвоить разную стоимость операциям вставки и удаления в случае их группировки (''сходство со штрафами за пропуски'') или искать любую пару подстрок обеих строк, обладающую достаточным сходством (''локальное сходство''). Примеры можно найти в книге Гусфилда [7], где рассматривается множество родственных задач.

Сложность задачи в наихудшем случае не вполне понятна. Для расстояния редактирования с единичной стоимостью она составляет <math>\Theta(n)</math> в случае, если <math>m = O(min(log \; n, (log_{\sigma} n)^2))</math> или <math>k = O(min(m^{1/4},log_{m \sigma} n))</math>. Для взвешенного расстояния редактирования сложность составляет <math>\Theta(n)</math> в случае <math>m = O(log_{\sigma} n)</math>. Неизвестно также, для какого значения k/m можно получить среднее время <math>O(n)</math>; до настоящего момента его удавалось получить для <math>k/m = 1/2 - O(1 / \sqrt{\sigma})</math>.

* [[Приближенное сравнение регулярных выражений]] – более сложный случай, где P может быть регулярным выражением]]

* [[Индексированное приближенное сравнение строк]] относится к случаю, при котором возможна предварительная обработка текста]]

* [[Локальное выравнивание (с вогнутыми штрафами за пропуски)]] относится к более сложной схеме с весами]]