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

Популярным обобщением всех вышеперечисленных вариантов является взвешенное расстояние редактирования, при котором операциям присваиваются положительные вещественные веса, а расстояние является минимальной суммой весов последовательности операций, преобразующих одну строку в другую. Вес операции удаления символа 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-расстоянию (которые далее будут называться расстояниями редактирования с единичной стоимостью), однако другие редукции не являются тривиальными.