Compresia MTF (Move to front)

Transmisia datelor multimedia in retele de calculatoare Compresia fara pierdere de calitateIIConf. Dr. Ing. Costin-Anton Boiangiu

UNIVERSITY POLITEHNICA of BUCHARESTDEPARTMENT OF COMPUTER SCIENCE2IntroducerePana acuma am considerat ca toate simbolurile de intrare sunt independenteAcest lucru nu este adevarat pentru cele mai uzuale tipuri de dateEx: text, imagini, codIdeea de bazaSe vor identifica pattern-urile (modelelr) simbolurilorSe for codifica aceste modele mai eficientRestul de simboluri vor fi codificate folosind un algoritmul de baza (mai putin eficient)In cele mai multe cazuri se va obtine o performanta mult mai bunaNotaAceasta tehnica poate fi folosite in cazul tipurilor de date precum textulEvident, nu va avea succes in cadrul datelor (aproape) intamplatoare - random3Codificarea bazata pe diagrameDictionarToate literele din alfabet +Cat mai multe diagrame (perechi de litere)Exemplu:Marimea dictionarului = 256 intrariAlfabet: caracterele ASCII printabile = 95Digrame: cele mai comune 161 de perechi de caractereAlt examplu: A = {a, b, c, d, r}, Dictionar:

4Exemplu

Input: abracadabraOutput: 1015Exemplu

Input: --racadabraOutput: 101X6Exemplu

Input: --racadabraOutput: 1011007Exemplu

Input: ---acadabraOutput: 1011001108Exemplu

Input: -----adadabraOutput: 1011001101119Exemplu

Input: -------abraOutput: 10110011011110110Exemplu

Input: ---------raOutput: 101100110111101X11Exemplu

Input: ---------raOutput: 10110011011110110012Exemplu

Input: ----------aOutput: 10110011011110110000013Problema: Care diagrame?

Sursa #1: Capitol dintr-o carte (LaTeX)Sursa #2: Cod CScurt istoricMai 1977: apare lucrarea (Ziv and Lempel, 1997)Desi articolul este intens matematizat, tehnica generala de lucru este de a considera siruri de caractere care se repata si de a le inlocui cu un numar a carui reprezentare sa fie mai mica decat cea a sirului originalMulte instrumente software de compresie se bazeaza pe acest algoritm: ZIP, ZOO, ARC, gzip, LhA, CAB, Arj, RARAcest algoritm este denumit LZ77 si nu este foarte raspandit din cauza dificultatilor de implementareSeptembrie 1978: apare lucrarea (Ziv and Lempel, 1998)Tehnica este deosebita de LZ77 in sensul ca se mentine un dictionar de siruri in loc de considerarea unei ferestreAlgoritmul este foarte popularAlgoritmul se numeste LZ78

Scurt istoric20 Iunie 1983: Terry Welch scrie o versiune a lui LZ78 bazandu-se pe simplificari substantiale si un management mai bun al dictionaruluiAlgoritmul se numeste LZW, dupa numele inventatorilor sai, Lempel-Ziv-Welch5 Iulie 1984: Apare UNIX compress, dupa publicarea articolului lui Welch 15 Junie 1987: Apare formatul grafic numit GIF (Graphics Interchange Format), care foloseste pentru compresie algoritmul LZW

Ideea compresiei bazate pe dictionarAceste metode constau dintr-o serie de reguli de identificare a unor grupuri de simboluri si gruparea/depunerea lor intr-un dictionar care se asociaza sursei de informatieDaca se intalneste un anumit grup de simboluri, se creaza un indicator (pointer) corespunzator locului ocupat de respectivul grup in dictionarCu cat se intalneste mai des un anumit grup de simboluri, cu atat este mai mare raportul de compresieAceste metode codeaza siruri de simboluri de lungime variabila cu semne individuale, fiecare semn reprezentand un indicator (index) intr-un dictionarCompresia se obtine atunci cand noile semne sunt de lungime mai mica

ExempluFie conventia reprezentarii unui cuvant dintr-o carte prin doua atribute: (Numarul paginii) / (numarul cuvantului din pagina)Atunci, mesajul Titlul acestui capitol este compresia datelor poate fi inlocuit prin 500/3 1/5 10/2 15/9 10/6 12/1Cuvantul Titlul este inlocuit prin 500/3, ceea ce reprezinta al treilea cuvant din pagina 500. Cuvantul compresia este al 6 cuvant din pagina 10

Ideea compresiei bazate pe dictionarMarimea mesajului comprimat depinde de marimea dictionarului, deci de numarul de pagini si de numarul de inregistrari pe paginaDaca aceste doua marimi se noteaza cu NP (numarul de pagini) si NR(numarul de inregistrari pe pagina) atunci numarul de biti pentru reprezentarea (codarea) unui cuvant din dictionar este[log2(NP)] + [log2(NR)],unde parantezele drepte arata rotunjurea la cel mai apropiat intregIntrucat trebuie considerat si marimea mesajului de la intrare, exprimat prin numarul de simboluri, NS, rezulta un raport de compresie:

