none
Suche nach ähnlichen Begriffen in Datensätzen (Meier, Maier, Mayr, etc.)

    Frage

  • Hallo zusammen,

    ich bin gerade dabei, eine Suche zu implementieren, welche ähnliche Begriffe berücksichtigt, also die verschiedenen Schreibweisen von Namen zum Beispiel oder ähnlich klingende Begriffe. Den T-SQL Befehl "SoundEx" würde ich hier gerne ausklammern, er ist mir zu "englisch" gestrickt.

    Nun habe ich mir zwei grundsätzliche Vorgehensweisen ausgedacht und würde gerne mal hören, wie ihr das so macht.

    Vorgehensweise 1

    Man könnte den Suchbegriff nehmen, die dazu passenden ähnlichen Wörter dazu packen und anschließend nach allen Begriffen in der Datenbank selektieren. Also der Anwender sucht nach "Meier" und das Programm sucht intern nach "Meier OR Mayer OR Mayer" etc. Das Problem hierbei ist, dass man vorher die ähnlichen Wörter erst mal finden muss. Was klingt zum Beispiel so ähnlich wie "Pferd"? Meinte der Anwender vielleicht "Herd" oder eher "Pferch"? Da bräuchte es ja so etwas wie einen Thesaurus oder eventuell einen Webdienst. Google funktioniert ja ähnlich.

    Vorgehensweise 2

    Zu jedem möglichen String in meiner Datenbank speichere ich einen Suchcode. Ich habe mich hier für die "Kölner Phonetik" entschieden, gemäß diesem schönen Blogbeitrag hier: Kölner Phonetik

    Nun kann ich meinen Suchbegriff in einen solchen Code umwandeln und mit den in der Datenbank gespeicherten Codes vergleichen und je nach gewünschtem Schärfegrad mehr oder weniger Ergebnisse finden. Das Problem hierbei ist, dass ich eine Tabelle brauche, welche zu jedem Datensatz und zu jedem sinnvollen zu durchsuchendem Feld einen Datensatz mit dem Suchcode speichert. Also wenn ich einen Datensatz des Typs "Kunde" habe und dieser die Felder "Name", "Vorname" und "Firmenbezeichnung" hat, so muss ich dazu drei Suchcodes speichern. Diese Suchcodes müssen auf irgendeine Art und Weise auch aktuell gehalten werden.

    Wie würde ihr das so angehen?

    Gruß, Karsten.

    Dienstag, 10. Oktober 2017 08:05

