Bit-Packing/Byte-Packing (Kompressions-Vorstufe)

[BeRsErKeR]

Bit- und Byte-Packing

Ich möchte hier einen kleinen Algorithmus vorstellen, um bestimmte Daten so zu transformieren, dass sie in einem nachfolgenden Schritt effizienter komprimiert werden können.

Ich bin mir fast sicher, dass dieser Algorithmus bereits Verwendung findet, ich konnte aber bisland nichts dazu finden. Wahrscheinlich weil er normalerweise einen anderen Namen hat oder allgemeiner formuliert wird. Ich habe auch gesehen, dass es andere Algorithmen mit dem Namen Bit-Packing gibt, die aber mit diesem hier vorgestellten Algorithmus nichts gemein haben.

Wenn jemand diesen Algorithmus kennt, wäre es nett wenn ihr mir den Namen sagt. Vielleicht auch ein Link oder so.

Prinzipiell handelt es sich um eine Umsortierung von Bits (Bit-Packing) oder Bytes (Byte-Packing). Ein Vorteil des Algorithmuses ist, dass theoretisch keine Zusatzinformationen nötig sind, sofern man von bestimmten Optionen wie "Aktivieren/Deaktivieren" oder variabler Range (siehe unten) absieht, die aber nicht notwendig sind.


Grobe Funktionsweise:

Der Algorithmus nimmt einen beliebig großen Datenstrom (n Bytes) und konvertiert ihn in einen Datenstrom gleicher Größe. Alle Informationen des Eingabe-Datenstroms sind auch im Ausgabe-Datenstrom in gleicher Form enthalten, aber an anderer Stelle.

Der Ausgabe-Datenstrom lässt sich in vielen Fällen (vorallem aber bei ASCII-Text, unkomprimierten Bild- und Audiodaten, usw) besser komprimieren - vorallem mit Hilfe von RLE.


Allgemeine Formulierung:

Kodierung

Eingabe: Datenstrom D, Range R
Ausgabe: Konvertierter Datenstrom K

1. Der Datenstrom D wird in Teile der Länge R zerlegt (beim Bit-Packing mit R=8 entspricht dies vollen Bytes).
2. Jedes n-te Bit oder Byte eines jeden Teils wird im Ziel-Datenstrom K mit den n-ten Bits/Bytes anderer Teile zusammen gelegt, wobei gilt: n=0..(R-1).


Dekodierung

Eingabe: Konvertierter Datenstrom K, Range R (muss identisch sein zu R bei der Kodierung)
Ausgabe: Dekodierter Datenstrom D

1. Der Datenstrom K wird in R gleichgroße Teile zerlegt (Größe = Datenstromgröße / R).
2. Jedes n-te Bit/Byte eines dieser Teile entspricht dem x-ten Bit/Byte im n-ten Ziel-Teil der Größe R im Ziel-Datenstrom D, wobei gilt: x=0..(R-1).


Vereinfachte Formulierung / Spezialfälle:

Eine gute Komprimierung wird beim Bit-Packing mit R=8, R=16, R=24 oder R=32 erzielt. Beim Byte-Packing mit R=2, R=3 oder R=4.

Ein Bit-Packing mit R=8 bewirkt vereinfacht gesagt das Zusammenlegen der n-ten Bits der Eingabe-Bytes im Ziel-Datenstrom. Dies ist bei ASCII-Text effektiv, da dort das höchstwertige Bit immer 0 ist und somit n 0-Bits im Ziel-Datenstrom hintereinander liegen (wobei n die Anzahl der Zeichen bzw. die Größe des Eingabe-Datenstroms in Byte ist). Ein Text aus 80 ASCII-Zeichen hätte also mindestens 80 0-Bits in Folge, was 10 0-Bytes entspricht. Diese können sehr gut RLE-kodiert werden. Grob gesagt spart man hier in jedem Fall rund 1/8 der Datenmenge unabhängig von der Zufälligkeit der Zeichen und ohne Entropiekodierung. Auch für Grafiken kann dies nützlich sein, da oft ähnliche Farbkomponenten nebeneinander liegen und somit z.B. häufig höherwertige Bits identisch sind. Die RLE-Effizienz von Bereichen, die nur aus 0en oder 255en bestehen, wird nicht vermindert, aber die RLE-Effizienz von anderen Bereichen. Kombiniert mit einem Byte-Packing mit R=3 oder R=4 kann hier teilweise noch mehr rausgeholt werden.

