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

[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).

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.

Weil die vorhergesagten Werte näher an den tatsächlichen liegen, kommen weniger verschiedene Werte vor. Weil genau so viele Werte vorkommen, sie sich aber weniger unterscheiden, sind sie zum einen regelmäßiger und zum anderen braucht man weniger Bits, um sie zu komprimieren.

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?

bzip2 nutzt zum Beispiel eine Burrows-Wheeler-Transformation gefolgt von Move to Front. Die meisten Archivierungsprogramme sortieren ihre Eingaben nach Dateierweiterungen, weil dann ähnliche Daten auch bei der Kompression nah beieinanderliegen und die Kompression dann ihre Modelle nicht so oft radikal ändern muss.

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

this

[Alexander Kornrumpf]

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.

Das ist einfach zu beantworten: Wenn jedes Bit Information tragen würde könntest du mit keinem denkbaren Verfahren verlustfrei komprimieren.

[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.

Das ist einfach zu beantworten: Wenn jedes Bit Information tragen würde könntest du mit keinem denkbaren Verfahren verlustfrei komprimieren.

Naja mir ist schon klar, dass alle Informationen erhalten bleiben müssen, aber kann man denn wirklich immer pauschal sagen, dass genau ein spezielles Bit keine Information trägt? Ich verstehe es eher so, dass eine Sequenz von Bits einen gewissen Informationsgehalt hat, der kleiner-gleich der Sequenzlänge ist. Das man nun aber genau identifizieren kann welche Bits aus der Sequenz keine Information tragen, kann man mMn nicht immer feststellen, jedenfalls nicht ohne bestimmtes Kontextwissen. Aber vielleicht irre ich mich da ja auch.

Ich nutze ja bei meinem Vorschlag Kontextwissen aus, dass ich über eine Analyse erhalte, daher wäre der Algo blind auf alle Daten angewandt sehr unvorteilhaft, in einem speziellen Kontext aber nicht. Daher glaube ich nicht so ganz, dass reine Huffman-Kodierung hier in jedem Fall alle "informationslosen" Bits vollständig wegoptimiert. Und zwar vorallem dann nicht, wenn die Daten im gesamten zu kodierenden Block sehr gleichverteilte Häufigkeiten aufweisen.

Außerdem finde ich die Argumentation "moderne Kompressionsverfahren können alle informationslosen Bits wegoptimieren" etwas aus der Luft gegriffen. Die Huffman-Kodierung z.B. kann allein angewendet bestimmte Sequenzen nicht ansatzweise optimal komprimieren und somit sind scheinbar noch viel zu viele informationslose Bits enthalten. Man denke nur an das Beispiel, wo RLE Huffman um Längen schlägt. Und selbst die modernen Kompressionen, die aus Kombinationen von Verfahren bestehen, sind mit Sicherheit nicht für alle Daten optimal.

[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.

Weil die vorhergesagten Werte näher an den tatsächlichen liegen, kommen weniger verschiedene Werte vor. Weil genau so viele Werte vorkommen, sie sich aber weniger unterscheiden, sind sie zum einen regelmäßiger und zum anderen braucht man weniger Bits, um sie zu komprimieren.

Das klappt dann aber auch nur bei spezifischen Daten gut. Bei Grafiken ist das natürlich sehr sinnvoll, vorallem auf Pixel-Ebene. Soweit ich das verstehe optimiert der Filter vorallem die Entropiekodierung bzw. die Wahrscheinlichkeit für das Auftreten von Matches.

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?

bzip2 nutzt zum Beispiel eine Burrows-Wheeler-Transformation gefolgt von Move to Front. Die meisten Archivierungsprogramme sortieren ihre Eingaben nach Dateierweiterungen, weil dann ähnliche Daten auch bei der Kompression nah beieinanderliegen und die Kompression dann ihre Modelle nicht so oft radikal ändern muss.

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

this

Ok danke für die Hinweise. Die Burrows-Wheeler-Transformation + Move to Front kannte ich bereits. Entropiekodierung (Huffman oder Arithmetic) darf sowieso in keinem Kompressions-Verfahren fehlen.

Sequitur fand ich auch noch ganz interessant, wobei das dann eher wieder in Richtung Lempel-Ziv geht. Falls es jemand nicht kennt. Ob das gegen modernere LZ-Ableger anstinken kann bezweifle ich aber.

[BeRsErKeR]

Mir ist gerade noch etwas eingefallen, wie man die Effizienz der Huffman-Kodierung noch leicht steigern kann, sofern man zusätzlich RLE nutzt.

Nehmen wir mal an, man würde alle Sequenzen von gleichen Literalen mit einer minimalen Sequenzlänge von 3 per RLE kodieren.

Wenn nun die Codes für bestimmte Literale relativ kurz sind (1-3 Bits) würde sich folgender Ansatz lohnen:

Da ein 3-faches Vorkommen eines Literals (und somit auch des Huffman-Codes) nicht möglich ist (da es sonst RLE-kodiert wäre), könnte man den Huffman-Code der aus 3 Aneinanderreihungen eines Literal-Codes besteht für ein weiteres Symbol verwenden.


Beispiel:

Das Literal 0 wird mit 2 Bits huffman-kodiert. Sagen wir mal 10b. In den komprimierten Daten könnte nun niemals 101010b vorkommen, denn dies würde 3 Nullen in Folge entsprechen und wäre somit RLE-kodiert. 101010b kann nun also zur Kodierung eines weiteren Literals genutzt werden. Das ist natürlich nur sinnvoll, wenn das Literal sonst mit mehr als 6 Bits kodiert werden würde.


Ich habe hier gerade den Fall, in dem ich für ein spezielles Dateiformat eine feste Huffman-Tabelle verwende und das häufigste Literal (in dem Fall 0) immer mit nur einem Bit (nämlich 0b) kodiere. Alle anderen Huffman-Codes beginnen demzufolge mit einer binären 1. Daher kann ich weitere Symbole kodieren, z.B. als 000b (in dem Fall nur 1 weiterer Code), oder aber mit 0001b und 0000b (2 weitere Codes), usw. Der binäre Prefix ist also in diesem Fall immer 000b. Das bringt vielleicht nicht viel, aber wenn ich das zweithäufigste Symbol (bei mir fest kodiert als 10b) ebenfalls so verwende, hätte ich mit 101010b noch einen weiteren Code zur Verfügung den ich sonst nicht hätte. Auch hier wäre wieder 1010100b und 1010101b möglich usw. In meinem Fall scheint das doch einiges zu bringen, da die meisten Literale mit 9 und mehr Bits kodiert werden müssen. Durch den Ansatz habe ich in diesem Beispiel bis zu 10 weitere Literale mit einer Länge <= 8.

Wenn man RLE schon für Sequenzen der Länge 2 einsetzt, könnte man da vielleicht noch mehr rausholen. Da bin ich mir aber nicht so ganz sicher, ob das sinnvoll ist. In diesem Fall wäre dann z.B. das Literal 00b verwendbar (das könnte ja dann sogar das Literal für RLE selbst sein :D ). 1010b geht dann auch usw. Dabei beißt sich zwar augenscheinlich die Schlange selbst in den Schwanz, da 2 Null-Bytes ohne RLE als 00b (also 2 Bits) kodiert werden könnten und mit RLE auf jeden Fall länger, allerdings gilt das dann nicht mehr wenn andere Symbole RLE-kodiert werden.

Vielleicht irre ich mich aber auch gerade gewaltig.