'Big Dictionary' Implementierung in Java

Question

Ich bin in der Mitte eines Java-Projekts, das ein 'großes Wörterbuch' von Wörtern verwenden wird. Mit 'Wörterbuch' meine ich bestimmte Zahlen (int), die Strings zugewiesen sind. Und mit "groß" meine ich eine Datei in der Größenordnung von 100 MB. Die erste Lösung, die ich gefunden habe, ist wahrscheinlich die einfachste. Bei der Initialisierung lese ich die ganze Datei ein und erstelle eine große HashMap, die später verwendet wird, um Strings zu suchen.

Gibt es eine effiziente Möglichkeit, dies zu tun, ohne dass die gesamte Datei bei der Initialisierung gelesen werden muss? Vielleicht nicht, aber was ist, wenn die Datei wirklich groß ist, sagen wir in der Reihenfolge des verfügbaren Arbeitsspeichers? Im Grunde suche ich nach einer Möglichkeit, die Dinge effizient in einem großen Wörterbuch zu suchen.

Danke für die Antworten bis jetzt, als Ergebnis habe ich realisiert, dass ich spezifischer in meiner Frage sein könnte. Wie Sie wahrscheinlich schon vermutet haben, hat die Anwendung mit Text Mining zu tun, insbesondere mit der Darstellung von Text in Form eines spärlichen Vektors (obwohl einige andere erfinderische Ideen hatten :)). Was für die Verwendung entscheidend ist, ist, in der Lage zu sein, Zeichenfolgen im Wörterbuch nachzuschlagen und ihre Schlüssel so schnell wie möglich zu erhalten. Der anfängliche Aufwand, die Wörterbuchdatei zu "lesen" oder in eine Datenbank zu indizieren, ist nicht so wichtig, solange die Nachschlagezeit optimiert ist. Nehmen wir an, dass die Wörterbuchgröße groß ist, vergleichbar mit der Größe des verfügbaren RAM.

Answer 1

