Levenshtein-Algorithmus Stringvergleich

  • 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:

    HP255G7:Win10pro2.004,4*AMD Ryzen3200U@2.60GHz,6+2GB-RadeonVega/237GBSSD:intlDVDRW,3xUSB3 ext4TB-HDX,XProfanX3+Xasm/Xpse

    • Anzeige

    Hallo!

    Wenn du gerade an deiner Website arbeitest oder dein aktuelles Hosting überdenkst: Wir betreiben mit NetzLiving eine Hosting-Plattform, die speziell auf Performance, Sicherheit und einfache Verwaltung ausgelegt ist.

    • ✔️ Schnelle Ladezeiten (optimiert für WordPress, WoltLab & Co.)
    • ✔️ Deutsche Server & DSGVO-konform
    • ✔️ Persönlicher Support (kein 0815-Ticket-System)

    Mehr erfahren

  • Ein sehr guter Algorithmus in diesem Bereich, der vor allem mit deutschen Wörtern sehr gut funktioniert, ist die sogenannte "Kölner Phonetik".

    Kölner Phonetik ? Wikipedia

    ˙˙˙ɯnɹ ɥɔsןɐɟ sǝןןɐ ˙˙˙ɹnʇɐʇsɐʇ ǝnǝu ssıǝɥɔs

  • Hm, ok, aber wie errechne ich dann die Ähnlichkeit zweier Wörter, die ich in Zahlenkolonnen umgewandelt habe?

    XProfan-Semiprofi (XProfan X4a+XPIA+LemonEd)/PureBasic 6.00/RAD Studio 11 (Alexandria)/Perl 5.34.00/Python 3.10.0
    Ryzen 5800X/Gigabyte B550m DS3H/32GB RAM@3600MHz/Radeon HD7770 OC/Asus Xonar SE/46TB HDD+512GB Samsung 980 Pro+2TB Crucial SSD/28" Samsung 4k
    Synology DS920+ mit 42TB
    XBox Classic/360S/Series X/PS3 Super Slim 500GB/PS4 Pro (XBL-ID: jacdelad, PSN: jacdelad84)
    OnePlus 9 Pro (12GB/256GB)
    https://jacdelad.bplaced.net

  • commänder: Danke - Super Hinweis!

    @Jaq: A) Beziehst du Dich jetzt auf Levenshtein (Die Zahl die da rauskommt ist eine Art Verwandtschaftsmaß zwischen zwei Worten): Du setzt einfach einen Treshold level und prüfst das Ergebnis, ob diese zulässige Fehlergrenze überschritten ist oder nicht.

    @Alle: B) Wenns es um "Kölner Phonetik" geht: Meine Umsetzung ist noch immer nicht fertig, weil ich die Resultate erst an offiziellen Ergebnissen verifizieren möchte (man blamiert sich ja nicht sonderlich gerne).

    Sinn des Kölner Verfahrens ist es, ein Filter darzustellen, das die Eingabeinterpretation gewissermaßen schwerhörig macht. Da sich Vokale in unterschiedlichen Dialekten oft verändern, werden sie z.B. mit "0" kodiert und, wenn sie nicht am Anfang stehen, einfach weggelassen. Zischlaute wiederum landen in Klasse "3", etc etc.

    Achtung: Es sind keine Zahlen, die dabei rauskommen, weil die scheinbar aus Ziffern bestehenden Vergleichsmuster eine führende Null kennen (Wenn nämlich Vokale als erstes Zeichen stehen) - sämtliche Math-Packages würden führende Nullen klarerweise wegschneiden. Weiters haben Integer-Zahlen eine begrenzte Stellenzahl, der Kölner Algorithmus aber nicht, was allgemein als Vorteil gegenüber Soundex() ins Treffen geführt wird.

    Wenn man das Ergebnis aber doch unbedingt als Zahl speichern will (meine Überlegungen gingen auch zuerst in diese Richtung), könnte man führende Nullen eventuell als negatives Vorzeichen speichern und dann alles Modulo (höchste Integerzahl/2) nehmen (Vorsicht, Rechte Dritter!).
    Es bleibt eine Frage der zeitlichen Performance, ob man die Vergleichsdatenbank um eine Spalte "Klingt wie ..." erweitert und nach Aufrufhäufigkeit index-sortiert (das setzt halt zu Beginn u.U. eine Vorab-Berechnung voraus), oder ob man das ganze "fliegend" hält.

    Die Übereinstimmung der erzeugten Muster ist dabei das Kriterium (in Google kommt da z.B. die Meldung "Meinten Sie ....?"). Eine Fehlerschwelle gibts dabei nicht, die ist - optimiert für die Deutsche Sprache - in den Kölner Algorithmus gewissermaßen schon eingebaut.

    Ich hoffe, das klang jetzt nicht anmaßend ;)

    Gruss

    HP255G7:Win10pro2.004,4*AMD Ryzen3200U@2.60GHz,6+2GB-RadeonVega/237GBSSD:intlDVDRW,3xUSB3 ext4TB-HDX,XProfanX3+Xasm/Xpse

  • Ich bezog mich auf die Kölner Phonetik. Da kommt am Ende eine Zahlenschlange raus, die ich unmöglich mit "=" oder so vergleichen kann.

    XProfan-Semiprofi (XProfan X4a+XPIA+LemonEd)/PureBasic 6.00/RAD Studio 11 (Alexandria)/Perl 5.34.00/Python 3.10.0
    Ryzen 5800X/Gigabyte B550m DS3H/32GB RAM@3600MHz/Radeon HD7770 OC/Asus Xonar SE/46TB HDD+512GB Samsung 980 Pro+2TB Crucial SSD/28" Samsung 4k
    Synology DS920+ mit 42TB
    XBox Classic/360S/Series X/PS3 Super Slim 500GB/PS4 Pro (XBL-ID: jacdelad, PSN: jacdelad84)
    OnePlus 9 Pro (12GB/256GB)
    https://jacdelad.bplaced.net

  • Die Ziffern sind Gruppenzugehörigkeitsbezeichner für die einzelnen Laute (Phoneme) eines Wortes. Es entsteht eine Ziffernzeichen-Schlange ("String"). Das selbe machst du für die Einträge Deiner Datenbank, somit hast du einen Suchstring und Vergleichsstrings.
    Und die kann man mit "=" vergleichen, oder etwa nicht?

    HP255G7:Win10pro2.004,4*AMD Ryzen3200U@2.60GHz,6+2GB-RadeonVega/237GBSSD:intlDVDRW,3xUSB3 ext4TB-HDX,XProfanX3+Xasm/Xpse

  • Ja schon, aber wenn ein Wort eine Ziffer mehr hat, dann kann ich den String nicht so einfach vergleichen, aber sie sind sich ziemlich ähnlich.

    XProfan-Semiprofi (XProfan X4a+XPIA+LemonEd)/PureBasic 6.00/RAD Studio 11 (Alexandria)/Perl 5.34.00/Python 3.10.0
    Ryzen 5800X/Gigabyte B550m DS3H/32GB RAM@3600MHz/Radeon HD7770 OC/Asus Xonar SE/46TB HDD+512GB Samsung 980 Pro+2TB Crucial SSD/28" Samsung 4k
    Synology DS920+ mit 42TB
    XBox Classic/360S/Series X/PS3 Super Slim 500GB/PS4 Pro (XBL-ID: jacdelad, PSN: jacdelad84)
    OnePlus 9 Pro (12GB/256GB)
    https://jacdelad.bplaced.net

  • Jaq hat recht: Mit dem Original-Levenshtein kann man nur Tippfehler ausbügeln, während das Kölner Verfahren nur Hörfehler ausbügelt. Sucht man ein Verfahren, daß beides gleichzeitig kann, ist man in Deutsch mit dem PHONEM-Algorithmus gut bedient. PHONEM funktioniert so, daß vor einem Levenshtein-Vergleich Buchstabengruppen austauscht werden: ph wird f, p wird b, t wird d etc., also (fast) gemäß den Regeln, die auch dem Kölner Algorithmus zugrunde liegen.

    HP255G7:Win10pro2.004,4*AMD Ryzen3200U@2.60GHz,6+2GB-RadeonVega/237GBSSD:intlDVDRW,3xUSB3 ext4TB-HDX,XProfanX3+Xasm/Xpse

Jetzt mitmachen!

Sie haben noch kein Benutzerkonto auf unserer Seite? Registrieren Sie sich kostenlos und nehmen Sie an unserer Community teil!