di  -  venerdì 9 novembre 2012

Per voi il termine “compressione” è sinonimo di WinZIP o WinRAR?

Ebbene spero non resterete delusi nello scoprire che il panorama è decisamente più ampio e che possiamo far risalire la nascita dei sistemi di compressione (senza perdita, lossless compression) 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.

24 Commenti »

I commenti inseriti dai lettori di AppuntiDigitali non sono oggetto di moderazione preventiva, ma solo di eventuale filtro antispam. Qualora si ravvisi un contenuto non consono (offensivo o diffamatorio) si prega di contattare l'amministrazione di Appunti Digitali all'indirizzo info@appuntidigitali.it, specificando quale sia il commento in oggetto.

  • # 1
    Antonio Barba
     scrive: 

    Povero PK :-\

  • # 2
    Alessio
     scrive: 

    Ok aspetto il resto della storia da PKZip a 7z (e oltre)

  • # 3
    erik_ilrosso
     scrive: 

    colpa della camicia, guarda che camicina e facce per bene gli altri e che faccia da delinquente e che camicia buzzurra pk la camicia ti segna a vita, se sei insicuro su quale mettere meglio una maglia nera neutra a collo alto

  • # 4
    Michele
     scrive: 

    Voglio la storia di LHA per Amiga

  • # 5
    maumau138
     scrive: 

    James Storer, nomen omen…

  • # 6
    Cesare Di Mauro
     scrive: 

    C’è da dire che esistevano già altri compressori prima di (PK)Zip, ma è quest’ultimo che s’è imposto come standard di fatto, complice forse la veloce adozione che ha avuto nel mondo PC (e da lì, gioco forza, anche per gli altri sistemi).

    Altra cosa, deflate è stato utilizzato anche in ambito grafico. Il PNG, infatti, è basato proprio su quest’algoritmo per la compressione (lossless) dei dati (previa applicazione di un filtro di predizione per ogni riga, atto a rendere più comprimibile lo stream).

    Comunque storia molto triste quella di Katz. Non avrei mai pensato che avesse potuto fare questa brutta fine… -_-

  • # 7
    Gianluca Santilio
     scrive: 

    Da giovane, usavo un altro formato molto diffuso al tempo che si chiamava arj. Qualcun altro lo ricorda se non sbaglio era molto performante nella compressione non fosse un pò lento nell’elaborazione

  • # 8
    Marco
     scrive: 

    Ultimamente mi sono incaponito e ho voluto provare ad usare FrontPAQ v8.
    sbalorditivo il rapporto di compressione ma una lentezza tremenda.

    Oggi la compressione lossless secondo me è trascurata un pò troppo, si tende ad aumentare la banda disponibile (penso alle comunicazioni) ma si fa poco o niente per comprimere efficientemente i dati. Eppure la potenza di calcolo media è in costante crescita e lo permetterebbe sempre più.

    grazie mille per l’articolo/post

  • # 9
    Cesare Di Mauro
     scrive: 

    Credo che quello della compressione sia uno dei settori più attivi, nonostante il dominio di Zip (e in parte RAR, anch’esso abbastanza diffuso e apprezzato).

    Il fatto è che risulta molto difficile spodestare gli standard, per cui anche programmi che fanno uso di algoritmi (mediamente) più efficienti generalmente finiscono per ritagliarsi una microscopica fetta di utenza affezionata (ma soprattutto “skillata”).

    Oppure tante volte vengono tirati fuori nuovi algoritmi di compressione per gioco o per passione, perché è un campo che, penso, attira i programmatori. Solo che poi questa roba rimane chiusa nel cassetto… O:-)

    @Gianluca: arj lo ricordo. Mi sembra fosse stato creato per PC, ma poi portato anche in altre piattaforme (sicuramente l’Amiga, dove l’ho conosciuto).

    Mai usato perché su Amiga lo standard era, e rimane ancora sostanzialmente, LHA (e prima ancora LZH), anche se negli ultimi anni si fece strada LZX (poi comprato da Microsoft: il formato CAB mi pare utilizzi lo stesso algoritmo, o comunque uno derivato direttamente da esso).

  • # 10
    Giacomo
     scrive: 

    Secondo me l’esempio del codice Morse non è attinente alla compressione, quanto alla prima digitalizzazione “brain powered”, dove il punto-linea è paragonabile all’1-0 della logica binaria.

  • # 11
    Jc
     scrive: 

    Ciao Giacomo, forse non è il punto linea che indicano la compressione ma la seguente logica applicata :
    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 = ·- – –

  • # 12
    Giacomo
     scrive: 

    @ Jc
    ah grazie, ora mi è chiaro l’esempio.

  • # 13
    ddr
     scrive: 

    ARJfag here.

  • # 14
    Rosario
     scrive: 

    a proposito di arj sopra citato, è tutt’altro che morto ed usa algoritmi di compressione molto veloci (fra i più veloci) ma soprattutto molto efficienti, in sostanza credo che la diffusione di un compressore sia legata tantissimo anche a fattori modaioli e di passaparola

  • # 15
    neutrino76
     scrive: 

    In ambiente windows esisteva (esiste) un altro programma chiamato WinACE che, a conti fatti, comprimeva più dello ZIP e del RAR. Come mai non si è praticamente diffuso? Sarebbe poi fico una comparazione tra i formati per vedere quello + performante. A mio modesto parere, vinceva questo ACE seguito a ruota da RAR e per ultimo ZIP.

  • # 16
    ddr
     scrive: 

    lo ricordo il winace…anzi è da qualche parte nell’hd…
    durante il periodo dello splitting selvaggio era sufficientemente diffuso.

  • # 17
    Massimo M
     scrive: 

    Un mio amico, Paolo Zibetti scrisse il primo compressore per Amiga. Poi un’altro “collega universitario” che purtroppo non ricordo il nome (Paolo Toccacieli?) lo accelerò aggiungendo dell’assembler al codice. Anno 1990-1992 circa
    Vennero menzionati anche su MCMicrocomputer, ai tempi (forse) rivista leader. Era LHA di cui sopra …
    Mi pare avesse preso sempre su una rivista simile l’algoritmo e lo avesse convertito in lha per Amiga, senza interfaccia video ma solo a riga di comando (senza hard disk il “workbench” non aveva tanta praticità, quindi tutto a riga di comando, unix like!)
    Ma non ricordo altro! Forse il compilatore .. Lattice C?

  • # 18
    neutrino76
     scrive: 

    e come non dimenticare LHA per AMiga? Però mi pare LHZ forniva prestazioni migliori….ovviamente tutto tramite shell….
    Cmq, non vorrei finire OT, era proprio grazie alla versatilità di Amiga che, grazie alla sua capacità di scrivere e leggere floppy in formato MS-DOS e insieme ad ARJ, riuscivo a trasferire file tra i due sistemi.

  • # 19
    KONEY
     scrive: 

    Mancherebbero delle parole a fine artikolo tipo la “a” su “abuso di alcool soli 37 anni” e “ruolo” su “intuizione abbia avuto un fondamentale”.

    e SI alla storia di LHA su Amiga ;)

  • # 20
    Cesare Di Mauro
     scrive: 

    Ma sei per caso il Koney amico di Phalanx (se hai presente Freaknet)? :D

    @Massimo M: Lattice (poi SAS) C era un compilatore molto diffuso per Amiga.

    LHA venne dopo LZH.

    Infine, sì, MC Microcomputer era LA rivista d’informatica per eccellenza, in Italia.

    @neutrino76: LHA permetteva un miglior rapporto di compressione rispetto a LZH.

    Comunque se fai una ricerca in giro trovi alcuni siti con comparazioni fra i diversi “archiviatori”.

  • # 21
    KONEY
     scrive: 

    Ehy si sono io!!

    Poi c’era LX su Amiga ke era una potenza, notevole la differenza del livello di compressione rispetto a LHA e anche la velocita’ era notevole.

  • # 22
    Mark0
     scrive: 

    Retroscena interessanti su PKZIP:

    http://blog.greggman.com/blog/arc_vs_zip__the_myth__the_legend/

    “Everyone was happy because some little guy, Phil Katz of PKZIP, showed some evil corporation SEA what for.” – Questa era la “leggenda” come mi ricordo di averla letta anche negli MC dell’epoca. Ma il video racconta una storia un po’ diversa.

    Info anche su Wikipedia:

    http://en.wikipedia.org/wiki/Phil_Katz

  • # 23
    Cesare Di Mauro
     scrive: 

    @Koney: piacere di “conoscerti”. :)

    Il programma per Amiga di cui parli non era LX, ma LZX (di cui parlato in un commento, prima).

  • # 24
    Mic
     scrive: 

    ehi
    e come non dimenticarsi del 7z ?
    e dell’algoritmo che ci sta sotto, l’LZMA ?

    http://www.maximumcompression.com/index.html
    qui ci sono i benchmark di qualsivoglia algoritmo inventato dall’uomo, per la cronaca

Scrivi un commento!

Aggiungi il commento, oppure trackback dal tuo sito.

I commenti inseriti dai lettori di AppuntiDigitali non sono oggetto di moderazione preventiva, ma solo di eventuale filtro antispam. Qualora si ravvisi un contenuto non consono (offensivo o diffamatorio) si prega di contattare l'amministrazione di Appunti Digitali all'indirizzo info@appuntidigitali.it, specificando quale sia il commento in oggetto.