Levenshtein+

Osoby w temacie będą wiedziały o co chodzi. ;)
Potrzebne będzie: tablica (kwadratowa o rozmiarze od 0 do maksymalnej długości
wzorca/słowa jakie zamierzacie porównywać). Pierwszy wiersz i kolumnę musicie
wypełnić kolejno liczbami od 1 do długości wzorca/słowa. W podanym poniżej
przykładzie n to długość wzorca, m długość słowa. Wartość w komórce [m,n]
tablicy jest naszą szukaną - jeżeli większa lub mniejsza od 2, to oba wyrazy są
podobne! Funkcja min jest wbudowana w Pascala - zwraca mniejszą wartość z dwóch
podanych. Nie zapomnijcie przed każdym użyciu funkcji wyzerować tablicę!

FUNCTION levenstein(wzor,slowo : wyraz):INTEGER;
VAR i,j,n,m : INTEGER; {zmienne pomocnicze}
BEGIN

n:=LENGTH(wzor);
m:=LENGTH(slowo);
for i:=0 TO n DO odleglosc[i,0]:=i;
for j:=0 TO m DO odleglosc[0,j]:=j;

FOR i:=1 TO n DO
BEGIN
FOR j:=1 TO m DO BEGIN
IF(slowo[j]=wzor[i]) THEN odleglosc[i,j]:=odleglosc[i-1,j-1] ELSE
IF(slowo[j-1]=wzor[i]) AND (slowo[j]=wzor[i-1]) THEN odleglosc[i,j]:=odleglosc[i-2,j-2]+1
ELSE
odleglosc[i,j]:=min(odleglosc[i-1,j-1]+1,min(odleglosc[i,j-1]+1,odleglosc[i-1,j]+1));
END;
END;

levenstein:=t[n,m];
END; { levenstein }

PS. Tylko nie kopiować słowo w słowo! Więcej

tutaj i

tutaj.
PS2. Podziękowania dla Błażeja za rozszerzenia algorytmu o czeski błąd (dodanie
jednego warunku).