Știința compresiei datelor pentru toți

Acesta este un termen ușor de înțeles, dar a cărui funcționare este dificil de explicat. Tocmai acest tip de noțiuni îmi place să le explic în acest blog.

În informatică, compresia datelor poate fi formulată după cum urmează: „Pentru a transforma o serie de biți într-o altă serie de biți mai mici utilizând un algoritm în timp ce reținem informațiile, adică„ trebuie să fie posibilă operația inversă ”

Compresie fără pierderi

Cel mai ușor algoritm de compresie fără pierderi de înțeles este Codificare RLE (Run Length Encoding) care constă în numărarea repetărilor unui personaj (sau a unui bit).

Exemplu de codificare RLE: cuvântul "ouuuuuaauuuuuu" este interpretat ca fiind o secvență a unui "o", 5 "u", 2 "a" și 6 "u", adică: "o5u2a6u". Prin urmare, am comprimat 14 caractere în 7 caractere (rata de compresie de 50%). Este evident că acest tip de codare este relevant numai dacă se repetă șiruri mari de caractere. Acesta este cazul codificării faxurilor pentru a codifica succesiunea de puncte
alb-negru pe o foaie (codare CCITT).

Alte tehnici de compresie fără pierderi sunt compresia entropiei . Acești algoritmi se bazează pe un studiu statistic al informațiilor care trebuie comprimate astfel încât să codifice caracterele recurente în foarte puțini biți. Cei mai renumiți algoritmi de entropie sunt algoritmul lui Huffman și algoritmul
LZ77.

Algoritmul lui Huffman

Cel mai bun mod de a înțelege acest algoritm este de a da un exemplu. Să ne stabilim obiectivul comprimării propoziției „OBIECTIVII SUNT INTELIGENTI”.

În reprezentarea ASCII clasică, aveți nevoie de 7 biți pe literă (2 ^ 7 = 128 caractere în total): această propoziție de 35 de caractere va ocupa, prin urmare, un spațiu de memorie de 35 * 7 = 245 biți.

Acum, folosind codificarea lui Huffman, vom studia numărul de apariții ale fiecărei litere din textul care trebuie comprimat, astfel încât să alocăm un număr mai mic de biți literelor cele mai utilizate:

C, F, Q, U, O, G: 1 apariție
L, SPAȚIU: 3 apariții
T, N: 4 apariții
E, S, I: 5 apariții

Apoi construim un copac în care fiecare frunză reprezintă o literă însoțită de greutatea sa (numărul de apariții). Apoi luăm cele mai mici 2 greutăți pentru a le grupa și a obține un nod cu o greutate egală cu suma celor 2 frunze și așa mai departe până la obținerea unui singur nod la sfârșit.

Cu exemplul nostru:

a) Regrupăm literele de greutate "1" și le adăugăm pentru a face noduri de greutate "2" (galben)
b) Adăugăm cele 2 litere de greutate "3" la 2 noduri de greutate "2" pentru a face noduri de greutate "5" (verde)
c) Adăugăm cele 2 litere de greutate "4" la nodurile de greutate "2" și "5" pentru a face noduri de greutate "6" și "9" (magenta).
d) Adăugăm cele 3 litere de greutate "5" la nodurile de greutate "5", "6" și "9" pentru a face noduri de greutate "10", "11" și "14" (portocaliu).
e) Terminăm arborele până obținem un nod comun de greutate „35” (roșu).
f) Rămâne să atribuiți o serie de biți fiecărei litere. Pentru a face acest lucru, alegem să adăugăm un bit „0” pentru ramurile din stânga și un bit „1” pentru ramurile din dreapta și obținem apoi următorul arbore: