74
правки
Изменения
Нет описания правки
В основу алгоритма положена идея динамического программирования по префиксу. Будем хранить матрицу <tex>D[0..m + 1][0..n + 1]</tex>, где <tex>D[i + 1][j + 1]</tex> {{---}} расстояние Дамерау {{---}} Левенштейна между префиксами строк <tex>S</tex> и <tex>T</tex>, длины префиксов {{---}} <tex>i</tex> и <tex>j</tex> соответственно.
Будем хранить дополнительную информациюзаполнять матрицу следующим образом, используя рекуррентное соотношение, описанное ниже: '''for''' i '''from''' 0 '''to''' m '''for''' j '''from''' 0 '''to''' n вычислить D(i, j); '''return''' D(m, n); Для учёта транспозиции потребуется хранение следующей информации. Инвариант:
<tex>sd[x]</tex> {{---}} индекс последнего вхождения <tex>x</tex> в <tex>S</tex>
<tex>dbDB</tex> {{---}} на i-й итерации внешнего цикла индекс последнего символа <tex>T: T[dbDB] = S[i]</tex> Тогда если на очередной итерации внутреннего цикла положить: <tex>i1 = sd[T[j]],\ j1 = DB</tex>, то <tex>D(i, j) = min(A, D(i1, j1) + (i - i1 - 1) + 1 + (j - j1 - 1))</tex>, где <tex>A = \left\{\begin{array}{llcl}0&&;&i = 0,\ j = 0\\i&&;&j = 0,\ i > 0\\j&&;&i = 0,\ j > 0\\D(i - 1, j - 1)&&;&S[i] = T[j]\\\rm{min}(\\&D(i, j - 1) + insertCost\\&D(i - 1, j) + deleteCost&;&j > 0,\ i > 0,\ S[i]\ne T[j]\\&D(i - 1, j - 1) + replaceCost\\)\end{array}\right.</tex>
Псевдокод алгоритма:
