Metode De Compresie Bazate Pe Dictionar - Codarea Lempel - Ziv

Metode de compresie bazate pe dictionar. Codarea Lempel-Ziv Cuprins Introducere Ideea compresiei bazate pe dictionar. Exemplu. Algoritmul Lempel-Ziv Algoritmul Lempel-Ziv-Welch Implementare si Exemple Concluzii Introducere Folosit in compress -uncompress, gzip-gunzip din UNIX , sau WinZip din Windows. Algoritmul de compresie este de tipul lungime variabila - lungime fixa. Exista si variante lungime variabila-lungime variabila. Textul se imparte in siruri (cuvinte) distincte. Acestea definesc un dictionar. Se codifica pozitia sirului in dictionar. Dictionarele pot fi statice sau adaptive. Un dictionar static este construit si transmis odata cu textul comprimat si este folosit ca referintele citate intr-o lucrare stiintifica. Un dictionar static este construit inaintea efectuariii compresiei si ramane neschimbat pe toata durata acesteia. Dictionarul 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 entropica. Dezavantajul 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 subunitar. De aceea, cei mai raspanditi sunt algoritmii de compresie bazati pe dictionare adaptive. Un dictionar adaptiv consta in adaugarea unei abrevieri pe langa anumite grupe de simboluri, cand apar prima oara, si utilizarea in continuare doar a abrevierilor. Cel 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 LZ77, si – a doua, din 1978, cunoscuta sub numele de LZ78.

1

Un exemplu: Fie mesajul „Titlul acestui capitol este compresia datelor”. Fie conventia reprezentarii unui cuvant dintr-o carte prin doua atribute, sub forma: (Numarul_paginii) / (numarul_cuvantului_din_pagina). Mesajul codat dupa aceasta conventie-regula este 500/3

1/5

10/2

15/9

10/6

12/1

Cuvantul „Titlul” este inlocuit prin 500/3, ceea ce reprezinta al treilea cuvant de pe pagina 500. Cuvantul „compresia” este al 6 cuvant de pe pagina 10. Marimea mesajului comprimat depinde de marimea dictionarului, deci de numarul de pagini si de numarul de inregistrari pe pagina. Fie NP (numarul de pagini) si NR (numarul de inregistrari pe pagina) atunci numarul de biti pentru reprezentarea (codarea) unui cuvant din dictionar este n = [log2(NP)] + [log2(NR)]. Intrucat trebuie considerat si marimea mesajului de la intrare, exprimat prin numarul de simboluri, NS, rezulta un raport de compresie RC( biti ) =

8 ⋅ NS 8 = {[ log( NP )] + [ log( NR )]} ⋅ NS {[ log( NP )] + [ log( NR )]}

Exemplu numeric: Fie NP = 2200 pagini; sunt necesari log2(2200) = 11.03 -> 12 biti pentru a coda numarul paginii. Fie NR = 256. Pentru reprezentarea binara a unui cuant este nevoie de log2(256) = 8 biti. Un cuvant oarecare din dictionar este codat pe 20 (12+8) biti. Mesajul comprimat va avea lungimea 20 biti * 6 cuvinte = 120 biti. In reprezentarea ASCII, cele 6 cuvinte au 46 de caractere si necesita 46 * 8 = 368 biti. Raportul de compresie este

RC ( biti ) =

320 biti = 3.06 . 120 biti

■ 2

Algoritmul Lempel-Ziv Schema de compresie trebuie sa imparta datele in sub-siruri, sa codeze sub-sirurile, si sa fie posibila si operatia inversa. Fie urmatorul sir de date: 001101100011010101001001001101000001010010110010110 1). Se imparte mesajul in subsiruri, astfel incat la fiecare definitie a unui subsir sa nu existe repetitiii, deci el sa nu fi fost definit anterior. 1.1 La inceputul sirului se pune o virgula pentru a evidentia sirul de lungime zero. 1.2 Se pune apoi o virgula dupa primul zero, intrucat nu a mai aparut. 1.3. Al doilea bit este zero si se considera si al doilea simbol, obtinandu-se sirul 01. Intrucat acesta este sir nou se pune virgula. 1.4 Urmeaza simbolul 1, care fiind caracter nou, atrage virgula dupa el. 1.5. Apoi apare un zero si doi de 1, ca sa fie un sir nou, s.a.m.d. … Rezultatul consta in urmatoarea lista de siruri, ce defineste dictionarul sau tabelul ,0,01,1,011,00,0110,10,101,001,0010, 01101,000,00101,001011,0010110 Tema pentru acasa Mesaj = 110010101000111101010100101011101011 Dictionar = ,1,10,0,101,01,00,011,11,010,1010,0101,0111,01011 2). Determinarea numarului de biti pentru reprezentarea secventei astfel obtinute. k = [ log2 N ] = [ log2 15] = 4

3) C odarea sirurilor, astfel obtinute. Se completeaza un tabel de forma de mai jos, in care se definesc: sirul, numarul ce arata pozitia sirului, prefixul, numarul ce arata pozitia prefixului, si codul sirului. Codul sirului este obtinut considerand numarul ce arata pozitia prefixului urmat de ultimul bit al sirului considerat.

3

Nr. sirului

Sirul

Codarea pozitiei sirului

Prefix

Codarea pozitiei prefixului

