Von C nach Java, Teil 4: Datenkompression und Verschlüsselung
Bei kaum einem anderen Themengebiet sind die Unterschiede zwischen C und Java so eklatant wie bei der Datenkompression und der Verschlüsselung. Der Artikel stellt die Unterschiede hierbei zwischen C und Java heraus und zeigt dafür Beispiele.
- Andreas Nieden
Bei kaum einem anderen Themengebiet sind die Unterschiede zwischen C und Java so eklatant wie bei der Datenkompression und der Verschlüsselung. Der Artikel stellt die Unterschiede hierbei zwischen C und Java heraus und zeigt dafür Beispiele.
Gab es Ende der 80er-Jahre lediglich Nischenangebote für C, hat sich mittlerweile bei der Datenkompression zlib als De-facto-Standard etabliert. Im Java-Umfeld hingegen sieht sich der Entwickler einer ganzen Reihe an Techniken gegenüber, und hier fällt es angesichts der Fülle an Möglichkeiten schwer, sich zu entscheiden. Zunächst sei aber erst mal ein kleiner Überblick über die technischen Gesichtspunkte bei der Datenkompression und Verschlüsselung gegeben.
Grundlagenarbeit
Alle Artikel der Reihe
In dieser Artikelserie bereits erschienen:
Mit fortschreitender technischer Entwicklung und dem damit verbundenen steigenden Datenaufkommen kam der Wunsch auf, große Datenmengen platzsparender auf dem Dateisystem unterzubringen. Dabei war ein Kompromiss zu schließen zwischen dem Grad der Platzoptimierung und der Geschwindigkeit beim Speichern und Lesen. Zahlreich Algorithmen tauchten in der Folge auf, und einige der Techniken wurden auch Bestandteil von Betriebssystemen.
Die frühen Gehversuche bestanden darin, aufeinanderfolgende gleiche Bytes zusammenzufassen, wobei dann lediglich das betreffende Byte und die Anzahl der Bytes in der Zieldatei abgelegt wurden. War der Algorithmus anfangs der einzige Versuch, kam er im weiteren Verlauf als "Nachbehandlung" bei komplexeren Methoden zum Einsatz, bis er schließlich aufgrund der in den meisten Fällen viel zu geringen Kompressionsrate ganz verschwand.
Verfeinert wurde das später dadurch, dass das Programm statt gleicher Bytefolgen die Häufigkeit von Bytes und später auch Bitmuster zum Thema machte. Methoden wie das "Huffman" Squeezing brachten hierbei beachtliche Erfolge, allerdings unter Beeinträchtigung insbesondere der benötigten Zeit für die Datenkompression (das Auspacken war um ein Vielfaches performanter). Programme wie pack gab es (in den 80er-Jahren) für viele Unix-Derivate, die sich dieser Methode bedienten.
Quellcode zum Artikel
Die im Artikel gezeigten Programmbeispiele finden Sie auf dem FTP-Server von heise Developer zum Download.
Die erste, richtig geeignete Implementierung einer Datenkompression erfolgte mit der Umsetzung des Lempel-Ziv-Welch-Algorithmus. Große Teile dieses Algorithmus hatten 1978 Abraham Lempel und Jacob Ziv entwickelt und auch veröffentlicht, während Terry A. Welch einige Verbesserungen 1983 hinzugefügte. Der Algorithmus beruht darauf, dass beliebige Folgen von Bytes innerhalb einer Datei erkannt und diese als beispielsweise 9 bis 16 Bit große Codes (Token) abgelegt werden, die dynamisch während des Kodiervorgangs erzeugt werden.
Um den Kompressionsvorgang für hohe Geschwindigkeit und große Datenmengen zu optimieren, bestand die Kunst hierbei darin, das Auffinden kodierter Zeichenketten zu beschleunigen, was letztlich ein Hash-Algorithmus bewerkstelligte. Es gibt eine Implementierung dieser Methode im compress.c-Programm, die (den Quelltext betreffend) vergleichsweise einfach und verständlich umgesetzt und daher bei den meisten Unix-Derivaten zum Quasi-Standard für das Komprimieren von Dateien wurde. Die entstandenen Bitcodes legte man nur mit der tatsächlich benötigten Bitlänge platzsparend ab, wobei der Kodierer (und beim Auspacken auch der Dekodierer) zu jedem Zeitpunkt "wusste", wie lang die aktuellen Codes sind.
Die Methode kam damals beim Komprimieren von Bilddaten zum Einsatz, und zwar im sogenannten GIF-Format, das sich gerade beim Gestalten von Webseiten großer Beliebtheit erfreute. Problematisch war, dass Unisys auf das Kompressionsverfahren LZW ein US-Patent hatte und ab 1994 seine Verwendung auch für freie Software mit Lizenzgebühren belegte. Das führte zu einer Ablösung des GIF-Formats durch das leistungsfähigere PNG-Format. Näheres dazu findet sich in einem entsprechenden Artikel bei Wikipedia.
Doch auch danach blieb die Kompression von Daten ein dringendes Thema, und die Anforderungen an geeignete Methoden waren ständig präsent. So verfeinerten sich die Methoden rund um den Lempel-Ziv-Welch-Algorithmus, und schließlich war ein Standard im Unix-Programm gzip entstanden, der die Vorteile der LZW-Datenkompression mit dem Huffman Squeezing verband und bis heute noch das wohl am meisten verwendete Programm zur verlustfreien Komprimierung beliebiger Dateien ist.
