Levenshtein-Distanz (Stringvergleich)

[p. specht]

Unscharfe String-Vergleiche
=====================

Es ist nicht ganz einfach, Eingaben mit Tippfehlern vom Computer trotzdem erkennen zu lassen. Der Levenshtein-Algorithmus erlaubt zumindest, einfache Preller bzw. Auslassungen zu erkennen. Etwas besser ist bei Datenbanken die SOUNDEX-Funktion, die allerdings meist für Englisch optimiert ist.

Das Gelbe vom Ei ist der Original-Levenshtein jedenfalls noch nicht. Es fehlt z.B. eine Änderung der Kostenbewertung (Variable cost&) in Abhängigkeit von möglichen Hörfehlern (y,ü,i,j ; sh sch ; t d ; p b; k g; h _ ), und vieles anderes mehr. Hier mal eine Basis zum rumspielen:

'### Alpha Version Code für Paule´s PC Forum ###
'### P. Specht  Nov.2010;  XProfan 11a Interpreter ###
WindowTitle "Levenshtein-Distanz (Stringvergleich)"
Cls @rgb(200,200,100)

proc LD  ' Compute Levenshtein-Distance
parameters s$,t$
s$=lower$(s$):var m&=len(s$)
t$=lower$(t$):var n&=len(t$)
declare d&[m&,n&],i&,j&,cost&,mi&,c&
case m& = 0 : return n&
case n& = 0 : return m&
i&=0 : while i&<=m& : d&[i&,0]=i& : inc i& : endwhile
j&=0 : while j&<=n& : d&[0,j&]=j& : inc j& : endwhile
i&=1
WHILE i&<=m&
    j&=1
    While j&<=n&
      cost&=1
      case Mid$(s$,i&,1)=Mid$(t$,j&,1):cost& = 0
        mi&=d&[i&-1,j&]+1
        c&=d&[i&,j&-1]+1
        case c&<mi& : mi&=c&
        c&=d&[i&-1,j&-1]+cost&
        case c&<mi& : mi&=c&
      d&[i&,j&]=mi&
   inc j&
   EndWhile
inc i&    
ENDWHILE
return d&[m&,n&]
Endproc

' Input Loop
declare str1$,str2$
While 1
Locate 10,10 : print "String1  =                                   ";
Locate 12,10 : print "String2  =                                   ";
Locate 14,10 : print "Ergebnis =                                   ";
Locate 10,21 : input str1$ : case str1$="" : End
Locate 12,21 : input str2$
Locate 14,21 : Print LD(str1$,str2$)
WaitInput
EndWhile
END