wie man unscharfe Suche in großen Daten macht

Question

Ich bin neu in diesem Bereich und ich frage mich hauptsächlich was der Stand der Technik ist und wo ich darüber lesen kann. Lassen Sie uns annehmen, dass ich nur einen Schlüssel/Wert-Speicher habe und irgendwie Abstand (key1, key2) definiert habe (nicht sicher, ob es eine Metrik sein muss, d. H. Ob die Dreiecksungleichung immer gelten muss).

Was ich will, ist meist eine Suche (Schlüssel) -Funktion, die mir alle Elemente mit Schlüsseln bis zu einer bestimmten Entfernung zum Suchschlüssel zurückgibt. Vielleicht ist diese Distanzgrenze konfigurierbar. Vielleicht ist das auch nur ein langsamer Iterator. Vielleicht kann es auch ein Zähllimit geben und ein Item (Schlüssel, Wert) ist mit einer Wahrscheinlichkeit P in der zurückgegebenen Menge, wo P = 1/Entfernung (Schlüssel, Suchschlüssel) oder so (dh die perfekte Übereinstimmung wäre sicherlich in den Set- und Close-Matches zumindest mit hoher Wahrscheinlichkeit).

---

Eine beispielhafte Anwendung ist in MusicBrainz Fingerabdruckabgleich. Sie verwenden den AcoustId Fingerabdruck und haben this compare function definiert. Sie benutzen den PostgreSQL GIN Index und ich denke (obwohl ich den Acoustid-Server Code nicht vollständig verstanden/gelesen habe) die GIN Partial Match Algorithm, aber ich habe nicht ganz verstanden ob das ist was ich gefragt habe und wie es funktioniert.

---

Für Text, was ich bisher gefunden ist etwas phonetic algorithm zu verwenden Wörter auf ihre Aussprache zu vereinfachen basiert. Ein Beispiel ist here. Dies dient hauptsächlich dazu, den Suchraum auf einen kleineren Bereich zu reduzieren. Dies hat jedoch mehrere Einschränkungen, z. es muss immer noch eine perfekte Übereinstimmung auf kleinerem Raum sein.

Aber ich suche auch nach einer allgemeineren Lösung, wenn das existiert.

Answer 1

Es gibt keine (schnelle) generische Lösung, jede Anwendung benötigt einen anderen Ansatz.

Keines der beiden Beispiele funktioniert tatsächlich traditionelle Suche nach dem nächsten Nachbarn. AcoustID (ich bin der Autor) sucht nur nach genauen Übereinstimmungen, aber es sucht in einer sehr hohen Anzahl von Hashes in der Hoffnung, dass einige von ihnen übereinstimmen werden. Das phonetische Suchbeispiel verwendet metaphone, um Wörter in ihre phonetische Darstellung zu konvertieren, und sucht nur nach exakten Übereinstimmungen.

Sie werden feststellen, dass, wenn Sie eine Menge Daten haben, die exakte Suche mit riesigen Hash-Tabellen das einzige ist, was Sie realistisch tun können. Das Problem besteht dann darin, wie Sie Ihr Fuzzy-Matching auf exakte Suche umstellen können.

Ein gängiger Ansatz ist die Verwendung von (LSH) mit einer intelligenten Hash-Methode, aber wie Sie in Ihren beiden Beispielen sehen können, können Sie manchmal mit noch einfacher Ansatz kommen.

Btw, Sie suchen speziell für die Textsuche, die einfachste Möglichkeit, wie Sie es tun können, teilen Sie Ihre Eingabe zu N-grams und indizieren diese. Je nachdem, wie Ihre Distanzfunktion definiert ist, können Sie ohne viel Arbeit die richtigen Kandidaten finden.

Answer 2

Ich schlage vor, Sie werfen einen Blick auf FLAN Fast Approximate Nearest Neighbors. Unscharfe Suche in großen Daten wird auch als ungefähre nächste Nachbarn bezeichnet.

Diese Bibliothek bietet Ihnen verschiedene Metrik, z euklidisches, Hamming und verschiedene Methoden des Clustering: LSH oder k-Mittel zum Beispiel.

Die Suche erfolgt immer in 2 Phasen.Zuerst füttern Sie das System mit Daten, um den Algorithmus zu trainieren, dies ist abhängig von Ihren Daten möglicherweise zeitaufwendig. Ich gruppierte erfolgreich 13 Millionen Daten in weniger als einer Minute (mit LSH).

Dann kommt die Suchphase, die sehr schnell ist. Sie können eine maximale Entfernung und/oder die maximale Anzahl von Nachbarn angeben.

Wie Lukas sagte, gibt es keine gute generische Lösung, jede Domäne wird ihre Tricks haben, um es schneller zu machen oder einen besseren Weg zu finden, indem sie die innere Eigenschaft der Daten nutzt.

Shazam verwendet eine spezielle Technik mit geometrischen Projektionen, um schnell Ihren Song zu finden. In der Computer Vision benutzen wir oft den BOW: Beutel mit Wörtern, der ursprünglich in der Texterfassung erschien.

Wenn Sie Ihre Daten als Graphen sehen können, gibt es andere Methoden für eine ungefähre Übereinstimmung unter Verwendung der spektralen Graphentheorie.

Lassen Sie uns wissen.

Answer 3

Je nachdem, wie Ihre Schlüssel/Werte aussehen, kann der Levenshtein-Algorithmus (auch Edit-Distance genannt) helfen. Es berechnet die geringste Anzahl von Bearbeitungsvorgängen, die zum Ändern einer Zeichenfolge erforderlich sind, um eine andere Zeichenfolge zu erhalten.

• http://en.wikipedia.org/wiki/Levenshtein_distance
• http://www.levenshtein.net/