Datenstrukturwahl für Ngramme bis Länge 5, wenn zählungsbasiertes Verteilungsmodell erstellt wird

Question

Ich baue ein Verteilungsmodell (zählungsbasiert) aus Text. Grundsätzlich muss ich für jedes ngram (eine Folge von Wörtern) eine Zählung speichern. Ich brauche einen recht schnellen Zugriff auf die Zählung. Für n = 5 sind technisch alle möglichen 5 Gramm (10^4)^5, selbst wenn ich eine konservative Schätzung von 10k Wörtern anwende, was zu hoch ist. Aber viele Kombinationen dieser N-Gramme würden im Text nicht existieren, so dass eine 5d-Array-Art der Struktur außer Betracht kommt.

Ich baute einen Trie, wo jedes Wort ein Knoten ist. Also wäre dieser Trie wirklich sehr breit, mit maximaler Tiefe 5. Das hat mir eine beträchtliche Speicherersparnis gebracht. Aber ich habe immer noch nicht genug Speicher (64 GB), nachdem ich genug Dateien trainiert habe. Um fair zu sein, verwende ich hier keine super-effizienten Java-Praktiken. Jeder Knoten hat eine Zählung, Index des Wortes als int. Ich habe dann eine HashMap, um Kinder zu speichern. Ich begann zunächst mit einer Liste. Ich habe versucht, es jedes Mal zu sortieren, wenn ich ein Kind hinzufügte, aber ich verlor viel Zeit dort, also wechselte ich zu HashMap. Selbst mit einer Liste wird mir nach dem Lesen einiger weiterer Dateien der Speicher ausgehen.

Also ich denke, ich muss meine Aufgabe in Teile aufteilen, speichern Sie jedes Teil auf der Festplatte. Aber letztendlich müsste ich beim Datenzugriff diese Datenstrukturen zusammenführen. Ich denke also, der Weg nach vorne ist eine Disk-basierte Lösung, wo ich weiß, auf welche Datei zugegriffen werden muss, wenn Ngrams mit etwas beginnen (eine Art Ordnung). Wie ich es sehe, ist das Problem mit trie nicht sehr effizient, wenn ich es zusammenführe. Ich müsste zwei Teile in den Speicher laden, um sie zusammenzuführen. Das würde nicht wirklich funktionieren.

Welchen Ansatz würden Sie empfehlen? Ich untersuchte eine HashMap-basierte Struktur für Sprachmodelle (wie die, die berkeleylm verwendet). Aber in ihrem Anwendungsfall brauchen sie das ngram nicht zu rekonstruieren, sie hashen es einfach und speichern den Hashwert als Kontext. Ich muss später auf den Kontext zugreifen können.

Irgendwelche Vorschläge? Gibt es einen Wert bei der Verwendung einer Datenbank? Können sie es tun, ohne sich zu merken?

Answer 1

Ich würde HashMap nicht verwenden, es ist ziemlich speicherintensiv, ein einfaches sortiertes Array sollte besser sein, Sie können dann binäre Suche darauf verwenden.

Vielleicht könnten Sie auch einen binären Präfix-Trie ausprobieren. Zuerst erstellen Sie eine einzelne Zeichenkette, zum Beispiel indem Sie die Buchstaben der Wörter in eine einzige Zeichenkette verschachteln (ich nehme an, Sie könnten sie auch verketten, getrennt durch ein Leerzeichen). Dieser lange String könnte dann in einem binären Trie gespeichert werden. Ein Beispiel finden Sie in CritBit1D.

Sie könnten auch einen mehrdimensionalen Baum verwenden. Viele Bäume sind auf 64-Bit-Nummern beschränkt, aber Sie können die acht führenden ASCII-Zeichen jedes Wortes in eine 64-Bit-Ganzzahl umwandeln und diese dann als 5D-Schlüssel speichern. Das sollte viel effizienter sein als ein 5D-Array. Multidim-Indizes sind: kd-Bäume, R-Bäume oder Quadtrees. Die 5-Gramm-Zählung und die vollen 5-Gramm-Zahlen (einschließlich der verbleibenden Zeichen) können getrennt in dem VALUE gespeichert werden, der mit jeder 5D-KEY verknüpft werden kann.

Wenn Sie Java verwenden, können Sie meine eigene tree versuchen. Es ist ein Prefix-Sharing Bitwise Quadtree. Es ist sehr speichereffizient, sehr gut geeignet für größere Datenmengen (1M Einträge aufwärts) und arbeitet nativ mit 'integer' anstelle von 'float'. Es hat auch sehr gute nächste Nachbarsuche.