74
правки
Изменения
м
'''if''' (T == "") '''then''' '''return''' 0 '''else''' '''return''' n
'''return''' m
D[i + 1, 1] = i D[i + 1, 0] = INF
D[1, j + 1] = j D[0, j + 1] = INF '''declare''' sd ''//Отсортированный алфавит (все символы из [0..количество различных символов в S и T)''] {{---}} отсортированный алфавит ''//для каждого элемента C алфавита задано значение sd[C]''
'''if''' Letter не содержится в sd добавить Letter в sd sd[Letter] = 0
'''declare''' '''int''' DB = 0 '''for''' j '''from''' 1 '''to''' n '''declare''' '''int''' i1 = sd[target[j - 1]] '''declare''' '''int''' j1 = DB '''if''' source[i - 1] == target[j - 1] '''then''' D[i + 1, j + 1] = D[i, j] DB = j '''else''' D[i + 1, j + 1] = minimum(D[i, j], D[i + 1, j], D[i, j + 1]) + 1 D[i + 1, j + 1] = minimum(D[i + 1, j + 1], D[i1, j1] + (i - i1 - 1) + 1 + (j - j1 - 1)) sd[S[i - 1]] = i
→Алгоритм
Псевдокод алгоритма:
'''int''' DamerauLevenshteinDistance('''char''' S[1..m], '''char''' T[1..n])'''
''// Обработка крайних случаев''
'''if''' (S == "") '''then'''
'''else''' '''if''' (T == "") '''then'''
'''declare''' '''int''' D[0..m + 1, 0..n + 1] ''// Динамика''
'''declare''' '''int''' INF = m + n ''// Большая константа''
''// База индукции''
D[0, 0] = INF;
'''for''' i '''from''' 0 '''to''' m
'''for''' j '''from''' 0 '''to''' n
'''foreach''' ('''char''' Letter '''in''' (S + T))
'''for''' i '''from''' 1 '''to''' m
'''return''' D[m + 1, n + 1]