Ein Byte-Packing mit R=3 oder R=4 eignet sich sehr gut für 24Bit- oder 32Bit-Bitmaps. Letzteres aber auch für Daten, die viele DWORDs enthalten. Ein Byte-Packing mit R=2 kann sich für Daten eignen, die viele WORDs enthalten, usw. Das liegt daran, dass WORD- bzw. DWORD-Werte oft in bestimmten Wertebereichen vorliegen und häufig höherwertige Bytes 0 sind, die dann durch das Byte-Packing im Zieldatenstrom zusammen liegen und gut RLE-kodiert werden können.

Als Beispiel sei hier eine 24Bit-Bitmap mit nur einer Farbe, nämlich Magenta, genannt (sehr extremes Beispiel zur Veranschaulichung). Ein Pixel wird durch 3 Bytes repräsentiert: r=255, g=0, b=255. Wird hier normales Byte-RLE ohne Byte- oder Bit-Packing angewandt, so wäre es nicht effektiv, da der Datenstrom diese Form hat:

255 0 255 255 0 255 255 0 255 ...

Mit einem Byte-Packing mit R=3 würde diese Sequenz so aussehen:

255 255 255 ... 0 0 0 ... 255 255 255 ...

Die Daten sind nun sehr effizient RLE-kodierbar. Bei 100 Pixeln wäre z.B. folgende Repräsentation möglich:

255 100 0 100 255 100

Aus 300 Bytes würden dadurch 6 Bytes werden. Wie gesagt ist das ein Extrembeispiel zur Veranschauung.

In diesem Fall wäre ein weiteres Bit-Packing nicht effizient, wobei es dafür auch gute Anwendungsfälle gibt.


Zusatzdaten:

Wie angesprochen benötigt man nur dann Zusatzdaten, wenn man z.B. die Information mitgeben will, dass das Bit- oder Byte-Packing durchgeführt wurde (1 Bit) oder wenn man eine variable Range angeben will. Die Range ist in der Regel aber auch sehr begrenzt.

Bei Komprimierungen wo z.B. immer 8-Bit Bit-Packing durchgeführt wird braucht man keinerlei Zusatzinfo, d.h. durch das Bit-Packing werden die Ausgangsdaten für die Komprimierung nicht vergrößert.

[DerAlbi]

Hallo, ich habe leider auch keinen Namen für das Verfahren anzubieten, aber ich habe soetwas für Bitmaps auch schonmal probiert.
Ich vermute, dass du neben dem Namen hier auch Feedback wünschst, deswegen gibt es von mir prompt einen Verbesserungsvorschlag:

Jede nachfolgende Entropiekodierung profitiert von einem ausgeprägten ungleichgewicht zwischen 0/1 - das weißt du vermutlich selbst. Es liegt daher auf der Hand den erzeugten Datenstrom noch weiter zu beeinflussen, indem du z.B. dessen Ableitung speicherst, was die den Schwerpunkt der Häufigkeitsverteilung nochmehr auf die bin. 0 legt bzw spiegelt.
Der gedanke dabei ist, dass du die aufeinanderfolgenden bits verXORst und das ganze inkl einem Startwert abspeicherst.

Aus
0011111000011110001011101000011111110 //16x '0', 21x '1' wird
0010000100010001001110011100010000001 //25x '0', 12x '1'
was bereits ein weniger guter fall ist, wie ich finde

Das eigentlich Tolle: im elektrotechnischen Sinne 'niederfrequente' Bits (seltene Änderung, also wahrscheinlich die Ansammlung aller höherwertigen Bits am Anfang des umsortieren Datenstroms) werden nach dieser Behandlung stark zu '0' tendieren und 'hochfrequente' bits (die LSBs z.B.) werden überwiegend zu '1' tendieren. Und: ist das 'Spektrum' suboptimal, wird es insgesamt nicht schlechter, denn eine Ableitung verwirft nur den Gleichanteil.

