Komprimierung eines 2D-Punktsatzes - Ideen?

Question

Komprimierung eines 2D-Punktsatzes - Ideen?

8

Ich habe eine Reihe von 2D-Punkten in einem Array gespeichert. Ich muss es so viel wie möglich komprimieren. Am besten schnell, aber kein Deal Breaker, Kompressionsrate ist das Ziel. Die Regeln sind:

ein Punkt = eine 32-Bit-Struktur, gespeichert als (x, y), 2 Bytes für jede Koordinate
a coordinate = ein "float" mit 8 Bits ganzzahligem Teil, 8 Bits Bruchteil

Spezielle Eigenschaften:

Ich kann die Reihenfolge der Punkte ändern, wie ich es für richtig halte
Ich habe die Punkte in der Reihenfolge der ganzzahligen Teile ihrer x und y, vielleicht kann ich das ausnutzen, aber die Nachkommastellen sind ziemlich zufällig von dem, was ich gesehen habe
Das Array, das ich erhalte, ist zusammenhängend (aus Sicht des Speichers)

Was ich bisher erforscht habe:

betrachte sie als einfache Ganzzahlen (32 Bit), sortiere sie (die Reihenfolge ist meine, um sie zu wählen), dann komprimiere sie wie in diese Frage .
Betrachte mein Array als einfache Zeichenkette und wende dann eine Burrows-Wheeler-Transformation an ( BWT) mit Lauflängencodierung oder Huffman
Behandle mein Array als einfache Binärdaten und wende dann ein LZW

Ich habe es nur geschafft, Huffman und BWT zu implementieren, aber keiner von beiden gibt mir eine gute Komprimierungsrate (oder verwende die Haupteigenschaft meines Datensatzes). Ich werde heute die erste Option versuchen.

Ich bin mir sicher, dass es bessere Ideen gibt. Hast du welche? Bist du auf etwas Ähnliches gestoßen und hast etwas wirklich gutes umgesetzt?

Beispiel für ein Dataset, in hex:

%Vor%

wo z.B. das Teilchen 15 67 03 73 (letzte Reihe) bedeutet Teilchen bei x = 15 und 67/256, y = 3 und 73/256. Wie Sie sehen, sind die Daten etwas geordnet, aber die Nachkommastellen sind völlig unzusammenhängend.

algorithm arrays c++ compression

webuster 20.04.2015, 10:41

quelle

2 Antworten

Tags und Links algorithm arrays c++ compression

Django: Verwenden von Annotate, Count und Distinct in einem Queryset Fehler beim Verbinden mit Sybase von VBScript - interner Fehler in der Client-Bibliothek

score 3 · Answer 1

Erste Option von OP ist geeigneter. Aber es kann weiter verbessert werden.

Koordinaten als 16-Bit-Ganzzahlen neu interpretieren.
Transformieren Sie Punktpositionen in Entfernungen entlang der Hilbert-Kurve (oder einer anderen raumfüllenden Kurve).
Sortieren Sie Entfernungen und wenden Sie dann die Delta-Codierung an (berechnen Sie die Differenzen benachbarter Entfernungen).
Abhängig von den Voreinstellungen für Komprimierung / Geschwindigkeit, (a) verwende etwas wie Elias oder Golomb-Codes (am schnellsten), (b) benutze Huffman-Kodierung oder (c) verwende etwas wie arithmetische Kodierung (beste Kompressionsrate).

Wenn es ein Muster in der Punkteverteilung gibt, könnten Sie für Schritt 4 erweiterte Kompressoren ausprobieren: LZ *, BWT oder PPM.

Hier sind die Ergebnisse des experimentellen Vergleichs für die in Schritt 4 verwendeten Methoden. Worst-Case-Szenario wird angenommen: Punkte sind zufällig im Bereich 00.00 .. FF.FF gleichmäßig verteilt (so dass die einzige Kompressionsmöglichkeit ist, Informationen über ihre Reihenfolge zu verlieren ). Alle Ergebnisse werden für 250000 Punkte berechnet:

%Vor%

Ich habe die Huffman-Codierung nicht versucht. FSE ist eine Methode, die der arithmetischen Codierung ähnelt. Zahlen nach dem Methodennamen zeigen Konfigurationsparameter: für Elias-Codierung - wie viele Bits werden für die Kodierung der einzelnen Bits verwendet, für die Golomb-Kodierung - wie viele niedrigstwertige Bits bleiben unkomprimiert, für FSE - wie viele höchstwertige Bits sind komprimiert (zusammen mit Bitlänge) ).

Alle Ergebnisse wurden von dieser Quelle produziert: Ссылка

score 1 · Answer 2

Verschachteln Sie die Bits, die die X- und Y-Koordinaten jedes Punktes darstellen, sortieren und komprimieren.

Zum Beispiel, wenn Sie den Punkt (X, Y) durch die zwei 16-Bit-Zahlen dargestellt haben

(X ₁₅ X ₁₄ X ₁₃ X ₁₂ X ₁₁ X ₁₀ X ₉ X ₈ X ₇ X ₆ X ₅ X _{4 <3> X X , Y ₁₅ Y ₁₄ Y ₁₃ Y ₁₂ Y ₁₁ Y ₁₀ Y ₉ Y ₈ Y ₇ Y ₆ Y ₅ Y < sub> 4 <3> <2}

Konvertiere es in die folgende 32-Bit-Nummer:

X ₁₅ Y ₁₅ X ₁₄ Y ₁₄ X ₁₃ Y < sub> 13 X ₁₂ Y ₁₂ X ₁₁ Y ₁₁ X ₁₀ Y & sub0; 10X & sub9; Y9XX8Yx8X _{Y & sub0; > 7 X <6> X5 <5> > X _{4 <4> <3 <3 2 X 1 X 1 X X 0 Y 0 0}}

Dies würde Vorteile aus jedem Clustering ziehen, das in den Daten erscheinen könnte, da nahe physisch nahe Punkte in nahen Positionen auf der sortierten Liste erscheinen und ihre Repräsentationen ihre Kopfbits teilen.

Aktualisieren : Der Punkt besteht darin, nahe Punkte in der Nähe von Positionen zu sortieren. Wenn Sie X- und Y-Bits mischen, erhalten Sie das, was zu langen Folgen von 32-Bit-Ganzzahlen führt, die identische Werte in ihren Kopf-Bits haben. Wenn Sie dann Deltas machen, werden Sie kleinere Werte haben, wenn Sie nur nach X und dann nach Y sortieren (oder umgekehrt).

Die Sache ist, dass Sie es dann als einen k-d Baum betrachten können, jedes Bit teilt den Raum (links / rechts oder oben / unten). Für die ersten Ebenen können Sie komprimieren und dann einfach sagen, wie viele Elemente es auf einer Seite gibt, bis Sie mit nur wenigen Elementen zu den Polen gelangen, die Sie durch explizite Angabe der verbleibenden paar Bits darstellen können. Für die beste Komprimierung müssen Sie die arithmetische Codierung verwenden.