18_Kompressionsverfahren

 Documents

 44 views
of 22
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Description
Kompressionsverfahren für Texte Prof. Dr. S. Albers Prof. Dr. Th. Ottmann WS03/04 1 Zeichenkettenverarbeitung ã Suche in Texten, Textindizes ã…
Share
Transcript
Kompressionsverfahren für Texte Prof. Dr. S. Albers Prof. Dr. Th. Ottmann WS03/04 1 Zeichenkettenverarbeitung • Suche in Texten, Textindizes • Mustererkennung (Pattern-Matching) • Verschlüsseln • Komprimiern • Analysieren (Parsing) • Übersetzen WS03/04 2 Kompressionsverfahren für Texte Verlustfreie Kompression Original kann perfekt rekonstruiert werden Beispiele: Huffman Code, Lauflängencodierung, arithmetische Codierung, Lempel-Ziv Verlustbehaftete Kompression: Unterschied zwischen Original und decodiertem Objekt, nutzt physiologische und psychologische Eigenschaften des Auges und Ohres aus, erlaubt höhere Kompressionsraten Beispiele: JPEG, MPEG WS03/04 3 Verlustfreie Kompressionsverfahren Ziel: Finde umkehrbare Codierung, so dass der Text wieder (verlustfrei) rekonstruiert werden kann. Beispiele: • Huffmann-Code • Lauflängen-Codierung • Arithmetische Codierung • Lempel-Ziv Codierung WS03/04 4 Verlustbehaftete Kompressionsverfahren Gegensatz: Verlustbehaftete Kompression für Bilder, Audio, Video Beispiele: • JPEG • MPEG • MP3 WS03/04 5 Arithmetische Codierung Ziel: # Bits der codierten Nachricht umgekehrt proportional zur Wahrscheinlichkeit der Nachricht. Wahrscheinlichkeit groß - # Bits klein Wahrscheinlichkeit klein - # Bits groß WS03/04 6 Arithmetische Codierung Beispiel: Huffmann Code Symbol p(Symbol) Code A 0.01 0 B 0.99 1 AAAA  1111 BBBB  0000 WS03/04 7 Arithmetische Codierung Idee: Stelle Symbole und Symbolfolgen als Intervall [l, r) bzw. als Element daraus dar. Beispiel: Symbol p(Symbol) Intervall F 0.1 [0.0, 0.1) I 0.3 [0.1, 0.4) N 0.3 [0.4, 0.7) O 0.2 [0.7, 0.9) @ 0.1 [0.9, 1.0) WS03/04 8 Arithmetische Codierung 0.4 0.31 0.229 0.2281 0.22810 1.0 0.9 @ O 0.7 N 0.4 I 0.1 F 0.1 0.22 0.22 0.2263 0.22792 x, y   x   y  x u, x   y  x o  u ,o  WS03/04 9 Arithmetische Codierung Decodierung durch Umkehrung: v, w  v  u  o  u , w  u  o  u  u ,o  Beispiel: 0.22792,0.2281  0.1, 0.4 :I   0.4264,0.427  0.4 , 0.7 :N  0.088,0.09  0.0 , 0.1:F  0.88,0.9  0.7 , 0.9 :O  0.9,1.0  0.9 ,1.0 :@  0.0,1.0 WS03/04 10 Arithmetische Codierung Es reicht natürlich ein Wert aus dem Intervall, z.B. der untere. Die Gesamtnachricht wird zur Codierung in Teilzeichenfolgen zerlegt, die durch Stoppzeichen beendet werden. Nachteil: Statisches Verfahren, passt sich nicht wechselnden Wahrscheinlichkeiten an. Nachteil: Aufwendige Berechnungen. WS03/04 11 Einfaches verlustfreies Kompressionsverfahren Ersetze häufig auftretendes Muster durch kurzes Codewort, verwende Wörterbuch für die Codeworte abracadabracadabra abra 1 1 2 2 1 cad 2 WS03/04 12 Einfaches verlustfreies Kompressionsverfahren Wörterbuchbasiertes Kompressionsverfahren: statisch: Wörterbuch wird vor Codierung festgelegt und bleibt unverändert dynamisch: Wörterbuch passt sich dem zu komprimierenden Text dynamisch an Lempel-Ziv: zip, TIFF ( Image File Format) Lempel-Ziv-Welch: Compress in Unix WS03/04 13 Einfaches verlustfreies Kompressionsverfahren Lempel-Ziv Idee: Baue das Wörterbuch simultan mit der Kodierung des Textes auf; anfangs seien für jeden Buchstaben des Alphabetes Codenummern im Wörterbuch WS03/04 14 Einfaches verlustfreies Kompressionsverfahren Kodierung von: ababcbabab Wörterbuch Eintrag # Ausgabe a 1 b 2 c 3 WS03/04 15 Einfaches verlustfreies Kompressionsverfahren Decodierung von: 1 2 4 3 5 8 Wörterbuch Eintrag # Ausgabe a 1 b 2 c 3 WS03/04 16 LZW Kodierung Algorithmus Lempel-Ziv-Welch Input: Ein Text T=t1…tn über dem Alphabet S Output: Die LZW Kodierung von T Initialisiere Wörterbuch D mit Zeichen aus S; Initialisiere string s = t1: while noch nicht alle Zeichen von T gelesen do lies nächstes Zeichen c; if s+c ist Anfangsstück eines Eintrags in D then s = s+c /* bestimme aktuellen Match*/ else { gib Codewort(s) aus; trage s+c in D ein; s=c} end while; gib Codewort(s) aus WS03/04 17 LZW Decodierung Input: Sequenz von Codewörtern Output: Zeichenfolge über dem Alphabet S Initialisiere Wörterbuch D mit Zeichen aus S; Lies lcw und gib Buchstaben string(lcw) aus, den lcw codiert; while noch nicht alle Codewörter gelesen do lies nächstes Codewort act; if act ist nicht in D then /* Spezialfall*/ { trage string(lcw) + firstchar(string(lcw)) in D ein; gebe string(lcw) + firstchar(string(lcw)) aus } else { trage string(lcw) + firstchar(string(act)) in D ein; gibt string(act) aus } lcw = acw end while WS03/04 18 Lempel-Ziv Kodierung: Beispiel T = COCOA AND BANANAS Wörterbuch D (anfangs) m #(m) m #(m) A 000 001 O 001 111 000 010 ... ... B C 000 011 S 010 011 000 100 ... ... D 011 010 ... ... Z N 001 110 011 011 WS03/04 19 Lempel-Ziv Kodierung: Beispiel T = COCOA AND BANANAS m #(m) add to D T C 000 011 ---- OCOA AND BANANAS O 001 111 CO 011 100 COA AND BANANAS CO 011 100 OC 011 101 A AND BANANAS A 000 001 COA 011 110 AND BANANAS 011 011 A 011 111 AND BANANAS A 000 001 A 100 000 ND BANANAS N 001 110 AN 100 001 D BANANAS D 000 100 ND 100 010 BANANAS 011 011 D 100 100 BANANAS WS03/04 20 Lempel-Ziv Kodierung: Beispiel m #(m) add to D T B 000 010 B 100 100 ANANAS AN 100 001 BA 100 101 ANAS AN 100 001 ANA 100 110 AS A 000 001 ANA 100 110 S S 010 011 AS 100 111 # (T) = 000 011 | 001 111 | 011 100 | 000 001 | 011 011 | ... WS03/04 21 Lempel-Ziv Eigenschaften • Wörterbuch passt sich dynamisch an die zu komprimierende Zeichenkette an, d.h. es enthält schließlich die am häufigsten vorkommende Zeichenkette • Wörterbuch (Code Tabelle) muss nicht übertragen werden. Bekannt sein muss nur die Anfangtabelle, alles weitere wird beim Decodieren dynamisch erzeugt. • Codieren und Decodieren ist in linearer Zeit möglich • LZ führt i.a. zu höheren Kompressionsraten als Huffmann WS03/04 22
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks