wake-up-neo.net

Fuzzy-Suchalgorithmus (ungefährer String-Matching-Algorithmus)

Ich möchte einen Fuzzy-Suchalgorithmus erstellen. Nach stundenlangen Recherchen habe ich jedoch große Probleme.

Ich möchte einen Algorithmus erstellen, der eine Fuzzy-Suche in einer Liste von Schulnamen durchführt.

Das habe ich mir bisher angeschaut:

Die meisten meiner Forschungen zeigen bei Google und Stackoverflow immer wieder auf "string metrics", wie zum Beispiel:

  • Levenshtein Abstand
  • Entfernung Damerau-Levenshtein
  • Needleman-Wunsch-Algorithmus

Dies gibt jedoch nur eine Bewertung darüber, wie ähnlich 2 Zeichenfolgen sind. Die einzige Möglichkeit, es als Suchalgorithmus zu implementieren, besteht darin, eine lineare Suche durchzuführen, den String-Metrik-Algorithmus für jeden String auszuführen und die Strings mit Punktzahlen über einem bestimmten Schwellenwert zurückzugeben. (Ursprünglich hatte ich meine Saiten in einem Probebaum gespeichert, aber das hilft mir hier offensichtlich nicht weiter!)

Obwohl dies für kleine Listen keine so schlechte Idee ist, wäre es für Listen mit beispielsweise 100.000 Namen problematisch, und der Benutzer führte viele Abfragen durch.

Ein weiterer Algorithmus, den ich mir angesehen habe, ist Rechtschreibprüfung, bei dem Sie nur nach möglichen Rechtschreibfehlern suchen. Dies ist jedoch auch sehr ineffizient, da für ein Wort mit der Länge 7 und einer Fehleranzahl von nur 2 mehr als 75.000 Wörter erforderlich sind.

Was brauche ich?

Kann mir bitte jemand ein guter effizienter Fuzzy-Suchalgorithmus vorschlagen. mit:

  • Name des Algorithmus
  • Wie es funktioniert oder wie es funktioniert
  • Vor- und Nachteile und wann es am besten genutzt wird (optional)

Ich verstehe, dass alle Algorithmen ihre Vor- und Nachteile haben werden und es keinen besten Algorithmus gibt.

44
Yahya Uddin

In Anbetracht dessen, dass Sie versuchen, eine Fuzzy-Suche in einer Liste von Schulnamen durchzuführen, glaube ich nicht, dass Sie eine traditionelle Zeichenfolgenähnlichkeit wie Levenshtein-Entfernung anstreben möchten. Ich gehe davon aus, dass Sie eine Benutzereingabe (entweder über die Tastatur oder über das Telefon) vornehmen und schnell die passende Schule finden möchten.

Abstandsmetriken zeigen an, wie ähnlich zwei Zeichenfolgen auf Ersetzungen, Löschungen und Einfügungen basieren. Diese Algorithmen sagen jedoch nichts darüber aus, wie ähnlich die Zeichenfolgen als Wörter in einer menschlichen Sprache sind.

Betrachten wir zum Beispiel die Wörter "Schmied", "Schmiede" und "Schmiede". Ich kann in zwei Schritten von "smythe" zu "smith" wechseln:

smythe -> smithe -> smith

Und von "smote" zu "smith" in zwei Schritten:

smote -> smite -> smith

Also haben die beiden den gleichen Abstand wie Zeichenfolgen , aber als Wörter , Sie unterscheiden sich erheblich. Wenn Ihnen jemand erzählt (gesprochene Sprache), dass er nach "Symthe College" sucht, würden Sie mit ziemlicher Sicherheit sagen: "Oh, ich denke, Sie meinen Smith." Aber wenn jemand "Smote College" sagte, wüssten Sie nicht, wovon er sprach.

