Ich arbeite gerade an der Implementierung einer Fuzzy-Suche für einen Terminologie-Webdienst und ich suche nach Vorschlägen, wie ich die aktuelle Implementierung verbessern könnte. Es ist zu viel Code zum Teilen, aber ich denke, eine Erklärung könnte ausreichen, um nachdenkliche Vorschläge zu geben. Mir ist klar, dass es viel zu lesen gibt, aber ich würde mich über jede Hilfe freuen.
Erstens ist die Terminologie im Grunde nur eine Anzahl von Namen (oder Begriffen). Für jedes Wort teilen wir es durch Leerzeichen in Token auf und durchlaufen dann jedes Zeichen, um es dem Trie hinzuzufügen. Auf einem Endknoten (z. B. wenn das Zeichen y in Erdbeere erreicht ist) speichern wir in einer Liste einen Index zur Master-Term-Liste. Ein Endknoten kann also mehrere Indizes haben (da der Endknoten für Erdbeere mit "Erdbeere" und "Allergie gegen Erdbeere" übereinstimmt).
Wie bei der eigentlichen Suche wird auch die Suchanfrage in Token nach Speicherplatz aufgeteilt. Der Suchalgorithmus wird für jedes Token ausgeführt. Das erste Zeichen des Such-Tokens muss übereinstimmen (Traw wird also nie mit Erdbeere übereinstimmen). Danach gehen wir durch die Kinder jedes einzelnen Knotens. Wenn ein Kind mit einem übereinstimmenden Zeichen vorhanden ist, setzen wir die Suche mit dem nächsten Zeichen des Such-Tokens fort. Wenn ein Kind nicht mit dem angegebenen Zeichen übereinstimmt, betrachten wir die Kinder mit dem aktuellen Zeichen des Such-Tokens (also nicht weiter). Dies ist der Unschärfeteil, also stimmt "stwb" mit "Erdbeere" überein.
Wenn wir das Ende des Such-Tokens erreichen, durchsuchen wir den Rest der Trie-Struktur an diesem Knoten, um alle möglichen Übereinstimmungen zu erhalten (da die Indizes zur Master-Term-Liste nur auf den Endknoten liegen). Wir nennen das den Roll-Up. Wir speichern die Indizes, indem wir ihren Wert auf ein BitSet setzen. Dann ergeben sich einfach und die BitSets aus den Ergebnissen jedes Such-Tokens. Dann nehmen wir, sagen wir mal, die ersten 1000 oder 5000 Indizes aus den andizierten BitSets und finden die tatsächlichen Begriffe, denen sie entsprechen. Wir verwenden Levenshtein, um jeden Begriff zu bewerten und sortieren dann nach Punkten, um unsere endgültigen Ergebnisse zu erhalten.
Das funktioniert ziemlich gut und ist ziemlich schnell. Es gibt über 390.000 Knoten im Baum und mehr als 1,1 Millionen aktuelle Begriffnamen. Es gibt jedoch Probleme damit, wie es ist.
Zum Beispiel gibt die Suche nach "Auto Katze" Katheterisierung zurück, wenn wir es nicht wollen (da die Suchanfrage zwei Wörter ist, sollte das Ergebnis mindestens zwei sein). Das wäre leicht genug zu überprüfen, aber es kümmert sich nicht um eine Situation wie Katheterisierungsprozedur, da es zwei Wörter ist. Im Idealfall möchten wir, dass es zu etwas wie Herzkatheterisierung passt.
Aufgrund der Notwendigkeit, dies zu korrigieren, haben wir einige Änderungen vorgenommen. Zum einen gehen wir durch den Trie in einer gemischten Tiefe-Breite-Suche. Im Wesentlichen gehen wir zuerst in die Tiefe, solange ein Charakter übereinstimmt. Diese untergeordneten Knoten, die nicht übereinstimmen, werden einer Prioritätswarteschlange hinzugefügt. Die Prioritätswarteschlange ist nach Editierdistanz geordnet, die bei der Suche nach dem Trie berechnet werden kann (da bei einer Übereinstimmung der Zeichen die Entfernung gleich bleibt und wenn nicht, wird sie um 1 erhöht). Auf diese Weise erhalten wir die Bearbeitungsentfernung für jedes Wort. Wir verwenden das BitSet nicht mehr. Stattdessen ist es eine Zuordnung des Index zu einem Terminfo-Objekt. Dieses Objekt speichert den Index der Anfragephrase und den Begriff Phrase und die Punktzahl. Wenn also die Suche "Car Cat" ist und ein Begriff "Catheterization procedure" ist, wird der Ausdruck Phraseindizes gleich 1 sein, wie auch die Phraseindizes. Für "Herzkatheterisierung" wird der Ausdruck Phraseindizes 1,2 sein, ebenso wie die Phraseindizes der Anfrage. Wie Sie sehen können, ist es danach sehr einfach, sich die Anzahl der Phraseindizes und der Phrasenindizes anzusehen. Wenn sie nicht mindestens der Anzahl der Suchworte entsprechen, können sie verworfen werden.
Danach addieren wir die Bearbeitungsabstände der Wörter, entfernen die Wörter aus dem Ausdruck, die mit dem Begriff Phrasenindex übereinstimmen, und zählen die restlichen Buchstaben, um den wahren Bearbeitungsabstand zu erhalten. Wenn Sie zum Beispiel den Begriff "Allergie gegen Erdbeeren" gefunden haben und Ihre Suchanfrage "Stroh" lautet, erhalten Sie bei Erdbeeren eine Bewertung von 7, dann würden Sie den Begriff Phrasenindex verwenden, um Erdbeeren aus dem Begriff zu entfernen und einfach zählen "Allergie gegen" (minus die Leerzeichen), um die Punktzahl von 16 zu erhalten.
Dies bringt uns die genauen Ergebnisse, die wir erwarten. Es ist jedoch viel zu langsam. Wo früher 25-40 ms für die Suche nach einem Wort benötigt wurden, könnte es jetzt eine halbe Sekunde dauern. Es geht hauptsächlich um Dinge wie die Instanziierung von TermInfo-Objekten, die Verwendung von .add () - Operationen, .put () -Operationen und die Tatsache, dass wir eine große Anzahl von Übereinstimmungen zurückgeben müssen. Wir können jede Suche auf 1000 Treffer beschränken, aber es gibt keine Garantie, dass die ersten 1000 Ergebnisse für "Auto" mit einem der ersten 1000 Übereinstimmungen für "Katze" übereinstimmen (denken Sie daran, dass es mehr als 1,1 Millionen Begriffe gibt).
Auch für ein einzelnes Abfragewort wie cat brauchen wir immer noch eine große Anzahl von Übereinstimmungen.Wenn wir nach 'Katze' suchen, wird die Suche mit dem Auto übereinstimmen und alle darunter liegenden Terminal-Knoten zusammenrollen (was sehr viel ist). Wenn wir jedoch die Anzahl der Ergebnisse einschränken würden, würde dies eine zu starke Betonung auf Wörter legen, die mit der Abfrage und nicht mit der Bearbeitungsentfernung beginnen. Wörter wie Katheterisierung würden daher eher als etwas wie Fell enthalten sein.
Also, im Grunde, gibt es irgendwelche Gedanken darüber, wie wir mit den Problemen umgehen könnten, die die zweite Implementierung behoben hat, aber ohne so viel von der Geschwindigkeit zu verlangsamen, die es eingeführt hat? Ich kann ausgewählten Code einfügen, wenn es die Dinge klarer machen könnte, aber ich wollte keine riesige Codewand posten.
Wow ... ein zäher.
Nun, warum implementierst du Lucene nicht? Es ist der beste und aktuelle Stand der Technik, wenn es um Probleme wie Ihre afaik geht.
Aber ich möchte einige Gedanken teilen ...
Fuziness ist nicht so etwas wie Stroh * es ist eher das Fehlschreiben einiger Wörter. Und jedes fehlende / falsche Zeichen addiert 1 zur Entfernung.
Es ist im Allgemeinen sehr, sehr schwer, Teilabgleich (Wildcards) und Unschärfe gleichzeitig zu haben!
Tokenizing ist generell eine gute Idee.
Alles hängt auch stark von den Daten ab, die Sie bekommen. Gibt es Rechtschreibfehler in den Quelldateien oder nur in den Suchanfragen?
Ich habe einige ziemlich nette Implementierungen gesehen, die multidimensionale Bereichsbäume verwenden.
Aber ich denke wirklich, wenn Sie all das oben genannte erreichen wollen, brauchen Sie eine ziemlich nette Kombination aus einem Graphensatz und einem netten Indexierungsalgorithmus.
Sie könnten zum Beispiel eine semantische Datenbank wie Sesam verwenden und beim Import Ihrer Dokumente jedes Token und Dokument als Knoten importieren. Dann können Sie abhängig von der Position im Dokument usw. eine gewichtete Relation hinzufügen.
Dann brauchen Sie die Token in einer Struktur, in der Sie effiziente Fuzzy-Matches wie z. B. bk-trees durchführen können. Ich denke, Sie könnten die Token in einer MySQL-Datenbank indizieren und bitweise Vergleichsfunktionen ausführen, um Unterschiede zu erhalten. Theres eine Funktion, die alle übereinstimmenden Bits zurückgibt, wenn Sie Ihre Zeichenfolgen zu ASCII übersetzen und die Bits gruppieren, die Sie ziemlich schnell etwas erreichen konnten.
Wenn Sie jedoch die Token mit der Zeichenfolge abgeglichen haben, können Sie eine hypothetische perfekte Übereinstimmungs-Anität konstruieren und Ihre semantische Datenbank nach den nächsten Nachbarn abfragen.
Sie müssten die Wörter in Teilwörter zerlegen, wenn sie zum Erreichen von Teilübereinstimmungen in Token umgewandelt werden.
Sie können jedoch auch Wildcard-Übereinstimmungen (Präfix, Suffix oder beides) machen, aber keine Unschärfe.
Sie können auch das ganze Wort oder verschiedene Verkettungen von Token indizieren.
Es kann jedoch spezielle bk-tree-Implementierungen geben, die dies unterstützen, aber ich habe noch nie eine gesehen.
Ich habe vor Jahren eine Reihe von Iterationen eines Rechtschreibkorrektors durchgeführt, und hier ist ein aktuelle Beschreibung der grundlegenden Methode. Im Grunde genommen befindet sich das Wörterbuch korrekter Wörter in einem Trie, und die Suche ist eine einfache Verzweigung. Ich benutzte wiederholte Tiefenanstiege, begrenzt durch Lev. Abstand, weil, da jedes zusätzliche Inkrement der Entfernung dazu führt, dass viel mehr von dem Trie gelaufen wird, die Kosten für eine kleine Entfernung im Wesentlichen exponentiell in der Entfernung sind, so dass eine kombinierte Tiefen- / Breitensuche nicht viel spart, sondern es macht viel komplizierter.
(Nebenbei: Sie wären erstaunt, auf wie viele Arten Ärzte versuchen können, "Acetylsalicylsäure" zu schreiben.)
Ich bin überrascht über die Größe Ihres Trie. Ein grundlegendes Wörterbuch akzeptabler Wörter ist vielleicht ein paar Tausend. Dann gibt es gemeinsame Präfixe und Suffixe. Da die Struktur ein Trie ist, können Sie Unterversuche miteinander verbinden und viel Speicherplatz sparen. Wie der Trie von Basispräfixen kann eine Verbindung zum Hauptwörterbuch herstellen, und dann können die Endknoten des Hauptwörterbuchs eine Verbindung mit dem Trie gemeinsamer Suffixe herstellen (die tatsächlich Zyklen enthalten können). Mit anderen Worten, der Trie kann zu einer endlichen Zustandsmaschine verallgemeinert werden. Das gibt Ihnen viel Flexibilität.
Ungeachtet dessen haben Sie ein Performance-Problem. Das Schöne an Performance-Problemen ist, je schlechter sie sind, desto leichter sind sie zu finden. Ich war eine echte Plage auf StackOverflow und wies darauf hin. Dieser Link erläutert, wie das geht, verweist auf ein detailliertes Beispiel und versucht zu zerstreuen einige populäre Mythen. Kurz gesagt, je mehr Zeit Sie damit verbringen, etwas zu tun, das Sie optimieren könnten, desto wahrscheinlicher wird es, wenn Sie es pausieren und einen Blick darauf werfen. Mein Verdacht ist, dass viel Zeit in Operationen mit übertriebener Datenstruktur investiert wird, anstatt nur auf die Antwort zu kommen. Das ist eine häufige Situation, aber beheben Sie nichts, bis Sie direkt auf das Problem hingewiesen werden.
Tags und Links algorithm java performance fuzzy-search levenshtein-distance