Задача 16.
Пусть x=(a1,a2,...,am) и y=(b1,b2,...,bn) - две заданных строки символов.
Определим d(x,y) как минимальное число вставок, удалений и замен символа, которое необходимо для преобразования x в y.
Например: d(ptslddf,tsgldds)=3
Для заданных x и y найти d(x,y).
|
Решение задачи 16.
Для x=a(1)...a(m) и y=b(1)...b(n), a(i) и b(i) символы, 1<=i<=m, 1<=j<=n, d(x,y) можно вычислить, применяя метод динамического программирования.
Определим массив d[0..m,0..n], элементы которого
d[i,j] = d(a(1)...a(i), b(1)...b(j)), 0<=i<=m,0<=j<=n,
так что
d[0,j]=j;
d[i,0]=i;
очевидным образом получаем
d[i,j]=min{d[i-1,j]+1,d[i,j-1]+1,d[i-1,j-1]+Pij}
где Pij=1 если a(i)<>b(i) и Pij=0 иначе (в правой части приведенного выше выражения первому элементу в min соответствует операция удаления из строки a(1)...a(i-1)a(i) последнего элемента a(i), после чего за d[i-1,j] операцию строка a(1)...a(i-1) преобразуется в строку b(1)...b(j), второму элементу - операция вставки символа b(j) в конец строки b(1)...b(j-1), полученной за d[i,j-1] операцию из строки a(1)...a(i), а третьему - контекстная замена ai на bj, замена осуществляется в случае ai<>bj (тогда Pij=1) и не происходит при совпадении ai и bj).
Получаем необходимое d(x,y)=d[m,n].
Алгоритм может быть записан так:
for i:=1 to m do
d[i,0]:=i;
for j:=1 to n do d[0,j]:=j;
for i:=1 to m do for j:=1 to n do
d[i,j]=min{d[i-1,j]+1,d[i,j-1]+1,d[i-1,j-1]+Pij};
|
