Problem znajdowania odległości redakcyjnej dwóch słów polega na policzeniu w ilu najmniej operacjach można przejść z jednego słowa do drugiego. Elementarne operacje to: usunięcie znaku, dodanie znaku, zamiana jednego znaku na inny.
Warto zauważyć, a właściwie to będzie to niezbędne, że dodanie znaku do jednego słowa (w celu zbliżenia się do drugiego) jest równoważne z usunięciem odpowiedniego znaku z drugiego słowa. Więc teraz zamiast robić wszystkie operacje na pierwszym słowie by uzyskać drugie, będziemy wykonywać operacje na obu słowach jednocześnie by doprowadzić oba do pewnego innego słowa. W ten oto sprytny sposób pozbyliśmy się operacji dodawania znaku, co znacznie ułatwi nam działanie.
Przyjmijmy, że mamy dane dwa słowa A1 i A2 o długościach odpowiednio d1 i d2. Oznaczmy sobie przez A1[1..i] podsłowo złożone z pierwszych i liter słowa A1 (analogicznie z drugim słowem). W szczególności A1[1..d1] to całe słowo A1, a A1[1..0] to podsłowo puste.
Niech stan będzie określony przez parę liczb (i,j). Niech wartością funkcji stanu D(i,j) będzie odległość redakcyjna słów A1[1..i] i A2[1..j] (reszta znaków ze słów A1 i A2 nas chwilowo nie obchodzi).
Przejdźmy obecnie :-) do zdefiniowania rekurencyjnej zależności między
stanami. Przyjmijmy, że chcemy obliczyć D(i,j) (czyli odległość
między A1[1..i] i A2[1..j]). Gdy A1[i]=A2[j]
(ostatnie znaki podsłów są równe) to odległość redakcyjna między
resztami tych podsłów (czyli bez ostatniego znaku, tzn. między
A1[1..i-1] i A2[1..j-1]) jest taka sama co odległość
między całymi tymi podsłowami (tzn. A1[1..i] i A2[1..j]).
Zatem żeby obliczyć wartość funkcji
dla stanu (i,j) musimy skorzystać ze stanu (i-1,j-1),
a konkretnie D(i,j)=D(i-1,j-1).
Gdy znaki A1[i] i A2[j] są różne to sytuacja się
nieco komplikuje. Teraz musimy wybrać najlepszą z trzech możliwości:
zamienić ostatnią literę jednego podsłowa na ostatnią drugiego
i zbadać odległość między resztami tych podsłów
(tzn. A1[1..i-1] i A2[1..j-1]); usunąć ostatnią
literę z pierwszego podsłowa i zbadać odległość między
resztą tego podsłowa (A1[1..i-1]) a całym drugim podsłowem
(A2[1..j]); usunąć literkę z drugiego podsłowa i postąpić
analogicznie. Oczywiście cokolwiek zrobimy w takiej sytuacji,
kosztuje nas to wykonanie pewnej elementarnej operacji,
zatem musimy dodać 1 do odległości znalezionej między
odpowiednimi podsłowami (wymienionymi w poprzednim zdaniu).
Zatem podsumowując:
No to jeszcze brakuje nam stanów początkowych. Będą to (i,0)
(i=0..d1) oraz (0,j) (j=0..d2). Oczywiście D(i,0)=i -
odległość słowa długości i od słowa pustego jest
równa i, bo jedyną sensowną rzeczą, którą możemy zrobić to usunąć
tych i literek. W szczególności D(0,0)=0.
Na dobrą sprawę to można by zadowolić się jedynie stanem początkowym
(0,0), a pozostałe stany podane wyżej wyliczyć
"algorytmem właściwym". W praktyce jednak dodaje to nam jedynie
niepotrzebną pracę. Np. żeby obliczyć D(i,0) musimy
najpierw stwierdzić, że nie istnieje znak A2[0];
później musielibyśmy skorzystać ze stanów (i-1,0),
(i,-1), (i-1,-1), a te dwa ostatnie nie istnieją.
W takim przypadku należałoby do programu dodać kilka instrukcji
warunkowych, które zabezpieczą nas przed "skorzystaniem"
z nieistniejącej wartości. A tego da się uniknąć jeżeli rozszerzy
się przestrzeń stanów początkowych, tak jak to podałem na początku.
Jak nietrudno się domyślić wynik, czyli odległość redakcyjna między całymi słowami A1 i A2, jest równy D(d1,d2).
Każdemu stanowi (i,j) odpowiada element w tablicy D[i,j], który jest równy D(i,j). Teraz przy założeniu, że mamy wypełnione pewne komórki tablicy (odpowiadające stanom początkowym) możemy wypełnić pozostałe komórki. Musimy to jednak robić w odpowiedniej kolejności. Jest to bardzo ważne, bo żeby wypełnić komórkę D[i,j] musimy znać np. D[i-1,j-1]. Kolejność jest określona (choć nie koniecznie jednoznacznie) przez rekurencyjne zależności między stanami. W tym przypadku możemy sobie pozwolić na wypełnianie tablicy wiersz po wierszu od lewej do prawej.
Opis teoretyczny skomplikowany, ale sam kod banalny - co widać na załączonym obrazku:
{A1 - slowo dlugosci d1
A2 - slowo dlugosci d2}
{wpisywanie stanow poczatkowych}
for i:=0 to d1 do
D[i,0]:=i;
for j:=0 to d2 do
D[0,j]:=j;
{algorytm wlasciwy}
for i:=1 to d1 do
for j:=1 to d2 do
if A1[i]=A2[j] then
D[i,j]:=D[i-1,j-1]
else
D[i,j]:=min(D[i-1,j]+1,D[i-1,j-1]+1,D[i,j-1]+1);
{wynik jest w D[d1,d2]}
Wadą tego rozwiązania jest duża złożoność pamięciowa. Ale można zauważyć, że wypełniając jeden wiersz korzystamy jedynie z poprzednich wartości w tym samym wierszu oraz z poprzedniego wiersza. Zatem można ograniczyć się z tablicy dwuwymiarowej do dwóch tablic jednowymiarowych - ogromna oszczędność.
{wpisywanie stanow poczatkowych, ale nie wszystkich}
for j:=0 to d2 do
D0[j]:=j;
for i:=1 to d1 do
begin
D1[0]:=i; {wpisanie stanu poczatkowego dla wiersza i}
for j:=1 to d2 do
{wypelnianie wiersza}
if A1[i]=A2[j] then
D1[j]:=D0[j-1]
else
D1[j]:=min(D0[j]+1,D0[j-1]+1,D1[j-1]+1);
{D0 - wiersz poprzedni}
D1 - wiersz aktualny (i-ty)}
for j:=1 to d2 do
{przepisanie jednej tablicy do drugiej;
wiersz i-ty staje sie poprzednim}
D0[j]:=D1[j];
end;
{wynik jest w D1[d2]}
Właściwie to nasz algorytm wypełnia d1*d2 komórek pamięci, każdą w czasie stałym. Stąd złożoność algorytmu jest O(d1*d2), co sprawia, że jest algorytmem wielomianowym. A zatem problem należy do klasy P.