Kompression für eine einzigartige Datenstrom

Question

Ich habe eine große Anzahl von integer-arrays.Jeder hat ein paar tausend Ganzzahlen in es, und jede ganze Zahl ist im Allgemeinen die gleiche wie die vor oder es ist verschiedenen von nur einem einzigen bit-oder zwei.Ich möchte schrumpfen die einzelnen array-down so klein wie möglich zu reduzieren, meine disk-IO.

Zlib schrumpft es auf etwa 25% seiner ursprünglichen Größe.Das ist nett, aber ich glaube nicht, dass der Algorithmus ist besonders gut geeignet für die problem.Kennt jemand eine compression library oder einfacher Algorithmus, der möglicherweise besser für diese Art von Informationen?

Update:zlib nach dem umwandeln in ein array xor-deltas schrumpft es auf etwa 20% der ursprünglichen Größe.

Answer 1

Wenn die meisten der ganzen Zahlen wirklich die gleichen wie zuvor sind, und die Inter-Symbol-Differenz kann in der Regel als ein einzelnes Bit-Flip ausgedrückt werden, das klingt wie ein Job für XOR.

Nehmen Sie einen Eingabestrom wie:

1101
1101
1110
1110
0110

und Ausgang:

1101
0000
0010
0000
1000

ein bisschen Pseudo-Code

compressed[0] = uncompressed[0]
loop
  compressed[i] = uncompressed[i-1] ^ uncompressed[i]

Wir haben jetzt die meisten der Ausgang auf 0 reduziert, auch wenn ein hoher Bit geändert wird. Die RLE-Komprimierung in jedem anderen Werkzeug, das Sie mit diesem einen großen Tag verwenden. Es wird noch besser funktioniert auf 32-Bit-Integer, und es kann immer noch eine radikal andere ganze Zahl Aufspringen im Stream kodieren. Sie sparte die Mühe mit der Behandlung selbst Bit-Verpackung, wie alles, was ein int große Menge bleibt.

Wenn Sie möchten, dekomprimieren:

uncompressed[0] = compressed[0]
loop
  uncompressed[i] = uncompressed[i-1] ^ compressed[i]

Dies hat auch den Vorteil eines einfachen Algorithmus zu sein, die wirklich laufen wird, sehr schnell, da es nur XOR ist.

Answer 2

Haben Sie darüber nachgedacht, Run-Length Encoding ?

oder diese versuchen: Anstatt die Zahlen selbst zu speichern, speichern Sie die Unterschiede zwischen den Zahlen. 1 1 2 2 2 3 5 wird 1 0 1 0 0 1 2. Jetzt sind die meisten der Zahlen, die Sie haben zu kodieren sind sehr klein. Um eine kleine ganze Zahl zu speichern, verwenden Sie einen 8-Bit-Integer anstelle der 32-Bit, die Sie auf den meisten Plattformen kodieren werden. Das ist ein Faktor 4 recht. Wenn Sie größere Lücken als die vorbereitet brauchen werden, bezeichnen die High-Bit des 8-Bit-Integer zu sagen, „diese Zahl in den nächsten 8 Bits erfordert als auch“.

Sie können das kombinieren mit einer Lauflängencodierung für eine noch bessere Kompressionsraten, abhängig von Ihren Daten.

Keine dieser Optionen ist besonders schwer zu implementieren, und sie alle laufen sehr schnell und mit sehr wenig Speicher (im Gegensatz zu, sagen wir, bzip).

Answer 3

Sie möchten, dass Ihre Daten vorverarbeitet - verwandeln sie reversibel in irgendeiner Form, die auf Ihre Back-End-Datenkompressionsverfahren besser geeignet ist, zuerst. Die Details werden hängen sowohl von den Back-End-Kompressionsverfahren, und (kritische) auf den Eigenschaften, die Sie von den Daten erwarten Sie komprimieren.

In Ihrem Fall zlib ist eine byteweise Komprimierungsmethode, aber Ihre Daten kommen in (32-Bit?) Ganze Zahlen sind. Sie müssen nicht selbst neu zu implementieren zlib, aber Sie müssen auf lesen, wie es funktioniert, so können Sie herausfinden, wie es zu präsentieren mit leicht komprimierbaren Daten, oder wenn es überhaupt für Ihre Zwecke geeignet ist.

Zlib implementiert eine Form von Lempel-Ziv-Codierung. JPG und viele andere verwenden Huffman für ihre Back-End-Codierung. Lauflängencodierung ist beliebt für viele Ad-hoc-Anwendungen. Etc., etc. ...

Answer 4

Vielleicht ist die Antwort zu pre-filter arrays in einer Weise Analog zu der Filtern verwendet, um zu erstellen, kleine PNG-Bilder.Hier sind einige Ideen, die Rechte aus der Spitze von meinem Kopf.Ich habe nicht versucht, diese Ansätze, aber wenn du Lust zu spielen, Sie interessant sein könnte.

1. Brechen Sie Ihre ints, jede in 4 Byte, so dass ich₀, ich₁, ich₂, ..., ich_n wird b_0,0, b_0,1, b_0,2, b_0,3, b_1,0, b_1,1, b_1,2, b_1,3, ..., b_n,0, b_n,1, b_n,2, b_n,3.Dann schreiben Sie all die b_i,0s, gefolgt von der b_i,1s, b_i,2s und b_i,3en.Wenn die meisten der Zeit, Ihre zahlen unterscheiden sich nur durch ein bit-oder zwei, Sie sollten Holen schöne lange läuft der wiederholten bytes komprimieren soll wirklich schön, mit so etwas wie Run-length-Kodierung oder zlib.Dies ist mein Favorit der Methoden, die ich präsentieren.

