Metode de compresie bazate pe dicționar - codarea Lempel-Ziv

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.

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

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 .