Ich verwende einen benutzerdefinierten Cython-Wrapper von dieser Marisa-Trie -Bibliothek als Schlüsselwert-Multimap.
Meine Trie-Einträge sehen wie key 0xff data1 0xff data2 aus, um key dem Tupel (data1, data2) zuzuordnen. data1 ist eine Zeichenfolge mit variabler Länge, aber data2 ist immer ein 4-Byte-Zeichen ohne Vorzeichen. Das 0xff ist ein Delimiter-Byte.
Ich weiß, dass ein Trie aus theoretischer Sicht nicht die optimalste Datenstruktur dafür ist, aber verschiedene praktische Überlegungen machen es zur besten verfügbaren Wahl.
In diesem Anwendungsfall habe ich ungefähr 10-20 Millionen Schlüssel, jeder hat durchschnittlich 10 Datenpunkte. data2 ist für viele Einträge überflüssig (in einigen Fällen ist data2 immer gleich für alle Datenpunkte eines gegebenen Schlüssels), daher hatte ich die Idee, den häufigsten data2 Eintrag zu nehmen und einen ("", base_data2) hinzuzufügen. Datenpunkt zu jedem Schlüssel.
Da ein MARISA-Trie meines Wissens keine Suffixkompression hat und für einen gegebenen Schlüssel jedes data1 eindeutig ist, ging ich davon aus, dass dies 4 Bytes pro Datentupel sparen würde, das einen redundanten Schlüssel verwendet (plus Hinzufügen von a einzelner 4-Byte "Wert" für jeden Schlüssel). Nachdem ich den Trie rekonstruiert hatte, überprüfte ich, dass die redundanten Daten nicht mehr gespeichert wurden. Ich erwartete eine beträchtliche Abnahme sowohl der serialisierten als auch der In-Memory-Größe, aber in der Tat ging der Platten-Trie von 566 MB auf 557 MB (und eine ähnliche Verringerung der RAM-Nutzung für einen geladenen Trie).
Daraus habe ich geschlossen, dass ich falsch liegen muss, da es keine Suffixkompression gibt. Ich speicherte nun die Einträge mit einer redundanten data2 -Nummer als key 0xff data1 0xff . Um diese Theorie zu testen, entfernte ich das nachgestellte 0xff und passte den Code an, der den Trie verwendet, um damit fertig zu werden. Der neue Trie ist von 557MB auf 535MB gesunken.
Das Entfernen eines einzelnen redundanten nachfolgenden Bytes hat also eine 2x größere Verbesserung bewirkt als das Entfernen von der gleichen Anzahl von 4-Byte-Sequenzen, also ist entweder die Suffix-Komprimierungstheorie völlig falsch oder sie ist in einigen sehr komplizierten implementiert Weg.
Meine verbleibende Theorie ist, dass das Hinzufügen des ("", base_data2) -Eintrags an einem höheren Punkt im Trie irgendwie die Kompression auf eine schreckliche Weise hinauswirft, aber es sollte nur 4 weitere Bytes hinzufügen, wenn ich viel mehr als entfernt habe das von unten im Trie.
Ich bin nicht optimistisch für eine Lösung, aber ich würde gerne wissen, warum ich dieses Verhalten sehe! Danke für Ihre Aufmerksamkeit.
Wie ich vermutete, wird dies durch Auffüllen verursacht.
in lib/marisa/grimoire/vector/vector.h , gibt es die folgende Funktion:
Der entscheidende Punkt ist: writer.seek((8 - (total_size() % 8)) % 8); . Nach dem Schreiben jedes Blocks füllt der Schreiber die nächste 8-Byte-Grenze auf.
Dies erklärt das Verhalten, das Sie sehen, wenn ein Teil der Daten, die durch die anfängliche Kürzung des Schlüssels entfernt wurden, durch Auffüllen ersetzt wurde.
Wenn Sie das zusätzliche Byte entfernt haben, hat es die Schlüsselgröße unter die nächste Grenze gebracht, was zu einer größeren Größenänderung geführt hat.
In der Praxis bedeutet dies, dass Sie wahrscheinlich die Einsparungen erzielen, die Sie im Speicher erwartet haben, da sich der Auffüllcode im Serialisierungsteil der Bibliothek befindet. Dies führte jedoch nicht zu Einsparungen auf der Festplatte Die RAM-Nutzung des Überwachungsprogramms sollte dies bestätigen.
Wenn es um Ihre Festplattengröße geht, können Sie die serialisierten Daten einfach deflationieren, da MARISA keinerlei Kompression anlegt.