Information Theory/Entropy Coding According to Huffman: Difference between revisions
Die Seite wurde neu angelegt: „ {{Header |Untermenü=Quellencodierung – Datenkomprimierung |Vorherige Seite=Komprimierung nach Lempel, Ziv und Welch |Nächste Seite=Weitere Quellencodierv…“ |
No edit summary |
||
| Line 6: | Line 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== | ||
Revision as of 00:02, 15 May 2016
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.
