Informationstheorie/Entropiecodierung nach Huffman: Unterschied zwischen den Versionen
David (Diskussion | Beiträge) (Die Seite wurde neu angelegt: „ {{Header |Untermenü=Quellencodierung – Datenkomprimierung |Vorherige Seite=Komprimierung nach Lempel, Ziv und Welch |Nächste Seite=Weitere Quellencodierv…“) |
David (Diskussion | Beiträge) |
||
| Zeile 6: | Zeile 6: | ||
}} | }} | ||
| − | ==Der Huffman–Algorithmus== | + | ==Der Huffman–Algorithmus== |
| + | |||
| + | Wir setzen nun voraus, dass die Quellensymbole qν einem Alphabet $\{q_μ\}$ = {'''A''', '''B''', '''C''', ...} mit dem Symbolumfang M entstammen und statistisch voneinander unabhängig seien. | ||
| + | Beispielsweise gelte für den Symbolumfang $M$ = 8: | ||
| + | |||
| + | David A. Huffman hat 1952 – also kurz nach Shannons bahnbrechenden Veröffentlichungen – einen Algorithmus zur Konstruktion von optimalen präfixfreien Codes angegeben. | ||
| + | Dieser ''Huffman–Algorithmus'' soll hier ohne Herleitung und Beweis angegeben werden, wobei wir uns hier auf Binärcodes beschränken. Das heißt: Für die Codesymbole gelte stets $c_ν$ ∈ {'''0''', '''1'''}. Hier ist das Rezept: | ||
| + | *Man ordne die Symbole nach fallenden Auftrittswahrscheinlichkeiten. | ||
| + | *Man fasse die zwei unwahrscheinlichsten Symbole zu einem neuen Symbol zusammen. | ||
| + | *Man wiederhole (1) und (2), bis nur mehr zwei (zusammengefasste) Symbole übrig bleiben. | ||
| + | *Man codiert die wahrscheinlichere Symbolmenge mit '''1''' und die andere Menge mit '''0'''. | ||
| + | *Man ergänzt in Gegenrichtung (also von unten nach oben) die jeweiligen Binärcodes der aufgespaltenen Teilmengen entsprechend den Wahrscheinlichkeiten mit '''1''' bzw. '''0'''. | ||
| + | |||
| + | |||
| + | {{Beispiel}} | ||
| + | Ohne Einschränkung der Allgemeingültigkeit setzen wir voraus, dass die $M$ = 6 Symbole '''A''', ... , '''F''' bereits entsprechend ihren Wahrscheinlichkeiten geordnet sind: | ||
| + | |||
| + | Durch paarweises Zusammenfassen und anschießendem Sortieren erhält man in fünf Schritten die folgenden Symbolkombinationen (resultierende Wahrscheinlichkeiten in Klammern): | ||
| + | :1. '''A''' (0.30), '''B''' (0.24), '''C''' (0.20), '''EF''' (0.14), '''D''' (0.12), | ||
| + | :2. '''A''' (0.30), '''EFD''' (0.26), '''B''' (0.24), '''C''' (0.20), | ||
| + | :3. '''BC''' (0.44), '''A''' (0.30), '''EFD''' (0.26), | ||
| + | :4. '''AEFD''' (0.56), '''BC''' (0.44), | ||
| + | :5. Root '''AEFDBC''' (1.00). | ||
| + | Rückwärts (gemäß den Schritten 5 bis 1) erfolgt dann die Zuordnung zu Binärsymbolen. Ein „x” weist darauf hin, dass in den nächsten Schritten noch Bits hinzugefügt werden müssen: | ||
| + | :5. '''AEFD → 1'''x, '''BC → 0'''x, | ||
| + | :4. '''<u>A → 11</u>''', '''EFD → 10'''x, | ||
| + | :3. '''<u>B → 01</u>''', '''<u>C → 00</u>''', | ||
| + | :2. '''EF → 101'''x, '''<u>D → 100</u>''', | ||
| + | :1. '''<u>E → 1011</u>''', '''<u>F → 1010</u>'''. | ||
| + | Die Unterstreichungen markieren die endgültige Binärcodierung. | ||
| + | |||
| + | {{end}} | ||
| + | |||
| + | |||
| + | |||
==Zum Begriff „Entropiecodierung”== | ==Zum Begriff „Entropiecodierung”== | ||
==Darstellung des Huffman–Codes als Baumdiagramm== | ==Darstellung des Huffman–Codes als Baumdiagramm== | ||
Version vom 15. Mai 2016, 00:02 Uhr
Inhaltsverzeichnis
Der Huffman–Algorithmus
Wir setzen nun voraus, dass die Quellensymbole qν einem Alphabet $\{q_μ\}$ = {A, B, C, ...} mit dem Symbolumfang M entstammen und statistisch voneinander unabhängig seien. Beispielsweise gelte für den Symbolumfang $M$ = 8:
David A. Huffman hat 1952 – also kurz nach Shannons bahnbrechenden Veröffentlichungen – einen Algorithmus zur Konstruktion von optimalen präfixfreien Codes angegeben. Dieser Huffman–Algorithmus soll hier ohne Herleitung und Beweis angegeben werden, wobei wir uns hier auf Binärcodes beschränken. Das heißt: Für die Codesymbole gelte stets $c_ν$ ∈ {0, 1}. Hier ist das Rezept:
- Man ordne die Symbole nach fallenden Auftrittswahrscheinlichkeiten.
- Man fasse die zwei unwahrscheinlichsten Symbole zu einem neuen Symbol zusammen.
- Man wiederhole (1) und (2), bis nur mehr zwei (zusammengefasste) Symbole übrig bleiben.
- Man codiert die wahrscheinlichere Symbolmenge mit 1 und die andere Menge mit 0.
- Man ergänzt in Gegenrichtung (also von unten nach oben) die jeweiligen Binärcodes der aufgespaltenen Teilmengen entsprechend den Wahrscheinlichkeiten mit 1 bzw. 0.
Ohne Einschränkung der Allgemeingültigkeit setzen wir voraus, dass die $M$ = 6 Symbole A, ... , F bereits entsprechend ihren Wahrscheinlichkeiten geordnet sind:
Durch paarweises Zusammenfassen und anschießendem Sortieren erhält man in fünf Schritten die folgenden Symbolkombinationen (resultierende Wahrscheinlichkeiten in Klammern):
- 1. A (0.30), B (0.24), C (0.20), EF (0.14), D (0.12),
- 2. A (0.30), EFD (0.26), B (0.24), C (0.20),
- 3. BC (0.44), A (0.30), EFD (0.26),
- 4. AEFD (0.56), BC (0.44),
- 5. Root AEFDBC (1.00).
Rückwärts (gemäß den Schritten 5 bis 1) erfolgt dann die Zuordnung zu Binärsymbolen. Ein „x” weist darauf hin, dass in den nächsten Schritten noch Bits hinzugefügt werden müssen:
- 5. AEFD → 1x, BC → 0x,
- 4. A → 11, EFD → 10x,
- 3. B → 01, C → 00,
- 2. EF → 101x, D → 100,
- 1. E → 1011, F → 1010.
Die Unterstreichungen markieren die endgültige Binärcodierung.