Interessant stelle ich mir auch die höheren Ableitungen vor, weil dort zum nachteil von 'niederfrequenten' Mustern, 'hochfrequente' muster zu blöcken zusammenlaufen. Und der Nachteil für 'niederfrequente' Muster ist in sofern nicht all zu dramatisch, da sich feste bitmuster an den Sprungstellen bilden.

2. Ableitung:
0011000110011001101011010010011000001 (man sieht nun bei niederfrequenzen die '11' kombination dominant)
3. Ableitung:
0010100101010101011110111011010100001
0011110111111111110001100110111110001 (4)
0010001100000000001001010101100001001 (5)
...

Wie man sieht bilden bestimte Ableitungen bei bestimten Frequenzverteilungen verschiedene Muster. hier im Beispiel verleitet z.B. die 3. Ableitung zum XOR 0x55, da sich bestimte Wiederholraten in dieser Ableitung als Alternierend 0/1 ausbilden.

Das tolle: je nach Eingangsdaten, kann man je nach original Bitposition im Byte die dominante Frequenz schätzen / ermitteln. (MSBs sind z.B. niederfrequenz bei Bitmaps und Wave...)

evtl ist das eine kleine Anregung, bei sowas kann man sich ja totoptimieren. evtl ist es aber auch keiner Aufmerksamkeit würdig^^

[Alexander Kornrumpf]

Aber allgemeingültig kann das ja nicht sein, sonst würden die Kompressionsalgorithmen das machen, oder?

[Artificial Mind]

Aber allgemeingültig kann das ja nicht sein, sonst würden die Kompressionsalgorithmen das machen, oder?

PNG nutzt verschiedene erste Ableitungen, heißen dort "Filter".

[Alexander Kornrumpf]

Aber allgemeingültig kann das ja nicht sein, sonst würden die Kompressionsalgorithmen das machen, oder?

PNG nutzt verschiedene erste Ableitungen, heißen dort "Filter".

Was ich meinte ist: Wenn es einen Preprocessing Schritt gäbe, der vor einem gegebenen Kompressionalgo immer sinnvoll ist, dann wäre der vermutlich Teil des Algorithmus. Oder wenn man da Haare spalten will: Die gängigen implementierungen des Algorithmus würden auch das Preprocessing implementieren. Insofern kann dieses Preprocessing doch nur sinnvoll sein, wenn man entweder mehr über seine Daten weiß als der generische Algorithmus, oder der Algorithmus selbst ziemlich naiv ist.

[Schrompf]

Ich glaube, es ist allen Beteiligten von vornherein klar, dass man damit nicht die Entropie umschiffen kann. Das alles dürfte nur für Daten funktionieren, bei denen man anhand von Kontextwissen bestimmte Eigenschaften voraussetzen kann. PNG tut das mit seinen Filtern und den üblichen Bildinhalten im Hinterkopf, und Berserker hat sicher auch bestimmte Daten dazu im Ohr.

[BeRsErKeR]

Ganz genau Schrompf. Es ist klar, dass das nur für bestimmte Daten sinnvoll ist. Beispiele hatte ich ja bereit genannt. Ich nutze dieses Preprocessing nur für Daten, wo eine deutliche Verbesserung der Komprimierung erzielt wird. Bei mir kann wahlweise eine Daten-Analyse vorgenommen werden und das Bit- und Byte-Packing aktiviert oder deaktiviert werden. Man könnte es ggf. auch von bestimmten Dateitypen abhängig machen.

Vielen Dank erstmal für das Feedback. Gerade das mit den Ableitungen sieht recht interessant aus. Da werde ich mich mal mit beschäftigen. :)

[antisteo]

Bitpacking ist inzwischen ein alter Schuh.

Ich kenne ein Kompressionsverfahren (und habe es auch implementiert), bei dem man Bits auch mit weniger als einem Bit packen kann. Das einzige, was man dazu braucht, ist die Wahrscheinlichkeit für jedes Bit, dass es 1 ist als Bruch (Zähler, Nenner). Mittels eines Modulo-Verfahren kann man dann die Bits so in einen Stream schreiben, dass z.B. wenn die 0 viel häufiger vorkommt, eine 0 nur 0,3 Bits Platz in Anspruch nimmt, während eine 1 dann ganze 2 Bits braucht. Anzuwenden ist das Verfahren vor allem, um besser als Huffman zu kodieren, der ja immer ganze Bits verschwendet.

