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 LZ77), basato sulla sostituzione delle stringhe ripetute con riferimenti a copie precedenti nel file. Da questo lavoro derivano molte varianti: LZ78 e soprattutto LZW (Lempel-Ziv-Welch, 1984), creato da Terry Welch, che trova ampia applicazione nei sistemi Unix e nei formati grafici GIF e TIFF.

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 da Eugene Roshal.

RAR per DOS 2.06

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.

Insieme alle BBS, è proprio l’arrivo dei floppy disk, e dei primi hard disk negli anni ’80, a dare una spinta importante alla diffusione software di archiviazione, che si vanno di seguito a riepilogare:

• ARC (1985, Thom Henderson / SEA): il primo grande archiviatore “all-in-one”, unisce archiviazione e compressione, diventando lo standard delle BBS.
• ZOO (1986, Rahul Dhesi): molto usato in ambienti UNIX e Amiga, introduce la gestione delle versioni dei file in archivio.
• PAK (1988, NoGate Consulting): promette una compressione più efficiente di ARC, ma rimane confinato a una nicchia.
• ZIP (1989, Phil Katz / PKWARE): basato sull’algoritmo Deflate, diventa subito lo standard de facto grazie alla sua specifica aperta. La diffusione esplode con PKZIP su DOS e poi con WinZip su Windows. Ancora oggi è onnipresente.
• ARJ (1990, Robert Jung): apprezzato dagli utenti esperti per le sue opzioni avanzate, multi-volume e recovery records. Diffuso soprattutto sulle BBS.
• LZH / LHA (1988, Haruyasu Yoshizaki): diffusissimo in Giappone e in ambito Amiga, spesso usato nei videogiochi e nei sistemi PC-98.
• RAR (1993, Eugene Roshal): introduce recovery record più robusti, multi-volume flessibili e compressione superiore. Grazie a WinRAR, diventa il preferito dai power user e dalle community di file sharing.
• ACE (1998, Marcel Lemke / WinACE): per alcuni anni insidiò ZIP e RAR con un’ottima compressione, ma il formato chiuso e vulnerabilità successive ne decretarono il declino.
• StuffIt (.sit), su Macintosh, dagli anni ’80 fino ai primi 2000, il re fu degli ambiente Apple. Creato da Raymond Lau (1987).
• CAB (Cabinet, 1995), usato da Microsoft per distribuire Windows, Office e driver. Non è pensato per gli utenti finali, ma per i setup automatici. Ancora oggi sopravvive nei pacchetti di driver firmati.
• gzip (1992, Gailly & Adler): basato su Deflate, diventa lo standard di Internet per la compressione HTTP e per i pacchetti .tar.gz.
• bzip2 (1996, Julian Seward): usa l’algoritmo Burrows–Wheeler, ottenendo compressione superiore, ma a costo di maggiore lentezza. Diffuso nelle distribuzioni Linux (.tar.bz2).
• 7-Zip / 7z (1999, Igor Pavlov): introduce l’algoritmo LZMA, con compressione elevatissima e formato libero. 7-Zip diventa il coltellino svizzero dei compressori, capace di aprire quasi tutto.
• xz (2009, LZMA2): evoluzione moderna, oggi standard nelle distribuzioni Linux per kernel e pacchetti (.tar.xz).

Dal Codice Morse all’algoritmo di Huffman, dagli archivi ARC alle moderne suite open come 7-Zip, la storia della compressione è fatta di innovazioni continue, di guerre tra formati e di standard che nascono e muoiono in pochi anni.

Oggi convivono tre grandi filoni:

• ZIP (universale, supportato nativamente ovunque).
• RAR (potente, ma proprietario).
• Formati open come 7z, gzip, bzip2 e xz, che dominano Linux, Internet e i progetti open source.

Il filo conduttore rimane lo stesso che aveva intuito Morse: ridurre la ridondanza, rendere l’informazione più leggera, farla viaggiare più velocemente.

Un obiettivo che, a quasi due secoli di distanza, resta centrale nell’era del cloud e dei big data.