XProfan

Deutsch

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 erst mal eine Basis-Proc zum rumspielen:

Kompilieren Markieren Separieren

'### P. Specht  Nov. 2010;  XProfan 11a Interpreter ###
WindowTitle "Levenshtein-Distanz (Stringvergleich)"
Cls @rgb(200,200,100)
print " EINGABETEIL SELBST GESTALTEN!"
waitinput
END

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

XProfan 11
Computer: Gerät, daß es in Mikrosekunden erlaubt, 50.000 Fehler zu machen, zB 'daß' statt 'das'...

10.04.2021 ▲

Vollständiges Zitat

Absatzweise zitieren Zeilenweise zitieren

RudiB.

Unscharfe String-Vergleiche

Das hört sich fast wie die Heisenbergsche Unschärfe-Relation an.
Ist mir zu hoch....klingt jedoch sehr interessant.
Aber das ist ein Problem das nicht mal Google mit seinen mächtigen Maschinen so wirklich zu 100% umsetzen kann. Und die sind da ja nun wirklich gut....
Habe mich auch schon mit diesem Problem rumgeschlagen. Da ist vor allem mal, wenn Du einen Buchstaben zu viel oder Zuwenig im String/Wort hast, dann hast Du eigentlich schon verloren....da geht nur Annäherung und Wahrscheinlichkeit . Ist Schwierig......

XProfan X4
Xprofan X4
Rudolf Beske / München

Hardware: NB Intel I9 - 16GByte RAM

10.04.2021 ▲

Vollständiges Zitat

Absatzweise zitieren Zeilenweise zitieren

p.specht

Da könnte dir auch Michael Wodrichs Umsetzung der sog. "KÖLNER PHONETIK" helfen! Board-Suchbegriff: Kölner Phonetik Soundex
Gruss

P.S.: Google benutzt den MCPA-Algorithmus, samt adaptiven Verbesserungen.
Beschreibung (engl.) am 2021-04-14 noch hier: [...]