Sir codat

1.

0

0001

empty

0 = 0000

0000+0 = 00000

2.

01

0010

0

1 = 0001

0001+1 = 00011

3.

1

0011

empty

0 = 0000

0000+1 = 00001

4.

011

0100

01

2 = 0010

00101

5.

00

0101

0

1 = 0001

00010

6.

0110

0110

011

4 = 0100

01000

7.

10

0111

1

3 = 0011

00110

8.

101

1000

10

7 = 0111

01111

9.

001

1001

00

5 = 0101

01011

10.

0010

1010

001

9 = 1001

10010

11.

01101

1011

0110

6 = 0110

01101

12.

000

1100

00

5 = 0101

01010

13.

00101

1101

0010

10 = 1010

10101

14.

001011

1110

00101

13 = 1101

11011

15.

0010110

1111

001011

14 = 1110

11100

Secventa comprimata este format prin concatenarea tuturor sirulor codate, aflate in ultima coloana a tabelului de mai sus. Se obtine: 00000-00011-00001-00101-00010-01000-00110-01111 01011-10010-01001-01010-10101-11011-11100 4) Raportul de compresie este RC =

15 * 8 = 1.6 15 * 5

Pentru fisiere cu secventa de lungime de milioane de simboluri se constata cu raport de compresie de pana la 2, depinzand si de continutul fisierului.

4

Algoritmul Lempel-Ziv-Welch ALGORITM 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 (dictionar) 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. Exemplul 1 Rezultatele:

- Fie alfabetul

Dictionarul = 'a' 'b' 'ab' 'aab' 'baab' 'bba' code =

'1' '2'

'2' '1'

A = {a ,b}

'bb' 'ba' '3' '5'

si mesajul in = abbaabbaab abbaaaabaa bba . 'aa'

'3' '7'

'abb' 'baa' '6' '6'

'aba'

'abba'

'aaa'

'8' '4'

Presupunand ca se cunoaste alfabetul si dictionarul, atat la emisie cat si la receptie, ar rezulta un raport de compresie RC =

23 * 8 184 = = 3.53 13 * 4 52

■ Exemplul 2 - Fie D=

'a' 'b'

A = {a ,b , c}

'c'

code =

si mesajul in = ababcbabab aaaaaaa . Se obtin rezultatele:

'ab' 'ba' '1' '2'

'abc'

'cb' 'bab'

'4' '3'

RC =

'5' '8'

'baba' '1' '10'

'aa'

'aaa'

'aaaa'

'11'

17 * 8 136 = = 2.61 13 * 4 52

■ 5

Exemplul 3 (Tema pentru acasa): Fie alfabetul in = /WED/WE/WE E/WEB/WET . Rezultatele: Dictionarul =

A = { /, W, E, D, T, B}

'/' 'W' 'E' 'D' 'T' 'B' '/W' 'WE' 'ED' 'D/' '/WEE' 'E/W' 'WEB' 'B/' '/WET'

code =

'1' '2'

'3' '4'

'7' '3'

'11' '12'

'8' '6'

si mesajul '/WE'

'E/'

'11' ■

CONCLUZII Rezultatele compresiei depind mult de tipul datelor de comprimat. In tabelul de mai jos se prezinta rezultatele obtinute pentru diferite continute ale fisierelor Adaptive Huffman Lempel-Ziv (compact sub Unix) (compress sub UNIX) LaTeX file 66% 44% Speech file 65% 64% Image file 94% 88% Aceasta metoda de compresie se foloseste la o serie de formaturi de imagine, cum sunt GIF si TIFF, in standardul V.24bis al modemurilor si in standardul PostScript Level 2. LZW scrie datele compresate sub forma de octeti si nu ca si cuvinte, ceea ce face ca datele comprimate sa fie independente de platforma. 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. Pentru secvente de intrare foarte mari lungimea dictionarului poate creste foarte mult. De 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 biti.

Anexa 2 – Codul Matlab pentru codarea LZW (Lempel-Ziv-Welch) 6

% ALGORITM DE CODARE LZW: % varianta cea mai simpla in care se cunoaste alfabetul; clc; clear; % se considera initializat dictionarul cu ASCII de la 0-255; A = 'ab' ; % alfabetul in = 'abbaabbaababbaaaabaabba'; % secventa de intrare; for i=1:length(A), D(i) = {A(i)}; end; % initializare dictionar: % initializari: i=1; gata = 0; code=[]; % citeste primul caracter: S = in(i); i=i+1; while ~gata, nou = 0; while ~nou & (i <= length(in)), % citeste urmatorul caracter: K = in(i); % cauta sirul SK in dictionar: [index, nou] = f_cauta_string([S K], D); if ~nou, S = [S K]; end; i = i+1; end; % while nou if nou, n = length(D); D(n+1) = {[S K]}; % actualizare dictionar; [index, nou] = f_cauta_string(S, D); % cauta indexul lui S index_string = num2str(index); % conversie str in numeric code = [code {index_string}]; % codifica S = K; end; if i > length(in), gata = 1; end; end; % while gata % Rezultate: code-corect = '1-2-2-1-3-5-3-7-6-6-8-4-1'; dictionar-corect = 'a-b-ab-bb-ba-aa-abb-baa-aba-abba-aaa-aab-baab-bba';

7