Was Sie brauchen, ist ein phonetischer Algorithmus wie Soundex oder Metaphon . Grundsätzlich zerlegen diese Algorithmen ein Wort in Phoneme und erstellen eine Darstellung, wie das Wort in der gesprochenen Sprache ausgesprochen wird. Sie können dann das Ergebnis mit einer bekannten Liste von Wörtern vergleichen, um eine Übereinstimmung zu finden.

Ein solches System wäre viel schneller als die Verwendung einer Distanzmetrik. Bedenken Sie, dass Sie bei einer Entfernungsmetrik die Benutzereingaben mit jedem Wort in Ihrer Liste vergleichen müssen, um die Entfernung zu ermitteln. Das ist rechenintensiv und die Ergebnisse, wie ich mit "smith" und "smote" gezeigt habe, können lächerlich schlecht sein.

Mit einem phonetischen Algorithmus erstellen Sie die Phonemdarstellung jedes Ihrer bekannten Wörter und platzieren sie in einem Wörterbuch (einer Hash-Map oder möglicherweise einem Trie). Das sind einmalige Startkosten. Wann immer der Benutzer einen Suchbegriff eingibt, erstellen Sie die Phonemdarstellung seiner Eingabe und schlagen sie in Ihrem Wörterbuch nach. Das ist viel schneller und führt zu viel besseren Ergebnissen.

Bedenken Sie auch, dass Menschen, die Eigennamen falsch schreiben, fast immer den richtigen Anfangsbuchstaben finden und häufig die Rechtschreibfehler wie das eigentliche Wort ausdrücken, das sie verwenden versuchten zu buchstabieren. Wenn dies der Fall ist, sind die phonetischen Algorithmen definitiv der richtige Weg.

33
Jim Mischel

Sie verwechseln Fuzzy-Suchalgorithmen mit der Implementierung: Bei einer Fuzzy-Suche in einem Wort werden möglicherweise 400 Ergebnisse aller Wörter mit einem Levenshtein-Abstand von beispielsweise 2 zurückgegeben. Für den Benutzer müssen Sie jedoch nur die Top 5-10 anzeigen.

In Bezug auf die Implementierung werden Sie alle Wörter im Wörterbuch vorverarbeiten und die Ergebnisse in einer Datenbank speichern. Die gängigen Wörter (und ihre Fuzzy-Likes) werden in der Cache-Ebene gespeichert, sodass Sie die Datenbank nicht bei jeder Anfrage erneut aufrufen müssen.

Sie können eine AI-Ebene hinzufügen, die die häufigsten Rechtschreibfehler hinzufügt, und sie der Datenbank hinzufügen. Und soweiter und sofort.

5
alfasin

Ich habe einen Artikel darüber geschrieben, wie ich eine Fuzzy-Suche implementiert habe:

https://medium.com/@Srekel/implementing-a-fuzzy-search-algorithm-for-the-debuginator-cacc349e6c55

Die Implementierung ist in Github und ist gemeinfrei. Schauen Sie sich das an.

https://github.com/Srekel/the-debuginator/blob/master/the_debuginator.h#L1856

Die Grundlagen sind: Teilen Sie alle Zeichenfolgen, nach denen Sie suchen, in Teile auf. Wenn Sie also Pfade haben, lautet "C:\documents\lol.txt" möglicherweise "C", "documents", "lol", "txt".

Stellen Sie sicher, dass Sie diese Zeichenfolgen in Kleinbuchstaben eingeben, um sicherzustellen, dass die Groß- und Kleinschreibung nicht berücksichtigt wird. (Möglicherweise nur, wenn die Suchzeichenfolge nur Kleinbuchstaben enthält).

Vergleichen Sie dann Ihren Suchbegriff damit. In meinem Fall möchte ich es unabhängig von der Reihenfolge abgleichen, so dass "loldoc" immer noch mit dem obigen Pfad übereinstimmt, obwohl "lol" hinter "doc" steht.