Exemplu numericDaca dictionarul contine 2200 pagini, sunt necesari log2(2200) = 11.03 => 12 biti pentru a coda numarul paginii, iar daca fiecare pagina contine cuvinte de lungime 256 sunt necesari un numar de :log2(256) = 8 biti pentru codarea fiecarui cuvantCa urmare, un cuvant oarecare din dictionar este codat pe 20 (=11+8) biti sau 2.5 => 3 octeti Mesajul comprimat va avea lungimea 20 biti * 6 cuvinte = 120 biti /18 octetiIn reprezentarea ASCII, cele 6 cuvinte necesita un total de (6+7+7+4+9+7) = 40 * 8 = 320 bitideci 40 octetiRaportul de compresie este

DictionareDictionarele pot fi statice adaptiveUn dictionar static este construit si transmis odata cu textul comprimat si este folosit ca referintele citate intr-o lucrare stiintificaUn dictionar static este construit inaintea efectuariii compresiei si ramane neschimbat pe toata durata acesteiaDictionarul static are avantajul ca poate fi ales (acordat) in vederea codarii, inregistrarile care apar cu cea mai mare frecventa putand fi codate cu numarul cel mai mic de biti, in conformitate cu regulile de codare enrtropicaDezavantajul folosirii unui dictionar static apare la compresia fisierelor mici, cand, din cauza transmisiei/memorarii atat a dictionarului cat si a fisierului comprimat, raportul de compresie nu este foarte bun, de multe ori chiar subunitarDe aceea, cei mai raspanditi sunt algoritmii de compresie bazati pe dictionare adaptive

DictionareUn dictionar adaptiv consta in adaugarea unei abrevieri pe langa anumite grupe de simboluri, cand apar prima oara, si utilizarea in continuare doar a abrevierilorCel mai folosit algoritm de compresie bazat pe dictionar este cel propus de Jacob Ziv si Abraham Lempel, in doua variante: prima din 1977, cunoscuta sub numele de LZ77a doua, din 1978, cunoscuta sub numele de LZ78Algoritmul Lempel-ZivUrmatorul exemplu se refera la o versiune simpla a algoritmului Lempel-ZivSchema de compresie trebuie sa imparta datele in sub-siruri, sa codeze sub-sirurile, si sa fie posibila si operatia inversaFie urmatorul sir de date:001101100011010101001001001101000001010010110010110

*Preluat din (Princeton, 2004)

Algoritmul Lempel-ZivPrimul pas consta in impartirea sirului de date in subsiruri, astfel incat la fiecare definitie a unui subsir sa nu existe repetitiii, deci el sa nu fi fost definit anteriorSe va utiliza virgula ca separator de sub-siruriLa inceputul sirului se pune o virgula pentru a evidentia sirul de lungime zeroSe pune apoi o virgula dupa primul zero, intracat nu a mai aparutAl doilea bit este zero si se considera si al doilea simbol, 1, obtinandu-se sirul 01Intrucat acesta este sir nou se pune virgulaUrmeaza simbolul 1, care fiind caracter nou, atrage virgula dupa elApoi apare un zero, mai trebuie un zero (deci inca un simbol), ca sa fie un sir nouRezultatul consta in urmatoarea lista de siruri,0,01,1,011,00,0110,10,101,001,0010,01101,000,00101,001011,0010110Algoritmul Lempel-ZivPasul doi consta in derminarea numarului de biti pentru reprezentarea secventei astfel obtinutePractic, se numeroteaza sirurile incepand cu primul sir de lungime nenulaSe determina numarul de biti dupa relatia

unde N reprezinta numarul de siruri si paranteza are rolul de rontunjire la cel mai mic intregPentru primul exemplu considerat se constata ca sunt 16 simboluri (inclusiv sirul de lungime zero) si sunt necesari 4 biti pentru reprezentarea fiecarui sir

Algoritmul Lempel-ZivPasul trei consta codificarea sirurilor, astfel obtinute Se completeaza un tabel in care se definesc: sirul, numarul ce arata pozitia siruluiprefixul, numarul ce arata pozitia prefixuluicodul siruluiCodul sirului este obtinut considerand numarul ce arata pozitia prefixului urmat de ultimul bit al sirului considerat