[Chromanoid]

http://code4k.blogspot.com/2010/12/crin ... table.html ist vielleicht ganz interessant dazu. Bezieht sich auf Exe-Kompression vom Crinkler.

[Alexander Kornrumpf]

Bitpacking ist inzwischen ein alter Schuh.

Ich kenne ein Kompressionsverfahren (und habe es auch implementiert), bei dem man Bits auch mit weniger als einem Bit packen kann. Das einzige, was man dazu braucht, ist die Wahrscheinlichkeit für jedes Bit, dass es 1 ist als Bruch (Zähler, Nenner). Mittels eines Modulo-Verfahren kann man dann die Bits so in einen Stream schreiben, dass z.B. wenn die 0 viel häufiger vorkommt, eine 0 nur 0,3 Bits Platz in Anspruch nimmt, während eine 1 dann ganze 2 Bits braucht. Anzuwenden ist das Verfahren vor allem, um besser als Huffman zu kodieren, der ja immer ganze Bits verschwendet.

Das ist jetzt ein Trollversuch oder?

[Artificial Mind]

Ich glaub einfach, dass dort die Zusammenhänge zwischen normaler Huffman-Kodierung und der Range-Kodierung oder Arithmetic-Kodierung nicht ganz klar sind ;)
Weiterführende Artikel:
http://en.wikipedia.org/wiki/Range_encoding
http://en.wikipedia.org/wiki/Arithmetic_encoding

[TGGC]

Bleibt noch die Frage, wieviel Kühlheit passt in 4k? Antwort gibts in zwei Wochen. ;-)

[hagbard]

Wenn ich den Algorithmus nicht falsch verstanden habe ist es dass was man in der Kommunikationstechnik Interleaving nennt. Allerdings wird es da nicht zur Komprimierung eingesetzt sondern um die Auswirkungen von Burst-Fehlern zu verringern...

[BeRsErKeR]

http://code4k.blogspot.com/2010/12/crin ... table.html ist vielleicht ganz interessant dazu. Bezieht sich auf Exe-Kompression vom Crinkler.

Vielen Dank für den Link. Mit EXE-Compression wollte ich mich eh noch beschäftigen. Da finde ich bestimmt reichlich gute Ideen.

Wenn ich den Algorithmus nicht falsch verstanden habe ist es dass was man in der Kommunikationstechnik Interleaving nennt. Allerdings wird es da nicht zur Komprimierung eingesetzt sondern um die Auswirkungen von Burst-Fehlern zu verringern...

Ah sehr gut. Vielen Dank für diese Information. Es scheint in der Tat das gleiche Verfahren zu sein. Beim Lesen hab ich dann auch noch eine mögliche Optimierungstechnik erkannt, und zwar die Eingangsdaten in Bereiche zu stückeln (was ich prinzipiell eh beim Komprimieren mache -> Blöcke). Das wäre aber auch innerhalb eines Daten-Blocks z.B. sinnvoll wenn ich an verschiedenen Stellen jeweils ähnliche Daten habe (bspw. Grafikdaten und Texte von Layern in einer Datei, Stückelung 50%/50% sprich 2 Blöcke mit eigenem Bit-Packing). Das könnte man über einen Wert am Anfang festlegen (BitPackingBlockSize) oder ggf. mit einer Art BitPackingBlock-Dictionary. Das wird aber wohl nur sehr selten sinnvoll sein denke ich. Aber vielleicht kann man da trotzdem was optimieren. Mal schauen.

Könnte z.B. für bestimmte Dateiformate was bringen, wo man genau weiß, wo und wie groß bestimmte Daten-Bereiche sind und was dort für Daten liegen. Eine 24Bit-Windows-Bitmap wäre hier eigentlich gut als Beispiel geeignet. Für die Pixeldaten wäre ein Byte-Packing mit R=3 sinnvoll, für die Headerdaten eher ein Byte-Packing mit R=4. Hier könnte man mit 7 Informationen (NumberOfBPBlocks, BPBlock1Offset, BPBlock1Size, BPBlock1R, BPBlock2Offset, BPBlock2Size, BPBlock2R) eventuell was rausholen. Müsste ich mal testen. Das bringt natürlich umso mehr, desto größer die gleichartigen Bereiche sind und desto "ähnlicher" sich die einzelnen Bytes dort sind.

