XProfan

Deutsch

p.specht

Der Jaro-Algorithmus ist ein Maß für gemeinsame Zeichen, die innerhalb von "nicht mehr als der halben Länge der längeren Zeichenkette" liegen, unter Berücksichtigung von Transpositionen (Verdrehungen). Winkler modifizierte diesen Algorithmus, um das Faktum zu berücksichtigen, dass Unterschiede am Anfang der Zeichenkette signifikanter sind als Unterschiede am Ende der Zeichenkette. Jaro und Jaro-Winkler eignen sich für den Vergleich kleinerer Zeichenketten wie Wörter und Namen.

Für weitere Stringähnlichkeitsvergleiche kennt man den Levenshtein-Algorithmus oder die Kölner Phonetik. Levenshtein zählt die Anzahl der Bearbeitungen (Einfügungen, Löschungen oder Substitutionen), die erforderlich sind, um eine Zeichenkette in die andere zu konvertieren.
Damerau-Levenshtein ist eine modifizierte Version, die Transpositionen auch als Einzelbearbeitung betrachtet. Obwohl die Ausgabe die ganzzahlige Anzahl der Bearbeitungen ist, kann diese standardisiert werden, um einen Ähnlichkeitswert durch eine Formel zu erhalten

In der Praxis ist es wichtig, eine Methode zu wählen, die der Art der Zeichenketten entspricht, die man vergleichen will. Manche Verfahre sind viel aufwändiger als etwa die Berechnung einer phonetischen Vorab-Kodierung. Von der Geschwindigkeit her ist die Reihenfolge: 1. Jaro, 2. Jaro-Winkler, 3. Levenshtein, 4. Damerau-Levenshtein, wobei zwischen schnellstem und langsamsten Algorithmus ein Faktor 2 bis 3 liegt..

Kompilieren Markieren Separieren

WindowTitle "Jaro-Winkler String-Ähnlichkeit"
'Q: https://rosettacode.org/wiki/Jaro_distance#Pascal
'Thema: https://en.wikipedia.org/wiki/Jaro%E2%80%93Winkler_distance
'Dissertation [Christen 2006]: Systemvergleich Jaro - Levenshtein
'https://users.cecs.anu.edu.au/~Peter.Christen/publications/tr-cs-06-02.pdf
'(D) Demo translation, 2018-10-28 by P.Specht, Vienna/EU
'Ohne jede Gewähr! No warranty whatsoever!
CLS:font 2
print format$("0.#######", JaroWinkler("DWAYNE","DUANE"))
print format$("0.#######", JaroWinkler("MARTHA","MARHTA"))
print format$("0.#######", JaroWinkler("DIXON","DICKSONX"))
print format$("0.#######", JaroWinkler("JELLYFISH","SMELLYFISH"))
' Solloutput:
' 0.822222
' 0.944444
' 0.766667
' 0.896296
waitinput
END

Proc JaroWinkler :parameters s1$,s2$

    declare l1&,l2&,match_distance&,matches&,i&,k&,trans&,gr&,kl&
    declare bs1&[255],bs2&[255]'max string length is here 255
    l1&=len(s1$):l2&=len(s2$)

    ifnot l1&:ifnot l2&:return 1:else:return 0:endif:endif

        match_distance&= if(l1&>l2&,l1&,l2&)\2-1
        '  matches&=0
        '  trans&=0

        Whileloop l1&:i&=&Loop

            gr&=i&-match_distance&
            kl&=i&+match_distance&

            whileloop if(1>gr&,1,gr&),if(kl&<l2&,kl&,l2&):k&=&Loop

                case bs2&[k&]:continue
                case mid$(s1$,i&,1)<>mid$(s2$,k&,1):continue
                bs1&[i&]=1:bs2&[k&]=1'1=true
                inc matches&:break

            endwhile

        endwhile

        casenot matches&:return 0
        k&=1

        whileloop l1&:i&=&Loop

            casenot bs1&[i&]:continue
            :whilenot bs2&[k&]:inc k&:endwhile
            case mid$(s1$,i&,1)<>mid$(s2$,k&,1):inc trans&
            inc k&

        endwhile

        trans&=trans&\2
        return ((matches&/l1&)+(matches&/l2&)+((matches&-trans&)/matches&))/3

    endproc