Comprimarea datelor; es - Compresie aritmică; bifează

Codificare aritmetică

Această parte va introduce o compresie fără pierderi numită codare aritmetică. Mai întâi va defini interesul algoritmului înainte de a prezenta compresia și decompresia efectuate de această codare

bifează

Descriere

Codificarea aritmetică este o codificare statistică, adică cu cât este reprezentat mai mult un caracter, cu atât mai puțini biți vor fi necesari pentru a-l codifica.

Este un verișor al codificării Huffman, care este totuși mai eficient decât cel din urmă (cu excepția cazului special în care toate greutățile frunzelor/nodurilor/rădăcinilor arborelui Huffman sunt puteri de 2). De asemenea, este mai ușor de implementat.

Avantajul codificării aritmetice față de codificarea Huffman este că acesta din urmă va codifica un caracter peste un număr întreg de biți (nu poate codifica 1,5 biți) unde poate codifica aritmetica. De exemplu, dacă un caracter este reprezentat la 90%, dimensiunea optimă a codului de caractere ar fi de 0,15 biți, în timp ce Huffman ar codifica probabil acest simbol pe 1 bit, sau de 6 ori prea mult.

Această codificare este utilizată foarte puțin în practică, dar rămâne prezentă, în special în formatul JPEG2000.

Comprimare

Pentru a demonstra compresia, vom folosi un exemplu și vom descrie fiecare etapă de compresie. Să codificăm cuvântul „ESIPE” folosind codarea aritmetică.

Primul pas este de a număra fiecare literă a cuvântului. Deci avem 2 „E”, 1 „S”, 1 „I” și 1 „P”. Apoi generăm o probabilitate de prezență în cuvânt, adică 40% șanse de a găsi un E și 20% șanse pentru celelalte litere. Ultima acțiune care trebuie efectuată pentru această primă parte, atribuim fiecărei litere un interval între 0 și 1, după cum urmează:

  • Litera „E” are o probabilitate de 40% (sau 0,4). Intervalul său este, prin urmare, [0,0,4 [
  • Litera „P” are o probabilitate de 20% (sau 0,2). Intervalul său este, prin urmare, [0,4,0,6 [
  • Etc.