Ich versuche eine Rechtschreibprüfung zu schreiben, die mit einem ziemlich großen Wörterbuch funktionieren sollte. Ich möchte wirklich, dass meine Wörterbuchdaten auf effiziente Weise indexiert werden, um anhand einer Damerau-Levenshtein- Distanz zu bestimmen, welche Wörter dem falsch geschriebenen Wort am nächsten kommen.
Ich suche eine Datenstruktur, die mir den besten Kompromiss zwischen Speicherplatzkomplexität und Laufzeitkomplexität bietet.
Basierend auf dem, was ich im Internet gefunden habe, habe ich einige Hinweise dazu, welche Art von Datenstruktur zu verwenden ist:
Trie
Dies ist mein erster Gedanke und sieht ziemlich einfach zu implementieren aus und sollte ein schnelles Nachschlagen / Einfügen ermöglichen. Die ungefähre Suche mit Damerau-Levenshtein sollte auch hier einfach zu implementieren sein. In Bezug auf die Speicherkomplexität sieht es jedoch nicht sehr effizient aus, da der Speicherplatz für Zeiger höchstwahrscheinlich einen hohen Overhead aufweist.
Patricia Trie
Dies scheint weniger Platz in Anspruch zu nehmen als ein normaler Trie, da Sie im Grunde die Kosten für das Speichern der Zeiger vermeiden, aber ich mache mir ein bisschen Sorgen über die Datenfragmentierung bei sehr großen Wörterbüchern wie dem, was ich habe.
Suffix-Baum
Ich bin mir nicht sicher, wie es scheint, finden es einige Leute beim Text-Mining nützlich, aber ich bin mir nicht sicher, was es in Bezug auf die Leistung für eine Rechtschreibprüfung bedeuten würde.
Ternärer Suchbaum
Diese sehen hübsch aus und sollten in Bezug auf Komplexität Patricia Tries nahe sein (besser?), Aber ich bin mir nicht sicher, ob es in Bezug auf Fragmentierung besser oder schlechter wäre als Patricia Tries.
Baum platzen
Dies scheint eine Art Hybrid zu sein und ich bin mir nicht sicher, welchen Vorteil es gegenüber Tries und dergleichen haben würde, aber ich habe mehrmals gelesen, dass es für das Text-Mining sehr effizient ist.
Ich würde gerne ein Feedback bekommen, welche Datenstruktur in diesem Zusammenhang am besten geeignet ist und was sie besser macht als die anderen. Wenn mir Datenstrukturen fehlen, die für eine Rechtschreibprüfung noch besser geeignet wären, bin ich auch sehr interessiert.
quelle
Antworten:
Ich bin auf dasselbe Problem gestoßen, bin aber anders vorgegangen. Sie können eine Art "Hash" -Funktion konstruieren, die für ein ähnliches Wort die gleiche oder eine nahe Zahl ergibt.
Das Problem ist, dass die Funktion, die beim Einfügen / Entfernen von Wörtern ein "gutes" Ergebnis liefert, beim Übergang ein "schlechtes" Ergebnis liefert und umgekehrt. Beispiel: Ordnen Sie Buchstaben Zahlen zu, ähnliche Buchstaben wie benachbarte Zahlen, und addieren Sie sie einfach für jeden Buchstaben in einem Wort. Dann erstellen Sie Hash-Tabellen mit Mengen für jeden Schlüssel und finden die Schnittmenge für das Wort.
Möglicherweise können einige Ergebnisse erzielt werden, wenn wir "Raum" von Wörtern betrachten. X zum Ändern des Buchstabens, Y zum Hinzufügen / Entfernen, Z zum Übergang oder so ähnlich.
Dies sind jedoch nur abstrakte Ideen, ich habe nicht genug Zeit, um sie umzusetzen.
quelle
Möglicherweise möchten Sie einen Metrikbaum für eine schnelle Suche verwenden, wenn Brute Force nicht möglich ist (versuchen Sie es immer mit Brut Force). Die Suche nach Ihren Nachbarn ist in , aber die Konstante in kann groß sein. Du scheinst Millionen von Saiten zu haben, also kann es ein guter Kompromiss sein.OO(log(n)) O
Speichern Sie die Zeichenfolgen nicht im Metrikbaum. Speichern Sie einfach einen Index und die Zeichenfolgen in einem Patricia-Baum.
Ich bin mir nicht sicher, welchen Baum Sie verwenden sollen. Dies hängt von Ihren Daten und Ihren Anforderungen ab (benötigen Sie eine schnelle Einfügung?). Aktualisieren Sie Ihre Frage, wenn Sie feststellen, dass ein Baum effizienter ist als die anderen.
Sie können sich auch spezialisierte Werkzeuge wie Lucene ansehen.
quelle