Betrachten Sie ChronicleMap (https://github.com/OpenHFT/Chronicle-Map) in einem nicht replizierten Modus. Es ist eine Off-Heap-Implementierung von Java Map, oder, aus einem anderen Blickwinkel, ein Superlightweight NoSQL Schlüssel-Wert-Speicher.

Was es für die Aufgabe aus der Box nützlich macht:

• Persistance auf der Festplatte über Memory-Mapped-Dateien (siehe Kommentar von Michał Kosmulski)
• Lazy Load (Plattenseiten werden nur bei Bedarf geladen) -> Schnellstart
• Wenn Ihr Datenvolumen größer ist als der verfügbare Arbeitsspeicher, wird das Betriebssystem selten verwendete Seiten automatisch auflösen.
• Mehrere JVMs können dieselbe Zuordnung verwenden, da der Off-Heap-Speicher auf Betriebssystemebene gemeinsam genutzt wird. Nützlich, wenn Sie die Verarbeitung in einem Map-Reduced-ähnlichen Framework durchführen, z. G. Hadoop.
• Strings werden in UTF-8-Form gespeichert, -> ~ 50% Speichereinsparungen, wenn Strings meist ASCII sind (wie maaartinus angegeben)
• int oder long Werte nur 4 (8) Bytes nimmt, wie wenn Sie primitive- haben spezialisierte Kartenimplementierung.
• Sehr wenig pro-Eintrag Speicher-Overhead, viel weniger als in Standard HashMap und ConcurrentHashMap
• Gut konfigurierbare Gleichzeitigkeit über Lock-Striping, wenn Sie bereits benötigen, oder wird die Textverarbeitung in Zukunft parallelisieren.

Answer 2

An der Stelle, an der Ihre Datenstruktur ein paar hundert MB zu RAM-Ordnungen ist, sollten Sie eine Datenstruktur zur Laufzeit nicht initialisieren, sondern eine Datenbank verwenden, die indexing unterstützt (was die meisten heutzutage tun) . Indexierung ist eine der wenigen Möglichkeiten, mit denen Sie den schnellsten Text abrufen können, sobald Ihre Datei so groß ist und Sie mit den Einstellungen Ihrer JVM - Xmx konfrontiert werden. Der Grund dafür ist, dass Ihre Datei unweigerlich zu crash your JVM geht, wenn Ihre Datei so groß oder viel größer als Ihre Einstellungen für die maximale Größe ist.

Wie zum Lesen der gesamten Datei bei der Initialisierung. Sie müssen dies schließlich tun, damit Sie den Text in Ihrem Code effizient suchen und analysieren können. Wenn Sie wissen, dass Sie nur einen bestimmten Teil Ihrer Datei gleichzeitig durchsuchen werden, können Sie lazy loading implementieren. Wenn nicht, können Sie genauso gut in die Kugel beißen und Ihre gesamte Datei in die Datenbank laden. Sie können parallelism in diesem Prozess implementieren, wenn es andere Teile Ihrer Codeausführung gibt, die davon nicht abhängen.

Bitte lassen Sie mich wissen, wenn Sie irgendwelche Fragen haben!

Answer 3

Wie in einem Kommentar erwähnt, speichert eine Trie viel Speicher.

Sie sollten auch mit byte s statt char s betrachten, da dies Ihnen einen Faktor von 2 für reinen ASCII-Text speichert oder wenn Sie Ihren nationalen charset verwenden, solange sie nicht mehr als 256 verschiedene Buchstaben haben.

Auf den ersten Blick macht die Kombination dieser Low-Level-Optimierung mit tries keinen Sinn, da bei ihnen die Knotengröße von den Zeigern dominiert wird. Aber es gibt einen Weg, wenn du auf ein niedriges Level gehen willst.

Was ist entscheidend für die Verwendung ist in der Lage, Strings nach oben im Wörterbuch aussehen, erhalten Sie ihre Schlüssel so schnell wie möglich.

Dann vergessen Sie keine Datenbank, da sie im Vergleich zu HashMap s verdammt langsam sind.

Wenn es nicht in den Speicher passt, ist die billigste Lösung normalerweise, mehr davon zu bekommen.Andernfalls sollten Sie nur die gebräuchlichsten Wörter laden und etwas langsamer für die anderen tun (z. B. eine Speicherabbilddatei).

---

Ich wurde gebeten, auf eine gute Tries-Implementierung zu zeigen, besonders Off-Heap. Mir sind keine bekannt.

Angenommen, das OP benötigt keine Wandlungsfähigkeit, insbesondere keine Änderbarkeit der Tasten, alles sieht sehr einfach aus.

Ich denke, das ganze Wörterbuch könnte leicht in eine einzige ByteBuffer verpackt werden. Nimmt man hauptsächlich ASCII an und mit etwas Bithacking, würde ein Pfeil 1 Byte pro Pfeilmarkierungszeichen und 1 bis 5 Bytes für den Kindzeiger benötigen. Der Kindzeiger wäre relativ (d. H. Die Differenz zwischen dem aktuellen Knoten und dem Kind), wodurch die meisten von ihnen in ein einzelnes Byte passen würden, wenn sie in einem base 128 encoding gespeichert würden.

Ich kann nur den Gesamtspeicherverbrauch schätzen, aber ich würde sagen, etwas wie < 4 Bytes pro Wort. Die obige Komprimierung würde das Nachschlagen verlangsamen, aber immer noch nicht annähernd den Wert, den ein einzelner Plattenzugriff benötigt.

Answer 4

Es klingt zu groß, um im Speicher zu speichern. Entweder speichern Sie es in einer relationalen Datenbank (einfach, und mit einem Index auf den Hash, schnell), oder eine NoSQL-Lösung, wie Solr (kleine Lernkurve, sehr schnell).

Obwohl NoSQL sehr schnell ist, wenn Sie die Leistung wirklich optimieren möchten und es Einträge gibt, die viel häufiger nachgeschlagen werden als andere, sollten Sie einen Cache mit begrenzter Größe für die zuletzt verwendeten (etwa) 10000 Suchvorgänge verwenden.