Am Beispiel Des Huffman- Algorithmus - Burgnetz.de
Mathematik für Information und Kommunikation Am Beispiel des HuffmanAlgorithmus Thomas Borys und (Christian Urff)
Huffman im Alltag MPEG JPEG Telefax MP3 ZIP
David Huffman David DavidHuffman Huffman [1925-1999] [1925-1999] www.soe.ucsc.edu/people/faculty/huffman.html
Gliederung 1. 1. Grundidee Grundideedes desHuffman-Algorithmus Huffman-Algorithmus 2. 2. Der DerHuffman-Algorithmus Huffman-Algorithmusexemplarisch exemplarischan aneinem einemBeispiel Beispiel 3. 3. Eigenschaften Eigenschaftender derHuffman-Codes Huffman-Codes 4. 4. Anwendung Anwendungdes desHuffman Huffmanbeim beimTelefax Telefax
Grundidee des Huffman-Algorithmus Kompressionsverfahren Kompressionsverfahren Verlustfreie Verlustfreie Kompression Kompression Verlustbehaftete Verlustbehaftete Kompression Kompression
Grundidee des Huffman-Algorithmus „Luft“ weglassen Verlustfreie Kompression
Grundidee des Huffman-Algorithmus Zusammenfassung skda fjlsakd lksdaj lskdaf lsdakj ölsadk jflaskfj sadflk lkdsjf lksdajf ölsakjf ölsakf lksadjflksajfdölsakdjfl sdlkfj sdalökj fldsak fjsaldök jlsadk jfaölskjd flsadkjfaslökjf aölskjfdiejlökajdsfiealkfjaiejlkasjfoiasejlkf saelifjlask jfsalifdjlksdajf ölskaj ldksaj ldsakfjlisafjlkds lkdsajfiejlkdsajfiesf lksadjfaeslksadjisaejflkdsjf lkdsjfilesajflkd isajfelkjldskjfasilfj esalkjflisadfjelkdjsafi eölakfjesaoi Unwichtiges weglassen ölaskjflsakdjfoiasjelkjesalfjafsalfj sdlakf jldsakfjfsaiejlksadjfiesa lkdsaj lidjsfa lkeaj iaejlkdf ielkf ösaldkfjlesajflkd isajfelkjldskjfasilfj esalkjflisadfjelkdjsafi eölakfjesaoi ölaskjflsakdjfoiasjelkjesalfjafsalfj sdlakf jldsakfjfsaiejlksadjfiesa lkdsaj lidjsfa lkeaj iaejlkdf ielkf ösaldkfjlesajflkd isajfelkjldskjfasilfj esalkjflisadfjelkdjsafi eölakfjesaoi ölaskjflsakdjfoiasjelkjesalfjafsalfj sdlakf jldsakfjfsaiejlksadjfiesa lkdsaj lidjsfa lkeaj iaejlkdf ielkf ösaldkfjlesajflkd isajfelkjldskjfasilfj esalkjflisadfjelkdjsafi eölakfjesaoi ölaskjflsakdjfoiasjelkjesalfjafsalfj sdlakf jldsakfjfsaiejlksadjfiesa lkdsaj lidjsfa lkeaj iaejlkdf ielkf ösaldkfjlesajflkd isajfelkjldskjfasilfj esalkjflisadfjelkdjsafi jldsakfjfsaiejlksadjfiesa lkdsaj lidjsfa lkeaj iaejlkdf ielkf ösaldkfjlesajflkd isajfelkjldskjfasilfj esalkjflisadfjelkdjsafi eölakfjesaoi ölaskjflsakdjfoiasjelkjesalfjafsalfj sdlakf jldsakfjfsaiejlksadjfiesa lkdsaj lidjsfa lkeaj iaejlkdf ielkf ösaldkfjlesajflkd isajfelkjldskjfasilfj esalkjflisadfjelkdjsafi jldsakfjfsaiejlksadjfiesa lkdsaj lidjsfa lkeaj iaejlkdf ielkf ösaldkfjlesajflkd isajfelkjldskjfasilfj esalkjflisadfjelkdjsafi eölakfjesaoi ölaskjflsakdjfoiasjelkjesalfjafsalfj sdlakf jldsakfjfsaiejlksadjfiesa lkdsaj lidjsfa lkeaj iaejlkdf ielkf ösaldkfjlesajflkd isajfelkjldskjfasilfj esalkjflisadfjelkdjsafi eölakfjesaoi ölaskjflsakdjfoiasjelkjesalfjafsalfj sdlakf jldsakfjfsaiejlksadjfiesa lkdsaj lidjsfa lkeaj iaejlkdf ielkf ösaldkfjl esajflkd isajfelkjldskjfasilfj esalkjflisadfjelkdjsafi eölakfjesaoi ölaskjflsakdjfoiasjelkjesalfjafsalfj sdlakf jldsakfjfsaiejlksadjfiesa lkdsaj lidjsfa lkeaj iaejlkdf ielkf ösaldkfjlesajflkd isajfelkjldskjfasilfj esalkjflisadfjelkdjsafi eölakfjesaoi ölaskjflsakdjfoiasjelkjesalfjafsalfj sdlakf jldsakfjfsaiejlksadjfiesa lkdsaj lidjsfa lkeaj iaejlkdf ielkf ösaldkfjl Verlustbehaftete Kompression
Grundidee des Huffman-Algorithmus !!!!! ! i eei r f r t f ulusst l r vveer t itietet e rrbbe a a s s u „Luft“ uweglassen m m h t rri ith o lglgo A nn-A a a m f m f f HHuuf r DDeer Verlustfreie Kompression
Grundidee des Huffman-Algorithmus ABRAKADABRA ASCII ASCII A 01000001 A 01000001 B 01000010 B 01000010 88 88Bit Bit Idee: Idee: häufig häufigvorkommende vorkommendeZeichen Zeichenbekommen bekommen einen einenkürzeren kürzerenCode, Code,selten seltenvorkommende vorkommende Zeichen Zeichenein einlängeres längeresCodewort Codewort z.B. z.B.A 0 A 0 B 11 B 11 . .
Grundidee des Huffman-Algorithmus Häufig benötigte Bücher stellt man in greifbare Nähe (Augenhöhe) Selten benötigte Bücher verstaut man weiter oben oder unten
Grundidee des Huffman-Algorithmus Morse-Code Morse-Code AA ··-EE ·· II ···· M M ---QQ ----··-UU ····-YY --· ·---- BB --······ FF ····--·· JJ ··----NN --·· RR ··--· · VV · ·· ·· ·-ZZ ----· ·· · CC --··--·· GG ----·· KK --··-OO ----SS ······ W W · ·---- DD --···· HH . . LL ··--···· PP ··----·· Morse TTSamuel -Samuel Morse XX [1791-1872] -[1791-1872] -· ·· ·-www.morsehistoricsite.org www.morsehistoricsite.org
Der Huffman-Algorithmus exemplarisch an einem Beispiel Ziel: Ziel:Jedem Jedemim imText Textvorkommenden vorkommendenZeichen Zeichenwird wirdein einBinärcode Binärcode zugewiesen! zugewiesen! Wurzelbaum Wurzelbaum Wurzel 0 1 Knoten Kanten 1 0 Blätter A 0 B 1 C 0 1 D E
Der Huffman-Algorithmus exemplarisch an einem Beispiel Text: Text: ABRAKADABRA ABRAKADABRA Häufigkeitsanalyse: Häufigkeitsanalyse: Buchstaben A Häufigkeit 5 B R K D
Der Huffman-Algorithmus exemplarisch an einem Beispiel Text: Text: ABRAKADABRA ABRAKADABRA Häufigkeitsanalyse: Häufigkeitsanalyse: Buchstaben A B Häufigkeit 5 2 R K D
Der Huffman-Algorithmus exemplarisch an einem Beispiel Text: Text: ABRAKADABRA ABRAKADABRA Häufigkeitsanalyse: Häufigkeitsanalyse: Buchstaben A B R Häufigkeit 5 2 2 K D
Der Huffman-Algorithmus exemplarisch an einem Beispiel Text: Text: ABRAKADABRA ABRAKADABRA Häufigkeitsanalyse: Häufigkeitsanalyse: Buchstaben A B R K Häufigkeit 5 2 2 1 D
Der Huffman-Algorithmus exemplarisch an einem Beispiel Text: Text: ABRAKADABRA ABRAKADABRA Häufigkeitsanalyse: Häufigkeitsanalyse: Buchstaben A B R K D Häufigkeit 5 2 2 1 1 A 5 B 2 R 2 D 1 K 1 Huffman-Liste 1
Der Huffman-Algorithmus exemplarisch an einem Beispiel DK 2 Zusammenführung D 1 K 1 D 1 A 5 B 2 DK 2 D 1 R 2 K 1 Huffman-Liste 2 K 1
Der Huffman-Algorithmus exemplarisch an einem Beispiel BR 4 A 5 B 2 DK 2 R 2 D 1 K 1 Huffman-Liste 3
Der Huffman-Algorithmus exemplarisch an einem Beispiel BDKR 6 A 5 BR 4 B 2 DK 2 R 2 D 1 K 1 Huffman-Liste 4
Der Huffman-Algorithmus exemplarisch an einem Beispiel ABDKR 11 A 5 BDKR 6 BR 4 B 2 DK 2 R 2 D 1 K 1 Huffman-Liste 5
Der Huffman-Algorithmus exemplarisch an einem Beispiel Codebaum Codetabelle Buchstaben Binärcode ABDKR 11 A 5 A 0 1 0 BDKR 6 1 BR 4 0 B 2 DK 2 1 R 2 0 D 1 1 K 1 0
Der Huffman-Algorithmus exemplarisch an einem Beispiel Codebaum Codetabelle Buchstaben Binärcode ABDKR 11 A 5 0 1 0 BDKR 6 1 BR 4 0 B 2 DK 2 1 R 2 0 D 1 1 K 1 A 0 B 100
Der Huffman-Algorithmus exemplarisch an einem Beispiel Codebaum Codetabelle Buchstaben Binärcode ABDKR 11 A 5 0 1 0 BDKR 6 1 BR 4 0 B 2 DK 2 1 R 2 0 D 1 1 K 1 A 0 B 100 D 110
Der Huffman-Algorithmus exemplarisch an einem Beispiel Codebaum Codetabelle Buchstaben Binärcode ABDKR 11 A 5 0 1 0 BDKR 6 1 BR 4 0 B 2 DK 2 1 R 2 0 D 1 1 K 1 A 0 B 100 D 110 K 111
Der Huffman-Algorithmus exemplarisch an einem Beispiel Codebaum Codetabelle Buchstaben Binärcode ABDKR 11 A 5 0 1 0 BDKR 6 1 BR 4 0 B 2 DK 2 1 R 2 0 D 1 1 K 1 A 0 B 100 D 110 K 111 R 101
Der Huffman-Algorithmus exemplarisch an einem Beispiel Buchstaben Binärcode Codierung Codierungdes desTextes: Textes: AA BB RR AA KK AA DD AA BB RR AA 0 100 101 0 111 0 110 Eingabe: Eingabe: Hauptteil: Hauptteil: Ausgabe: Ausgabe: 0 100 101 0 A 0 B 100 D 110 K 111 R 101 Zusammenfassung Zusammenfassungdes desAlgorithmus: Algorithmus: Häufigkeitstabelle Häufigkeitstabelle 1.1.Erstelle Erstelledie dieHuffman-Liste. Huffman-Liste. 2.2.Wiederhole die Wiederhole dieZusammenführung Zusammenführungder derbeiden beidenmit mitder dergeringsten geringsten Häufigkeit Häufigkeitbeschrifteten beschriftetenBäume Bäumeso solange, lange,bis bisdie dieHuffman-Liste Huffman-Listenur nur noch nochaus auseinem einemBaum, Baum,dem demHuffman-Baum, Huffman-Baum,besteht. besteht. Codebaum Codebaum Interaktives InteraktivesExperimentiersystem: Experimentiersystem:www.ph-karlsruhe.de/ ziegenbalg www.ph-karlsruhe.de/ ziegenbalg
Eigenschaften des Huffman-Codes Decodieren Decodierenwir wirden denText: Text: ABDKR 11 11001110101 11001110101 D A 5 0 1 0 BDKR 6 1 BR 4 0 B 2 DK 2 1 R 2 0 D 1 1 K 1
Eigenschaften des Huffman-Codes Decodieren Decodierenwir wirden denText: Text: ABDKR 11 110 110 01110101 01110101 D A 5 0 1 0 BDKR 6 1 BR 4 0 B 2 DK 2 1 R 2 0 D 1 1 K 1 A
Eigenschaften des Huffman-Codes Decodieren Decodierenwir wirden denText: Text: ABDKR 11 110 110 00 1110101 1110101 D A 5 0 1 0 BDKR 6 1 BR 4 0 B 2 DK 2 1 R 2 0 D 1 1 K 1 A K
Eigenschaften des Huffman-Codes Decodieren Decodierenwir wirden denText: Text: ABDKR 11 A 5 110 110 00 111 111 0101 0101 0 1 0 D BDKR 6 1 BR 4 0 B 2 DK 2 1 R 2 0 D 1 1 K 1 A K A
Eigenschaften des Huffman-Codes Decodieren Decodierenwir wirden denText: Text: ABDKR 11 A 5 110 110 00 111 111 00 101 101 0 1 0 D BDKR 6 1 BR 4 0 B 2 DK 2 1 R 2 0 D 1 1 K 1 A K A R
Eigenschaften des Huffman-Codes Der DerHuffman-Code Huffman-Codeist istpräfixfrei. präfixfrei. Vergleich Vergleichmit mitdem demTelefonsystem: Telefonsystem: Das Telefonnummernsystem Das Telefonnummernsystemist istauch auchpräfixfrei. präfixfrei. Beispiel: Beispiel: Wählt Wähltman man110, 110,„weiß“ „weiß“das dasSystem, System,dass dassman manfertig fertigmit mitwählen wählenist istund undverbindet verbindeteinen einen mit der Polizei. Das liegt daran, dass die Nummer 110 nie Anfangsteil (Präfix) einer mit der Polizei. Das liegt daran, dass die Nummer 110 nie Anfangsteil (Präfix) einer anderen anderenNummer, Nummer,z.B. z.B.gibt gibtes eskeine keineTelefonnummer Telefonnummer11011. 11011. Woran Woranerkennt erkenntman maneinen einenpräfixfreien präfixfreienCode? Code? Ein Codebaum liefert einen präfixfreien Ein Codebaum liefert einen präfixfreienCode, Code,wenn wenndie diezu zucodierenden codierendenZeichen Zeichennur nurinin den denBlättern Blätterndes desBaumes Baumesstehen. stehen.Beim BeimMorsecode Morsecodeist istdies diesbeispielsweise beispielsweisenicht nichtder der Fall, daher muss nach jedem Buchstaben eine kleine Pause mitgeteilt werden. Fall, daher muss nach jedem Buchstaben eine kleine Pause mitgeteilt werden. 0 1 0 1 1 0 E A B C D I präfixfrei präfixfrei - - N N Morsecode Morsecode T M
Eigenschaften Huffman-Codes A 5 B 2 DK 2 D 1 R 2 K 1 Huffman-Liste 2 In Inder derHuffman-Liste Huffman-Listezwei zweihaben habenwir wir„B“ „B“und und„R“ „R“zu zueinem einemBaum Baum zusammengeführt, zusammengeführt,wir wirhätten hättenauch auch„DK“ „DK“und und„B“ „B“wählen wählenkönnen. können.
Eigenschaften des Huffman-Codes Codebaum* Codetabelle* ABDKR 11 0 Buchstaben Binärcode 1 A 5 BDKR 6 0 1 R 2 BDK 4 0 1 B 2 DK 2 0 D 1 1 K 1 A 0 B 110 D 1110 K 1111 R 10
Eigenschaften des Huffman-Codes Buchstaben Binärcode Codierung* Codierung*des desTextes: Textes: AA BB RR AA KK AA DD AA BB RR AA 0 110 10 0 1111 0 1110 0 110 10 0 Mittlere MittlereCodewortlänge Codewortlänge23/11 2,1. 23/11 2,1. L p l A 0 B 110 D 1110 K 1111 R 10 n i i i 1 Die DieFormel Formelliefert liefertden denErwartungswert Erwartungswertder derZufallsvaribalen Zufallsvaribalen„Codewortlänge“. „Codewortlänge“. Der DerHuffman-Algorithmus Huffman-Algorithmusminimiert minimiertdie diemittlere mittlereCodewortlänge Codewortlängeund undliefert lieferteine eine möglichst kurze also eine optimalen Codierung. möglichst kurze also eine optimalen Codierung. Die DieHuffman-Codewortlänge Huffman-Codewortlängeist istein einMaß Maßfür fürdie dieEntropie Entropieeines einesTextes. Textes.
Anwendungsbeispiele MPEG JPEG Telefax MP3 ZIP
1728 Pixel pro Zeile Telefax-Codierung Speicherplatzbedarf: 1011*1728 1.747.008 Bit (ca. 1,7 MBit) Übertragung würde 1747008 bit/2400 bit/sec 727sec bzw. 12 min dauern. 1011 Zeilen
Lauflängencodierung 7w, 4s, 8w, 10s, 4w, 3s, 7w, 3s, 8w, 3s, 4w, 3s, 5w, 3s, 5w, 6s, 5w, 16s, 2w, 3s, 8w, 3s, 7w Lauflängencodierung (run-length) Häufigkeitsanalyse: 8 7 6 5 4 3 2 1 0 3s 4w 8w 7w 5w 10s 4s 6s 16s 2w
Telefax Häufigkeitsanalyse Huffman-Algorithmus
Telefax-Code: Lauflänge Codes für Schwarz (Ausschnitt) 1s 010 2s 11 3s 10 4s 011 5s 0011 6s 0010 7s 00011 8s 000101 9s 000100 10s 0000100 11s 0000101 12s 0000111 13s 00000100 14s 00000111 15s 000011000 16s 0000010111 17s 0000011000 18s 0000001000 19s 00001100111 20s 00001101000
Effizienz der Kompression Es lassen sich Kompressionsraten von bis zu 1:50 erreichen. Ohne Kompression Mit Kompression Datenmenge 1,7 MBit 0,04 MBit Übertragungsdauer 12 min (720 sec) 15 sec
ti.t. i e kke m aam s k s rrk e e fm fm u u A ee A r r h IIh r r ü ffü e k e nk DDaan Mathematik für Information und Kommunikation Am Beispiel des HuffmanAlgorithmus Thomas Borys und (Christian Urff)
Erstelle die Huffman-Liste. 2. Wiederhole die Zusammenführung der beiden mit der geringsten Häufigkeit beschrifteten Bäume so lange, bis die Huffman-Liste nur noch aus einem Baum, dem Huffman-Baum, besteht. Ausgabe: Codebaum Zusammenfassung des Algorithmus: Eingabe: Häufigkeitstabelle Hauptteil: 1. Erstelle die Huffman-Liste. 2.
and Huffman code can be found in [2] (pg. 190-201 and 441-449). Finally, the code stream for the block is formed by applying the code Huffman code tables as shown in Tables 3 and 4. 3 Fault Tolerant Design for the JPEG Huffman Coding System From the Huffman coding process as described in the previous section, the Huffman code tables play an
fax 800-836-2765 www.chapman-huffman.com email: orders@chapman-huffman.com 5 800-225-4621 4 fax 800-836-2765 www.chapman-huffman.com email: orders@chapman-huffman.com handpiece controls, trays arms handpiece controls, trays arms 3 handpiece automatic mini control with floor valves gray straight 60-250-00 1182.90
according to Huffman, which assigns short code words to symbols frequently used and long code words to symbols rarely used for both DC and AC coefficients, each symbol is encoded with a variable-length code. Figure 2(a) Flowchart of Huffman Algorithm 3.1 Huffman Coding The Huffman encoding algorithm starts by constructing
Fig3. Huffman tree (2) From the Huffman tree it can be concluded that the Huffman code that is formed is in table 1. Table 3. Huffman Coding Character Huffman Code E 0000 I 0001 K 001 M 10 T 11 A 01 Advances in Health Science Research, volume 6 438
Huffman (1) Problématique L'encodage de Huffman nécessite une connaissance à priori de la probabilité d'apparition des symboles. Il faut alors effectuer une étude statistique des données pour générer un code. Ensuite effectuer l'encodage de Huffman. Procédure d'encodage se fait en deux étapes.
result, we get a Huffman tree, and by labelling each left and right edge to 0 and 1, we create codewords for symbols. For example, the codeword for A is 00 and codeword for B is 0101. This completes the basic Huffman encoding process. The CHE only sends the length of each Huffman codeword, but requires additional computation as explained in the .
9 Huffman encoding Huffman encoding: Uses variable lengths for different characters to take advantage of their relative frequencies. Some characters occur more often than others. If those characters use 8 bits each, the file will be smaller. Other characters need 8, but that's OK; they're rare. Char ASCII value ASCII (binary) Hypothetical Huffman
Waterhead 1003 1346 St James 1041 1393 Chadderton South 1370 964 Failsworth West 1596 849 Chadderton North 2038 791 Chadderton Central 2096 695 Failsworth East 2234 643 Shaw 2295 893 Royton South 3008 628 Royton North 3297 808 Crompton 3858 510 Saddleworth West and Lees 3899 380 Saddleworth North 5892 309 Saddleworth South 6536 260 3.3 There is a wealth of evidence to suggest links between .
