Bester Komprimierungsalgorithmus? (Siehe unten für die Definition der besten)

Question

ich eine Liste der folgenden Tupel in einem komprimierten Format gespeichert werden soll, und ich habe mich gefragt, welchen Algorithmus gibt mir

• kleinste komprimierte Größe
• schnellste de/Kompression
• tradeoff Optimum ("Knie" der Kompromißkurve)

sieht Meine Daten wie folgt aus:

(<int>, <int>, <double>), 
(<int>, <int>, <double>), 
... 
(<int>, <int>, <double>) 

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 von großem Nutzen.

Answer 1

Da die "Zeit" -Ints nahe beieinander sein können, versuchen Sie, nur die erste zu speichern und speichern Sie danach die Differenz im Int-Wert (Delta-Codierung). Sie können dasselbe auch für den zweiten Int versuchen.

Eine andere Sache, die Sie versuchen können, ist, die Daten von [int1, int2, doppelt], [int1, int2, doppelt] ... zu [int1, int1 ...], [int2, int2 ... zu reorganisieren ... ], [doppelt, doppelt ...].

Um den Kompressionsbereich zu ermitteln, in dem sich Ihr Ergebnis befindet, können Sie Ihre Daten in eine Datei schreiben und den Kompressor CCM von Christian Martelock here herunterladen. Ich fand heraus, dass es für solche Datensammlungen sehr gut funktioniert. Es verwendet einen ziemlich schnellen context mixing 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.

Answer 2

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. Eines davon ist Google protocol buffers.

Zum Beispiel in C# mit protobuf-net, können Sie einfach eine Klasse erstellen, um die Daten zu halten:

[ProtoContract] 
public class Foo { 
    [ProtoMember(1)] 
    public int Value1 {get;set;} 
    [ProtoMember(2)] 
    public int Value2 {get;set;} 
    [ProtoMember(3)] 
    public double Value3 {get;set;} 
} 

Dann einfach [de] serialisiert eine Liste oder Foo [] usw., über die ProtoBuf.Serializer Klasse .

Ich behaupte nicht, dass es wird ganz so platzsparend wie Ihre eigenen rollen, aber es wird ziemlich 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 einfach zu verwenden ist, da es Protokollpufferimplementierungen für various languages gibt. Es verwendet auch viel weniger CPU als normale Komprimierung (GZip/DEFLATE/etc) und/oder Xml-basierte Serialisierung.

Answer 3

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:

Zuerst, wenn möglich, sortieren Sie die Tupel in aufsteigender Reihenfolge. Verwenden Sie zuerst die abstrakte ID und dann den Zeitstempel. Angenommen, Sie haben viele Messwerte vom selben Sensor, werden ähnliche IDs nahe beieinander platziert.

Als nächstes, wenn die Messungen in regelmäßigen Abständen vorgenommen werden, den Zeitstempel durch den Unterschied zum vorherigen Zeitstempel ersetzen (mit Ausnahme des allerersten Tupels für einen Sensor, natürlich.) Zum Beispiel wenn alle Messungen bei 5 vorgenommen werden In Minutenintervallen liegt das Delta zwischen zwei Zeitstempeln normalerweise bei 300 Sekunden. Das Zeitstempelfeld wird daher viel kompressibler sein, da die meisten Werte gleich sind.

Dann unter der Annahme, dass die gemessenen Werte zeitlich stabil sind, alle Messwerte durch ein Delta vom vorherigen Messwert für denselben Sensor ersetzen. 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.

Answer 4

Hier ist ein gemeinsames Schema, das in den meisten Suchmaschinen verwendet wird: Speichern von Deltawerten und Codieren des 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 nicht die beste Komprimierungsrate, aber normalerweise die schnellste für die Codierung/Decodierung Durchsatz.

Answer 5

sortieren, wie bereits vorgeschlagen, dann speichern

(erstes ints) (zweiter ints) (doppelte)

transponierte Matrix. Dann komprimiert

Answer 6

Große Antworten, für die Aufzeichnung, ich werde diejenigen fusionieren ich in den Ansatz upvoted ich schließlich mit:

1. sortieren und reorganisieren die Daten so, dass ähnliche Zahlen sind neben einander, ich. e. sortiert nach id zuerst, dann von Zeitpunkt und neu anordnen (<int1>, <int2>, <double>), ...-([<int1>, <int1> ...], [<int2>, <int2> ... ], [<double>, <double> ...]) (als

2. auf der Zeitstempel-Delta-Codierung verwendet durch schnaader und Stephan Leclercq vorgeschlagen (und vielleicht auch auf den anderen Werten), wie durch schnaader und ididak vorgeschlagen

3. verwenden Protokoll-Puffer serialisiert (ich werde sie in der Anwendung trotzdem verwenden, das ist so nicht gehen zu Abhängigkeiten oder etwas hinzufügen) Dank Marc Gravell für mich zeigt. zu.