Wenn man ein eigenes Dateiformat entwirft könnte man das eventuell berücksichtigen und gezielt sowas forcieren und dann gut komprimieren. Also beispielsweise als DWORDs zusammenlegen, alle WORDs, alle QWORDs und alle Einzelbytes. Jeweils in bestimmte Bereiche.

[Krishty]

Könnte z.B. für bestimmte Dateiformate was bringen, wo man genau weiß, wo und wie groß bestimmte Daten-Bereiche sind und was dort für Daten liegen. Eine 24Bit-Windows-Bitmap wäre hier eigentlich gut als Beispiel geeignet. Für die Pixeldaten wäre ein Byte-Packing mit R=3 sinnvoll

Zweidimensionale Deltakompression bringt da afaik deutlich mehr (siehe PNG).

Wenn man ein eigenes Dateiformat entwirft könnte man das eventuell berücksichtigen und gezielt sowas forcieren und dann gut komprimieren. Also beispielsweise als DWORDs zusammenlegen, alle WORDs, alle QWORDs und alle Einzelbytes. Jeweils in bestimmte Bereiche.

Wenn ich Dateiformate für Echtzeitanwendungen entwickle, verhagel ich mir nicht die Cachetauglichkeit indem ich die Komprimierbarkeit berücksichtige. Wenn ich sie für Archivierung entwickle, nutze ich deutlich leistungsfähigere Filter als Interleaving.

[BeRsErKeR]

Könnte z.B. für bestimmte Dateiformate was bringen, wo man genau weiß, wo und wie groß bestimmte Daten-Bereiche sind und was dort für Daten liegen. Eine 24Bit-Windows-Bitmap wäre hier eigentlich gut als Beispiel geeignet. Für die Pixeldaten wäre ein Byte-Packing mit R=3 sinnvoll

Zweidimensionale Deltakompression bringt da afaik deutlich mehr (siehe PNG).

Interessant. Ist es so, dass die Differenzen mit weniger Bits gespeichert werden oder dient dies auch als Vorfilter, um möglichst ähnliche Werte zu erzeugen? Letzteres klingt logischer. Danke auf jeden Fall für den Hinweis.

Wenn man ein eigenes Dateiformat entwirft könnte man das eventuell berücksichtigen und gezielt sowas forcieren und dann gut komprimieren. Also beispielsweise als DWORDs zusammenlegen, alle WORDs, alle QWORDs und alle Einzelbytes. Jeweils in bestimmte Bereiche.

Wenn ich Dateiformate für Echtzeitanwendungen entwickle, verhagel ich mir nicht die Cachetauglichkeit indem ich die Komprimierbarkeit berücksichtige. Wenn ich sie für Archivierung entwickle, nutze ich deutlich leistungsfähigere Filter als Interleaving.

Abgesehen von der Deltakompression - kannst du mir ein paar weitere Filter nennen?

[BeRsErKeR]

Zum Thema Deltakompression fällt mir noch etwas ein, was man gut mit Bit-Packing kombinieren könnte. Wenn die Differenzen vorzeichenbehaftet gespeichert werden und man vom Zweierkomplement abweicht und für negative Zahlen einfach die positive Zahl verwendet mit gesetztem höchstwertigem Bit könnte ein anschließendes Bit-Packing noch was rausholen, sofern die Differenzen in einem bestimmten Bereich schwanken.

Beispiel:

100 102 100 97 101 100

Mit Deltakompression so wie ich sie hier verstehe:

100 +2 -2 -3 +4 -1

Wenn man diese dann nicht im Zweierkomplement ausdrückt:

(die Hundert lass ich mal weg) 00000010 10000010 10000011 00000100 10000001

Hier wär ein Bit-Packing wieder sehr sinnvoll, sofern die Absolutwerte der Differenzen ähnlich sind.

[TGGC]

Das muss ein ziemlicher schlechter Packalgo sein, wenn er nichtmal eine -1 im Zweierkomplement vernuenftig packen kann. Macht es bei dem wirklich noch Sinn, mit solchem Bitgeschiebe ein paar Prozent rauszuholen?

