Последовательное приближенное сравнение строк
Ключевые слова и синонимы
Сравнение строк, допускающее ошибки или разность; неточное сравнение строк; полуглобальное или полулокальное сходство последовательностей
Постановка задачи
Пусть даны текстовая строка [math]\displaystyle{ T = t_1 t_2 ... t_n }[/math] и строка образца [math]\displaystyle{ P = p_1 p_2 ... p_m }[/math], представляющие собой последовательности над алфавитом [math]\displaystyle{ \Sigma }[/math] размера [math]\displaystyle{ \sigma }[/math], а также функция расстояния между строками d и порог k. Задача приближенного сравнения строк (approximate string matching, ASM) заключается в нахождении всех текстовых позиций, завершающих так называемое приблизительное вхождение P в T; иначе говоря, в вычислении множества [math]\displaystyle{ \{ j, \exist i, 1 \le i \le j, d(P, t_i ... t_j) \le k \} }[/math]. В последовательной версии задачи T, P и k уже заданы, при этом алгоритм может быть настроен для конкретного d.
Решения этой задачи заметно различаются в зависимости от используемой метрики расстояния d. Далее будет использоваться очень популярная метрика, называемая расстоянием Левенштейна или расстоянием редактирования и определяемая как минимальное количество операций вставки символа, удаления символа и замены одного символа на другой, необходимых для преобразования одной строки в другую. Также будет уделено внимание другим распространенным вариантам, таким как indel-расстояние, в котором допускаются только вставки и удаления и которое является двойственным к нахождению самой длинной общей подпоследовательности lcs (d(A, B) = |A| + |B| - 2 • lcs(A, B)), а также расстояние Хэмминга, в котором рассматриваются только замены.
Популярным обобщением всех вышеперечисленных вариантов является взвешенное расстояние редактирования, при котором операциям присваиваются положительные вещественные веса, а расстояние является минимальной суммой весов последовательности операций, преобразующих одну строку в другую. Вес операции удаления символа c обозначим за [math]\displaystyle{ w(c \to e) }[/math], вес операции вставки c – за [math]\displaystyle{ w( \to c) }[/math], вес операции замены c на [math]\displaystyle{ c' \ne c }[/math] – за [math]\displaystyle{ w(c \to c' }[/math]. Предполагается, что [math]\displaystyle{ w(c \to c) = 0 }[/math] и что выполняется неравенство треугольника, то есть [math]\displaystyle{ w(x \to y) + w(y \to z) \ge w(x \to z) }[/math] для любых [math]\displaystyle{ x, y, z \in \Sigma \cup \{ \epsilon \} }[/math]. Поскольку расстояние теперь может быть асимметричным, примем за d(A; B) стоимость преобразования A в B. Разумеется, любой результат, полученный для метрики взвешенного расстояния редактирования, применим к расстояниям редактирования, Хэмминга и indel-расстоянию (которые далее будут называться расстояниями редактирования с единичной стоимостью), однако другие редукции не являются тривиальными.
Рассматриваются сложность в наихудшем и в среднем случаях. Во втором варианте предполагается, что образец и текст генерируются случайным образом посредством равномерного и независимого выбора из [math]\displaystyle{ \Sigma }[/math]. Для простоты и практичности будем далее полагать m = o(n).
