mixmastertobsi: Levenshtein Distance Alternative

Hallo,

für unsere Fehlertolerante Suche im Webshop nutzen wir die Levenshtein Disance. Nun wollen wir auf MySQL 5.7 umstellen, doch leider lässt sich hier die Levenshtein Distance nicht mehr nutzen.

Da wir die Levenshtein Distance schon einige Jahr nutzen, meine Frage an Euch, ob es gute Alternativen dazu gibt?

https://rosettacode.org/wiki/Levenshtein_distance

  1. Lieber mixmastertobsi,

    die Levenshtein Distance kenne ich bisher nur von PHP.

    auf MySQL 5.7 umstellen, doch leider lässt sich hier die Levenshtein Distance nicht mehr nutzen.

    Und warum nicht? Warum schweigst Du Dich hier aus?

    Da wir die Levenshtein Distance schon einige Jahr nutzen,

    Wie macht ihr das bisher? Erzähl doch mal!

    meine Frage an Euch, ob es gute Alternativen dazu gibt?

    Ich kenne keine. Aber hier finde ich spontan Hinweise, wie man das vielleicht doch in MySQL (wieder) hinbekommt:

    Erzähl doch mal, ob und warum es wirklich nicht mehr möglich sein soll mit MySQL 5.7 eine solche Funktion zu nutzen!

    Liebe Grüße,

    Felix Riesterer.

    1. weil man die nicht mehr compelieren kann.

      1. Hallo,

        weil man die nicht mehr compelieren kann.

        Auf drei Fragen und zwei Aufforderungen, mehr zu erzählen, nur mit einem Halbsatz zu antworten, ist ziemlich frech. Bist du sicher, dass du hier richtig bist?

        Gruß
        Kalk

        1. Hallo,

          also ich versuche es mal etwas detaillierter und hoffe, ich bekomme dann auch eine detaillierte Antwort.

          Lt. meinem Admin greift diese Levensthein Datei auf mysql-lib 18 zurück. Bei Ubunutu 16.04 mit MariaDB 10.1 gibt es allerdings mysql-lib 18 nicht mehr, sondern nur nur lib20 und damit lässt sich die Levensthein-Erweiterung nicht mehr einbinden.

          Ich habe nun die Funktion von folgendem Link verwendet und diese funktioniert auch, allerdings wesentlich langsamer, als wie es davor war.

          https://stackoverflow.com/questions/13909885/how-to-add-levenshtein-function-in-mysql

  2. Ich würde behaupten, dass eine fehlertolerante Suche per Levenshtein-Distanz einer SQL DB nicht gut tut. Eine Indizierung ist dann nicht wirklich effizient. Man kann natürlich einen Index auf die Suchspalte legen, aber SQL muss dann immer noch einen Full Index Scan machen.

    Es gibt im Netz Vorschläge, die Levenshtein-Distanzfunktion als Stored Procedure zu implementieren; ich weiß allerdings nicht, wie effizient der Procedure-Interpreter (oder -Compiler?) von MySQL ist. Bei vielen 1000 Sätzen, die zu durchsuchen sind, kann ich mir vorstellen, dass das langsam wird.

    Du brauchst eine Methode, die einfacher über den Index nutzbar ist - ich hatte dazu Trigramme im Kopf, finde spontan aber nichts dazu.

    Rolf

    1. Hello,

      eine ausführliche Diskussion dazu müss schon im Archiv sein, soweit ich mich erinnere.

      Liebe Grüße
      Tom S.

      --
      Es gibt nichts Gutes, außer man tut es
      Andersdenkende waren noch nie beliebt, aber meistens diejenigen, die die Freiheit vorangebracht haben.
  3. Hello,

    gerstern Abend hat die Suche leider 0 Treffer ergeben, was ich gar nicht glauben wollte, weil ich mir sicher war, dass das hier schon Thema war.

    Und siehe da: heute liefert die Suche nach "soundex" wieder Treffer.

    Zu beachten ist die Sprache des Webshops, bzw. seiner Produkte. Aund außerdem sollte man bereits beim Anlegen eines Datensatzes einen "normalisierten Wert" in einer Extraspalte ablegen, damit nicht erst beim späteren Vergleich alle Referenzwerte durchgerechnet werden müssen.

    Liebe Grüße
    Tom S.

    --
    Es gibt nichts Gutes, außer man tut es
    Andersdenkende waren noch nie beliebt, aber meistens diejenigen, die die Freiheit vorangebracht haben.
    1. Jau, sowas hatte ich mir vorgestellt. Ob man nun Verfeinerungen einbaut, die bestimmte Buchstabenähnlichkeiten ausgleichen, muss man gucken. Trivial wird das sicher nicht sein.

      Rolf

    2. Hallo TS,

      gerstern Abend hat die Suche leider 0 Treffer ergeben, was ich gar nicht glauben wollte, weil ich mir sicher war, dass das hier schon Thema war.

      Und siehe da: heute liefert die Suche nach "soundex" wieder Treffer.

      Ich kann mir keinen Umstand vorstellen, der das von dir beschriebene Verhalten erklären würde. Bist du sicher, dass du dich gestern nicht vertippt hast oder so?

      LG,
      CK

      1. Hello,

        Ich kann mir keinen Umstand vorstellen, der das von dir beschriebene Verhalten erklären würde. Bist du sicher, dass du dich gestern nicht vertippt hast oder so?

        Ziemlich sicher. Ich habe es mehrmals versucht. Das kam mir so vor, als wäre die Suche gar nicht durchgeführt worden. Es kam aber die Antwort, dass die Suche 0 Treffer ergeben hätte.

        Liebe Grüße
        Tom S.

        --
        Es gibt nichts Gutes, außer man tut es
        Andersdenkende waren noch nie beliebt, aber meistens diejenigen, die die Freiheit vorangebracht haben.
        1. Hallo TS,

          Ich kann mir keinen Umstand vorstellen, der das von dir beschriebene Verhalten erklären würde. Bist du sicher, dass du dich gestern nicht vertippt hast oder so?

          Ziemlich sicher. Ich habe es mehrmals versucht. Das kam mir so vor, als wäre die Suche gar nicht durchgeführt worden. Es kam aber die Antwort, dass die Suche 0 Treffer ergeben hätte.

          Ich habe deine Suchbegriffe gefunden. Ich weiß jetzt, was dein Problem war: du hast nicht nach soundex gesucht, sondern nach tag:mysql soundex. Das von dir gesuchte Posting ist allerdings mit „php“ und „sql“ getaggt, daher hast du 0 Suchergebnisse geliefert bekommen.

          LG,
          CK

          1. Hallo,

            tag:mysql vs „sql“

            kann man die nicht als synonym kennzeichnen?

            Gruß
            Kalk

            1. Hallo Tabellenkalk,

              tag:mysql vs „sql“

              kann man die nicht als synonym kennzeichnen?

              Klar könnte man das, wäre aber falsch. Gibt ja auch andere DBMS 😀

              LG,
              CK

              1. Hallo,

                wäre aber falsch.

                Und da wir hier sooft über andere Dialekte diskutieren, lieber keine Suchergebnisse liefern…

                Wenn nicht "synonym", dann halt "ungefähr äquivalent" und im Suchergebnis dann: „genau so haben wir nicht, aber vielleicht ist das ähnlich genug?“

                Gruß
                Kalk

                1. Hallo Tabellenkalk,

                  wäre aber falsch.

                  Und da wir hier sooft über andere Dialekte diskutieren, lieber keine Suchergebnisse liefern…

                  Es geht nicht darum keine Ergebnisse zu liefern, sondern darum, dass ich das zusammenlegen von mysql und sql nicht für einen sinnvollen Lösungsweg halte.

                  Wenn nicht "synonym", dann halt "ungefähr äquivalent" und im Suchergebnis dann: „genau so haben wir nicht, aber vielleicht ist das ähnlich genug?“

                  Ich weiß nicht recht. Ich muss darüber nachdenken.

                  LG,
                  CK

                2. Hallo

                  Wenn man es genau nimmt, sollte „sql“ ein Synonym (auch) für „mysql“ sein, da es der Gattungs- bzw. Überbegriff für alle SQL-basierten Implementierungen, wie eben auch MySQL, ist. Umgekehrt darf „mysql“ aber nicht Synonym für „sql“ sein.

                  @Christian Kruse: Gibt die Forensoftware eine solche „Einrichtungssynonymisierung“ her?

                  Tschö, Auge

                  --
                  Wenn man ausreichende Vorsichtsmaßnahmen trifft, muss man keine Vorsichtsmaßnahmen mehr treffen.
                  Toller Dampf voraus von Terry Pratchett
                  1. Hallo Auge,

                    Wenn man es genau nimmt, sollte „sql“ ein Synonym (auch) für „mysql“ sein, da es der Gattungs- bzw. Überbegriff für alle SQL-basierten Implementierungen, wie eben auch MySQL, ist. Umgekehrt darf „mysql“ aber nicht Synonym für „sql“ sein.

                    Das hätte hier nicht ausgereicht.

                    @Christian Kruse: Gibt die Forensoftware eine solche „Einrichtungssynonymisierung“ her?

                    Nein. Ich glaube auch nicht, dass das so, wie hier dargestellt, eine Lösung ist.

                    Ich habe beim Mittagessen darüber ein wenig nachgedacht, ich glaube, die Richtung, die du hier beschreibst ist schon richtig: Such-Synonyme für Tags, die frei definierbar sind; etwa wenn nach tag:mysql gesucht wird, muss auch nach tag:sql gesucht werden. Wenn nach tag:sql gesucht wird, muss auch nach tag:mysql (und tag:postgresql, etc, pp) gesucht werden. Um die spezifischeren Suchtreffer zu favorisieren, sollte es zu einem Synonym noch einen Malus geben, der die Relevanz des Suchtreffers herunter setzt.

                    Dazu muss aber halt neben den notwendigen Datenstrukturen und User-Interfaces auch die redaktionelle Arbeit geschehen…

                    LG,
                    CK

                    1. Hallo Christian Kruse,

                      Dazu muss aber halt neben den notwendigen Datenstrukturen und User-Interfaces auch die redaktionelle Arbeit geschehen…

                      Wie ist das gemeint? Korrektes Tagging?

                      Bis demnächst
                      Matthias

                      --
                      Rosen sind rot.
                      1. Hallo Matthias,

                        Dazu muss aber halt neben den notwendigen Datenstrukturen und User-Interfaces auch die redaktionelle Arbeit geschehen…

                        Wie ist das gemeint? Korrektes Tagging?

                        Korrektes Tagging sollte natürlich immer passieren, damit die Qualität der Suchergebnisse verbessert wird. Aber das meinte ich nicht. Die Synonyme müssen halt gepflegt werden. sqlmysql und mysql => sql sind ja bei weitem nicht die einzigen Such-Synonyme, die es geben müsste.

                        Edit allgemein sollten wir dann auch darüber nachdenken, ob man die Such-Synonyme nicht gleich so baut, dass sie auf dem ganzen Such-String arbeiten. So dass z.B. die Suche nach html auch nach html5 sucht, mal als willkürliches Beispiel herausgegriffen.

                        LG,
                        CK

                    2. Hallo

                      Dazu muss aber halt … auch die redaktionelle Arbeit geschehen…

                      Das allerdings. Wenn ich ehrlich bin, habe ich das nach meinem ersten Experiment, ein Synonym anzulegen, — welches ja grandios gescheitert ist — nie wieder angefasst. Ich weiß nicht einmal, wie ich an die Funktion herankäme, geschweige denn, wie sie zu bedienen ist.

                      Tschö, Auge

                      --
                      Wenn man ausreichende Vorsichtsmaßnahmen trifft, muss man keine Vorsichtsmaßnahmen mehr treffen.
                      Toller Dampf voraus von Terry Pratchett
                      1. Hallo Auge,

                        Dazu muss aber halt … auch die redaktionelle Arbeit geschehen…

                        Das allerdings. Wenn ich ehrlich bin, habe ich das nach meinem ersten Experiment, ein Synonym anzulegen, — welches ja grandios gescheitert ist — nie wieder angefasst. Ich weiß nicht einmal, wie ich an die Funktion herankäme, geschweige denn, wie sie zu bedienen ist.

                        Tag-Synonyme sind etwas anderes, da geht es wirklich darum mehrere gleichbedeutende Tags zusammen zu fassen zu einem. Das dürfte hier nicht geschehen, deshalb schrieb ich ja auch von „Such-Synonymen“.

                        LG,
                        CK

          2. Hello,

            schonmal danke fürs Suchen der Fehlerquelle: Hier! ;-)

            Ich meine zwar, dass ich auch noch ohne Tags gesucht hatte, aber das habe ich vielleicht auch nur geträumt.

            Liebe Grüße
            Tom S.

            --
            Es gibt nichts Gutes, außer man tut es
            Andersdenkende waren noch nie beliebt, aber meistens diejenigen, die die Freiheit vorangebracht haben.