Изменения

В основу алгоритма положена идея динамического программирования по префиксу. будем хранить матрицу <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> соответственно. Будем редактировать элементы матрицы по формуле:

В оригинальной задаче <tex>deleteCost = insertCost = 1;</tex> <tex>replaceCost = \begin{cases}1, & S[i] \neq T[j], \\ 0, & S[i] = T[j]; \end{cases}</tex> <tex>transpositionCost = \begin{cases}1, & S[i] = T[j - 1] \wedge S[i - 1] = T[j], \\ \infty, & \textnormal{иначе. }\end{cases}</tex> Псевдокод алгоритма: '''int''' DamerauLevenshteinDistance('''char''' S[1..m], '''char''' T[1..n])''' ''// Обработка крайних случаев'' '''if''' (S == "") '''then''' '''if''' (T == "") '''then''' '''return''' 0 '''else''' '''return''' n '''else''' '''if''' (T == "") '''then''' '''return''' m '''declare''' '''int''' dD[0..m+ 1, 0..n+ 1] ''// Динамика'' '''declare''' '''int''' i, j, costINF = m + n ''// Большая константа'' ''// База динамикииндукции'' D[0, 0] = INF;

dD[i+ 1, 1] = i D[i + 1, 0] = iINF '''for''' j '''from''' 1 0 '''to''' тn D[1, j + 1] = j dD[0, j+ 1] = INF '''declare''' sd ''//Отсортированный алфавит (все символы из S и T)'' ''//для каждого элемента C алфавита задано значение sd[C]'' '''foreach''' ('''char''' Letter '''in''' (S + T)) '''if''' Letter не содержится в sd добавить Letter в sd sd[Letter] = j0

'''declare''' '''int''' DB = 0 '''for''' j '''from''' 1 '''to''' n ''// Стоимость замены'declare''' '''ifint''' Si1 = sd[i] == Ttarget[j- 1] ] '''thendeclare''' costChange = 0 '''elseint''' costChange j1 = 1DB '''if''' Ssource[i- 1] == Ttarget[j - 1] и S'''then''' D[i - + 1, j + 1] = TD[i, j] '''then''' costTransposition DB = 1j '''else''' costTransposition = inf ''// значение константы inf очень велико'' ''// costTransposition = inf, то использовать'' ''// транспозицию заведомо невыгодно'' d D[i+ 1, j+ 1] = minimum( dD[i-1, j ] , D[i + 1, ''// удаление'' dj], D[i , j-+ 1] ) + 1, ''// вставка'' d D[i-+ 1, j-+ 1] = minimum(D[i + costChange ''// замена'' d1, j + 1], D[i1, j1] + (i-2, i1 - 1) + 1 + (j-2j1 - 1)) sd[S[i - 1] + costTransposition ''// транспозиция'' )] = i '''return''' dD[m+ 1, n+ 1]