La nascita dei sistemi di compressione (senza perdita, lossless compression) si può far risalire addirittura al 1838, con il Codice Morse. Infatti Samuel Morse, nel suo famoso codice, applicò un semplice processo di riduzione della lunghezza delle informazioni trasmesse:
sostituire ai caratteri che appaiono con frequenza maggiore un codice composto da un numero inferiore di simboli, in modo da risparmiare spazio nella codifica
Codice Morse
Morse decise che le lettere a frequenza maggiore fossero rappresentate da codici più piccoli mentre quelle meno usate con dei codici più lunghi:
- e = ·
- a = · -
- q = - - ·-
- j = ·- - -
Gli studi sui sistemi di compressione come li conosciamo oggi, invece, cominciano negli anni ’40 con lo sviluppo della Teoria dell’Informazione. Nel 1949 Claude Shannon e Robert Fano presentano un metodo per assegnare codici pre-definiti (statici) a blocchi di testo, basandosi sulla probabilità che essi ripetano: nasce la Compressione Statistica. La scelta dei codici avviene su base statistica derivata della tipologia dei dati trattati, in modo da massimizzare il risultato della compressione.
Shannon e Fano
La tecnica viene migliorata da David Huffman nel 1951, permettendo di stabilire i codici analizzando il testo (file) che si sta comprimendo invece che operare su base statistica. In pratica l’algoritmo di Huffman stila dinamicamente un elenco delle volte in cui nel file analizzato compaiono ripetuti i diversi simboli e, successivamente, crea una sorta di vocabolario che associa ad ogni simbolo un numero sulla base della classifica redatta. Il tutto viene tradotto con questa codifica, creando così un alfabeto ridotto capace di dare le stesse informazioni con un numero minore di caratteri.
Le prime applicazioni pratiche vengono realizzate direttamente in hardware, con codici di compressione statici in modo da stimare il livello di compressione atteso.
Nel 1977 Abraham Lempel e Jacob Ziv, introducono la tecnica di codifica “pointer-based” (algoritmo LZ): questa soluzione si basa sull'idea di sostituire occorrenze di stringhe ripetute con puntatori a precedenti copie.
A fine anni ’70, con la possibilità di storage diretto dei file (floppy e primissimi hard disk), cominciano ad essere sviluppati i primi software di compressione, basati proprio sulla soluzione “adattativa” proposta da Huffman.
Abraham Lempel e Jacob Ziv
Nella metà degli anni ’80 (1984), Terry Welch crea l’algoritmo LZW (Lempel-Ziv-Welch), che sfrutta la versione LZ78 dell’algoritmo sviluppato da Lempel e Ziv, diventando decisamente popolare soprattutto nel mondo Unix.
Nel 1982 James Storer e Thomas Szymanski creano una variante dell’LZ77 conosciuta come LZSS, che, a differenza dell’algoritmo originale, non presenta i problemi intrinseci di ridondanza (esempio: puntatore nullo). Tale algoritmo è alla base di quello che oggi è forse il compressore più apprezzato, ovvero WinRAR, e del relativo formato di compressione RAR, presentato ufficialmente nel 1993.
Pochi anni primi, nel 1991, PKWARE rende pubbliche le specifiche della propria variante dell’LZ77, chiamandola “Deflate”. La società fondata da Phillip W. Katz sviluppa “Deflate” come base per il proprio PKZIP ed il relativo formato ZIP la cui specifica tecnica viene tenuta periodicamente aggiornata e pubblicata (RFC 1951).
Phillip W. Katz
Il formato ZIP si impone velocemente come nuovo standard-de-facto, relegando il precedente LZW soprattutto come motore di compressione per i formati grafici GIF e TIFF (proprio nella variante senza perdita di qualità).
Per dovere di cronaca bisogna ricordare che Katz non ha mai saputo sfruttare commercialmente il “Deflate” e, agli inizi del 2000, viene trovato morto per abuso di alcool a soli 37 anni, tra l’altro in uno stato di semi-povertà, nonostante la sua intuizione abbia avuto un ruolo fondamentale per il progresso dell’informatica.