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

Популярным обобщением всех вышеперечисленных вариантов является ''взвешенное расстояние редактирования'', при котором операциям присваиваются положительные вещественные веса, а расстояние является минимальной суммой весов последовательности операций, преобразующих одну строку в другую. Вес операции удаления символа c обозначим за <math>w(c \to e)</math>, вес операции вставки c – за <math>w( \to c)</math>, вес операции замены c на <math>c' \ne c</math> – за <math>w(c \to c'</math>. Предполагается, что <math>w(c \to c) = 0</math> и что выполняется неравенство треугольника, то есть <math>w(x \to y) + w(y \to z) \ge w(x \to z)</math> для любых <math>x, y, z \in \Sigma \cup \{ \epsilon \}</math>. Поскольку расстояние теперь может быть асимметричным, примем за d(A; B) стоимость преобразования A в B. Разумеется, любой результат, полученный для метрики взвешенного расстояния редактирования, применим к расстояниям редактирования, Хэмминга и indel-расстоянию (которые далее будут называться ''расстояниями редактирования с единичной стоимостью''), однако другие редукции не являются тривиальными.

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