Codes & Formate. Digitales Koffer packen Mit Huffman Codierung

  • Published on
    05-Apr-2015

  • View
    103

  • Download
    0

Embed Size (px)

Transcript

<ul><li> Folie 1 </li> <li> Codes &amp; Formate </li> <li> Folie 2 </li> <li> Digitales Koffer packen Mit Huffman Codierung </li> <li> Folie 3 </li> <li> Lernziele Sie knnen erklren, warum es normalerweise zwei Schritte braucht um Information mglichst effizient zu speichern, bzw. zu bermitteln Sie knnen erklren, warum die Verteilung der Zeichen in einer Nachricht einen entscheidenden Einfluss darauf hat, wie effizient diese Nachricht komprimiert werden kann Sie wissen, was eine Huffman Codierung ist und knnen sie auf eine kurze Textnachricht anwenden </li> <li> Folie 4 </li> <li> Aufgabenstellung: Sie wollen ihrem Freund eine Text-Botschaft bermitteln, knnen dazu aber nur Zahlen verwenden (entscheiden Sie selbst ob sie Dezimal- oder Binrzahlen benutzen). berlegen Sie sich eine Methode, wie die gegebene Botschaft mglichst genau und mglichst kompakt in Zahlen bersetzt werden kann. Dann erstellen Sie zwei Textdokumente: 1. Ein Dokument soll nur die Zahlenfolge enthalten 2. Im anderen Dokument formulieren Sie eine Anleitung, mit deren Hilfe ihr Freund die ursprngliche Botschaft aus der Zahlenfolge rekonstruieren kann </li> <li> Folie 5 </li> <li> Auswertung Hat es geklappt? Was war schwierig? Welche Informationen wurden bermittelt? (genau?) Wie viele Zahlen waren ntig? (kompakt?) Welche anderen Botschaften knnten so verschickt werden? Welche grundstzliche Idee steckt hinter dieser Methode? </li> <li> Folie 6 </li> <li> Folie 7 </li> <li> Information Genau &amp; Kompakt Codieren Komprimieren Koffer (~ Format) so whlen, dass alles eingepackt werden kann, was man im Urlaub vielleicht brauchen knnte Ziel: Der Koffer soll fr alle Urlaube geeignet sein! Effizient packen, so dass mglichst wenig Luft im Koffer bleibt kann davon abhngen, was genau eingepackt wurde! Ziel: Der Koffer fr diesen Urlaub soll mglichst klein werden! Koffer packen (Komprimieren von Information) </li> <li> Folie 8 </li> <li> Effizientes Packen von Buchstaben 1. Codieren von Buchstaben als binre Codewrter ASCII Code 2. Komprimieren der Bitsequenz z.B. Huffman Codierung krzere Sequenz + neue Codewrter 3. Speichern oder bermitteln 4. Dekomprimieren 5. Decodieren -&gt; Darstellen </li> <li> Folie 9 </li> <li> DezimalHexBinrZeichen 96600110 0000` 97610110 0001a 98620110 0010b 99630110 0011c 100640110 0100d 101650110 0101e 102660110 f 103670110 0111g 104680110 1000h 105690110 1001i 1066A0110 1010j 1076B0110 1011k 1086C0110 1100l 1096D0110 1101m 1106E0110 1110n 1116F0110 1111o 112700111 0000p 113710111 0001q 114720111 0010r 115730111 0011s 116740111 0100t 117750111 0101u 118760111 0110v 119770111 w 120780111 1000x 121790111 1001y 1227A0111 1010z 1237B0111 1011{ 1247C0111 1100| 1257D0111 1101} 1267E0111 1110~ 1277F0111 1111DEL ASCII (American Standard Code for Information Interchange) Kleinbuchstaben: </li> <li> Folie 10 </li> <li> Arbeitsauftrag Ihr Ziel ist herauszufinden, wie die Huffman Codierung funktioniert und sie selbst anwenden zu knnen Benutzen Sie dazu das Applet: WindowsHuffmanShannonFano.jar Experimentieren Sie mit dem Applet (nur Huffman Code) und versuchen Sie, die Fragen im Arbeitsblatt zu beantworten </li> <li> Folie 11 </li> <li> Besprechung Suchen Sie sich einen Partner und tauschen Sie ihre Ergebnisse aus Notieren Sie alles, was ihnen beiden noch unklar ist Knnen Sie die grundstzliche Idee formulieren? </li> <li> Folie 12 </li> <li> Lernziele Sie knnen erklren, warum es normalerweise zwei Schritte braucht um Information mglichst effizient zu speichern, bzw. zu bermitteln Sie knnen erklren, warum die Verteilung der Zeichen in einer Nachricht einen entscheidenden Einfluss darauf hat, wie effizient diese Nachricht komprimiert werden kann Sie wissen, was eine Huffman Codierung ist und knnen sie auf eine kurze Textnachricht anwenden </li> <li> Folie 13 </li> <li> Grundstzliche Idee bei Huffman Hufige Zeichen (Buchstaben) werden in kurze Codewrter bersetzt Das funktioniert nur, wenn der entstehende Code (die Codewrter) prfixfrei ist! Die Bumchen-Taktik zeigt, wie man diese Ideen umsetzt. </li> <li> Folie 14 </li> <li> Huffman Komprimierung </li> <li> Folie 15 </li> <li> Lernziele Sie knne eine kurze Nachricht entschlsseln, die mit dem Huffman Verfahren komprimiert wurde Sie knnen erklren, was ein prfixfreier Code ist Sie knnen beschreiben, fr welche Nachrichten die Huffman Komprimierung besonders geeignet ist Sie kennen einige Vor- und Nachteile von Datenkomprimierung </li> <li> Folie 16 </li> <li> Huffman Decodierung Die binre Nachricht: 0100111101001110010100111110 Die Codewrter: e=110 d=111 o=00 p=010 s=011 u=100 c=101 </li> <li> Folie 17 </li> <li> Und was daran war jetzt prfixfrei ? o=00 p=010 s=011 u=100 c=101 e=110 d=111 </li> <li> Folie 18 </li> <li> Pseudocode... ist eine sprachliche Mischung aus natrlicher Sprache, mathematischer Notation und einer hheren Programmier- sprache arrayMax(A, n) // Input: Ein Array A, der n Integer Werte enthlt // Output: Das maximale Element in A currentMax = A[0] for i = 1 to n - 1 if currentMax &lt; A[i] currentMax = A[i] end return currentMax </li> <li> Folie 19 </li> <li> decodieren(nachricht_bin, codewortliste) // Input: die Bitsequenz nachricht_bin und // eine Liste, die binren Codeworten Zeichen zuordnet // Output: nachricht_txt; die decodierte Nachricht, eine Sequenz von Zeichen nachricht_txt = leer; lnge = 1; while (nachricht_bin != leer) zeichen_bin = get_first_n_bits(nachricht_bin, lnge); if found_in(zeichen_bin, codewortliste) zeichen_txt = get_letter(zeichen_bin, codewortliste) nachricht_txt = attach_letter(zeichen_txt); nachricht_bin = delete_first_n_bits(lnge); lnge = 1; else lnge ++; end return nachricht_txt; </li> <li> Folie 20 </li> <li> Pseudocode fr Huffman Codierung codieren(nachricht_ascii) // Input: die Bitsequenz nachricht_ascii, bestend aus einer Sequenz von ASCII Zeichen (jeweils ein Byte) // Output: nachricht_bin; die codierte Nachricht, eine Bitsequenz // codewortliste; eine Liste, die binren Codeworten ASCII Zeichen zuordnet </li> <li> Folie 21 </li> <li> Komprimierung allgemein originale Nachricht (z.B. ASCII) codierte Nachricht + Liste (z.B. Huffman) codierte Nachricht + Liste (z.B. Huffman) originale Nachricht (z.B. ASCII) Komprimieren, z.B. mit Huffman Codierung Dekomprimieren, z.B. mit Huffman Decodierung speichern /verschicken Welche Informationen braucht es hier? </li> <li> Folie 22 </li> <li> Huffman Komprimierung 1. ASCII Nachricht in 8-er Blcke aufteilen, zhlen wie oft jeder Block vorkommt 2. Blcke nach Hufigkeit ordnen 3. Mit Huffman Baum prfixfreie Codewortliste erstellen 4. ASCII Nachricht nach Huffman bersetzen, siehe Liste 5. Bitsequenz &amp; Liste in File speichern, evtl. verschicken 6. Auch transportiert werden muss die Information, dass dieses File Huffman-codiert ist </li> <li> Folie 23 </li> <li> Fragen zu Huffman &amp; Komprimierung 1. Was ist die grundlegende Idee hinter Huffman Komprimierung? 2. Wann ist Huffman am effizientesten? 3. Wann lohnt sich Huffman sicher nicht? 4. Warum benutzt z.B. Word kein Huffman Komprimierung? 5. Was wren andere grundlegende Ideen zu Komprimierung von Daten? (Erklren Sie anhand eines Beispiels) 6. Was sind allgemeine Vorteile von Datenkomprimierung? 7. Was sind allgemeine Nachteile der Datenkomprimierung? originale Nachricht codierte Nachricht originale Nachricht </li> <li> Folie 24 </li> <li> Enthropie </li> <li> Folie 25 </li> <li> Lernziele Sie verstehen, was Hamlet mit dem zersplitternden Weinglas zu tun hat, und wie beide mit der Huffman Kodierung zusammenhngen Sie kennen die allgemeine Form der Huffman Kodierung </li> <li> Folie 26 </li> <li> Was ist eigentlich Information? Was ist das kleinstmgliche Bisschen an Information? Sein oder nicht Sein, das ist hier die Frage. </li> <li> Folie 27 </li> <li> Ein BIT ist: eine Bezeichnung fr eine Binrziffer (blicherweise 0 und 1). eine Maeinheit fr die Datenmenge bei digitaler Speicherung von Daten. Die Datenmenge entspricht in diesem Fall der verwendeten Anzahl von binren Variablen zur Abbildung der Information. eine Maeinheit fr den Informationsgehalt (siehe Shannon). Dabei ist 1 Bit der Informationsgehalt, der in einer Auswahl aus zwei gleich wahrscheinlichen Mglichkeiten enthalten ist. There are 10 sorts of people: o those who unterstand binary and o those who do not. </li> <li> Folie 28 </li> <li> 1. 0101010101010101... 2. 1111111111111111... 3. 0110001101100101... 4. 0010111001100101... 5. 0000000011111111... 6. 0011001100110011... Ordnen Sie diese Bitsequenzen nach Informationsgehalt (aufsteigend) </li> <li> Folie 29 </li> <li> 1. 0101010101010101... 2. 2. 1111111111111111... 1. (= 1 Bit) 3. 0110001101100101... 4c 4. 0010111001100101... 4b (ASCII = ce) 5. 0000000011111111... 4a 6. 0011001100110011... 3. </li> <li> Folie 30 </li> <li> Entropie ist eine physikalische Zustandsgre in der Thermodynamik ein Ma fr den mittleren Informationsgehalt oder auch Informationsdichte eines Zeichensystems Warum sollte uns das interessieren? Huffman Komprimierung ist das Paradebeispiel fr eine Entropiecodierung </li> <li> Folie 31 </li> <li> Entropie &amp; Wahrscheinlichkeit Der Normalzustand (= maximale Entropie) ist die Gleichverteilung Abweichungen von der Gleichverteilung bedeuten: es gibt eine gewisse Ordnung, Struktur man kann es kompakter beschreiben 0100011110101010100101010101 0000000000000011111111111111 was ist wahrscheinlicher? was trgt mehr Information? </li> <li> Folie 32 </li> <li> Berechnen der Informationsdichte H = Entropie Z = endliches Alphabet von Zeichen z = ein einzelnes Zeichen p = Auftretenswahrscheinlichkeit (=Hufigkeit z/Gesamthufigkeit) Fr das deutsche Alphabet: </li> <li> Folie 33 </li> <li> Wozu brauchen wir das? 1. ASCII Nachricht in 8-er Blcke aufteilen, zhlen wie oft jeder Block vorkommt 2. Blcke nach Hufigkeit ordnen 3. Mit Huffman Baum prfixfreie Codewortliste erstellen 4. ASCII Nachricht nach Huffman bersetzen, siehe Liste 5. Bitsequenz &amp; Liste in File speichern, evtl. verschicken 6. Auch transportiert werden muss die Information, dass dieses File Huffman-codiert ist 1. 0101010101010101... 2. 1111111111111111... 3. 0110001101100101... 4. 0010111001100101... 5. 0000000011111111... 6. 0011001100110011... Was, wenn wir nicht wissen ob es ASCII Zeichen sind? (z.B. beim zippen) </li> <li> Folie 34 </li> <li> Wozu brauchen wir das? Entropie wird pro Zeichen berechnet, aber was ist ein Zeichen? bin: 01100011 01100101 ASCII: c e 1. 0101010101010101... 2. 1111111111111111... 3. 0110001101100101... 4. 0010111001100101... 5. 0000000011111111... 6. 0011001100110011... Normierung fr unterschiedliche Block-, bzw. Zeichenlngen noch allgemeiner: konditionelle Entropie </li> <li> Folie 35 </li> <li> Huffman generalisiert 1. Binre Nachricht durch Entropietests/Schtzung darauf analysieren, welche Bits ein Zeichen bilden sollten, so dass sich die niedrigste Entropie ergibt 2. Binre Nachricht in Zeichen aufteilen, zhlen wie oft jedes Zeichen vorkommt 3. Blcke nach Hufigkeit ordnen 4. Mit Huffman Baum prfixfreie Codewortliste erstellen 5. Binre Nachricht nach Huffman bersetzen, s. Liste 6. Bitsequenz &amp; Liste in File speichern, evtl. verschicken 7. Auch transportiert werden muss die Information, dass dieses File Huffman-codiert ist </li> <li> Folie 36 </li> <li> Entropiecodierung bedeutet mit einer Entropieschtzung herausfinden, welche Abschnitte der originalen Bitsequenz man als Zeichen ansehen sollte diese Zeichen dann so in prfixfreie Codewrter bersetzen, dass den hufigsten Zeichen die krzesten Codewrter zugeordnet werden ACHTUNG: trade-off der Listengrsse bercksichtigen! </li> <li> Folie 37 </li> <li> Entropiecodierung ist eine allgemeine Methode um zu bestimmen, wie viel Luft im Koffer ist, und den Koffer dann so umzupacken, dass mglicht wenig Luft verbleibt wie Legomodell verpacken. Zuerst muss man herausfinden, in wie kleine Teile man es zerlegen soll, und dann braucht man eine Methode, um diese Teile effizient ineinander zu stapeln </li> <li> Folie 38 </li> <li> Huffman Codierung ist die wohl am weitesten verbreitete Art der Entropiecodierung wird oft als letzter Schritt auf beliebige Bitsequenzen angewandt ist nur annhernd optimal. Bsp: vllig zufllige Sequenz mit drei mal mehr Nullen als Einsen - (1/4*lg(1/4)+3/4*lg(3/4)) = 0.811278 Bit/Zeichen(=Bit) weniger als ein Bit geht aber nicht, die beiden krzest mglichen Codewrter haben jeweils ein Bit </li> <li> Folie 39 </li> <li> Lernziele - erreicht?? Sie verstehen, was Hamlet mit dem zersplitternden Weinglas zu tun hat, und wie beide mit der Huffman Kodierung zusammenhngen Sie kennen die allgemeine Form der Huffman Kodierung Zusatz: Sie knnen erklren a) warum die Block-Entropie einer Bitsequenz am kleinsten ist, wenn man die gesamte Sequenz als einen einzigen Block (= ein Zeichen) ansieht b) warum es trotzdem keinen Sinn macht, die ganze Sequenz als eine einziges Zeichen zu kodieren </li> <li> Folie 40 </li> <li> (Datei-) Formate </li> <li> Folie 41 </li> <li> Lernziele Sie kennen die allgemeine Definition von Codierung Sie wissen, was ein (Datei-) Format ist und warum die meisten Formate einen header haben Sie knnen eine Binre Reprsentation fr das Speichern eines Spielzustands entwickeln Sie verstehen, wie die Begriffe Information, Code und Format zusammenhngen </li> <li> Folie 42 </li> <li> Komprimierung allgemein originale Nachricht (Bitsequenz) codierte Nachricht + Liste (Bitsequenz) codierte Nachricht + Liste (Bitsequenz) originale Nachricht (Bitsequenz) Komprimieren, z.B. mit Huffman Codierung Dekomprimieren, z.B. mit Huffman Decodierung speichern /verschicken Welche Informationen braucht es hier? </li> <li> Folie 43 </li> <li> Information Genau &amp; Kompakt Codieren Komprimieren Koffer (~ Format) so whlen, dass alles eingepackt werden kann, was man im Urlaub vielleicht brauchen knnte Ziel: Der Koffer soll fr alle Urlaube geeignet sein! Effizient packen, so dass mglichst wenig Luft im Koffer bleibt kann davon abhngen, was genau eingepackt wurde! Ziel: Der Koffer fr diesen Urlaub soll mglichst klein werden! Koffer packen (Komprimieren von Information) </li> <li> Folie 44 </li> <li> Codieren Welche Informationen braucht es hier? Nicht-digitale Information Digitale Information Nicht-digitale Information Digitale Information Komprimieren Komprimierte digitale Information Entkomprimieren Digitalisieren Entdigitalisieren?! Darstellen Wie geht das? Beispiel :Fisch ers Fritz fischt frische... </li> <li> Folie 45 </li> <li> Digitale Reprsentation von Schach Was ist wichtig? nur die Information, die einen Spielstande eindeutig definiert Was ist mglich? alle Spielstnde mssen reprsentiert werden knnen Wie packe ich es geschickt ein? es geht nicht um maximale Effizienz, man muss aber trotzdem keinen Speicherplatz verschwenden Vorschlge? Wie viele Bits brauchen Sie? oder: ein universeller digitale Koffer fr Schach </li> <li> Folie 46 </li> <li> Ein Schach Format (.sch), 257 BIT Das erste Bit gibt an, wer am Zug ist (1=schwarz, 0=weiss) Die folgenden 256 Bit reprsentieren die Belegung der 64 Felder, mit jeweils 4 Bit pro Feld (nummeriert zeilenweise von links nach rechts, dann spaltenweise von...</li></ul>

Recommended

View more >