Codes & Formate

  • Published on
    03-Jan-2016

  • View
    29

  • Download
    0

Embed Size (px)

DESCRIPTION

Codes & Formate. Digitales Koffer packen. Mit Huffman Codierung. Lernziele. Sie knnen erklren, warum es normalerweise zwei Schritte braucht um Information mglichst effizient zu speichern, bzw. zu bermitteln - PowerPoint PPT Presentation

Transcript

<ul><li><p>Codes &amp; Formate</p></li><li><p>Digitales Koffer packenMit Huffman Codierung</p></li><li><p>LernzieleSie knnen erklren, warum es normalerweise zwei Schritte braucht um Information mglichst effizient zu speichern, bzw. zu bermittelnSie knnen erklren, warum die Verteilung der Zeichen in einer Nachricht einen entscheidenden Einfluss darauf hat, wie effizient diese Nachricht komprimiert werden kannSie wissen, was eine Huffman Codierung ist und knnen sie auf eine kurze Textnachricht anwenden</p></li><li><p>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:Ein Dokument soll nur die Zahlenfolge enthaltenIm anderen Dokument formulieren Sie eine Anleitung, mit deren Hilfe ihr Freund die ursprngliche Botschaft aus der Zahlenfolge rekonstruieren kann</p></li><li><p>AuswertungHat 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?</p></li><li><p>Information Genau &amp; KompaktCodierenKomprimierenKoffer (~ Format) so whlen, dass alles eingepackt werden kann, was man im Urlaub vielleicht brauchen knnteZiel: 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)</p></li><li><p>Effizientes Packen von BuchstabenCodieren von Buchstaben als binre CodewrterASCII CodeKomprimieren der Bitsequenzz.B. Huffman Codierungkrzere Sequenz + neue Codewrter Speichern oder bermittelnDekomprimierenDecodieren -&gt; Darstellen</p></li><li><p>ASCII(American Standard Code for Information Interchange)</p><p>Kleinbuchstaben:</p><p>DezimalHexBinrZeichen96600110 0000` 97610110 0001a 98620110 0010b 99630110 0011c 100640110 0100d 101650110 0101e 102660110 0110f 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 0111w 120780111 1000x 121790111 1001y 1227A0111 1010z 1237B0111 1011{ 1247C0111 1100| 1257D0111 1101} 1267E0111 1110~ 1277F0111 1111DEL</p></li><li><p>ArbeitsauftragIhr Ziel ist herauszufinden, wie die Huffman Codierung funktioniert und sie selbst anwenden zu knnenBenutzen Sie dazu das Applet: WindowsHuffmanShannonFano.jar Experimentieren Sie mit dem Applet (nur Huffman Code) und versuchen Sie, die Fragen im Arbeitsblatt zu beantworten</p></li><li><p>BesprechungSuchen Sie sich einen Partner und tauschen Sie ihre Ergebnisse ausNotieren Sie alles, was ihnen beiden noch unklar istKnnen Sie die grundstzliche Idee formulieren?</p></li><li><p>LernzieleSie knnen erklren, warum es normalerweise zwei Schritte braucht um Information mglichst effizient zu speichern, bzw. zu bermittelnSie knnen erklren, warum die Verteilung der Zeichen in einer Nachricht einen entscheidenden Einfluss darauf hat, wie effizient diese Nachricht komprimiert werden kannSie wissen, was eine Huffman Codierung ist und knnen sie auf eine kurze Textnachricht anwenden</p></li><li><p>Grundstzliche Idee bei HuffmanHufige Zeichen (Buchstaben) werden in kurze Codewrter bersetztDas funktioniert nur, wenn der entstehende Code (die Codewrter) prfixfrei ist!Die Bumchen-Taktik zeigt, wie man diese Ideen umsetzt.</p></li><li><p>Huffman Komprimierung </p></li><li><p>LernzieleSie knne eine kurze Nachricht entschlsseln, die mit dem Huffman Verfahren komprimiert wurde Sie knnen erklren, was ein prfixfreier Code istSie knnen beschreiben, fr welche Nachrichten die Huffman Komprimierung besonders geeignet istSie kennen einige Vor- und Nachteile von Datenkomprimierung</p></li><li><p>Huffman DecodierungDie binre Nachricht: 0100111101001110010100111110Die Codewrter:</p><p>e=110d=111o=00p=010s=011u=100c=101</p></li><li><p>Und was daran war jetzt prfixfrei?o=00p=010s=011u=100c=101e=110d=111</p></li><li><p>Pseudocode... ist eine sprachliche Mischung aus natrlicher Sprache, mathematischer Notation und einer hheren Programmier-sprachearrayMax(A, n) // Input: Ein Array A, der n Integer Werte enthlt // Output: Das maximale Element in A</p><p>currentMax = A[0] for i = 1 to n - 1 if currentMax &lt; A[i] currentMax = A[i]endendreturn currentMax</p></li><li><p>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 Zeichennachricht_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;elselnge ++;endendreturn nachricht_txt;</p></li><li><p>Pseudocode fr Huffman Codierungcodieren(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 </p></li><li><p>Komprimierung allgemeinKomprimieren,z.B. mit Huffman CodierungDekomprimieren,z.B. mit Huffman Decodierungspeichern /verschickenWelche Informationen braucht es hier?</p></li><li><p>Huffman KomprimierungASCII Nachricht in 8-er Blcke aufteilen, zhlen wie oft jeder Block vorkommtBlcke nach Hufigkeit ordnenMit Huffman Baum prfixfreie Codewortliste erstellenASCII Nachricht nach Huffman bersetzen, siehe ListeBitsequenz &amp; Liste in File speichern, evtl. verschicken Auch transportiert werden muss die Information, dass dieses File Huffman-codiert ist </p></li><li><p>Fragen zu Huffman &amp; KomprimierungWas ist die grundlegende Idee hinter Huffman Komprimierung?Wann ist Huffman am effizientesten?Wann lohnt sich Huffman sicher nicht?Warum benutzt z.B. Word kein Huffman Komprimierung?Was wren andere grundlegende Ideen zu Komprimierung von Daten? (Erklren Sie anhand eines Beispiels)Was sind allgemeine Vorteile von Datenkomprimierung?Was sind allgemeine Nachteile der Datenkomprimierung?</p></li><li><p>Enthropie</p></li><li><p>LernzieleSie verstehen, was Hamlet mit dem zersplitternden Weinglas zu tun hat, und wie beide mit der Huffman Kodierung zusammenhngenSie kennen die allgemeine Form der Huffman Kodierung </p></li><li><p>Was ist eigentlich Information?Was ist das kleinstmgliche Bisschen an Information?Sein oder nicht Sein,das ist hier die Frage.</p></li><li><p>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:those who unterstand binary andthose who do not.</p></li><li><p>0101010101010101...1111111111111111...0110001101100101...0010111001100101...0000000011111111...0011001100110011...</p><p>Ordnen Sie diese Bitsequenzen nach Informationsgehalt (aufsteigend)</p></li><li><p>Ordnen Sie diese Bitsequenzen nach Informationsgehalt (aufsteigend)0101010101010101... 2.1111111111111111... 1. (= 1 Bit)0110001101100101... 4c0010111001100101... 4b (ASCII = ce)0000000011111111... 4a0011001100110011... 3.</p></li><li><p>Entropie isteine physikalische Zustandsgre in der Thermodynamikein Ma fr den mittleren Informationsgehalt oder auch Informationsdichte eines Zeichensystems</p><p>Warum sollte uns das interessieren? Huffman Komprimierung ist das Paradebeispiel fr eine Entropiecodierung</p></li><li><p>Entropie &amp; WahrscheinlichkeitDer Normalzustand (= maximale Entropie) ist die GleichverteilungAbweichungen von der Gleichverteilung bedeuten:es gibt eine gewisse Ordnung, Strukturman kann es kompakter beschreiben</p><p> 0100011110101010100101010101</p><p>0000000000000011111111111111was ist wahrscheinlicher?was trgt mehr Information?</p></li><li><p>Berechnen der InformationsdichteH = EntropieZ = endliches Alphabet von Zeichen z = ein einzelnes Zeichenp = Auftretenswahrscheinlichkeit(=Hufigkeit z/Gesamthufigkeit)Fr das deutsche Alphabet:Eine perfekte Komprimierung wrde diesen Entropiewert erreichen</p></li><li><p>Wozu brauchen wir das?ASCII Nachricht in 8-er Blcke aufteilen, zhlen wie oft jeder Block vorkommtBlcke nach Hufigkeit ordnenMit Huffman Baum prfixfreie Codewortliste erstellenASCII Nachricht nach Huffman bersetzen, siehe ListeBitsequenz &amp; Liste in File speichern, evtl. verschicken Auch transportiert werden muss die Information, dass dieses File Huffman-codiert ist 0101010101010101...1111111111111111...0110001101100101...0010111001100101...0000000011111111...0011001100110011...</p><p>Was, wenn wir nicht wissen ob es ASCII Zeichen sind?(z.B. beim zippen)</p></li><li><p>Wozu brauchen wir das?Entropie wird pro Zeichen berechnet - aber was ist ein Zeichen?8er: 01100011 011001014er: 0110 0011 0110 0101</p><p> 0101010101010101...1111111111111111...0110001101100101...0010111001100101...0000000011111111...0011001100110011...</p><p>Normierung fr unterschiedliche Block-, bzw. Zeichenlngennoch allgemeiner:konditionelle Entropie</p></li><li><p>Huffman generalisiertBinre Nachricht durch Entropietests/Schtzung darauf analysieren, welche Bits ein Zeichen bilden sollten, so dass sich die niedrigste Entropie ergibtBinre Nachricht in Zeichen aufteilen, zhlen wie oft jedes Zeichen vorkommtBlcke nach Hufigkeit ordnenMit Huffman Baum prfixfreie Codewortliste erstellenBinre Nachricht nach Huffman bersetzen, s. ListeBitsequenz &amp; Liste in File speichern, evtl. verschicken Auch transportiert werden muss die Information, dass dieses File Huffman-codiert ist </p></li><li><p>Entropiecodierung bedeutetmit einer Entropieschtzung herausfinden, welche Abschnitte der originalen Bitsequenz man als Zeichen ansehen sollte</p><p>diese Zeichen dann so in prfixfreie Codewrter bersetzen, dass den hufigsten Zeichen die krzesten Codewrter zugeordnet werden ACHTUNG: trade-off der Listengrsse bercksichtigen!</p></li><li><p>Entropiecodierung ist eine allgemeine Methode um zu bestimmen, wie viel Luft im Koffer ist, und den Koffer dann so umzupacken, dass mglicht wenig Luft verbleibtwie 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</p></li><li><p>Huffman Codierungist die wohl am weitesten verbreitete Art der Entropiecodierung wird oft als letzter Schritt auf beliebige Bitsequenzen angewandtist 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 BitLsung: Arithmetische Codierung</p></li><li><p>Arithmetische Codierung (Zusatz)Die gesamte Nachricht in einer einzigen Zahl ...... ausserdem braucht es die Zeichen und ihre Frequenz ...... und einen schnellen Computer A = 0.6B = 0.3C = 0.1D = 0.1Zahl = 0.536 Nachricht = ACD</p></li><li><p>Lernziele - erreicht??Sie verstehen, was Hamlet mit dem zersplitternden Weinglas zu tun hat, und wie beide mit der Huffman Kodierung zusammenhngenSie kennen die allgemeine Form der Huffman KodierungZusatz:Sie knnen erklrena) warum die Block-Entropie einer Bitsequenz am kleinsten ist, wenn man die gesamte Sequenz als einen einzigen Block (= ein Zeichen) ansiehtb) warum es trotzdem keinen Sinn macht, die ganze Sequenz als eine einziges Zeichen zu kodieren</p></li><li><p>(Datei-) Formate</p></li><li><p>LernzieleSie kennen die allgemeine Definition von CodierungSie wissen, was ein (Datei-) Format ist und warum die meisten Formate einen header habenSie knnen eine Binre Reprsentation fr das Speichern eines Spielzustands entwickelnSie verstehen, wie die Begriffe Information, Code und Format zusammenhngen</p></li><li><p>Komprimierung allgemeinKomprimieren,z.B. mit Huffman CodierungDekomprimieren,z.B. mit Huffman Decodierungspeichern /verschickenWelche Informationen braucht es hier?</p></li><li><p>Information Genau &amp; KompaktCodierenKomprimierenKoffer (~ Format) so whlen, dass alles eingepackt werden kann, was man im Urlaub vielleicht brauchen knnteZiel: 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)</p></li><li><p>CodierenWelche Informationen braucht es hier?DigitalisierenEntdigitalisieren?!DarstellenWie geht das?Beispiel:Fischers Fritz fischt frische...</p></li><li><p>Digitale Reprsentation von SchachWas ist wichtig?nur die Information, die einen Spielstande eindeutig definiertWas ist mglich?alle Spielstnde mssen reprsentiert werden knnenWie packe ich es geschickt ein?es geht nicht um maximale Effizienz, man muss aber trotzdem keinen Speicherplatz verschwenden</p><p>Vorschlge? Wie viele Bits brauchen Sie?oder: ein universeller digitale Koffer fr Schach</p></li><li><p>Ein Schach Format (.sch), 257 BITDas 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 oben nach unten). Das erste Bit pro Feld steht fr die Farbe der Figur: Die letzten 3 Bit pro Feld stehen fr die Figur, die hier steht:</p></li><li><p>Ein Format fr Schieber-JassDas Spiel: 4 Spieler haben zu Beginn je 9 Karten, spielen sie reihum aus, und nach jeder Runde wandern 4 Karten auf den einen oder anderen Stapel von gespielten Karten. Aufgabe: erfinden Sie ein Format, mit dem jeder mgliche Zustand des Spiels binr reprsentiert werden kann.Formulieren Sie von Ihnen erfundene Codierung so, dass ein anderer Schler eine entsprechende Bitsequenz in den Spielzustand zurckbersetzen knnteGeben Sie an, wie viele Bits fr die Speicherung eines Spielzustands bentigt werden</p></li><li><p>Und wie passt das jetzt alles zusammen?InformationCodierungFormat</p></li><li><p>Definition Code:</p></li><li><p>Definition von Code, langIm Allgemeinen ist ein Code eine Vereinbarung ber einen Satz (eine Menge) von Symbolen (Bedeutungstrgern, oder Verweisen) zum Zweck des Informationsaustauschs. Information existiert nicht in reiner Form; sie ist immer in irgendeiner Weise formuliert. Ein Code ist allgemein ausgedrckt eine Formulierung von Information. Das setzt folgende Elemente voraus:mindestens eine informationsformulierende Instanz (Aufzeichner/Sender)mindestens eine informationsempfangende Instanz (Lesender/Empfnger) kann unter Umstnden auch identisch mit (1) seinein zu bermittelnder, abstrakter Inhalt, die Informationeine Vereinbarung zum Zweck der Informationsformulierung und gegebenenfalls Informationsbermittlung. Diese enthlt einen Satz von Bedeutungstrgern oder Symbolen, der beiden Instanzen (1) und (2) bekannt ist, und gegebenenfalls Regeln zur Verwendung der Symbole</p></li><li><p>Was ist eigentlich Information?Was ist das kleinstmgliche Bisschen an Information?</p><p>1 oder 0 Sein oder nicht Seintrue oder falseInformation existiert nicht i...</p></li></ul>