Последовательное приближенное сравнение строк

Ключевые слова и синонимы

Сравнение строк, допускающее ошибки или разность; неточное сравнение строк; полуглобальное или полулокальное сходство последовательностей

Постановка задачи

Пусть даны текстовая строка T = t1t 2.. tn и строка образца P = p1p2 : : : pm, представляющие собой последовательности над алфавитом S размера a, а также функция расстояния между строками d и порог k. Задача приближенного сравнения строк (approximate string matching, ASM) заключается в нахождении всех текстовых позиций, завершающих так называемое приблизительное вхождение P в T; иначе говоря, в вычислении множества fj; 9 i; 1 < i < j; d(P; t i : : : tj) < kg. В последовательной версии задачи T, P и k уже заданы, при этом алгоритм может быть настроен для конкретного d.

Решения этой задачи заметно различаются в зависимости от используемой метрики расстояния d. Далее будет использоваться очень популярная метрика, называемая расстоянием Левенштейна или расстоянием редактирования и определяемая как минимальное количество операций вставки символа, удаления символа и замены одного символа на другой, необходимых для преобразования одной строки в другую. Также будет уделено внимание другим распространенным вариантам, таким как indel-расстояние, в котором допускаются только вставки и удаления и которое является двойственным к нахождению самой длинной общей подпоследовательности lcs (d(A; B) = jAj + \B\ - 2 • lcs(A; B)), а также расстояние Хэмминга, в котором рассматриваются только замены.

Популярным обобщением всех вышеперечисленных вариантов является взвешенное расстояние редактирования, при котором операциям присваиваются положительные вещественные веса, а расстояние является минимальной суммой весов последовательности операций, преобразующих одну строку в другую. Вес операции удаления символа c обозначим за w(c ! e), вес операции вставки c – за w( -> c), вес операции замены c на c / с – за w(c !c 0). Предполагается, что w(c ! c) = 0 и что выполняется неравенство треугольника, то есть w(x ! y) + w(y ! z) > w(x ! z) для любых x; y; z 2 S U {e}. Поскольку расстояние теперь может быть асиммтеричным, примем за d(A; B) стоимость преобразования A в B. Разумеется, любой результат, полученный для метрики взверешнного расстояния редактирования, применим к расстояниям редактирования, Хэмминга и indel-расстоянию (которые далее будут называться расстояниями редактирования с единичной стоимостью), однако другие редукции не являются тривиальными.

Рассматриваются сложность в наихудшем и в среднем случаях. Во втором варианте предполагается, что образец и текст генерируются случайным образом посредством равномерного и независимого выбора из S. Для простоты и практичности будем далее полагать m = o(n).