Hochleistungskompression mit .NET-Bordmitteln

Geschrieben von: Bernhard Spuida
Kategorie: Aprilscherz

Das Internet kennt einen 'Heiligen Gral': Bandbreite. Bandbreite ist kostbar, sie muß gespart werden um uns als Betreibern eines Auftrittes möglichst wenig Traffic-Kosten zu verursachen und um den Besuchern einen möglichst schnellen Zugang zum gewünschten Inhalt zu gewähren. In diesem Artikel werden wir sehen welche Möglichkeiten uns das .NET Framework bietet um möglichst hohe Kompression - und somit möglichst effiziente Bandbreitennutzung - zu erreichen.

Die angesehene wissenschaftliche Zeitschrift 'Nature' hat kürzlich ein neues Verfahren zur Beschleunigung der Datenübertragung in Netzwerken vorgestellt. Gewaltig - die Beschleunigung beträgt ca. 3500 Prozent gegenüber gewöhnlichem Breitbandinternet! Der 'Schönheitsfehler' daran ist allerdings, daß es sich um eine Modifikation an einem grundlegenden Protokoll handelt, eine derartige Änderung läßt sich nicht so schnell in die Praxis übertragen, schließlich muß sie laut dem OSI Modell [1]in die entsprechenden Protokollstacks aller Betriebssysteme integriert werden.

Wir müssen also auf einer höheren Ebene ansetzen, bei den Anwendungen. Da Microsoft dem .NET Framework eine sehr umfangreiche Auswahl an Klassen mitgegeben hat, werden wir doch sicherlich etwas finden können was unseren Wünschen entspricht...

Grundlegendes zur Datenkompression

Bevor wir uns in das .NET Framework stürzen, wollen wir uns mit der Funktionsweise von Kompressionsalgorithmen beschäftigen, es kann ja nie schaden zu wissen wovon man spricht.

Bei der Auswahl von Algorithmen zur Kompression von Daten sind zwei Dinge wichtig:

a) Ist die Abbildung eindeutig? D.h. kann ich sicher sein daß nicht zwei verschiedene Dateien identische komprimierte Dateien ergeben?

b) Ist die Kompression verlustfrei oder verlustbehaftet? Bei Graphiken (jpg) und Musik (mp3) stören kleine Artefakte (z.B. Kästchen an harten Übergängen in Graphiken) durch Verlust von Daten nicht unbedingt da die Grundinformation erhalten bleibt, bei Texten hingegen ist der Verlust von Inhalt gravierend - man stelle sich vor daß durch Kompression jeder zehnte Buchstabe in einem Text verloren geht...

Fangen wir nun mit dem einfachsten Verfahren an, Run Length Encoding (RLE). Hier werden einfach Ketten von gleichen Werten durch den Wert und die Anzahl der Wiederholungen ersetzt: AAAAAAAAAABBBBB wird so zu 10A5B - ein ganz netter Fortschritt, nicht wahr? Diese einfache Codierung wird zum Beispiel in Fax-Übertragungen eingesetzt, die entsprechenden Standards heissen 'CCITT Group 3' bzw. 'CCITT Group 4' [2], je nach dem Grad der Effizienz (Zeilen-orientiert bzw. Zeilen- und Spalten-orientiert). Die Effizienz beträgt immerhin 5:1 bzw. 10:1.

Aber was ist wenn die Daten schnell wechseln und viele verschiedene Werte annehmen können? Dann würde ein derartiges Verfahren ja zu einer Aufblähung der Datenmenge führen. Die Lösung heißt: Ersetzungstabellen verwenden! Jedes der 'klassischen' Kompressionsverfahren wie LZW [3] (Achtung: patentiert!) beruht auf Tabellen die in einer Datei vorhandene (Bit-)Muster nach Häufigkeit sortiert mit wesentlich kürzeren Ersatzmustern verknüpfen. Dabei sollte natürlich den häufigsten und/oder längsten Mustern das kürzestmögliche Ersatzmuster zugewiesen werden. Ein wesentliches Problem besteht in der Größe der Tabellen die abhängig von der Anzahl der Muster stark anwachsen können. Die Zuweisungsalgorithmen sind der wesentlichste Unterschied zwischen den verschiedenen 'Zip'-Methoden. Implementationen der verschiedenen Standard-Algorithmen (zip, gzip, bzip2 und TAR) finden sich in der #ziplib. Im Download befindet sich übrigens auch ein schönes Beispiel für die Anwendung von Kompressionsverfahren im Internet. Derartige Kompressionsverfahren sind inzwischen sowohl Server- als auch Browser-seitig Standard, Stichwort 'HTTP/compress'. Eine weitere wichtige Anforderung an das Kompressionsverfahren ist für derartige Anwendungen die Geschwindigkeit. Was nützt eine hohe Kompressionsrate wenn Packen und Entpacken länger als die Übertragung unkomprimierter Daten brauchen?

Auf zu neuen Ufern

Aber da muß doch noch mehr gehen, diese Standards reichen ja doch schon in die Urzeit des Internet zurück, wenn nicht sogar noch weiter [4]. Einen Überblick über die für das Internet verbindlichen Standards und Protokolle findet man in den sogenannten Requests For Comment (RFCs). Diese 'Bitten um Stellungnahme' sind verbindliche Normen, egal wie harmlos sich diese Bezeichnung anhört.

Also stöbern wir mal in dieser Schatzgrube...

Da! RFC 1321, aus dem Jahr 1992. Wesentlich jünger als die bisher diskutierten Verfahren. Verfasst vom MIT, einer Hochburg der Computerwissenschaften, und von Ron Rivest, Mitbegründer der renommierten Sicherheitsfirma RSA. Wenn das nicht für einen qualitativ hochwertigen Algorithmus bürgt. Lesen wir mal, was in der Einleitung steht - unter anderem:

