Изменения
Нет описания правки
где <tex>\rm{d}(S_1,S_2)</tex> — расстояние Левенштейна между строками <tex>S_1</tex> и <tex>S_2</tex>, а |S| - длина строки S.
== Формула ==
вернуть D(M, N)
</code>
== Редакционное предписание ==
''Редакционным предписанием'' называется последовательность действий, необходимых для получения из первой строки второй кратчайшим образом. Обычно действия обозначаются так: '''D''' (англ. delete) — удалить, '''I''' (англ. insert) — вставить, '''R''' (англ. replace) — заменить, '''M''' (англ. match) — совпадение.
Например, для 2-х строк «hell123» и «hello214» можно построить следующую таблицу преобразований:
{| class="wikitable" border = "1"
!'''M''' ||'''M''' ||'''M''' ||'''M''' ||'''R''' ||'''M''' ||'''R''' ||'''I'''
|-
|'''h''' ||'''e''' ||'''l''' ||'''l''' ||'''1''' ||'''2''' ||'''3''' ||
|-
|'''h''' ||'''e''' ||'''l''' ||'''l''' ||'''o''' ||'''2''' ||'''1''' ||'''4'''
|}
== Код получения редакционного предписания ==
В строке '''S''' содержится последовательность действий, необходимых для получения из первой строки второй кратчайшим образом.
readln(s1);
readln(s2);
n := length(s1);
m := length(s2);
for i := 1 to n do d[0, i] := i;
for i := 1 to m do d[i, 0] := i;
for i := 1 to n do for j := 1 to m do
if s1[i] = s2[j] then
begin
d[i, j] := d[i - 1, j - 1];
p[i, j].x := i - 1;
p[i, j].y := j - 1;
end else
begin
if (d[i - 1, j] <= d[i, j - 1]) and (d[i - 1, j] <= d[i - 1, j - 1]) then
begin
d[i, j] := d[i - 1, j] +1;
p[i, j].x := i - 1;
p[i, j].y := j;
end;
if (d[i, j - 1] <= d[i - 1, j] )and (d[i, j - 1] <= d[i - 1, j - 1]) then
begin
d[i, j] := d[i, j - 1] +1;
p[i, j].x := i;
p[i, j].y := j - 1;
end;
if (d[i - 1, j - 1] <= d[i, j - 1]) and (d[i - 1, j - 1] <= d[i - 1, j]) then
begin
d[i, j] := d[i - 1, j - 1] + 1;
p[i, j].x := i - 1;
p[i, j].y := j - 1;
end;
end;
x := n;
y := m;
while (x > 0) and (y > 0) do
begin
if p[x, y].x - x = 0 then s := 'D' + s else
if p[x, y].y - y = 0 then s := 'I' + s else
if s1[x] = s2[y] then s := 'M' + s else s := 'R' + s;
x := p[x, y].x;
y := p[x, y].y;
end;
writeln(s);
== Разные цены операций ==
Цены операций могут зависеть от вида операции (вставка, удаление, замена) и/или от участвующих в ней символов, отражая разную вероятность разных ошибок при вводе текста, и т. п. В общем случае:
* w(a, b) — цена замены символа a на символ b
* w(ε, b) — цена вставки символа b
* w(a, ε) — цена удаления символа a
Для решения задачи о редакционном расстоянии, необходимо найти последовательность замен, минимизирующую суммарную цену. Расстояние Левенштейна является частным случаем этой задачи при
* w(a, а) = 0
* w(a, b) = 1 при a≠b
* w(ε, b) = 1
* w(a, ε) = 1
Как частный случай, так и задачу для произвольных w, решает алгоритм Вагнера — Фишера, приведённый ниже. Здесь и ниже мы считаем, что все w неотрицательны, и действует правило треугольника: если две последовательные операции можно заменить одной, это не ухудшает общую цену (например, заменить символ x на y, а потом с y на z не лучше, чем сразу x на z).
== Литература ==
*http://en.wikipedia.org
*Романовский И.В. "Дискретный анализ"
