Appearance
Kompression
Informationsgehalt
Buchstabenhäufigkeit
Die Buchstabenhäufigkeit gibt an, wie oft ein Buchstabe in einem Text vorkommen. Die Häufigkeit der einzelnen Buchstaben ist je nach Sprache unterschiedlich. Das folgende Diagramm zeigt die durchschnittliche Buchstabenhäufigkeit in deutschen Texten:
Informationsgehalt
Wir führen ein Experiment durch. Aus einem deutschen Text werden etwa 40% der Buchstaben entfernt. Zuerst werden die vier häufigsten Buchstaben E, N, R und I entfernt. Danach werden diese Buchstaben sowie T, S und A beibehalten und die restlichen entfernt. Obschon etwa die gleiche Menge Buchstaben entfernt worden sind, bleibt der Text nach dem Entfernen der häufigen Buchstaben verständlicher.
Offenbar tragen die häufigen Buchstaben weniger zum Inhalt des Textes bei. Sie haben einen kleineren Informationsgehalt.
Experiment
Um uns den Informationsgehalt besser vorstellen zu können, führen wir ein Experiment durch.
- Im folgenden Text sind nur ca. 60% der Buchstaben vorhanden, und zwar diejenigen, welche am häufigsten in der deutschen Sprache vorkommen:
er reie s sae r Na n in? Es is er aer i seine in; Er a en naen in e Ar, Er ass in sier, er ae in ar.
- Im folgenden Text sind ebenfalls ungefähr 60% der Buchstaben vorhanden, nun aber die seltensten:
Wr rtt o pat durch acht ud Wd? t dr Vatr mt m Kd; r hat d Kab wohl dm Arm, r fat h chr, r halt h warm.
Es fällt uns auf, dass wir den zweiten Text viel mehr Wörter erraten können und eventuell sogar den Text erkennen (es handelt sich um die erste Strophe vom Gedicht «Erlkönig».
Wir können daraus schliessen, dass die seltenen Buchstaben im zweiten Text mehr Information enthalten als die häufigen Buchstaben.
Redundanz
Online-Tool Informationsgehalt
Bedeutung
Der Mathematiker Claude Shannon hat 1948 auf Grund der Erkenntnis, dass nicht alle Zeichen gleich viel Information enthalten, die Informationstheorie begründet.
Sie beschreibt den Zusammenhang zwischen Information und Codierungen mit Hilfe der Wahrscheinlichkeitstheorie. Dank der Informationstheorie kann mathematisch bewiesen werden, dass mit bestimmten binären Codierungen die Daten weniger Speicherplatz benötigen.
Heute werden die Erkenntnisse aus der Informationstheorie vielerorts eingesetzt, beispielsweise
- in der Kommunikation zwischen Computern (z.B. WLAN, Mobilfunk),
- in der Kryptologie, also bei der Verschlüsselung von Daten,
- bei der Speicherung von Daten (z.B. Word-Dokumente, Bilder, Musik),
- bei der Erzeugung von Zufall im Computer.
Huffman-Codierung
David Huffman hat 1952 ein Verfahren entwickelt, mit welchem Zeichen platzsparender codiert werden können. Seine Idee ist, dass Zeichen, welche häufig im Text vorkommen, einen kürzeren Code erhalten, als Zeichen, welche selten im Text vorkommen.
Die Huffman-Codierung und ähnliche Verfahren werden für das Komprimieren von Dateiformaten wie DOCX, JPG oder MP3 eingesetzt. [2]
Binärbaum
Bei der Textcodierung haben wir schon Binärbäume kennengelernt. Sie eignen sich zum decodieren von binären Nachrichten. Dazu beginnen wir beim Startknoten zuoberst. Von diesem aus geht es entweder nach links oder rechts unten weiter. Eine 0 im Code bedeutet nach links gehen, eine 1 nach rechts gehen. Wenn ein Knoten mit einem Buchstaben erreicht wird, hat man ein Zeichen decodiert, man beginnt wieder von vorne.
Huffman-Algorithmus
Am Beispiel des Texts «EINTRITT FREI» wird der Huffman-Algorithmus erläutert.
1. Häufigkeitstabelle erstellen
Zuerst werden alle im Text vorkommenden Zeichen und deren Häufigkeiten in eine Tabelle eingetragen:
| Zeichen | E | I | N | T | R | ␣ | F |
|---|---|---|---|---|---|---|---|
| Häufigkeit | 2 | 3 | 1 | 3 | 2 | 1 | 1 |
2. Binärbaum erstellen
Nun geht es darum, einen Binärbaum zu erstellen. Dazu wird zunächst für jeden Buchstaben ein Knoten gebildet. Dabei wird die Häufigkeit in den Knoten geschrieben, der Buchstaben darunter.
Nun werden die zwei Knoten mit den kleinsten Häufigkeiten an einen neuen Knoten angehängt. Der neue Knoten enthält die Summe der Häufigkeiten der ursprünglichen Knoten:
Dies wird wiederholt, bis alle Knoten miteinander verbunden sind. Wenn zwei Knoten die gleiche Häufigkeit haben, spielt es keine Rolle, welcher gewählt wird. Im nächsten Schritt wird der kleinste Knoten «N» mit «R» zusammengefasst. Es könnten aber auch «N» und «E» zusammengefasst werden oder «N» mit dem neu erstellten Knoten.
Der neu erstellte Knoten kann beim nächsten Schritt ebenfalls verwendet werden. Knoten, welche bereits zusammengefasst wurden, werden nun nicht mehr berücksichtigt.
In der Grafik sind jeweils alle Knoten, welche noch zusammengefasst werden müssen, violett oder rot eingefärbt. Der zuletzt neu erzeugte Knoten ist rot eingefärbt.
Wichtig ist, dass immer zwei Knoten so zusammengefasst werden, dass eine möglichst kleine Summe entsteht.
Nun werden die beiden Knoten mit Häufigkeit 2 zusammengefasst:
Die kleinste Summe ist nun 6. Es gibt verschiedene Möglichkeiten, hier werden die Knoten I und T zusammengefasst:
Nun ist die kleinstmögliche Summe 7, indem der übriggebliebene 3-er Knoten und der 4-er Knoten zusammengefasst werden:
Jetzt gibt es nur noch zwei offene Knoten:
3. Kanten beschriften
Wenn der Baum fertig ist, werden alle Äste, welche nach links zeigen, mit einer «0» markiert, alle die nach rechts zeigen mit einer «1».
4. Zeichencodierung aus dem Baum ablesen
Nun kann eine Codierungstabelle erstellt werden, indem der Code für jedes Zeichen beginnend beim Startknoten vom Baum abgelesen wird:
| Zeichen | E | I | N | T | R | ␣ | F |
|---|---|---|---|---|---|---|---|
| Code | 111 | 00 | 101 | 01 | 100 | 1100 | 1101 |
(Quelle: Wikimedia Commons) ↩︎
Quelle: Wikipedia: Huffman coding ↩︎