pagina |
ALGORITMI OTTIMIZZATI Pertanto si può fare l’osservazione eclatante che segue: avendo selezionato mille algoritmi di compressione (per esempio perché li si riconosce come i più efficaci è possibile costruire un algoritmo di compressione che, a meno di tre caratteri, agisce altrettanto bene su tutto il testo T di quello che realizza, per T, il migliore dei mille algoritmi di compressione selezionati. Questo algoritmo S che sintetizza i 1000 altri funziona come segue. Quando gli si sottopone un testo T, prova i 1000 algoritmi di compressione C(1), C(2), … C (1000) e ripete quello che da il miglior risultato per la compressione di T. Immaginiamo che sia C(358) l'algoritmo che ha dato il testo compresso T’. L’algoritmo di sintesi S propone il testo complesso 358 T’ (T’ preceduto dal numero 358) che non ha che tre caratteri di più di quello proposto dal migliore algoritmo per T. L’algoritmo di decompressione associato a S è facile da descrivere: legge l'intestazione, 358, poi decomprime T’ utilizzando il decompressone associato a C(358). Notiamo che, dal punto di vista pratico, questo metodo per sintetizzare algoritmi di compressione non è molto ragionevole (soprattutto utilizzando 1000 algoritmi o più): da una parte la lunghezza dell’algoritmo S è circa la |
somma delle lunghezze degli algoritmi sintetizzati, e d'altra parte S funziona, per la compressione, in un tempo che è la somma dei tempi di funzionamento degli algoritmi sintetizzati (per la decompressione al contrario S è molto efficace). Riguardo la ricerca dell'algoritmo di compressione ottimale il risultato seguente è molto interessante: esiste una funzione opti di compressione che è altrettanto buona a meno di una costante c, di qualunque altro algoritmo di compressione. Questa funzione di compressione opti, quando i testi da comprimere sono molto lunghi, economizzerà almeno la stessa percentuale di testo (la costante c. per i testi lunghi è trascurabile) di qualunque algoritmo di compressione immaginabile. La funzione opti è dunque una funzione di compressione ottimale che ottiene, per l'infinità degli algoritmi di compressione possibili, ciò che l’algoritmo di sintesi di prima otteneva per mille algoritmi. Disgraziatamente la funzione di compressione opti non è calcolabile, ovvero non è programmabile. Esiste sicuramente un tale oggetto matematico, ma non si possono costruire dei programmi che la calcolino. Fortunatamente si dimostra anche che opti è approssimabile (per esempio da algoritmi che sintetizzano un numero sempre maggiore di algoritmi). Tutto ciò costituisce una buona ragione per credere che il problema della compressione è un problema che si svilupperà indefinitivamente. |
|
Compressione a partire dalle regolarità statistiche |
|
Immaginiamo di sapere che un testo composto da "0" e "1" possiede la proprietà statistica seguente. La sequenza "00" appare con la probabilità 1/2 (al posto di 1/4 se c'è equiprobabilità di simboli) "01" appare con la probabilità 1/4; "11" appare con probabilità 1/8. |
Mostriamo che questo codice fa risparmiare spazio chiedendoci come diviene un messaggio di 2000 bit (1000 coppie di bit). La metà circa delle coppie (500) sono dei "00" che sono codificate "0" e prendono dunque 500 bit circa. Un quarto delle coppie (250) sono dei "01" che sono codificate con "10" e prendono 500 bit. Un ottavo dellle coppie (125) sono dei "11" che sono codificate con "111" e prendono 375 bit. Un ottavo dellle coppie (125) sono dei "10" che sono codificate con "110" e prendono 375 bit. Il messaggio che inizialmente occupava 2000 bit, è diventato un messaggio di 500+500+375+375=1750 bit. |
pagina |