[BeRsErKeR]

Das muss ein ziemlicher schlechter Packalgo sein, wenn er nichtmal eine -1 im Zweierkomplement vernuenftig packen kann. Macht es bei dem wirklich noch Sinn, mit solchem Bitgeschiebe ein paar Prozent rauszuholen?

EIn Reihe von kleinen negativen Integern im Zweierkomplement kann er sehr gut packen. Man erhält dann viele 1en und somit im Idealfall viele Bytes mit dem Wert 255. Das Problem ist der Übergang von negativ zu positiv. Hier ist es durchaus besser für den Algo wenn Werte, die sich nur durch das Vorzeichen unterscheiden, möglichst viele identische Bits aufweisen.

Ehrlich gesagt bin ich bislang aber nur von vorzeichenlosen Werten ausgegangen. Mit Gleitkommawerten und vorzeichenbehafteten Werten gibt es da in der Tat Probleme was die Effizienz angeht.

Bilddaten sind aber zum Glück meist vorzeichenlos, genau wie Textdaten. Daher wird man hier selten eine große Veränderung im Bitmuster haben, wenn sich die Werte der Bytes kaum ändern. Ausnahmen sind halt die Sprünge bei 2er-Potenzen. Höherwertige Bits bleiben dann aber dennoch identisch.

Allerdings geht es hier ja nur um die Delta-Kompression, wo immer Vorzeichen dabei sind und die Werte unabhängig von den eigentlichen Daten (bzw. deren Repräsentation) sind. Hier das Zweier-Komplement zu umgehen hat also keinen Einfluss auf die Eingangsdaten oder andersrum.

Genauer gesagt: Wenn ich eine -1 in den Eingangsdaten habe (im Zweier-Komplement), dann kann das auch so bleiben. Die Differenz zum Vorgängerbyte hat dann einen Wert von -127 bis +127. Dieser Wert wird dann nicht im Zweier-Komplement gespeichert und kann besser gepackt werden. Das Bit-Packing und dessen Effizienz ist dann aber unabhängig davon ob die -1 in den Eingangsdaten im Zweier-Komplement vorliegt oder nicht.

Das Ganze war nur ein kleiner Gedankengang meinerseits. Ob es (Deltakompression + Bit-Packing) effizient ist glaub ich eigentlich selbst nicht. Da braucht man schon sehr geeignete Daten. Ich überlege ob man das über eine Art Sprungliste für bestimmte Bereiche machen könnte, quasi ein partielles Filtern. Dafür braucht man wieder Zusatzinfos (Anzahl der Bereiche, Offset und Länge pro Bereich), aber vielleicht bringt es was.

Ich hatte mir gedacht, dass ich das nur auf Daten anwende, die nicht ohnehin schon gut RLE-komprimierbar sind oder als Match auftauchen. Das ist dann aber wieder ziemlich aufwendig bei der Analyse, da ich ja erst filtern und dann nach RLE/Matches suchen muss.

[TGGC]

Hier ist es durchaus besser für den Algo wenn Werte, die sich nur durch das Vorzeichen unterscheiden, möglichst viele identische Bits aufweisen.

Fuer welchen Algo soll das denn gelten? Wie ich schon sagte packt der dann ehh ziemlich schlecht, sinnlos den zu verbessern.

[spobat]

Der Algorithmus, wie du ihn beschreibst, hört sich komplizierter an, als er ist finde ich.
"Verschiebe das jedes mod(x, y)-Byte um z stellen, und schaue, ob viele gleiche Bytes hintereinander sind". So habe ich es verstanden.
Dabei ist es doch "nur" eine Mustererkennung. In deinem Magenta-Bild wäre die optimale Kodierung doch (255 0 255) 100, nicht 255 100 0 100 255 100.
Du erkennst also das Muster 255 0 255

[BeRsErKeR]

Hier ist es durchaus besser für den Algo wenn Werte, die sich nur durch das Vorzeichen unterscheiden, möglichst viele identische Bits aufweisen.

Fuer welchen Algo soll das denn gelten? Wie ich schon sagte packt der dann ehh ziemlich schlecht, sinnlos den zu verbessern.

