Rešitev: Levenshteinova razdalja

Iz MaFiRaWiki

Naloga: Levenshteinova razdalja

 Levenshtein[u_,v_]:=Module[{L},
 ClearAll[L]; 
 L[i_,0]:=i;
 L[0,j_]:=j;
 L[i_,j_]:=L[i,j]=
 Min[{L[i-1,j-1]+If[ui==vj,0,1],L[i-1,j]+1,
 L[i,j-1]+1}];
 Return[Table[L[i,j],{i,0,Length[u]-1},{j,0,Length[v]}]]
 ]

Na primer, poiščimo Levenshteinovo razdaljo med besedama "miza" in "miška".

 u={"m","i","z","a"}
 v ={"m","i","š","k","a"}

Dobimo matriko, kjer nam število v zadnji vrstici in zadnjem stolpcu poda za koliko vstavljanj, brisanj ali zamenjav znakov se besedi razlikujeta.

 Levenshtein[u,v]//MatrixForm

vrne

 \begin{bmatrix}   0&1&2&3&4&5\\   1&0&1&2&3&4\\   2&1&0&1&2&3\\   3&2&1&1&2&3\\   4&3&2&2&2&2\\\end{bmatrix}
Osebna orodja