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

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

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