Visualizzazioni Totali

TRA I PRIMI IN ITALIA A PARLARE DI BITCOIN (DAL 2012!): PER ESSERE SEMPRE AGGIORNATI SULLE NOVITA' TECNOLOGICHE DEL WEB SEGUITE LA PAGINA FACEBOOK (LINK A SINISTRA)

lunedì 19 settembre 2016

E' Possibile La "Lossless Recursive Compression Of Random Data"?

Nel 2012 Constant Wong e una compagnia cinese annunciò la creazione della "Lossless Recursive Compression Of Random Data", 8 anni di fatica per sviluppare una tecnologia di compressione ricorsiva senza perdita di dati.
Tale tecnologia, per i dati random, è sempre stata considerata impossibile da raggiungere.
Infatti è possibile applicare lo stesso algoritmo di compressione più volte ma aspettarsi di continuare a ridurre le dimensioni dei dati è sempre stata considerata una cosa impossibile da raggiungere.
Anzi dopo 1 compressione, rieseguendola, potrebbe verificarsi un aumento delle dimensioni del file.
Questo è prevedibile.
Se un dato algoritmo Lossless potrebbe produrre più compressioni di dati con lo stesso metodo e senza perdita d'informazioni, probabilmente avrebbe fatto ciò la prima volta che viene eseguito (e non in modo ricorsivo).
Dunque applicando nuovamente lo stesso metodo per i dati compressi è in teoria impossibile produrre un'ulteriore riduzione delle dimensioni.
Quello che invece si può fare è la combinazione di più algoritmi di compressione diversi.
Ad esempio, LZ77 si combina bene con la codifica di Huffman.
La fattibilità di diverse compressioni dipende dalla "profondità" del files (cioè dalla dimensione minima che è possibile raggiungere) e dall'algoritmo utilizzato.
Quindi in poche parole, non è possibile: comprimere dati Random e in modo ricorsivo con lo stesso algoritmo.
La fantomatica Lossless Recursive Compression invece è in grado di comprimere dati random o discreti, più volte, senza alcuna perdita di qualità.
In altre parole, dopo la compressione dei file, essi riducono la loro dimensione ma non la forma originale.
Come detto prima tendenzialmente un file una volta compresso, non può essere ulteriormente compresso con la stessa tecnologia perchè non è più lo stesso tipo di file: è diventato random.
Pertanto, se con ciò si possono comprimere dati random, lo si può fare più volte.
La compagnia spiegò di aver raggiunto questo, tramite teoremi matematici con serie di progressione geometriche.
Wong sottolineò che uno degli aspetti più innovativi della tecnologia è che poteva comprimere e decomprimere i dati digitali in tempo reale.
Questo sarebbe stato fondamentale per l'implementazione di streaming video, broadcasting e telecomunicazioni.
Questa tecnologia avrebbe risolto anche sovraccarichi di rete consentendo inoltre di migliorare la capacità delle strutture di storage e limitando i consumi energetici.


FUNZIONAMENTO E TEOREMA DI SHANNON (SOURCE CODING THEOREM)
Se due file sono compressi con la tecnologia di compressione ricorsiva, anche se solo un bit venisse compresso dopo ogni passaggio, potrebbero essere entrambi ridotti a un singolo 0 o 1.
Come potrebbero essere quindi decodificati se questo stesso bit origina due files diversi?
Questo secondo gli sviluppatori non accade perché dopo che un file subisce un gran numero di passaggi di compressione, raggiungerà l'optimum, rendendo gli ulteriori passaggi trascurabili.
Inoltre, anche nel caso che due files diventino esattamente uguali al loro "optimum" per pura coincidenza, i files decompressi saranno sicuramente diversi, perché i due files son passati attraverso un diverso numero di passaggi per raggiungere lo stesso "optimum".
Il Teorema di Shannon afferma che se due files differenti possono entrambi essere compressi in modo ricorsivo ad essere ricondotti ad un singolo 0, come si potrebbe decodificare il singolo 0 originando due file diversi?
Lo stesso Teorema stabilisce dei limiti di massima compressione per quanto riguarda un insieme di dati e definisce il significato operativo dell'entropia.
Il teorema dice che, per una serie di variabili aleatorie indipendenti di lunghezza che tende ad infinito, non è possibile comprimere i dati in un messaggio più corto dell'entropia totale senza perdita di informazione.
Al contrario, compressioni arbitrariamente vicine al valore di entropia sono possibili, con probabilità di piccole perdite d'informazione (casuale).
Esiste un limite inferiore e superiore alla minima lunghezza attesa di una serie di parole di codice, in funzione dell'entropia della parola in ingresso (vista come una variabile aleatoria) e della dimensione dell'alfabeto in esame.
Secondo il team cinese invece, se un file è passato attraverso quattro passaggi per diventare un singolo 0 e un altro file è passato attraverso cinque passi per diventare la stessa cosa, decodificando i singoli 0 quattro volte (ripristinando il file originale di 16 0's) e cinque volte (file originale di 32 0's) si avranno due file completamente diversi (decodificati dallo stesso singolo 0!).
Questa tecnologia comprime files sostituendo stringhe di bit e rendendoli più brevi (9 bit).
Poi se molti file possono essere compressi in modo ricorsivo per diventare file a 8 bit, ci saranno 256 files diversi compressi, e ciascuno può essere decodificato attraverso diversi passaggi, con conseguente creazione d' infiniti files differenti.
Ovviamente non tutte le stringhe di 8 bit possono essere sostituiti da stringhe, questo è ciò che il team intendeva quando parlava di "optimum", ovvero un file che non può essere compresso ulteriormente, in quanto non può più essere sostituito da un segnale/stringa.
Tutto molto interessante, peccato che il Loseless Recursive Compression, al pari della compressione I2BP, rimarrà uno dei più grandi misteri (e forse bluff) dell'informatica recente.


ALTRI ARTICOLI
Tutti I Codec e Formati Audio Di Compressione
Tutti I Codec e Formati Video Di Compressione
Differenze Tra Compressione Lossy e Lossless: Vantaggi e Svantaggi
La Storia Di Jan Sloot e Il Misterioso Sloot Digital Coding System
Il Mistero Della Compressione Video I2BP: Idea Rivoluzionaria o Bluff? (2001)

Nessun commento:

Posta un commento