Die Webseiten der Fachschaft Informatik am ERG Saalfeld
Der Huffmann-Algorithmus
Dieses Verfahren beruht darauf, häufig vorkommende Zeichen in einem kürzeren und selten vorkommende Symbole in einem
längeren Code zu verschlüsseln.
Reihenfolge
|
Beispiel:
MISSISSIPPI
|
Häufigkeitsanalyse - die Ermittlung der Häufigkeit jedes vorkommenden Zeichen
|
Zeichen |
M |
P |
I |
S |
Häufigkeit
| 1 |
2 |
4 |
4 |
|
Ein binärer Baum, aus dem sich der Huffman-Code jedes einzelnen
Zeichens ableiten lässt, wird erzeugt.
Man beginnt immer mit den zwei Buchstaben, welche die
kleinste Häufigkeit besitzen und addiert deren Häufigkeiten.
Mit dieser Summe wird dann weitergerechnet und die nächste Häufigkeit addiert.
Häufigkeit des nächsten Buchstaben
>
Summe
->
Buchstabe wird auf die rechte Seite geschrieben
Häufigkeit des nächsten Buchstaben
<
Summe
->
Buchstabe wird auf die linke Seite geschrieben
Dies wird nun solange wiederholt, bis alle Zeichen in einem einzigen Baum sind.
Wenn man an einer Verzweigung des Baumes nach
links eine "0" und an einer Verzweigung nach rechts eine "1" zuordnet,
ergibt sich ein eindeutiger Code für jedes einzelne Zeichen.
|
|
Dem häufigsten Zeichen wird der kürzest mögliche Code, dem seltensten der optimal längste Code zugeordnet.
|
Zeichen
| S |
I |
M |
P |
Code
| 0 |
11 |
100 |
101 |
|
In der Ursprungsdatei wird jedes Zeichen durch seinen neuen Code ersetzt.
|
M I S S I S S I P P I
=
100 11 0 0 11 0 0 11 101 101 11
|
Die Information, welcher Code welchem Zeichen entspricht, wird an die Datei angehängt.
Meist werden dort noch weitere diverse statistische und technische Parameter gespeichert.
Dadurch vergrößert sich die Datei wieder geringfügig.
Mit dem Huffman-Verfahren lässt sich ein Text typischerweise auf ca. 2/3 seiner
ursprünglichen Größe reduzieren.
|
Vergleich:
MISSISSIPPI
(ASCII):
11 BYTE = 88 Bit
MISSISSIPPI
(Huffman-verschl.):
21 Bit
Einsparung bei diesem Wort:
67 Bit = 76%
|
Es lässt sich mit mathematischen Mitteln beweisen, dass keine einfach durchgeführte Kodierungsstrategie zu einem besseren Ergebnis führen kann.
Hier das ganze noch als animiertes Gif:
Aufgaben
- Wenden Sie diesen Algorithmus auf das Wort "ABRAKADABRA" an.
- Beschreiben Sie diesen Algorithmus in Worten.
- Informieren Sie sich über den Erfinder dieses Algorithmus. (5 Fakten)
- Zeigen Sie, dass es sich um einen Algorithmus handelt.
zurück
© ERG Saalfeld - Anne-Kathrin Kaptain 08.12.2016 ; animiertes Gif: HD. Kirmse Januar 2020
|