Rešitev2: Levenshteinova razdalja

Iz MaFiRaWiki


Razdalja med nizoma s1 in s2 naj bo minimalno število operacij, ki jih potrebujemo, da spremenimo s1 v s2. Na voljo imamo naslednje operacije:

- spremeni črko,

- vstavi črko,

- zamenjaj črko.


Rekurzivna formula

Minimalno število operacij za pretvorbo niza s1 v s2 označimo z d(s1,s2).

Velja naslednja rekurzivna formula:

d("",s2) = |s2|
d(s1,"") = |s1|
d(s1+c1,s2+c2) = min(
  if(c1=c2, potem  d(s1,s2)  (*nič*), sicer  d(s1,s2)+1 (*zamenjaj*)),
  d(s1,s2+c2)+1,       (*briši*)
  d(s1+c1,s2)+1        (*dodaj*)
)

Rešitev (samo izpis razdalje)

ClearAll[Levenshtein]
Levenshtein["", ""] := 0
Levenshtein["", s2_String] := StringLength[s2]
Levenshtein[s1_String, ""] := StringLength[s1]

Levenshtein[s1_String, s2_String] := 
    Levenshtein[s1, s2] = First[Sort[{
          If[StringTake[s1, -1] == StringTake[s2, -1],
            Levenshtein[StringDrop[s1, -1], StringDrop[s2, -1]],
            Levenshtein[StringDrop[s1, -1], StringDrop[s2, -1]] + 1],
          Levenshtein[StringDrop[s1, -1], s2] + 1,
          Levenshtein[s1, StringDrop[s2, -1]] + 1
          }]]

Primer

In[6]:= Levenshtein["matematika","fizika"]
Out[6]= 7

Rešitev (izpis operacij)

ClearAll[Levenshtein]
Levenshtein["", ""] := {0, {}}
Levenshtein["", s2_String] := {StringLength[s2], Map[{"Dodaj", #} &, Characters[s2]]}
Levenshtein[s1_String, ""] := {StringLength[s1], Map[{"Brisi", #} &, Characters[s1]]}

Levenshtein[s1_String, s2_String] := 
    Levenshtein[s1, s2] = Module[{tmp},
      First[Sort[{
            If[StringTake[s1, -1] == StringTake[s2, -1],
              {First[tmp = Levenshtein[StringDrop[s1, -1], StringDrop[s2, -1]]], 
                 Append[Last[tmp], {"0", StringTake[s1, -1]}]},
              {First[tmp = Levenshtein[StringDrop[s1, -1], StringDrop[s2, -1]]] + 1, 
                 Append[Last[tmp], {"Zamenjaj", StringTake[s1, -1] -> StringTake[s2, -1]}]}
              ],
            {First[tmp = Levenshtein[StringDrop[s1, -1], s2]] + 1,
              Append[Last[tmp], {"Brisi", StringTake[s1, -1]}]},
            {First[tmp = Levenshtein[s1, StringDrop[s2, -1]]] + 1, Append[Last[tmp], {"Dodaj", StringTake[s2, -1]}]}
            }]]
      ]

Primer

In[12]:= Levenshtein["matematika","fizika"]
Out[12]= {7,{{Brisi,m},{Brisi,a},{Brisi,t},{Brisi,e},{Zamenjaj,m->f},{Zamenjaj,a->i},{Zamenjaj,t->z},
         {0,i},{0,k},{0,a}}}

Glej tudi

http://www.cs.unm.edu/~luger/ai-final/code/editdist.html

Osebna orodja