Besserer Komprimierungsalgorithmus für Vektordaten?

Question

Ich muss einige räumlich korrelierte Datensätze komprimieren. Derzeit bekomme ich 1,2x-1,5x Kompression mit zlib, aber ich denke, es sollte möglich sein, mehr wie 2x zu bekommen. Die Datensätze haben verschiedene Felder, aber z.B. scheint zlib Probleme zu haben, Listen von Punkten zu komprimieren.

Die Punkte stellen ein Straßennetz dar. Sie sind Paare von 4-Byte-Festkommazahlen der Form XXXXYYYY. Wenn ein einzelner Datenblock 100 Punkte enthält, gibt es in der Regel nur wenige Kombinationen der oberen beiden Bytes von X und Y (räumliche Korrelation). Die unteren Bytes ändern sich jedoch ständig und müssen für zlib wie Zufallsdaten aussehen.

Ebenso haben die Datensätze 4-Byte-IDs, die in der Regel konstante High-Bytes und variable Low-Bytes haben.

Gibt es einen anderen Algorithmus, mit dem diese Art von Daten besser komprimiert werden kann? Ich verwende C++.

bearbeiten : Bitte keine weiteren Vorschläge zur Änderung der Daten selbst. Meine Frage bezieht sich auf automatische Kompressionsalgorithmen. Wenn jemand einen Link zu einer Übersicht über alle gängigen Kompressionsalgorithmen hat, werde ich das als Antwort akzeptieren.

Answer 1

Sie werden wahrscheinlich viel bessere Ergebnisse erzielen, wenn Sie versuchen, die Daten auf der Grundlage Ihres Wissens über ihre Struktur selbst zu komprimieren.

Allzweck-Komprimierungsalgorithmen behandeln Ihre Daten einfach als Bitstrom. Sie suchen nach häufig verwendeten Bitfolgen und ersetzen sie durch kürzere Wörterbuchindizes.

Aber die doppelten Daten werden nicht entfernt. Die duplizierte Sequenz wird kürzer, aber sie wird immer noch genauso oft dupliziert wie vorher.

So wie ich es verstehe, haben Sie eine große Anzahl von Datenpunkten in der Form

XXxxYYYyy, wobei die Großbuchstaben sehr einheitlich sind. Man muss sie also herausrechnen.

Schreiben Sie die Liste so um, dass sie in etwa so aussieht:

XXYY // a header describing the common first and third byte for all the subsequent entries
xxyy // the remaining bytes, which vary
xxyy
xxyy
xxyy
...
XXYY // next unique combination of 1st and 3rd byte)
xxyy
xxyy
...

Jetzt wird jede Kombination der selten variierenden Bytes nur noch einmal aufgelistet und nicht mehr für jeden Eintrag, in dem sie vorkommt, dupliziert. Das bedeutet eine erhebliche Platzersparnis.

Grundsätzlich sollten Sie versuchen, doppelte Daten selbst zu entfernen, bevor Sie sie durch zlib laufen lassen. Sie können das besser machen, weil Sie zusätzliche Kenntnisse über die Daten haben.

Ein anderer Ansatz könnte darin bestehen, diese Koordinaten nicht als absolute Zahlen zu speichern, sondern als Deltas, d. h. als relative Abweichungen von einem Ort, der so gewählt wird, dass er möglichst nahe an allen Einträgen liegt. Ihre Deltas werden kleinere Zahlen sein, die mit weniger Bits gespeichert werden können.

Answer 2

Nicht spezifisch für Ihre Daten, aber ich würde empfehlen, 7zip anstelle von zlib auszuprobieren, wenn Sie können. Ich habe damit lächerlich gute Kompressionsraten gesehen.

http://www.7-zip.org/

Answer 3

Sortieren Sie die Punkte nach einer Art Näherungsmaß, so dass der durchschnittliche Abstand zwischen benachbarten Punkten klein ist. Speichern Sie dann die Differenz zwischen benachbarten Punkten.

Vielleicht gelingt es Ihnen sogar noch besser, die Punkte so zu sortieren, dass die meisten Differenzen sowohl auf der x- als auch auf der y-Achse positiv sind, aber ich kann es nicht mit Sicherheit sagen.

Als Alternative zu zlib gibt es eine Familie von Komprimierungstechniken, die gut funktionieren, wenn die Wahrscheinlichkeitsverteilung zu kleinen Zahlen geneigt ist universelle Codes . Sie müssten für vorzeichenbehaftete Zahlen optimiert werden (kodieren abs(x)<<1 + (x < 0 ? 1 : 0) ).