Algoritmul Lempel-ZivNr. siruluiSirulCodareapozitiei siruluiPrefixCodarea pozitiei prefixuluiSir codat100001empty0 = 00000000+0 = 000002 01 001001 = 00010001+1 = 000113 1 0011empty0 = 00000000+1 = 000014 0110100012 = 0010001015 00 01010 1 = 0001000106 0110 01100114 = 0100010007 10 011113 = 0011001108 1011000107 = 0111011119 0011001005 = 01010101110 001010100019 = 10011001011 01101101101106 = 01100110112 0001100005 = 01010101013 00101 1101001010 = 10101010114 00101111100010113 = 11011101115 0010110 111100101114 = 111011100Algoritmul Lempel-ZivSecventa comprimata este formata prin concatenarea tuturor sirulor codate, aflate in ultima coloana a tabelului precedentSe obtine:00000-00011-00001-00101-00010-01000-00110-0111101011-10010-01001-01010-10101-11011-11100Comparand lungimea secventei comprimate cu lungimea secventei originale se constata ca secventa comprimata are o lungime mai mareAcest rezultat este explicat prin faptul ca secventa de intrare este de lungime foarte micaPentru fisiere cu secventa de lungime de milioane de simboluri se constata cu raport de compresie de pana la 2, depinzand si de continutul fisierului

28LZ78LZ77 presupune localitatea grupurilor de simboluriLZ78:Nu exista un buffer de cautare dictionarul este explicitCodificatorul/decodificatorul construiesc dictionarul intr-un mod sincronizatCodificare: i = indexul din dictionarc = codul urmatorului simbolExample:wabbawabbawabbawabbawoowoowoo29Exemplu LZ78IndexIntr.Dictionar: Input: wabbawabbawabbawabbawoowoowooOutput:

30Exemplu LZ78IndexIntr.1wDictionar: Input: wabbawabbawabbawabbawoowoowooOutput:

31Exemplu LZ78IndexIntr.1w2aDictionar: Input: -abbawabbawabbawabbawoowoowooOutput:

32Exemplu LZ78IndexIntr.1w2a3bDictionar: Input: --bbawabbawabbawabbawoowoowooOutput:

33Exemplu LZ78IndexIntr.1w2a3b4baDictionar: Input: ---bawabbawabbawabbawoowoowooOutput:

34Exemplu LZ78IndexIntr.1w2a3b4ba5Dictionar: Input: -----wabbawabbawabbawoowoowooOutput:

35Exemplu LZ78IndexIntr.1w2a3b4ba56waDictionar: Input: ------wabbawabbawabbawoowoowooOutput:

36Exemplu LZ78IndexIntr.1w2a3b4ba56wa7bbDictionar: Input: --------bbawabbawabbawoowoowooOutput:

37Exemplu LZ78IndexIntr.1w2a3b4ba56wa7bb8aDictionar: Input: ----------awabbawabbawoowoowooOutput:

38Exemplu LZ78IndexIntr.1w2a3b4ba56wa7bb8a9wabDictionar: Input: ------------wabbawabbawoowoowooOutput:

39Exemplu LZ78IndexIntr.1w2a3b4ba56wa7bb8a9wab10baDictionar: Input: ---------------bawabbawoowoowooOutput:

40Exemplu LZ78IndexIntr.1w2a3b4ba56wa7bb8a9wab10baDictionar: Input: ------------------wabbawoowoowooOutput:

11wabb41Exemplu LZ78Dictionar: Input: ----------------------awoowoowooOutput:

11wabb12awIndexIntr.1w2a3b4ba56wa7bb8a9wab10ba42Exemplu LZ78Dictionar: Input: -------------------------oowoowooOutput:

11wabb12aw13oIndexIntr.1w2a3b4ba56wa7bb8a9wab10ba43Exemplu LZ78Dictionar: Input: --------------------------owoowooOutput:

11wabb12aw13o14oIndexIntr.1w2a3b4ba56wa7bb8a9wab10ba44Exemplu LZ78Dictionar: Input: ----------------------------woowooOutput:

11wabb12aw13o14o15woIndexIntr.1w2a3b4ba56wa7bb8a9wab10ba45Exemplu LZ78Dictionar: Input: ------------------------------owooOutput:

11wabb12aw13o14o15wo16owIndexIntr.1w2a3b4ba56wa7bb8a9wab10ba46Exemplu LZ78Dictionar: Input: ---------------------------------ooOutput:

11wabb12aw13o14o15wo16ow17ooIndexIntr.1w2a3b4ba56wa7bb8a9wab10ba47LZ78ObservatieDaca continuam sa codificam, dictionarul continua sa creascaSolutii practiceOprirea cresterii dictionaruluiefectiv ,considerarea dictionarului ca unul staticMicsorarea dictionaruluiEx: pe baza statisticilor de utilizareResetarea dictionaruluiFara a cunoaste informatii specifice referitoare la sursa, tehnicile de mai sus nu garanteaza succesulAlgoritmul Lempel-Ziv-WelchIdea de baza este de a imparti (parse-in limba engleza) secventa de intrare in blocuri (siruri) diferite de lungime diferita

Multimea blocurilor diferite defineste un dictionar

Indexul cuvintelor din dictionar este salvat in fisierul comprimat

