Textpresse
Wie man kurze Strings effizient komprimiert
Klassische Komprimierungsverfahren produzieren bei kleinen Datenmengen wie einzelnen Wörtern mehr Overhead, als die Komprimierung einspart. Besser gehts mit auf die Daten zugeschnittenen Verfahren. Eine Einführung in binäre Bäume und Shannon-Fano-Coding.
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 [1], aber die helfen beim Komprimieren kurzer Strings nicht weiter.
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.