Algorisme de compressió sense pèrdua
| S'ha proposat que «Còdec sense pèrdua» sigui fusionat a aquest article. (Vegeu la discussió, pendent de concretar). Data: 2022 |
| Aquest article o secció no cita les fonts o necessita més referències per a la seva verificabilitat. |
S'anomena algorisme de compressió sense pèrdua a qualsevol procediment de codificació que tingui com a objectiu representar certa quantitat d'informació sense utilitzar-ne una menor quantitat, i és possible una reconstrucció exacta de les dades originals.
La compressió sense pèrdues és una tècnica que consisteix en la garantia de generar un duplicat exacte del flux de dades d'entrada després d'un cicle de compressió/expansió. És generalment implementada usant un o dos diferents tipus de models: estàtic o basat en diccionari.
El model estàtic llegeix i codifica mentre utilitza la probabilitat d'aparició d'un caràcter. La seva forma més simple fa servir una taula estàtica de probabilitats, en l'inici generar un arbre de Huffman tenia costos significants per tant no sempre era generat, en el seu lloc s'analitzaven blocs representatius de dades, donant una taula de freqüència característica. Llavors els arbres de Huffman es generaven i els programes tenien accés a aquest model estàtic.
- Però utilitzar un model estàtic té les seves limitacions. Si un flux d'entrada no concorda bé amb la prèviament estadística acumulada, la relació de compressió es degradaria, possiblement fins al punt que el flux de dades sortint fos tan llarg que l'entrant.
Per tant la següent millora òbvia va ser construir una taula estàtica a cada flux d'entrada únic.
El model basat en diccionari utilitza un codi simple per reemplaçar cadenes de símbols, els models estàtics generalment codifiquen un símbol a la vegada. L'esquema de compressió basada en diccionari utilitza un concepte diferent. Llegeix una entrada de dades i observa per grups de símbols que apareixen en el diccionari. Si una cadena concorda, un indicador o índex al diccionari pot sortir en lloc del codi del símbol
Alguns algorismes de compressió sense pèrdues són els algorismes Lempel-Ziv que inclouen: LZ77 LZ78 LZ-W
Aquest sistema de compressió s'usa en compressors de fitxers (RAR, Gzip, bzip, zip, 7z, ARJ, LHA) i de disc, també en imatges (PNG, RLE) i en algun format d'àudio (FLAC, WAV), en vídeo és molt rar, sol ser utilitzat per a captura.