Algoritmul Lempel-Ziv-WelchAlgoritm de codare LZW: Date intiale: Alfabetul A; secventa de intrare in; #1. Initializeaza dictionarul cu simbolurile alfabetului; #2. Initializeaza secventa comprimata: code =; #3. Citeste primul caracter de intrare, sirul prefix S: S = in(1); #4. Cat Timp nu s-a parcurs toata secventa de intrare EXECUTA: #4.1.Citeste urmatorul caracter de intrare: K = in(i+1). #4.2. Daca sirul SK este in tabel ATUNCI #4.2.1. Asigneaza: S = SK; ALTFEL #4.2.2. Memoreaza SK in dictionar;#4.2.3. Asigneaza: S = K;#4.2.4. Scrie: code = code + code(S)End #4.2; End #5; END.

Exemplu (1)Fie mesajul abba_baba_buba si dictionarul initializat cu alfabetul sursei, adica D={a,_,b,u}.

Initializare: code={}, S=D={a,_,b,u}

Citeste primul caracter: abba_baba_buba

Exemplu (1)Citeste urmatorul caracter abba_baba_buba

Citeste urmatorul caracter abba_baba_buba

Exemplu (1)Citeste urmatorul caracter abba_baba_buba

Citeste urmatorul caracter abba_baba_buba

Exemplu (1)Citeste urmatorul caracter abba_baba_buba

Citeste urmatorul caracter abba_baba_buba

Exemplu (1)Citeste urmatorul caracter abba_baba_buba

Citeste urmatorul caracter abba_baba_buba

Exemplu (1)Citeste urmatorul caracter abba_baba_buba

Citeste urmatorul caracter abba_baba_buba

Exemplu (1)Citeste urmatorul caracter abba_baba_buba

Citeste urmatorul caracter abba_baba_buba

Exemplu (1)Citeste urmatorul caracter abba_baba_buba

Rezultatele finale sunt:D = { 'a' '_' 'b' 'u' 'ab' 'bb' 'ba' 'a_' '_b' 'bab' 'ba_' '_bu' 'ub'}code = {1, 3, 3, 1, 2, 7, 7, 9, 4}Presupunand ca se cunoaste alfabetul si dictionarul, atat la emisie cat si la receptie, ar rezulta un raport de compresie maxim

Exemplu (2)IndexIntr.12a3b4o5w678910Dictionar: Output:

Input: wabbawabbawabbawabbawoowoowoop = Exemplu (2)IndexIntr.12a3b4o5w678910Dictionar: Output:

Input: wabbawabbawabbawabbawoowoowoop = w Exemplu (2)IndexIntr.12a3b4o5w6wa78910Dictionar: Output:

5 (w)Input: -abbawabbawabbawabbawoowoowoop = waExemplu (2)IndexIntr.12a3b4o5w6wa7ab8910Dictionar: Output:

5 (w)2 (a)Input: --bbawabbawabbawabbawoowoowoop = abExemplu (2)IndexIntr.12a3b4o5w6wa7ab8bb910Dictionar: Output:

5 (w)2 (a)3 (b)Input: ---bawabbawabbawabbawoowoowoop = bbExemplu (2)IndexIntr.12a3b4o5w6wa7ab8bb9ba10Dictionar: Output:

5 (w)2 (a)3 (b)3 (b)Input: ----awabbawabbawabbawoowoowoop = baExemplu (2)IndexIntr.12a3b4o5w6wa7ab8bb9ba10aDictionar: Output:

5 (w)2 (a)3 (b)3 (b)2 (a)Input: -----wabbawabbawabbawoowoowoop = aExemplu (2)IndexIntr.12a3b4o5w6wa7ab8bb9ba10aDictionar: Output:

5 (w)2 (a)3 (b)3 (b)2 (a)1 ()Input: ------wabbawabbawabbawoowoowooIndexIntr.11w121314151617181920p = wExemplu (2)IndexIntr.12a3b4o5w6wa7ab8bb9ba10aDictionar: Output:

5 (w)2 (a)3 (b)3 (b)2 (a)1 ()

Input: -------abbawabbawabbawoowoowooIndexIntr.11w121314151617181920p = waExemplu (2)IndexIntr.12a3b4o5w6wa7ab8bb9ba10aDictionar: Output:

5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)

Input: --------bbawabbawabbawoowoowooIndexIntr.11w12wab1314151617181920p = wabExemplu (2)IndexIntr.12a3b4o5w6wa7ab8bb9ba10aDictionar: Output:

5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)

Input: ---------bawabbawabbawoowoowooIndexIntr.11w12wab1314151617181920p = bbExemplu (2)IndexIntr.12a3b4o5w6wa7ab8bb9ba10aDictionar: Output:

5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)

Input: ----------awabbawabbawoowoowooIndexIntr.11w12wab13bba14151617181920p = bbaExemplu (2)IndexIntr.12a3b4o5w6wa7ab8bb9ba10aDictionar: Output:

5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)

Input: -----------wabbawabbawoowoowooIndexIntr.11w12wab13bba14151617181920p = aExemplu (2)IndexIntr.12a3b4o5w6wa7ab8bb9ba10aDictionar: Output:

5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)

