Wie man kleine Dateneinheiten effizient komprimiert
Kleine Datenmengen erfordern eine besondere Behandlung beim Komprimieren. Eine Einführung in binäre Bäume und Shannon-Fano-Coding.
![](https://heise.cloudimg.io/width/610/q85.png-lossy-85.webp-lossy-85.foil1/_www-heise-de_/imgs/18/4/6/2/6/2/7/9/ct1724txtz_Shor_129985-ola-uwei-ONLINE-23466f6d191a5853.jpeg)
- Oliver Lau
Gzip, Zip, 7-Zip und wie sie nicht alle heißen, arbeiten mit Komprimierungsverfahren wie LZ77, Deflate oder LZMA, die eines gemeinsam haben: Damit sich die komprimierten Daten wieder entpacken lassen, ordnen ihnen die Packer Verwaltungsdaten bei (Overhead). Vereinfacht gesagt steht darin, dass eine bestimmte Bytefolge in den unkomprimierten Daten einer bestimmten, relativ kurzen Bitfolge in den komprimierten Daten entspricht. Wenn die unkomprimierten Daten also viele gleiche Bytefolgen enthalten, die man auf kurze Bitfolgen abbilden kann, spart man dadurch sehr viel Platz.
Das Dekomprimieren dreht die Abbildung um: Die kurzen Bitfolgen werden nach und nach gelesen, im in den Verwaltungsdaten enthaltenen Codebook nachgeschlagen und durch die ursprünglichen Bytefolgen ersetzt. Um möglichst viel Platz zu sparen, bietet es sich beim Komprimieren an, möglichst häufig auftretende Bytefolgen durch möglichst kurze Bitfolgen zu ersetzen. Es gibt noch mehr Tricks wie die Burrows-Wheeler-Transformation in Bzip2, aber die helfen beim Komprimieren kurzer Strings nicht weiter.
- Um große Datenmengen zu packen, eignen sich die in gängigen Tools wie Zip implementierten Kompressionsverfahren.
- An kleinen Datenportionen, beispielsweise Namen für Menschen oder Orte, scheitern sie aber.
- Mit ein paar Kenntnissen in Kodierungstheorie können Sie auch diese Daten auf rund ein Drittel ihrer ursprünglichen Größe schrumpfen.
Komprimierungssoftware muss für die unterschiedlichsten Daten – von Texten über Code bis hin zu Bildern und Videos – möglichst gute Ergebnisse liefern. Deshalb kann sie nicht alle mit einem vorab festgelegten Satz an Bytefolgen komprimieren, sondern muss zunächst für jede Datei die jeweils optimalen Bytefolgen finden.
Das war die Leseprobe unseres heise-Plus-Artikels "Wie man kleine Dateneinheiten effizient komprimiert". Mit einem heise-Plus-Abo können sie den ganzen Artikel lesen und anhören.