Answer 4

Ohne die Daten und ihre genaue Verteilung gesehen zu haben, kann ich nicht mit Sicherheit sagen, was die beste Methode ist, aber ich würde vorschlagen, dass Sie jede Gruppe von 1-4 Datensätzen mit einem Byte beginnen, dessen 8 Bits Folgendes anzeigen:

0-1 Anzahl der Bytes der ID, die aus dem vorherigen Datensatz übernommen werden sollen 2-4 Format des Positionssatzes 6-7 Anzahl der aufeinanderfolgenden Datensätze, die das gleiche "Modus"-Byte verwenden

Jeder Positionsdatensatz kann auf eine von acht Arten gespeichert werden; alle anderen Typen außer 000 verwenden vorzeichenbehaftete Verschiebungen. Die Zahl nach dem Bitcode gibt die Größe des Positionsdatensatzes an.

000 - 8 - Zwei volle Vier-Byte-Positionen 001 - 3 - Zwölf Bits für X und Y 010 - 2 - Zehn Bit für X und sechs Bit für Y 011 - 2 - Sechs-Bit-X und Zehn-Bit-Y 100 - 4 - Zwei sechzehn-Bit-Verschiebungen mit Vorzeichen 101 - 3 - Sechzehn-Bit-X- und 8-Bit-Y-Verschiebung mit Vorzeichen 110 - 3 - Acht-Bit-Verschiebung mit Vorzeichen für X; 16-Bit für Y 111 - 2 - Zwei Acht-Bit-Verschiebungen mit Vorzeichen

Ein Modusbyte von Null speichert alle für einen Punkt zutreffenden Informationen ohne Bezug zu einem früheren Punkt, so dass insgesamt 13 Bytes zur Speicherung von 12 Bytes nützlicher Informationen verwendet werden. Andere Modusbytes ermöglichen die Verdichtung von Datensätzen auf der Grundlage der Ähnlichkeit mit früheren Datensätzen. Wenn sich vier aufeinanderfolgende Datensätze nur im letzten Bit der ID unterscheiden und entweder X und Y innerhalb von +/- 127 des vorherigen Datensatzes liegen oder X innerhalb von +/- 31 und Y innerhalb von +/- 511 oder X innerhalb von +/- 511 und Y innerhalb von +/- 31, dann können alle vier Datensätze in 13 Byte gespeichert werden (durchschnittlich 3,25 Byte pro Datensatz, was einer Platzersparnis von 73 % entspricht).

Für die Komprimierung kann ein "gieriger" Algorithmus verwendet werden: Man untersucht einen Datensatz, um zu sehen, welche Größe ID und XY in der Ausgabe verwendet werden müssen, und nimmt dann bis zu drei weitere Datensätze auf, bis einer gefunden wird, der entweder nicht zu den vorherigen Datensätzen mit den gewählten Größen "passt" oder kleiner geschrieben werden könnte (man beachte, dass, wenn z.B. der erste Datensatz X- und Y-Verschiebungen hat, die beide gleich 12 sind, die XY mit zwei Bytes geschrieben werden würde, aber bis man die folgenden Datensätze liest, wüsste man nicht, welches der drei Zwei-Byte-Formate zu verwenden ist).

Bevor Sie Ihr Format in Stein meißeln, würde ich vorschlagen, Ihre Daten durchlaufen zu lassen. Es kann sein, dass eine kleine Anpassung (z. B. die Verwendung von 7+9 oder 5+11 Bit-Formaten anstelle von 6+10) viele Daten besser verpacken würde. Die einzige Möglichkeit, das herauszufinden, ist, zu sehen, was mit Ihren echten Daten passiert.

Answer 5

Es sieht so aus, als ob die Burrows-Wheeler-Transformation könnte für dieses Problem nützlich sein. Es hat die eigenartige Tendenz, sich wiederholende Bytes aneinander zu reihen, wodurch zlib besser komprimiert werden könnte. Dieser Artikel schlägt vor, dass ich andere Algorithmen als zlib mit BWT kombinieren sollte.

Intuitiv hört sich das teuer an, aber ein Blick auf den Quellcode zeigt, dass die Rückwärts-BWT O(N) ist, mit 3 Durchläufen über die Daten und einem moderaten Speicherplatz-Overhead, was sie wahrscheinlich schnell genug auf meiner Zielplattform (WinCE) macht. Die Vorwärtstransformation ist ungefähr O(N log N) oder etwas darüber, wenn man einen gewöhnlichen Sortieralgorithmus annimmt.