Input: ------------wabbawabbawoowoowooIndexIntr.11w12wab13bba14aw151617181920p = awExemplu (2)IndexIntr.12a3b4o5w6wa7ab8bb9ba10aDictionar: Output:

5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)

Input: -------------abbawabbawoowoowooIndexIntr.11w12wab13bba14aw151617181920p = waExemplu (2)IndexIntr.12a3b4o5w6wa7ab8bb9ba10aDictionar: Output:

5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)

Input: --------------bbawabbawoowoowooIndexIntr.11w12wab13bba14aw151617181920p = wabExemplu (2)IndexIntr.12a3b4o5w6wa7ab8bb9ba10aDictionar: Output:

5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)12 (wab)

Input: ---------------bawabbawoowoowooIndexIntr.11w12wab13bba14aw15wabb1617181920p = wabbExemplu (2)IndexIntr.12a3b4o5w6wa7ab8bb9ba10aDictionar: Output:

5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)12 (wab)

Input: ----------------awabbawoowoowooIndexIntr.11w12wab13bba14aw15wabb1617181920p = baExemplu (2)IndexIntr.12a3b4o5w6wa7ab8bb9ba10aDictionar: Output:

5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)12 (wab)9 (ba)

Input: -----------------wabbawoowoowooIndexIntr.11w12wab13bba14aw15wabb16ba17181920p = baExemplu (2)IndexIntr.12a3b4o5w6wa7ab8bb9ba10aDictionar: Output:

5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)12 (wab)9 (ba)

Input: ------------------wabbawoowoowooIndexIntr.11w12wab13bba14aw15wabb16ba17181920p = wExemplu (2)IndexIntr.12a3b4o5w6wa7ab8bb9ba10aDictionar: Output:

5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)12 (wab)9 (ba)11 (w)

Input: -------------------abbawoowoowooIndexIntr.11w12wab13bba14aw15wabb16ba17wa181920p = waExemplu (2)IndexIntr.12a3b4o5w6wa7ab8bb9ba10aDictionar: Output:

5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)12 (wab)9 (ba)11 (w)

Input: --------------------bbawoowoowooIndexIntr.11w12wab13bba14aw15wabb16ba17wa181920p = abExemplu (2)IndexIntr.12a3b4o5w6wa7ab8bb9ba10aDictionar: Output:

5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)12 (wab)9 (ba)11 (w)7 (ab)

Input: ---------------------bawoowoowooIndexIntr.11w12wab13bba14aw15wabb16ba17wa18abb1920p = abbExemplu (2)IndexIntr.12a3b4o5w6wa7ab8bb9ba10aDictionar: Output:

5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)12 (wab)9 (ba)11 (w)7 (ab)

Input: ----------------------awoowoowooIndexIntr.11w12wab13bba14aw15wabb16ba17wa18abb1920p = baExemplu (2)IndexIntr.12a3b4o5w6wa7ab8bb9ba10aDictionar: Output:

5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)12 (wab)9 (ba)11 (w)7 (ab)

Input: -----------------------woowoowooIndexIntr.11w12wab13bba14aw15wabb16ba17wa18abb1920p = baExemplu (2)IndexIntr.12a3b4o5w6wa7ab8bb9ba10aDictionar: Output:

5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)12 (wab)9 (ba)11 (w)7 (ab)16 (ba)

Input: ------------------------woowoowooIndexIntr.11w12wab13bba14aw15wabb16ba17wa18abb19baw20p = bawExemplu (2)IndexIntr.12a3b4o5w6wa7ab8bb9ba10aDictionar: Output:

5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)12 (wab)9 (ba)11 (w)7 (ab)16 (ba)

Input: -------------------------oowoowooIndexIntr.11w12wab13bba14aw15wabb16ba17wa18abb19baw20wop = wo5 (w)

Exemplu (2)IndexIntr.12a3b4o5w6wa7ab8bb9ba10aDictionar: Output:

5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)12 (wab)9 (ba)11 (w)7 (ab)16 (ba)

Input: --------------------------owoowooIndexIntr.11w12wab13bba14aw15wabb16ba17wa18abb19baw20wop = oo5 (w)4 (o)

IndexIntr.21oo222324252627282930Exemplu (2)IndexIntr.12a3b4o5w6wa7ab8bb9ba10aDictionar: Output:

5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)12 (wab)9 (ba)11 (w)7 (ab)16 (ba)

Input: ---------------------------woowooIndexIntr.11w12wab13bba14aw15wabb16ba17wa18abb19baw20wop = o5 (w)4 (o)4 (o)

IndexIntr.21oo22o2324252627282930Exemplu (2)IndexIntr.12a3b4o5w6wa7ab8bb9ba10aDictionar: Output:

5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)12 (wab)9 (ba)11 (w)7 (ab)16 (ba)

Input: ----------------------------woowooIndexIntr.11w12wab13bba14aw15wabb16ba17wa18abb19baw20wop = w5 (w)4 (o)4 (o)