Das Matching muss eine gewisse Punktzahl haben, um gut zu sein. Der wichtigste Teil, denke ich, ist aufeinanderfolgende Übereinstimmung . Je mehr Zeichen direkt hintereinander übereinstimmen, desto besser. "Doc" ist also besser als "dcm".

Dann möchten Sie wahrscheinlich eine zusätzliche Punktzahl für ein Match vergeben, das am Anfang eines Teils liegt. Sie erhalten also mehr Punkte für "doc" als für "ocu".

In meinem Fall gebe ich auch mehr Punkte für das Zuordnen des Endes eines Teils.

Und schließlich möchten Sie vielleicht zusätzliche Punkte vergeben, um den letzten Teil (e) abzugleichen. Dies führt dazu, dass die Übereinstimmung mit dem Dateinamen/der Endung höher ist als die der Ordner, die dorthin führen.

3
Srekel

Ein einfacher Algorithmus für "eine Art Fuzzy-Suche"

Um ehrlich zu sein, ist die Fuzzy-Suche in einigen Fällen meistens nutzlos und ich denke, dass ein einfacherer Algorithmus das Suchergebnis verbessern kann und gleichzeitig das Gefühl vermittelt, dass wir immer noch eine Fuzzy-Suche durchführen.

Hier ist mein Anwendungsfall: Filtern einer Liste von Ländern mithilfe der "Fuzzy-Suche" .

Die Liste, mit der ich gearbeitet habe, hatte zwei Länder, die mit Z begannen: Sambia und Simbabwe.

Ich habe Fusejs verwendet.

In diesem Fall hatte die Ergebnismenge bei Eingabe der Nadel "zam" 19 Übereinstimmungen und die relevanteste für einen Menschen (Sambia) am Ende der Liste. Und die meisten anderen Länder im Ergebnis hatten nicht einmal den Buchstaben z im Namen.

Dies war für eine mobile App, bei der Sie ein Land aus einer Liste auswählen können. Es sollte ungefähr so ​​sein, als müsste man einen Kontakt aus den Kontakten des Telefons auswählen. Sie können die Kontaktliste filtern, indem Sie einen Begriff in das Suchfeld eingeben.

IMHO, diese Art von begrenztem Inhalt, von dem aus gesucht werden kann, sollte nicht so behandelt werden, dass die Leute fragen "Was zum Teufel?!?".

Man könnte vorschlagen, nach dem relevantesten Treffer zu sortieren. Dies kommt in diesem Fall jedoch nicht in Frage, da der Benutzer das "Item of Interest" in der reduzierten Liste immer visuell finden muss. Beachten Sie, dass dies ein Filter-Tool sein soll, keine Suchmaschine "à la Google". Das Ergebnis sollte daher vorhersehbar sortiert sein. Und vor dem Filtern war die Sortierung alphabetisch. Die gefilterte Liste sollte also nur eine alphabetisch sortierte Untermenge der ursprünglichen Liste sein.

Also habe ich mir folgenden Algorithmus ausgedacht ...

  1. Nimm die Nadel ... in diesem Fall: zam
  2. Fügen Sie das Muster .* Am Anfang und Ende der Nadel ein
  3. Fügen Sie das .* - Muster zwischen die einzelnen Buchstaben der Nadel ein
  4. Führen Sie eine Regex-Suche im Heuhaufen mit der neuen Nadel durch, die jetzt .*z.*a.*m.* Lautet.

In diesem Fall wird der Benutzer ein erwartetes Ergebnis erzielen, indem er alles findet, was irgendwie die Buchstaben z, a und m aufweist, die in dieser Reihenfolge erscheinen. Alle Buchstaben in den Nadeln sind in der gleichen Reihenfolge in den Streichhölzern enthalten.

Dies passt auch zu Ländernamen wie Mo zam bique ... was perfekt ist.

Ich denke nur, dass wir manchmal nicht versuchen sollten, eine Fliege mit einer Panzerfaust zu töten.

2
asiby