2. Wenn die zahlen in jedem array sind eng Verwandte zu die davor, Sie könnte vielleicht store der ursprünglichen ganzen Zahl, gefolgt von diffs gegen den vorherigen Eintrag - diese sollte eine kleinere Menge von Werten zu zeichnen, die in der Regel Ergebnisse in einer kompakteren form.

3. Wenn Sie verschiedene bits unterschiedlich, Sie vielleicht noch ziemlich große Unterschiede, aber wenn Sie mehr sind wahrscheinlich zu großen numerischen Unterschiede entsprechen (in der Regel) ein oder zwei bits unterschiedlich, Sie können es besser mit einem Schema, in dem Sie erstellen ahebyte array - nutzen Sie die ersten 4 bytes zu codieren, die erste ganze Zahl, und dann für jede nachfolgende Eingabe, verwenden Sie 0 oder mehr bytes, um anzugeben, welche bits sollten umgedreht werden und - Speicherung 0, 1, 2, ..., oder 31 in byte, mit einer Wächter (sage 32), um anzuzeigen, wenn Sie fertig sind.Dies kann dazu führen, die rohe Anzahl der bytes, die benötigt werden, um zu repräsentieren und integer etwas in der Nähe von 2 im Durchschnitt, die meisten bytes aus einem begrenzten Satz (0 - 32).Führen, dass Strom durch zlib, und vielleicht werden Sie angenehm überrascht sein.

Answer 5

Haben Sie versucht bzip2 für dieses? http://bzip.org/

Es ist immer besser als zlib für mich.

Answer 6

Da Ihr Anliegen ist Disk IO zu reduzieren, werden Sie wollen jeden Integer-Array unabhängig zu komprimieren, ohne auf andere Integer-Arrays unter Bezugnahme.

Eine übliche Technik für Ihr Szenario ist es, die Unterschiede zu speichern, da eine kleine Anzahl von Differenzen mit kurzen Codeworten codiert werden. Es klingt wie Sie mit Ihrem eigenen Kodierungsschema für Unterschiede kommen müssen, da sie Multibit-Unterschiede sind vielleicht ein 8-Bit-Byte in etwa so als Ausgangspunkt verwendet wird:

• 1 Bit, um anzuzeigen, dass eine vollständige neue Ganzzahl folgt, oder dass dieses Byte kodiert für einen Unterschied von der letzten ganzen Zahl,
• 1 Bit, um anzuzeigen, dass es mehr Bytes folgen, mehr einzelne Bit Unterschiede für die gleiche ganze Zahl aufnehmen.
• 6 Bits, die die Bit-Zahl aufzuzeichnen von Ihrem bisherigen integer zu wechseln.

Wenn es mehr als 4 Bits verschieden ist, dann die ganze Zahl speichern.

Dieses Schema möglicherweise nicht angemessen sein, wenn Sie auch eine Menge völlig verschiedenen Codes haben, da sie 5 Bytes jeder nehmen nun statt 4.

Answer 7

„Zlib schrumpft es um einen Faktor von etwa 4-fach.“ nimmt eine Datei von 100K nun bedeutet, dass negativ 300K; das ist ziemlich beeindruckend von jeder Definition :-). Ich nehme an, Sie meinen es schrumpft es um 75%, das heißt, auf 1/4 seiner ursprünglichen Größe.

Eine Möglichkeit für eine optimierte Kompression ist wie folgt (eine ganze Zahl ist 32 Bit annimmt und höchstens 3 Bits von Element zu Element zu ändern).

• Ausgabe die erste Ganzzahl (32 Bits).
• Ausgabe der Anzahl der Bitänderungen (n = 0-3, 2 Bits).
• Output n Bit-Spezifizierer (0-31, 5 Bits jeweils).

Im schlimmsten Fall für diese Kompression 3 Bitänderungen in jeder ganzen Zahl (2 + 5 + 5 + 5 Bits), die in Richtung der ursprünglichen Größe 17/32 neigen wird (46,875% Kompression).

Ich sage „tendiert zu“, da die erste ganze Zahl immer 32 Bit ist aber für jede anständige Größe Array, die erste ganze Zahl wäre vernachlässigbar.

Im besten Fall ist eine Datei mit identischen Zahlen (keine Bit-Änderungen für jede ganze Zahl, nur die zwei Null-Bits) - dies wird dazu neigen, in Richtung 2/32 Originalgröße (93,75% Kompression)

.

Wenn Sie durchschnittlich 2 Bits pro verschiedene aufeinanderfolgende ganze Zahl (wie Sie sagen, ist Ihr allgemeiner Fall), werden Sie 2 erhalten + 5 + 5 Bits pro ganze Zahl, die auf 12/32 oder 62,5% Kompression neigen wird.

Ihre Break-even (wenn zlib 75% Kompression gibt) ist 8 Bit pro ganze Zahl, die

sein würde,

• Einbit-Änderungen (2 + 5 = 7 Bits.): 80% der Übergänge
• double-Bit-Änderungen (2 + 5 + 5 = 12 Bits.): 20% der Übergänge

Dies bedeutet, dass Ihr Durchschnitt 1,2 Bit Änderungen pro integer sein müßte dies lohnt.

Eine Sache, ich würde vorschlagen, Blick ist 7zip - dies hat eine sehr liberale Lizenz und Sie können es mit Ihrem Code verknüpfen (ich glaube, die Quelle als auch verfügbar ist)

.

Ich bemerke (für meine Sachen sowieso) führt es viel besser als WinZip auf einer Windows-Plattform, so kann es auch outperform zlib.