IndexIntr.21oo22o2324252627282930Exemplu (2)IndexIntr.12a3b4o5w6wa7ab8bb9ba10aDictionar: Output:

5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)12 (wab)9 (ba)11 (w)7 (ab)16 (ba)

Input: -----------------------------oowooIndexIntr.11w12wab13bba14aw15wabb16ba17wa18abb19baw20wop = wo5 (w)4 (o)4 (o)11 (w)

IndexIntr.21oo22o23wo24252627282930Exemplu (2)IndexIntr.12a3b4o5w6wa7ab8bb9ba10aDictionar: Output:

5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)12 (wab)9 (ba)11 (w)7 (ab)16 (ba)

Input: ------------------------------owooIndexIntr.11w12wab13bba14aw15wabb16ba17wa18abb19baw20wop = oo5 (w)4 (o)4 (o)11 (w)

IndexIntr.21oo22o23wo24252627282930Exemplu (2)IndexIntr.12a3b4o5w6wa7ab8bb9ba10aDictionar: Output:

5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)12 (wab)9 (ba)11 (w)7 (ab)16 (ba)

Input: -------------------------------wooIndexIntr.11w12wab13bba14aw15wabb16ba17wa18abb19baw20wop = oo5 (w)4 (o)4 (o)11 (w)21 (oo)

IndexIntr.21oo22o23wo24oo252627282930Exemplu (2)IndexIntr.12a3b4o5w6wa7ab8bb9ba10aDictionar: Output:

5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)12 (wab)9 (ba)11 (w)7 (ab)16 (ba)

Input: --------------------------------wooIndexIntr.11w12wab13bba14aw15wabb16ba17wa18abb19baw20wop = w5 (w)4 (o)4 (o)11 (w)21 (oo)

IndexIntr.21oo22o23wo24oo252627282930Exemplu (2)IndexIntr.12a3b4o5w6wa7ab8bb9ba10aDictionar: Output:

5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)12 (wab)9 (ba)11 (w)7 (ab)16 (ba)

Input: ---------------------------------ooIndexIntr.11w12wab13bba14aw15wabb16ba17wa18abb19baw20wop = wo5 (w)4 (o)4 (o)11 (w)21 (oo)

IndexIntr.21oo22o23wo24oo252627282930Exemplu (2)IndexIntr.12a3b4o5w6wa7ab8bb9ba10aDictionar: Output:

5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)12 (wab)9 (ba)11 (w)7 (ab)16 (ba)

Input: ----------------------------------oIndexIntr.11w12wab13bba14aw15wabb16ba17wa18abb19baw20wop = woo5 (w)4 (o)4 (o)11 (w)21 (oo)23 (wo)

IndexIntr.21oo22o23wo24oo25 woo2627282930Exemplu (2)IndexIntr.12a3b4o5w6wa7ab8bb9ba10aDictionar: Output:

5 (w)2 (a)3 (b)3 (b)2 (a)1 ()6 (wa)8 (bb)10 (a)12 (wab)9 (ba)11 (w)7 (ab)16 (ba)

Input: -----------------------------------IndexIntr.11w12wab13bba14aw15wabb16ba17wa18abb19baw20wop = o5 (w)4 (o)4 (o)11 (w)21 (oo)23 (wo)4 (o)

