Speicher effizienter müssen Strings speichern Tonnen (war: HAT-Trie-Implementierung in Java)

Question

ich mit einem großen Satz arbeitete (5-20 Mio.) von String Tasten (durchschnittliche Länge 10 Zeichen) , die ich in Speicherdatenstruktur in einem speichern müssen dass unterstützt die folgende Operation in konstanter Zeit oder in der Nähe von konstanter Zeit:

// Returns true if the input is present in the container, false otherwise
public boolean contains(String input)

Java HashMap erweist sich als weit mehr als zufrieden stellend, wie Durchsatz angeht, ist aber viel Speicherplatz einnimmt. Ich bin auf der Suche nach einer Lösung, Speicher effizient ist und noch einen Durchsatz unterstützt, die anständig ist (vergleichbar mit oder fast so gut wie Hashing).

Ich kümmere mich nicht um die Einfügen / Löschen mal. In meiner Anwendung werde ich nur Einfügungen (nur beim Start) durchführen und anschließend nur die Datenstruktur unter Verwendung der contains Methode für das Leben der Anwendung wird abgefragt wird.

las ich, dass die HAT-Trie-Datenstruktur am nächsten ist, für meine Bedürfnisse. Ich frage mich, ob es eine Bibliothek, die eine Implementierung hat.

Andere Vorschläge mit Zeigern auf Implementierungen begrüßen zu können.

Danke.

Answer 1

Die trie scheint wie eine sehr gute Idee für Ihre Einschränkungen.

Eine alternative "Denken außerhalb der Box":

Wenn Sie einige Wahrscheinlichkeit leisten können „present“ für eine Reihe von beantworten, die nicht vorhanden ist

EDIT: Wenn Sie Fehlalarme leisten können, eine Bloom Filter verwenden wie WizardOfOdds vorgeschlagen in die Kommentare.

k = 1, ein Bloom-Filter ist wie eine Hash-Tabelle ohne die Schlüssel: jeder „Eimer“ ist einfach ein Boolescher Wert, der mindestens ein Eingang mit der gleichen Hash-sagt, wenn vorhanden war. Wenn 1% Fehlalarme akzeptabel ist, kann Ihre Hash-Tabelle als etwa 100 * 20 Millionen Bits oder rund 200 MiB klein sein. Für 1 in 1000 Fehlalarme, 2GiB.

mehrere Hash-Funktionen verwenden, anstatt kann man die falsch-positive Rate für die gleiche Menge an Bits verbessern.

Answer 2

Google bringt einen Blog-Post bis auf HAT versucht in Java . Aber ich sehe nicht, wie das Ihr Problem direkt lösen: Die Struktur ist eine flache trie über Präfixe des Schlüssels, mit den Blättern Hashtables hält die Suffixe aller Schlüssel mit dem angegebenen Präfix sein. Also insgesamt, haben Sie eine Menge von Hash-Tabellen alle Schlüssel zu speichern, die in Ihrer aktuellen großen Hash-Tabelle sind (vielleicht ein paar Byte pro Schlüssel Einsparung insgesamt wegen der gemeinsamen Präfixe). So oder so, benötigen Sie einen Platz sparender hashtable als die Standard-Java ein, oder die pro-Objekt-Overhead wird Sie genauso schwer getroffen. Warum also nicht nur mit einem spezialisierten hashtable Klasse für String-Schlüssel starten, wenn Sie diesen Weg nehmen, und Sorgen über die Trie-Teil nur dann, wenn es sich noch lohnt scheint dann?

Answer 3

Für die Raumeffizienz, O (log (n)) Lookup und einfachen Code, versuchen binäre Suche über ein Array von Zeichen. 10 20 Millionen Tasten mit einer durchschnittlichen Länge macht 200 Millionen Zeichen: 400 MB, wenn Sie 2 Bytes / char müssen; 200MB, wenn Sie mit 1. Auf diesen man irgendwie müssen wegkommen können, um die Grenzen zwischen den Tasten in der Anordnung darstellen. Wenn Sie ein Trennzeichen behalten können, ist, dass ein Weg; sonst könnte man eine parallele Anordnung von int-Offsets verwenden.

Die einfachste Variante wäre ein Array von Strings, auf einem hohen Raumkosten von pro-Objekt-Overhead verwenden. Es sollte noch eine Hash-Tabelle in der Raumeffizienz schlagen, wenn auch nicht so eindrucksvoll.

Answer 4

ähnlich wie bei einem Trie ist ein ternärer Suchbaum, sondern ein ternärer Suchbaum hat den Vorteil, wenige Speicher benötigt wird. Sie können über ternäre Suchbäume lesen hier , hier und hier . Auch eine der wichtigsten Arbeiten zum Thema von Jon Bentley und Robert Sedgewick ist hier . Es spricht auch über Strings schnell sortieren, so lassen Sie sich nicht durch abschrecken.