Wllkmmn b ppslts – Oder: Warum wir Komprimierung brauchen

By appsoluts 1 Jahr agoNo Comments

Um Datenmengen zu verkleinern, wird das Prinzip der Komprimierung angewendet. Im Folgenden erklären wir Komprimierung an einem Text Beispiel und zeigen, wie viele Bits wir dadurch einsparen können – stellt euch dann mal vor, wie hilfreich dieses Prinzip bei wirklich großen Datenmengen sein kann. 

Jedes Zeichen aus einem Text, den wir speichern wollen, nimmt 8 Einsen/Nullen (also 8 Bit) ein. Das klingt zwar bei unseren Rechnern mit hunderten von Gigabyte an Speicherplatz nach nicht viel; allerdings macht es einen großen Unterschied, wenn wir Daten mit einer langsamen Internetverbindung laden oder sehr lange Texte haben. Nehmen wir alle Harry Potter Bände (auf Deutsch) zusammen, kommen wir auf etwa 9,7 Millionen Zeichen, die abgespeichert 9,7 MB groß wären. Um diese Daten zu verkleinern, brauchen wir Komprimierung.

Einer der bekanntesten Komprimierungsalgorithmen ist der Huffman-Code, der 1952 entwickelt wurde. Die Grundidee ist simpel: Zeichen, die häufig vorkommen, sollen abgekürzt werden. Prinzipiell machen wir Menschen das oft unbewusst, indem wir Formulierungen wie “zum Beispiel” mit “z.B.” oder “unter anderem” mit “u.a.” abkürzen. Der Huffman-Code nutzt Baumstrukturen, um die häufigsten Zeichen mit möglichst wenig Bit darzustellen. Schauen wir uns folgendes Beispiel an:

Willkommen bei appsoluts!

Im ersten Schritt zählen wir, wie oft jedes Zeichen in unserem Text vorkommt, dazu gehören auch Leerzeichen. Dann sortieren wir unsere Zeichen nach der Häufigkeit:

Zeichen Anzahl
l 3
i 2
o 2
m 2
e 2
<Space> 2
p 2
s 2
W 1
k 1
n 1
b 1
a 1
u 1
t 1
! 1

Nun beginnen wir unten in der Liste und nehmen die beiden ersten Zeichen, setzen sie nebeneinander und erzeugen einen neuen Knoten oberhalb mit ihrer Summe. In unserem Beispiel sind das “!” und “t”. Beide kommen einmal vor, deswegen verbinden wir sie mit einem Knoten, die die Zahl 2 erhält. Nun sortieren wir unseren neuen Knoten in der Liste zwischen “i” und “l” ein und nehmen die nächsten beiden Zeichen.

Das können wir so lange fortführen, bis wir an unseren bereits kombinierten Knoten kommen. Hier machen wir dasselbe wie zuvor: Wir addieren die Häufigkeit von “i” und unsere Knoten mit “t” und “!”, erhalten die Summe 4 und können den neuen Knoten wieder in unserer Liste einfügen.

Auf diese Art und Weise gehen wir nun durch unsere Liste nach oben und verbinden immer wieder neue Knoten, bis wir keine Liste, sondern nur noch einen großen Knoten haben. Dieser Knoten ist der sogenannte Huffman-Baum und enthält nun alle Zeichen. Je öfter ein Zeichen vorkommt, desto weiter oben befindet es sich im Baum.

Unser fertiger Baum ist die Grundlage für den Huffman-Code. Wir suchen uns nun jedes Zeichen aus unserem Text “Willkommen bei appsoluts!” aus dem Baum heraus. Wir starten am obersten Knoten und entscheiden, ob wir den rechten oder den linken Pfad nehmen. Für den rechten Pfad notieren wir uns eine “1”, für den linken Pfad notieren wir uns eine “0”. Fangen wir bei “W” an: Wir gehen einmal nach links, zweimal nach rechts und wieder zweimal nach links. Das macht “01100”, also 5 Bit statt 8 Bit. Deutlicher wird es beim “l”: Da es das häufigste Zeichen ist, gehen wir nur zweimal nach rechts und einmal nach links: “110”. Mit dieser Methode können wir nun jeden Buchstaben unseres Textes mit Bits ersetzen und erhalten einen Text, der 99 Bit statt 200 Bit groß ist. Somit konnten wir mehr als die Hälfte der Daten sparen. Hier der Vergleich zwischen dem ursprünglichen Text in Bits und dem mit Huffman kodierten Text:

11101010100101100011011000110110110101101111011010110110101101101010011001110110000001000100011010100110100101100000010010000110000011100000111011001110111101100011011010101110001011101100111010000100

100001111011011100011110100110010011100000010100001111100010101101110110101110011110101101101011001

Wenn ihr selbst Huffman-Bäume erzeugen wollt, könnt ihr dieses Tool ausprobieren. Auch wenn man mit dem Huffman-Code bereits große Datenmengen einsparen kann, gibt es noch effektivere Komprimierungsalgorithmen. So kann man mit gzip die Datenmenge um bis zu 90% reduzieren.

Komprimierung bringt viele Vorteile mit sich, unter anderem schnellere Ladezeiten und einfachere und schnellere Übermittlung der Daten, somit spart es Datenvolumen und ist außerdem nachhaltiger. Daher ist dies ein Grund, warum wir Komprimierung oft in der Entwicklung von Smartphone Anwendungen verwenden.

Category:
  Allgemein
this post was shared 0 times
 000

Leave a Reply

Your email address will not be published.

Diese Website verwendet Akismet, um Spam zu reduzieren. Erfahre mehr darüber, wie deine Kommentardaten verarbeitet werden.