IndexIntr.21oo22o23wo24oo25 woo2627282930Exemplu decodificare (2)IndexIntr.12a3b4o5w678910Dictionar: Input: 5 2 3 3 2 1 6 8 10 12 9 11 7 16 5 4 4 11 21 23 4p = Output:Exemplu decodificare (2)IndexIntr.12a3b4o5w678910Dictionar: Input: 5 2 3 3 2 1 6 8 10 12 9 11 7 16 5 4 4 11 21 23 4p = w Output: wExemplu decodificare (2)IndexIntr.12a3b4o5w6wa78910Dictionar: Input: - 2 3 3 2 1 6 8 10 12 9 11 7 16 5 4 4 11 21 23 4p = wa Output: waExemplu decodificare (2)IndexIntr.12a3b4o5w6wa7ab8910Dictionar: Input: - - 3 3 2 1 6 8 10 12 9 11 7 16 5 4 4 11 21 23 4p = ab Output: wabExemplu decodificare (2)IndexIntr.12a3b4o5w6wa7ab8bb910Dictionar: Input: - - - 3 2 1 6 8 10 12 9 11 7 16 5 4 4 11 21 23 4p = bb Output: wabbExemplu decodificare (2)IndexIntr.12a3b4o5w6wa7ab8bb9ba10Dictionar: Input: - - - - 2 1 6 8 10 12 9 11 7 16 5 4 4 11 21 23 4p = ba Output: wabbaExemplu decodificare (2)IndexIntr.12a3b4o5w6wa7ab8bb9ba10a Dictionar: Input: - - - - - 1 6 8 10 12 9 11 7 16 5 4 4 11 21 23 4p = a Output: wabbaExemplu decodificare (2)IndexIntr.12a3b4o5w6wa7ab8bb9ba10a Dictionar: Input: - - - - - - 6 8 10 12 9 11 7 16 5 4 4 11 21 23 4p = wa Output: wabbawaIndexIntr.11w121314151617181920Exemplu decodificare (2)IndexIntr.12a3b4o5w6wa7ab8bb9ba10a Dictionar: Input: - - - - - - - 8 10 12 9 11 7 16 5 4 4 11 21 23 4p = wa Output: wabbawaIndexIntr.11w121314151617181920Exemplu decodificare (2)IndexIntr.12a3b4o5w6wa7ab8bb9ba10a Dictionar: Input: - - - - - - - 8 10 12 9 11 7 16 5 4 4 11 21 23 4p = wabb Output: wabbawabbIndexIntr.11w12wab1314151617181920Exemplu decodificare (2)IndexIntr.12a3b4o5w6wa7ab8bb9ba10a Dictionar: Input: - - - - - - - - 10 12 9 11 7 16 5 4 4 11 21 23 4p = bb Output: wabbawabbIndexIntr.11w12wab1314151617181920Exemplu decodificare (2)IndexIntr.12a3b4o5w6wa7ab8bb9ba10a Dictionar: Input: - - - - - - - - 10 12 9 11 7 16 5 4 4 11 21 23 4p = bba Output: wabbawabbaIndexIntr.11w12wab13bba14151617181920Exemplu decodificare (2)IndexIntr.12a3b4o5w6wa7ab8bb9ba10a Dictionar: Input: - - - - - - - - - 12 9 11 7 16 5 4 4 11 21 23 4p = bba Output: wabbawabbaIndexIntr.11w12wab13bba14151617181920Exemplu decodificare (2)IndexIntr.12a3b4o5w6wa7ab8bb9ba10a Dictionar: Input: - - - - - - - - - 12 9 11 7 16 5 4 4 11 21 23 4p = a Output: wabbawabbaIndexIntr.11w12wab13bba14151617181920Exemplu decodificare (2)IndexIntr.12a3b4o5w6wa7ab8bb9ba10a Dictionar: Input: - - - - - - - - - 12 9 11 7 16 5 4 4 11 21 23 4p = awab Output: wabbawabbawabIndexIntr.11w12wab13bba14aw151617181920Exemplu decodificare (2)IndexIntr.12a3b4o5w6wa7ab8bb9ba10a Dictionar: Input: - - - - - - - - - - 9 11 7 16 5 4 4 11 21 23 4p = wab Output: wabbawabbawabIndexIntr.11w12wab13bba14aw151617181920Exemplu decodificare (2)IndexIntr.12a3b4o5w6wa7ab8bb9ba10a Dictionar: Input: - - - - - - - - - - 9 11 7 16 5 4 4 11 21 23 4p = wab Output: wabbawabbawabIndexIntr.11w12wab13bba14aw151617181920Exemplu decodificare (2)IndexIntr.12a3b4o5w6wa7ab8bb9ba10a Dictionar: Input: - - - - - - - - - - 9 11 7 16 5 4 4 11 21 23 4p = wab Output: wabbawabbawabIndexIntr.11w12wab13bba14aw151617181920Exemplu decodificare (2)IndexIntr.12a3b4o5w6wa7ab8bb9ba10a Dictionar: Input: - - - - - - - - - - 9 11 7 16 5 4 4 11 21 23 4p = wabba Output: wabbawabbawabbaIndexIntr.11w12wab13bba14aw15wabb1617181920Exemplu decodificare (2)IndexIntr.12a3b4o5w6wa7ab8bb9ba10a Dictionar: Input: - - - - - - - - - - - 11 7 16 5 4 4 11 21 23 4p = ba Output: wabbawabbawabbaIndexIntr.11w12wab13bba14aw15wabb1617181920Exemplu decodificare (2)IndexIntr.12a3b4o5w6wa7ab8bb9ba10a Dictionar: Input: - - - - - - - - - - - 11 7 16 5 4 4 11 21 23 4p = baw Output: wabbawabbawabbawIndexIntr.11w12wab13bba14aw15wabb16ba17181920Exemplu decodificare (2)IndexIntr.12a3b4o5w6wa7ab8bb9ba10a Dictionar: Input: - - - - - - - - - - - - 7 16 5 4 4 11 21 23 4p = w Output: wabbawabbawabbawIndexIntr.11w12wab13bba14aw15wabb16ba17181920 and so on ConcluziiAsa cum este de asteptat, rezultatele compresiei depind mult de tipul datelor de comprimatIn tabelul de mai jos se prezinta rezultatele obtinute pentru diferite continute ale fisierelor

Adaptive Huffman(compact sub Unix)Lempel-Ziv(compress sub UNIX)LaTeX file66%44%Speech file65%64%Image file94%88%ConcluziiAceasta metode de compresie se foloseste la o serie de standarduri de imagine GIF si TIFFstandardul V.24bis al modemurilor standardul PostScript Level 2LZW este un algoritm general care poate lucra pe orice tip de dateEste rapid atat la compresie cat si la decompresie si nu necesita operatii in virgula mobilaLZW scrie datele compresate sub forma de octeti si nu ca si cuvinte, ceea ce face ca datele comprimate sa fie independente de platforma

