Ich möchte eine Liste der folgenden Tupel in einem komprimierten Format speichern und ich frage mich, welcher Algorithmus mir
gibtMeine Daten sehen folgendermaßen aus:
%Vor%Einer der beiden Ints bezieht sich auf einen Zeitpunkt und es ist sehr wahrscheinlich, dass die Zahlen, die in einer Liste enden, nahe beieinander liegen. Das andere int stellt eine abstrakte ID dar und die Werte sind weniger wahrscheinlich nah, obwohl sie auch nicht völlig zufällig sind. Das Double repräsentiert eine Sensorablesung und obwohl es eine Korrelation zwischen den Werten gibt, ist es wahrscheinlich nicht sehr nützlich.
Da die "Zeit" -Ints nahe beieinander sein können, versuchen Sie, nur die erste zu speichern und speichern Sie danach die Differenz vor dem Int (Delta-Codierung). Sie können dasselbe auch für den zweiten int versuchen.
Sie können auch versuchen, die Daten von [int1, int2, double], [int1, int2, double] ... zu [int1, int1 ...], [int2, int2 ...] zu reorganisieren. , [doppelt, doppelt ...].
Um den Komprimierungsbereich zu ermitteln, in dem sich Ihr Ergebnis befindet, können Sie Ihre Daten in eine Datei schreiben und den Kompressor-CCM von Christian Martelock herunterladen hier . Ich fand heraus, dass es für solche Datensammlungen sehr gut funktioniert. Es verwendet einen ziemlich schnellen Kontextmixing -Algorithmus. Sie können es auch mit anderen Kompressoren wie WinZIP vergleichen oder eine Komprimierungsbibliothek wie zLib verwenden, um zu sehen, ob es sich lohnt.
Hier ist ein allgemeines Schema, das in den meisten Suchmaschinen verwendet wird: Speichere Deltas von Werten und kodiere das Delta unter Verwendung eines variablen Bytecodierschemas, d.h. wenn das Delta kleiner als 128 ist, kann es mit nur 1 Byte codiert werden. Weitere Informationen finden Sie unter vint in Lucene und Protokollpuffern.
Dies wird Ihnen nicht die beste Kompressionsrate geben, aber normalerweise die schnellste für die Kodierung / Dekodierung.
Wenn ich die Frage richtig lese, möchten Sie einfach die Daten effizient speichern. Offensichtlich sind einfache Optionen wie komprimiertes XML einfach, aber es gibt direktere binäre Serialisierungsmethoden. Einer der wichtigsten Punkte sind die Protokollpuffer von Google.
Sie können beispielsweise in C # mit protobuf-net einfach eine Klasse erstellen, in der die Daten gespeichert werden :
%Vor%Dann serialisieren Sie einfach eine List oder Foo [] usw. über die ProtoBuf.Serializer-Klasse.
Ich behaupte nicht, dass es ganz so platzsparend sein wird wie Ihr eigenes, aber es wird verdammt nah sein. Die Protokollpufferspezifikation nutzt den Speicherplatz recht gut (z. B. mit base-128 für ganze Zahlen, so dass kleine Zahlen weniger Platz benötigen). Aber es wäre einfach, es auszuprobieren, ohne den gesamten Serialisierungscode selbst schreiben zu müssen.
Dieser Ansatz ist nicht nur einfach zu implementieren, sondern hat auch den Vorteil, dass er von anderen Architekturen aus einfach zu verwenden ist, da es Protokollpufferimplementierungen für verschiedene Sprachen . Es verwendet auch viel weniger CPU als reguläre [de] Komprimierung (GZip / DEFLATE / etc) und / oder xml-basierte Serialisierung.
Die meisten Komprimierungsalgorithmen funktionieren bei diesen Daten genauso schlecht. Es gibt jedoch ein paar Dinge ("Vorverarbeitung"), die Sie tun können, um die Komprimierbarkeit der Daten zu erhöhen, bevor Sie sie einem gzip- oder deflate-ähnlichen Algorithmus zuführen. Versuchen Sie Folgendes:
Sortieren Sie die Tupel, wenn möglich, zuerst in aufsteigender Reihenfolge. Verwenden Sie zuerst die abstrakte ID und dann den Zeitstempel. Angenommen, Sie haben viele Messwerte von demselben Sensor, werden ähnliche IDs nahe beieinander platziert.
Wenn die Messungen in regelmäßigen Abständen durchgeführt werden, ersetzen Sie als nächstes den Zeitstempel durch den Unterschied zum vorherigen Zeitstempel (mit Ausnahme des allerersten Tupels für einen Sensor). Zum Beispiel, wenn alle Messungen nach 5 Minuten durchgeführt werden Intervallen ist das Delta zwischen zwei Zeitstempeln normalerweise nahe 300 Sekunden. Das Zeitstempelfeld wird daher viel kompressibler sein, da die meisten Werte gleich sind.
Unter der Annahme, dass die gemessenen Werte zeitlich stabil sind, ersetzen Sie dann alle Messwerte durch ein Delta vom vorherigen Messwert für denselben Sensor. Auch hier sind die meisten Werte nahe bei Null und somit kompressibler.
Außerdem sind Gleitkommawerte aufgrund ihrer internen Darstellung sehr schlechte Kandidaten für die Komprimierung. Versuchen Sie, sie in eine ganze Zahl zu konvertieren. Zum Beispiel erfordern Temperaturmessungen höchstwahrscheinlich nicht mehr als zwei Dezimalziffern. Multiplizieren Sie die Werte mit 100 und runden Sie sie auf die nächste Ganzzahl.
Großartige Antworten, um das festzuhalten, werde ich diejenigen, die ich aufgestockt habe, mit dem Ansatz verschmelzen, den ich schließlich verwende:
Sortieren und reorganisieren Sie die Daten so, dass ähnliche Zahlen nebeneinander liegen, d. e. zuerst nach ID sortieren, dann nach Zeitstempel und neu anordnen von (<int1>, <int2>, <double>), ... nach ([<int1>, <int1> ...], [<int2>, <int2> ... ], [<double>, <double> ...]) (wie von
schnaader und Stephan Leclercq
Verwenden Sie die Delta-Codierung für die Zeitstempel (und möglicherweise für die anderen Werte), wie von schnaader und ididak
Verwenden Sie Protokollpuffer zum Serialisieren (ich werde sie sowieso in der Anwendung verwenden, so dass keine Abhängigkeiten oder irgendetwas hinzugefügt werden). Danke an Marc Gravell für den Hinweis auf mich es.
Tags und Links algorithm compression