Text Coding Project - Descărcare gratuită PDF
1 Instruire ISN pentru profesori Terminale Denis Bouhineau, Éric Gaussier, Alexandre Termier, Cyril Labbé, Philippe Bizard, Anne Rasse, Jean-Marc Vincent UFR IM 2 AG Formare pentru profesori terminali Nivelul I 1/34
2 Planul 1 Obiectivul 2 Tematicul 3 Algoritmul 4 Implementarea 5 Codul lungimii de rulare 6 Realizarea 2/34
3 Obiectivele proiectului 1 Analiza algoritmului și proiectarea arborilor, cozile prioritare, iterațiile recursive 2 Scrierea codului în limbaj C consolidând practica acestui limbaj, fișiere, co-dezvoltare 3 Validarea la fiecare etapă analiza complexității, evaluarea performanței (experimentare) Mini -structura proiectului: munca în echipă: perechi cu normă întreagă (peste o săptămână) autonomie Evaluare: apărare/demonstrație software Procedură: demonstrație: 15 minute întrebări: 15 minute Obiective: arată ce funcționează pregătește jocuri de testare planifică cursul prezentării lucrul la discurs 3/34
4 Planificarea organizației: organizare: TD de la 8:30 la 9:30, sala de mașini apoi luni: start [sala TD] marți: arhitectura proiectului [sala mașinilor] miercuri: intrări/ieșiri bit-by-bit [sala TD] joi: dezvoltare [sala mașinilor] Vineri: validare, analiză costuri, demo [sala TD] Supraveghere: Denis Bouhineau, Éric Gaussier, Alexandre Termier, Cyril Labbé, Philippe Bizard, Anne Rasse, Jean-Marc Vincent Pagina web: 4/34
5 Tema proiectului: compresie fără pierderi În meniu: programele algoritmului Huffman pentru codificarea și decodarea citirii/scrierii fișierelor binare de compresie/decompresie din mers Executa algoritmul de codificare a lungimii variante de versiune de bază (istoric, secvență de evadare, PackBits) Experimentare pe diferite formate de date: texte, programe (sursă și binară), imagini etc. 5/34
6 Memento-uri: Huffman care codifică alfabetul de intrare A (caractere, pixeli etc.), alfabetul de ieșire (bit) un cod Huffman: asociază cu fiecare element din A o secvență pe: A codificare decodare A caracteristici: cod de lungime variabilă (= cod Morse; Ascii cod) proprietate prefix: codare (a 1) = w 1, codificare (a 2) = w 2 w 1 și w 2 nu sunt prefixe între ele (algoritm eficient de decodare) 6/34
7 Aplicarea codificării Huffman Codificați o secvență de elemente pe A într-un fișier binar: asociați un cod scurt cu cele mai frecvente elemente de compresie a secvenței inițiale Note: codul trebuie construit în conformitate cu textul inițial. înainte de codificare: Static Huffman în timpul codificării: Dynamic Huffman Trebuie cunoscut în timpul decodificării. (transmis sau recalculat identic) 7/34
8 Arborele Huffman O reprezentare a unui cod Huffman = Arborele Huffman set de frunze = elemente ale unui acces stâng copil = 0; acces la copilul potrivit = 1 cod (a) = secvența σ a etichetelor căii: rădăcină σ a 0 1 E A B D C F cod (e) = 1; cod (a) = 001; cod (c) = 0110; etc. proprietatea prefixului este respectată! 8/34
9 Algoritm de codare Dat fiind un arbore Huffman: S = a 1. o R 0 1 EABDCF 1 construcția unei tabele de codare C prima scanare în profunzime a arborelui Huffman prin memorarea secvenței σ rădăcină σ nod curent pentru fiecare frunză a: C [a] = σ Rq: ceva recursiv sau iterativ (cu stivă explicită) 2 traversare a S și producția R folosind C 9/34
10 Algoritm de decodare Date unui arbore Huffman: RS = a 1. o traversare 0 1 EABDCF 1 a arborelui Huffman de-a lungul R (0: copil stâng; 1: copil drept) 2 la fiecare frunză a ajuns: scrierea unui în S reveni la rădăcina arborelui Huffman/34
11 Construiți un copac Huffman? Depinde de frecvența elementelor lui A în S: frecvență înaltă = elemente apropiate de rădăcină Obținerea unui tabel de frecvențe: Freq [ai] = fi (fi = frecvența lui ai în S, un real între 0 și 1) Abordare statică: 1 construcție a frecvenței pe o cale 1 a lui S (fi = numărul de apariții ale ai/S) 2 construcție a arborelui Huffman (folosind frecvența) 11/34
12 Algoritm informal pentru construirea arborelui Folosim o coadă de prioritate (Fap) F din care: elementele sunt noduri ale arborelui prioritățile sunt reale (valoare mare prioritate mare) Algo: 1 introduceți elementele (ai, Freq [ai]) în fap F 2 atâta timp cât F conține cel puțin 2 elemente extrageți două elemente (n 1, f 1) și (n 2, f 2) cu greutatea minimă a inserției F (n, f 1 + f 2) în F, unde n este un nou nod de copii stângi n 1 și copii dreapta n 2 3 elementul rămas în F este rădăcina arborelui Huffman 12/34
13 Structuri de date Set A: caractere ale unui cod Ascii extins (0 la 255) Frecvența tabelului: tabelul numerelor reale indexate de la 0 la 255 Arborele Huffman: fie înlănțuirea celulei prin indicatori sau tabel (256 coli 511 noduri) Fap F: secvența de perechi (nod arbore, real) Secvență pe: secvența de caractere 0 și 1 13/34
14 Arhitectură globală Un set de programe interconectate: Decodare S Calcul frecvență Freq Construcție Ax arbore R Codificare comunicare posibilă prin fișiere, sau tuburi (țeavă)/34