ConcluziiLZW este cunoscut ca facand parte din categoria algoritmilor de codare bazati pe dictionar sau substitutionalAlgoritmul construieste un dictionar (denumit si tabel de translatie sau tabel de siruri) al datelor ce apar in fluxul de date ce trebuie comprimatIn fluxul de date se identifica forme de date (substrings) si memorate in intrarile dictionaruluiDaca un subsir nu este prezent in dictionar, la momentul intalnirii sale, respectivul subsir se memoreaza si se codifica in dictionarCodul alocat subsirului este scris in secventa de iesire, care este secventa comprimataCand se intalneste un subsir deja existent in dictionar, in secventa de iesire se scrie codul subsirului existent in dictionar

ConcluziiAvantajul LZW este ca nu trebuie memorat dictionarul in vederea decodarii secventei comprimate, lucru avantajos in unele aplicatii

Cand se comprima fisiere text, LZW initializeaza primele 256 intrari ale dictionarului cu codul ASCII ca fiind fraze (siruri de lungime 1)

Mai departe, toate subsirurile sunt construite pe baza simbolurilor individuale, definite anterior

ConcluziiPentru secvente de intrare foarte mari lungimea dictionarului poate creste foarte multDe aceea, in practica, dimensiunea dictionarului este limitata la 4096 cuvinte, ceea ce corespunde la o reprezentare a indexului (codul cuvintelor sir din dictionar) de 12 bitiDaca indexul este reprezentat prin secvente binare de lungime variabila, atunci se obtine varianta lungime variabila-lungime variabila a algoritmului Lempel-Ziv

Atentie!!! Algoritmul LZ codifica pozitia prefixului urmat de ultimul caracterAlgoritmul LZW codifica numai pozitia sirului in dictionar si numai pentru cuvinte(siruri) noi din dictionar

Compresia MTF (Move to front)Una dintre cele mai intuitive metode de compresie a datelorFolosete o tehnic adaptiv bazat pe un dicionar, realiznd compresia fiierul de intrare cuvnt cu cuvnt Un cuvnt este definit ca orice ir de caractere situat ntre dou spaii albe sau ntre dou caractere ce marcheaz o linie nouDeoarece nu se iau n considerare spaiile albe, aceast metoda de compresie este una cu pierderi de date, neputnd diferenia la ieire de exemplu: _ i ___ 122Algoritmul de compresiePentru fiecare cuvnt din fiierul de intrare Dac cuvntul este unul care a mai fost ntlnit n prealabil Returneaz poziia Mut cuvntul la nceputul listei Altfel Adaug cuvntul la nceputul listei de cuvinte

123DetaliiAlgoritmul construiete gradual o list de cuvinte ntlnite la intrare (un dicionar)Cel mai recent cuvnt ntlnit de-a lungul procesului de compresie este mutat la nceputul listeica urmare, cuvintele cele mai des ntlnite n text vor avea tendina de a se grupa n apropierea nceputului listei. Codificnd cuvintele situate la indici mai mici n dicionar cu un numr mai mic de bii dect cuvintele situate mai la sfritul listei de cuvinte, se obine o compresie mai bun dect dac s-ar nlocui fiecare cuvnt cu un numr ntreg spre exemplu124DezavatajePrincipala deficiena a compresiei MTF o reprezint creterea necontrolat n dimensiune a dicionarului folosit, care poate duce la probleme de memorie (n cazul n care fiierul de intrare conine mai multe cuvinte dect pot fi memorate pe aparatul de calcul)Solutie:limitarea dimensiunii listei de cuvinte la un numr prestabilit; deoarece majoritatea cuvintelor cele mai des ntlnite sunt mutate n fa, cuvintele care rmn pe dinafar (i deci vor fi transmise necodat) apar foarte rar i astfel eficiena compresiei nu este afectat foarte tareCe se intampla spre exemplu n cazul n care fiecare cuvnt are o lungime foarte mare (de exemplu 8000 de caractere)?memoria devine iari insuficient125ProprietatiIn orice moment, dicionarul va conine primele 4096 cele mai recent ntlnite cuvinte (presupunnd c dimensiunea sa este limitat la 4096)Acestea nu sunt ns neaprat i cele mai des ntlnite cuvinte din textCa urmare, cuvintele cele mai comune pot fi uitate foarte uor dup 4096 de poziii, n caz c nu se repet din nouExist pericolul ca algoritmul s consume cea mai mare parte din timp adaptndu-se constant la noile tipare ce apar n text, fr a se concentra pe densitatea de apariie a elementelor (care este de fapt cheia acestui tip de compresie)126Exemplu127

Exemplu128

Exemplu129

Exemplu130