Stell dir mal Daten vor, bei denen 100 Werte jeweils ein Delta zwischen +/- 15 haben. Die Werte an sich sind aber relativ verschieden, sprich es kommen keine längeren Sequenzen vor. Wenn du nun die negativen Deltas im Zweierkomplett interpretierst sind die einzelnen Werte immer noch relativ schlecht komprimierbar. Nimmst du meinen Ansatz hast du bei allen 100 Bytes Werte, bei denen 3 Bits im höherwertigen Nibble immer 0 sind. Das heißt du hast mindestens eine Sequenz von 300 0-Bits drin, was 37 0-Bytes entspricht. Die kann man mit RLE z.B. als 2 Bytes ausdrücken und würde somit 35% der Datenmenge einsparen. Wie gesagt, das sind Extrembeispiele, daher gucke ich grad ob man den Filter vielleicht nur partiell sinnvoll einsetzen kann.

Der Algorithmus, wie du ihn beschreibst, hört sich komplizierter an, als er ist finde ich.
"Verschiebe das jedes mod(x, y)-Byte um z stellen, und schaue, ob viele gleiche Bytes hintereinander sind". So habe ich es verstanden.
Dabei ist es doch "nur" eine Mustererkennung. In deinem Magenta-Bild wäre die optimale Kodierung doch (255 0 255) 100, nicht 255 100 0 100 255 100.
Du erkennst also das Muster 255 0 255

Das ist ein Beispiel. Stell dir halt ein paar rote Pixel dazwischen vor. Dann greift dein Vorschlag nicht mehr. Das Byte-Packing ist dann immer noch sinnvoll.

[TGGC]

Wenn du nun die negativen Deltas im Zweierkomplett interpretierst sind die einzelnen Werte immer noch relativ schlecht komprimierbar.

So'n Quatsch, das ist genau so gut komprimierbar.

[BeRsErKeR]

Wenn du nun die negativen Deltas im Zweierkomplett interpretierst sind die einzelnen Werte immer noch relativ schlecht komprimierbar.

So'n Quatsch, das ist genau so gut komprimierbar.

Und wie? Ich gehe natürlich davon aus, dass sich positive und negative Werte zufällig abwechseln. Ich sollte vielleicht noch dazu sagen, dass ich hier von RLE- und wörterbuchbasierter Komprimierung spreche.

[TGGC]

Ich sollte vielleicht noch dazu sagen, dass ich hier von RLE- und wörterbuchbasierter Komprimierung spreche.

[BeRsErKeR]

Da du eventuell andere Komprimierungsverfahren im Kopf hattest, könntest du die vielleicht ja mal nennen. Ich bin zur Zeit dabei eine Deflate-ähnliche Komprimierung zu optimieren. Ich teste momentan viel mit Bilddaten. Daher hab ich mir das Bit-Packing auch in Hinblick auf RLE überlegt. Hätte ich vielleicht gleich dazu sagen sollen.

[TGGC]

Die schon erwaehnte Huffman-Kodierung wird einfach die meist vorkommenden Zahlen durch kurze Codes ersetzen, vollkommen egal ob sie positiv, negativ oder sonstwas sind. Die ist auf Teil von deflate.

[BeRsErKeR]

Ja ok, die Entropiekodierung (Huffman, Arithmetic, etc) kommt zum Schluss eh drüber, das ist klar. Obiges Verfahren würde aber Blöcke mit relativ zufälligen Werten mit geringen Deltas gut "vor-"komprimieren und ggf. auch seltene Literale komplett überflüssig machen. Das ist ja bei der Kombination von RLE und Huffman schon zu beachten. Klar wären Daten, die z.B. das Literal 0 sehr oft enthalten gut entropiekodierbar, da die 0 dann meinetwegen nur 1 Bit benötigt. Wenn ich aber 1000 Nullen in Folge durch 3 RLE-Bytes ersetzen kann und dadurch nur noch eine Null in den Daten habe (diese 0 wird dann bei der Entropiekodierung wesentlich schlechter abschneiden), so wäre es dennoch effizienter, da 1000 Bits immer noch viel mehr sind als ~24. :) Und die Kombination aus Deltakompression + Bit-Packing dient ja gerade dazu, mehr RLEs zu erhalten (jedenfalls in dem von mir gezeigten Ansatz). Das Verfahren darf man natürlich nur anwenden, wenn die Gewinne aus RLEs die eventuellen Verluste bei der Entropiekodierung überbieten. Daher wäre eine Analyse wichtig und in 99% der Fälle würde es nur für bestimmte Bereiche (daher partielles Anwenden) sinnvoll sein.

Um es vielleicht noch etwas spezifischer für meine Anwendung auszudrücken. Es gibt die 256 normalen Byte-Literale und einige Spezialliterale (z.B. für RLE oder Match). Am Ende werden all diese Literale entropiekodiert (momentan mit Huffman). Mein Vorfiltern würde nur die Eingangsdaten (also nur normale Byte-Literale und deren Auftrittshäufigkeit) verändern. Im Idealfall sollten später aber möglichst viele RLE- und Match-Literale vorhanden sein (sonst ist bei den Daten eh nicht viel komprimierbar, abgesehen von Huffman) und daher ist es auch wichtiger für diese Spezial-Literale kurze Entropiekodierungen zu erhalten (was wie gesagt durch das Vorfiltern in Hinblick auf RLE höchstens noch begünstigt wird). Das ist in der Regel übrigens auch der Fall. Das Vorfiltern ermöglicht in diesem Fall also einfach zusätzliche RLE-Operationen bei Daten, die keine direkten Sequenzen aus gleichen Bytes sind. Da das nicht überall sinnvoll ist versuche ich das über eine Sprungliste zu realisieren. Pro Datenblock kann über 1 Bit erstmal festgelegt werden, ob der Filter überhaupt aktiv ist. Wenn er aktiv ist, gibt es mindestens einen Eintrag in der Sprungliste. Die Sprungliste besteht aus einem Wert für die Anzahl der Einträge und den Einträgen selbst, die jeweils einen Filterbereich (Offset, Länge) angeben. Ich realisiere all diese Werte über EncodedInts (also Variablen, die mit ihrer Wertgröße auch an Bitanzahl zunehmen, ähnlich UTF-8). Um es weiter zu optimieren speichere ich bei den Einträgen die Offsets als Differenz zum Offset des letzten Eintrags. Somit bleiben die Werte kleiner und brauchen weniger Platz. Die Sprungslisten sind also sehr klein. Sie könnten theoretisch ebenfalls mit entropiekodiert werden, aber ich weiß nicht ob das zielführend ist. Naja ich werd das mal ausimplementieren und dann ein paar Tests (Pixelgrafiken, S/W-/Farbfotos, EXEn, usw) machen.

[TGGC]

Was ne Milchmaedchenrechnung. Den kleinen Teil der Bits, die du mit Hin und Hergerechne und Rumgeschiebe fuer dein RLE komprimierbar machen willst, halten ehh keine Information. Die wird jede moderne (d.h. wahrscheinlich alles aus den letzten 20 Jahren...) Kompression ohnehin nicht speichern.

[BeRsErKeR]

Was ne Milchmaedchenrechnung. Den kleinen Teil der Bits, die du mit Hin und Hergerechne und Rumgeschiebe fuer dein RLE komprimierbar machen willst, halten ehh keine Information. Die wird jede moderne (d.h. wahrscheinlich alles aus den letzten 20 Jahren...) Kompression ohnehin nicht speichern.

Wieso halten diese Bits keine Information? Du hast ja keine Vorgabe "die Daten können nur in dem Wertebereich vorliegen", sondern sie sind beliebig. Wenn aber größere Bereiche mit einem bestimmten geeigneten Wertebereich vorkommen, dann kann man sie durch Transformation geeignet für RLE machen. Zu beachten gilt auch, dass das nicht für alle Daten überhaupt möglich ist, sondern maximal für Daten, in denen kein Delta mit einem Absolutwert >127 vorkommt.

Ich frage mich wie "moderne Kompressionen" dort die "informationslosen Bits" erkennen wollen? Sie sind in meinen Augen nicht informationslos. Klar ist es möglich, wenn man weiß "in dem Bereich der Datei liegen immer Werte im Wertebereich x - y". Aber dann wäre es ein sehr spezifischer Algorithmus für ein bestimmtes Dateiformat. Ich untersuche hier gerade die Tauglichkeit für allgemeine Daten.