'...where a large file must be compressed in a secure manner...', also '...wenn große Dateien zuverlässig komprimiert werden müssen...'

und

'The MD5 algorithm is designed to be quite fast on 32-bit machines. In addition, the MD5 algorithm does not require any large subsitution tables; the algorithm can be coded quite compactly.' d.h. 'Der MD5 Algorithmus ist für hohe Geschwindigkeit auf 32 Bit-Maschinen ausgelegt. Des weiteren benötigt er keine großen Ersetzungstabellen; der Algorithmus kann recht kompakt implementiert werden'.

Perfekt, wenn wir unsere obigen Anforderungen betrachten. Heutige PCs sind 32 Bit-Maschinen, die kompakte Codegröße verspricht uns problemlose Implementierung in clientseitigem Code, wir müssen uns also nicht auf die Existenz einer Implementierung im Browser verlassen! Und die Tatsache daß wir auf die lästigen Ersetzungstabellen verzichten können heißt das wir gerade bei Daten mit wenigen Musterwiederholungen noch gewaltige Kompressionszuwächse erwarten können.

Einen Punkt gilt es aber noch zu klären: sind die komprimierten Daten eindeutig, oder anders gefragt, habe ich Informationsverluste zu erwarten? Rivest schreibt dazu in RFC 1321 in Anschluß an die entsprechende Beweisführung (die ich hier auslasse):

'It is conjectured that the difficulty of coming up with two messages having the same message digest is on the order of 2^64 operations, and that the difficulty of coming up with any message having a given message digest is on the order of 2^128 operations. The MD5 algorithm has been carefully scrutinized for weaknesses.' oder auf Deutsch: 'Es wird angenommen daß die Komplexität der Aufgabe mit zwei Nachrichten mit identischem Nachrichtencode zu finden in der Größenordnung von 2^64 Operationen und die Komplexität eine Nachricht mit gegebenem Nachrichtencode in der Größenordnung von 2^128 Operationen angesiedelt ist. Der MD5-Algorithmus wurde sorgfältig auf Schwächen untersucht.'

Besser können wir es gar nicht mehr treffen: schneller, kompakter Code, kleine Zieldateien und keine Informationsverluste! Auf zur Praxis.

MD5 in der .NET-Praxis

Das .NET Framework stellt uns dankenswerterweise bereits eine vollständige Implementation von MD5 zur Verfügung. Wir finden sie im Namespace System.Security.Cryptography.MD5, nicht weiter verwunderlich wenn man bedenkt daß Ron Rivest aus der Kryptographie kommt - er ist immerhin das 'R' im RSA-Algorithmus. Außerdem kann Datenkompression in der Kryptographie auch vorteilhaft angewandt werden, da sie die Entropie der zu verschlüsselnden Datei anhebt. Nun ein Beispiel in VB.NET:

Dim data(DATA_SIZE) As Byte

' Dies ist eine Implementation der abstrakten MD5-klasse.
Dim md5 As New MD5CryptoServiceProvider()

Dim result As Byte() = md5.ComputeHash(data)

Und nun dasselbe in C#:

byte[] data = new byte[DATA_SIZE];

// Dies ist eine Implementation der abstrakten MD5-klasse.
MD5 md5 = new MD5CryptoServiceProvider();

byte[] result = md5.ComputeHash(data);

Mehr ist in unserem serverseitigem Code nicht nötig um mit MD5 Daten zu komprimieren! Das .NET Framework macht unser Leben deutlich leichter. Was die clientseitige Funktionalität angeht so muß dort natürlich die .NET Runtime ebenfalls vorhanden sein, wenn wir auf der empfangenden Seite auch ein derart leichtes Leben haben wollen. Sollte dies nicht der Fall sein, so läßt sich allerdings ohne weiteres die ausführlich dokumentierte Referenzimplementierung von MD5 aus Anhang A der RFC 1321 adaptieren.

Schlußbemerkung

Faszinierend, was man mit ein wenig Recherche zum Thema Datenkompression erreichen kann. Da die Datenmengen im Internet immer größer werden, muß man sich zunehmend Gedanken über die Optimierung der Datenübertragung machen, schließlich zahlt man auch als Content Provider.

Viel Spaß bei der Suche nach weiteren kreativen Möglichkeiten der Datenkompression!

Verwandte Artikel

Debugging in der Tiefe
Neues in .NET Codename "Swinomish"

Links zu anderen Sites

Data Compression Reference Center
Eine weitere wichtige RFC
RFC 1321
Weitere überraschende Anwendungen für Kompression

Wenn Sie jetzt Fragen haben...

Wenn Sie Fragen rund um die in diesem Artikel vorgestellte Technologie haben, dann schauen Sie einfach bei uns in den Community Foren der deutschen .NET Community vorbei. Die Teilnehmer helfen Ihnen gerne, wenn Sie sich zur im Artikel vorgestellten Technologie weiterbilden möchten.

Haben Sie Fragen die sich direkt auf den Inhalt des Artikels beziehen, dann schreiben Sie dem Autor! Unsere Autoren freuen sich über Feedback zu ihren Artikeln. Ein einfacher Klick auf die Autor kontaktieren Schaltfläche (weiter unten) und schon haben Sie ein für diesen Artikel personalisiertes Anfrageformular.

Und zu guter Letzt möchten wir Sie bitten, den Artikel zu bewerten. Damit helfen Sie uns, die Qualität der Artikel zu verbessern - und anderen Lesern bei der Auswahl der Artikel, die sie lesen sollten.