Felix Riesterer: Volltextsuche mit Tippfehlertoleranz

Liebe Mitlesende,

für mein Projekt möchte ich noch die Suchfunktion dahingehend verbessern, dass sie auch ähnliche Schreibweisen akzeptiert. Bisher musste man den exakten Wortlaut eingeben, damit das Gewünschte überhaupt gefunden werden konnte.

Nach welchen Suchbegriffen muss ich da ixquicken? "site search" oder "Volltextsuche" führen nicht zu Treffern, die Features wie similar_text() oder levenshtein() beinhalten.

Ich habe eine Liste mit den plain-text-Inhalten jeder URL, über die ich eine Liste von Strings "matchen" lassen möchte und frage mich, ob es da nicht schon etwas fertiges gibt.

Wer kann mir Hinweise geben?

Liebe Grüße,

Felix Riesterer.

--
"Wäre die EU ein Staat, der die Aufnahme in die EU beantragen würde, müsste der Antrag zurückgewiesen werden - aus Mangel an demokratischer Substanz." (Martin Schulz, Präsident des EU-Parlamentes)
  1. für mein Projekt möchte ich noch die Suchfunktion dahingehend verbessern, dass sie auch ähnliche Schreibweisen akzeptiert.

    Nach welchen Suchbegriffen muss ich da ixquicken?

    N-Gramm.

    1. Liebe(r) Wikipedia,

      N-Gramm.

      das erscheint mir kein praktischer, sondern eher ein theoretischer Hinweis zu sein. Wie ich schon schrieb, suche ich eine Lösung in Richtung Levenshtein-Distanz und eventuell Soundex-Mechanismus, um Ähnlichkeiten bei Wörtern zu erkennen. Mudguards Antwort war da schon eher in die Richtung, die ich denke.

      Diese N-Gramme-Sache geht deutlich in ihrer Gründlichkeit über das hinaus, was ich überhaupt zu implementieren imstande bin und was als Größenordnung für mein Projekt überhaupt sinnvoll lösbar ist. Wenn ich den Artikel verstanden habe, ist diese Lösung eher etwas, das Häufigkeitslisten benötigt, wofür ich schlicht keine Ressourcen habe, um diese irgendwo vernünftig zu speichern.

      Aber Danke für diesen Denkanstoß.

      Liebe Grüße,

      Felix Riesterer.

      --
      "Wäre die EU ein Staat, der die Aufnahme in die EU beantragen würde, müsste der Antrag zurückgewiesen werden - aus Mangel an demokratischer Substanz." (Martin Schulz, Präsident des EU-Parlamentes)
  2. Hi,

    für mein Projekt möchte ich noch die Suchfunktion dahingehend verbessern, dass sie auch ähnliche Schreibweisen akzeptiert.

    evtl. ein angepaßter Soundex (das Original ist für englisch optimiert).
    Bei soundex werden ähnlich klingende Buchstaben auf ein Zeichen abgebildet, z.B: b und p, d und t. Doppelte Buchstaben werden auf einen reduziert. Usw.

    Für deutsche Texte müßte man das halt anpassen, ä kann z.B. wie e behändelt werden. Und es bietet sich an, ggf. auch Buchstabengruppen zu betrachten, z.B. ph wie f (und wie v und w) behandeln, th wie t (und d) usw.

    Ich hab das schon mal gemacht, aber für meinen Arbeitgeber, darf daher nicht den kompletten Algorithmus rausrücken.

    Wobei zu beachten ist:

    Für den Suchbegriff ist das noch einfach, wenn größere Texte in DB-Spalten durchsucht werden sollen, ist das halt aufwändig. Die müssen halt entweder einmalig (bei Insert/update) in eine zweite Spalte konvertiert werden, oder jedesmal live in der Suche ...

    Aber das dürfte auf die meisten "Ähnlichkeitssuchen" zutreffen.

    cu,
    Andreas

    --
    Warum nennt sich Andreas hier MudGuard?
    O o ostern ...
    Fachfragen per Mail sind frech, werden ignoriert. Das Forum existiert.
    1. @@MudGuard:

      nuqneH

      Bei soundex werden ähnlich klingende Buchstaben auf ein Zeichen abgebildet

      Damit erschlägt man aber keine Vertipper. Da wären auf der Tastatur nebeneinander liegende Buchstaben „ähnlich“.

      Qapla'

      --
      „Talente finden Lösungen, Genies entdecken Probleme.“ (Hans Krailsheimer)
      1. Lieber Gunnar Bittersmann,

        Damit erschlägt man aber keine Vertipper. Da wären auf der Tastatur nebeneinander liegende Buchstaben „ähnlich“.

        vielleicht ist genau dafür dann diese Levenshtein-Distanz brauchbar? Hast Du weiterführende Hinweise?

        Liebe Grüße,

        Felix Riesterer.

        --
        "Wäre die EU ein Staat, der die Aufnahme in die EU beantragen würde, müsste der Antrag zurückgewiesen werden - aus Mangel an demokratischer Substanz." (Martin Schulz, Präsident des EU-Parlamentes)
        1. Hallo

          Damit erschlägt man aber keine Vertipper. Da wären auf der Tastatur nebeneinander liegende Buchstaben „ähnlich“.

          vielleicht ist genau dafür dann diese Levenshtein-Distanz brauchbar? Hast Du weiterführende Hinweise?

          Wenn ich das richtig lese, nur bedingt. Es vergleicht ja nur zwei Zeichenketten und gibt an, wieviele Ersetzungen stattfinden müssen, um aus Zeichenkette 1 Zeichenkette 2 zu machen.

          Die Funktion berücksichtigt aber nicht, wie typische Fehleingaben aussehen. Vermutlich müssten verschiedene Funktionen kombiniert werden.

          1. Die von Gunnar angesprochene Venutzung bemachbarter Zasten. (???)
          2. Auslassng oder fälschliche Doppplung von Bucchsaben. (levenshtein)
          3. Richtige™ Rächtschraibfehler. (soundex)
          4. Unterschiedliche Schreibweisen z.B. wegen der Rechtschreibreform (bei Mudguard gefunden: aufwändig vs. aufwendig) (soundex)

          Wie schnell das bei größeren Texten unerwünscht langsam wird, vermag ich nicht einzuschätzen. Vom Aufwand, das zu zufriedenstellend zu implementieren …

          Tschö, Auge

          --
          Verschiedene Glocken läuteten in der Stadt, und jede von ihnen vertrat eine ganz persönliche Meinung darüber, wann es Mitternacht war.
          Terry Pratchett, "Wachen! Wachen!"
          ie:{ fl:| br:> va:) ls:[ fo:) rl:( ss:| de:> js:| zu:}
          Veranstaltungsdatenbank Vdb 0.3
          1. Liebes Auge,

            Vermutlich müssten verschiedene Funktionen kombiniert werden.

            1. Die von Gunnar angesprochene Venutzung bemachbarter Zasten. (???)
            2. Auslassng oder fälschliche Doppplung von Bucchsaben. (levenshtein)
            3. Richtige™ Rächtschraibfehler. (soundex)
            4. Unterschiedliche Schreibweisen z.B. wegen der Rechtschreibreform (bei Mudguard gefunden: aufwändig vs. aufwendig) (soundex)

            vielleicht sollte ich so vorgehen?

            1.) Jeder Datensatz wird wortweise phonetisch kodiert, aber anstelle von soundex vielleicht besser mit der Kölner Phonetik. Dieser Schritt geschieht nicht bei jeder Suche, sondern einmalig, wenn eine Seite gespeichert wurde.

            2.) Jeder Suchbegriff wird wie beim ersten Schritt phonetisch kodiert.

            3.) Die phonetischen Codes aller Seiten werden "wortweise" mit den ebenso phonetisch kodierten Suchbegriffen verglichen.

            4.) Jeder Treffer wird auf korrekte Schreibweise überprüft, Abweichungen mit levenshtein() gemessen und mittels eines Grenzwertes (wieviele Ersetzungen sind zulässig?) als Treffer anerkannt oder verworfen.

            Wie schnell das bei größeren Texten unerwünscht langsam wird, vermag ich nicht einzuschätzen. Vom Aufwand, das zu zufriedenstellend zu implementieren …

            Dazu müsste ich obigen Algorithmus erst einmal implementieren und dann sehen, wie er sich sowohl bei der Treffer-Ermittlung, als auch in der Performanz bewährt.

            Liebe Grüße,

            Felix Riesterer.

            --
            "Wäre die EU ein Staat, der die Aufnahme in die EU beantragen würde, müsste der Antrag zurückgewiesen werden - aus Mangel an demokratischer Substanz." (Martin Schulz, Präsident des EU-Parlamentes)
    2. Lieber MudGuard,

      vielen Dank für Deinen Hinweis! In den Kommentaren im PHP-Manual hatte ich Hinweise zu einer Verknüpfung von Soundex und Levenshtein-Distanz gelesen. Hast Du mit dieser zweiten Funktionalität schon Erfahrungen gemacht?

      Ich hab das schon mal gemacht, aber für meinen Arbeitgeber, darf daher nicht den kompletten Algorithmus rausrücken.

      Und etwas fertiges unter einer freien Lizenz kennst Du anscheinend auch nicht - schade. Ist levenshtein() in Deinem Algorithmus enthalten?

      Liebe Grüße,

      Felix Riesterer.

      --
      "Wäre die EU ein Staat, der die Aufnahme in die EU beantragen würde, müsste der Antrag zurückgewiesen werden - aus Mangel an demokratischer Substanz." (Martin Schulz, Präsident des EU-Parlamentes)
      1. Hi,

        Und etwas fertiges unter einer freien Lizenz kennst Du anscheinend auch nicht - schade. Ist levenshtein() in Deinem Algorithmus enthalten?

        Nein, Levenshtein ist nicht enthalten.

        Soundex an sich ist frei verfügbar. Eine freie an die deutsche Sprache angepaßte Version kenne ich nicht.

        Wir benutzen das, um vom User eingetippte Straßennamen auf real existierende Straßennamen zu matchen. Zuerst wird natürlich der direkte Vergleich gemacht, und nur wenn's keinen Treffer gibt, wird's per angepaßtem  Soundex probiert. Und das klappt bei den Straßennamen, die nicht korrekt sind, zu über 80 Prozent. Gut genug ...

        cu,
        Andreas

        --
        Warum nennt sich Andreas hier MudGuard?
        O o ostern ...
        Fachfragen per Mail sind frech, werden ignoriert. Das Forum existiert.
        1. Lieber MudGuard,

          Soundex an sich ist frei verfügbar. Eine freie an die deutsche Sprache angepaßte Version kenne ich nicht.

          kanntest Du das hier schon? Kölner Phonetik (Wikipedia / PHP-Userkommentar)

          Wir benutzen das, um vom User eingetippte Straßennamen auf real existierende Straßennamen zu matchen. Zuerst wird natürlich der direkte Vergleich gemacht, und nur wenn's keinen Treffer gibt, wird's per angepaßtem  Soundex probiert. Und das klappt bei den Straßennamen, die nicht korrekt sind, zu über 80 Prozent. Gut genug ...

          Das ist natürlich keine Volltextsuche. Ich hätte gerne etwas gehabt, das mir einen String s (oder ein array(s1, s2, s3) über einen größeren String ausprobiert und sagt "ja, da ist etwas, das passt". Mal sehen, ob ich mit der "Kölner Phonetik"-Geschichte weiterkomme.

          Aber vielen Dank für Deine Anregungen! Sie haben mich zu neuen Stichworten geführt!

          Liebe Grüße,

          Felix Riesterer.

          --
          "Wäre die EU ein Staat, der die Aufnahme in die EU beantragen würde, müsste der Antrag zurückgewiesen werden - aus Mangel an demokratischer Substanz." (Martin Schulz, Präsident des EU-Parlamentes)
  3. Nach welchen Suchbegriffen muss ich da ixquicken? "site search" oder "Volltextsuche" führen nicht zu Treffern, die Features wie similar_text() oder levenshtein() beinhalten.

    Ich habe eine Liste mit den plain-text-Inhalten jeder URL, über die ich eine Liste von Strings "matchen" lassen möchte und frage mich, ob es da nicht schon etwas fertiges gibt.

    Die Ähnlichkeit von zwei strings bringt doch nichts. Denn entweder müßte man man für jeden gespeicherten string eine Ähnlichkeit zu jedem möglichen Suchstring ablegen oder bei jeder Suche alle gespeicherten Strings mit dem Suchbegriff auf Ähnlichkeit prüfen.

    Oder hast Du letzteres vor?

    Wer kann mir Hinweise geben?

    Ich habe vor ein paar Jahren lange gesucht und nichts brauchbares gefunden, nicht brauchbar im Sinne von nicht praktikabel. (quasi für einen Chatbot) Bis auf "N-Gramm" habe ich mich in dem Zusammenhang auch mit allen Stichworten die hier gefallen sind beschäftigt.

    In der Hoffnung, keinen schlechten Hinweis zu geben, helfe ich vielleicht wenigstens eine nicht erfolgversprechende Suche früher abzubrechen.

    Ich bin mir aber insgesamt nicht sicher, ob ich deine Aufgabe richtig verstanden habe. Hast Du wirklich zwei Listen*, also keine Unbekannten? Zerlegst Du die Strings in Wörter und willst auch ähnliche Wörter matchen? Müssen Tippfehler berücksichtigt werden (wo Du doch Kontrolle über die strings hast)?

    Beschreibe doch noch mal was Du unter welchen Voraussetzungen vergleichen willst. Was soll inwiefern als ähnlich erkannt werden? Wortebene, Buchstabenebene oder beides?

    *Willst Du etwa bestimmte Wörter (Liste 2) in Texten automatisch auf passende Artikel (Liste 1) verlinken? Hört sich so an.