Alle Antworten

  • Hallo Karsten,

    was "ähnliche Begriffe" in dem Sinne sind nach dem sie gefunden werden sollen, muss für eine Einschätzung wie das Problem gelöst werden soll zunächst hinreichend definiert werden. Deine Ansätze scheinen, so wie ich sie verstehe, auf den Gleichklang der Wörter abzuzielen.

    Bei Berücksichtigung des Klangs, ist es wohl nicht unerheblich darüber nachzudenken, welche Regionen dies abdecken soll, neben verschiedenen Sprachen kommen mir da auch Dialekte in den Sinn. So mag Meier, wie Mayer klingen, wenn es ein Deutscher ausspricht, ein Franzose könnte dort zu einem sehr unterschiedlichen Klang kommen.

    In Wörterbüchern ist oft die Lautschrift hinterlegt, diese könnte für einen Vergleich des Klangs herangezogen werden. "Herd" ([heːɐ̯t]) und "Pferch" ([pfɛrç]) würde ich zum Beispiel nicht gleich/ähnlich klingend zu "Pferd" ([pfeːɐ̯t]) sehen, eher "fährt" ([fɛːɐ̯t]).

    Der erste Ansatz hat den Vorteil, dass Du selbst festlegen kannst was als ähnlich betrachtet werden soll.

    Die zweite Vorgehensweise  hat den Vorzug das die Suchcodes berechnet werden können, evtl. mit irritierenden Ergebnis. Evtl. kann hierzu ein Netzwerk trainiert werden, um eine Gewichtung zu Erzeugen, welche die Ergebnisse verbessert.

    Für mich persönlich würde ich lieber selbst entscheiden ob bei Meier auch Mayer gefunden werden soll, vielleicht sollten alternative Schreibweisen nur als Option angeboten werden.


    - Gruß Florian

    Mittwoch, 11. Oktober 2017 08:38
  • Hallo Florian,

    es ist tatsächlich gar nicht so einfach zu entscheiden, was ein "ähnlicher" Begriff sein soll. In unserem Programm wird vor allem nach Namen von Personen und Bezeichnung von Firmen gesucht. Da macht das Einbeziehen von verschiedenen Schreibweise absolut Sinn, da man ja nie weiß, wie der gesuchte Begriff in der Datenbank abgelegt ist. Aber darüber hinaus müsste man eigentlich noch Tippfehler abfangen, da die Suchbegriffe ja eingetippt werden. Und diese Tippfehler sind klanglich gar nicht zu erfassen, da hilft auch kein Thesaurus weiter. Da kommt mir allerdings die Kölner Phonetik entgegen, da dieser Algorithmus sehr auf die Buchstaben eingeht. Zum Beispiel liefert das Wort "Pferd" den Code "1372". Das Wort "sferd" liefert "8372". Es sind also von 4 möglichen Stellen 3 übereinstimmende Stellen vorhanden. Ebenso "Pferf", das liefert den Code "1373" wo ebenso 3 Stellen übereinstimmen. Im Moment versuche ich mich an der Variante 2, auch wenn dies bedeutet, dass man einen Suchindex mit pflegen muss.

    Gruß, Karsten.

    Mittwoch, 11. Oktober 2017 08:53
  • Hallo Karsten,

    falls Du den SQL Server verwendest, dann sieh Dir mal diese TechNet Wiki Artikel an: SQL Server: Implementierung eines N-Gram Suchindex (de-DE)


    Olaf Helper

    [ Blog] [ Xing] [ MVP]

    Mittwoch, 11. Oktober 2017 10:08
  • Hallo Karsten,

    falls Du den SQL Server verwendest, dann sieh Dir mal diese TechNet Wiki Artikel an: SQL Server: Implementierung eines N-Gram Suchindex (de-DE)


    Olaf Helper

    [ Blog] [ Xing] [ MVP]

    Ein sehr interessanter Artikel, vielen Dank dafür. Im Grunde genommen entspricht er der Vorgehensweise 2 von mir, also dem Umwandeln von Wörtern in einen Suchcode. Ich schaue mir das nochmal in Ruhe an, vor allem würden mich die Unterschiede im Suchergebnis interessieren - im Vergleich zur Kölner Phonetik.

    Gruß, Karsten.

    Mittwoch, 11. Oktober 2017 11:10
  • Ist im Einsatz mit ~20 Mio. internationalen Adressen und läuft wie geschmiert.

    Olaf Helper

    [ Blog] [ Xing] [ MVP]

    Mittwoch, 11. Oktober 2017 11:23
  • Hab grade ein interessantes Beispiel gefunden, an dem man den Suchcode mal testen könnte. Laut Kölner Phonetik kommt für "Heimer" und "Omar" genau der gleiche Suchcode raus, nämlich "067". Hier würde ich mich schwertun, das jemandem zu erklären...

    Gruß, Karsten.

    Mittwoch, 11. Oktober 2017 12:00
  • Ist im Einsatz mit ~20 Mio. internationalen Adressen und läuft wie geschmiert.

    Olaf Helper

    [ Blog] [ Xing] [ MVP]

    Saubere Sache. Was kommen denn da für Werte zusammen, bezüglich Größe der Indextabelle zum Beispiel oder der Laufzeit?

    Gruß, Karsten.

    Mittwoch, 11. Oktober 2017 13:39
  • Die Größenberechnung der Indextabelle steht im Artikel und Laufzeit hängt natürlich etwas von der Maschine ab; in meinem konkreten Fall mit warmen Cache lagen die Suchen bei ~700 ms, hängt aber auch stark von der Länge der Suchbegriffe ab.

    Olaf Helper

    [ Blog] [ Xing] [ MVP]

    Mittwoch, 11. Oktober 2017 16:25