[Sify]Cellula Automata, LossLess compression
Salve a tutti,
premetto che sono molto appassionato di informatica\matematica, ma non frequento ancora l'università, quindi non sono un esperto. Ieri mi è venuta un'idea che non so giudicare, l'idea di usare la cellula automata per la compressione lossless dei dati, in questo modo:
Avendo una sequenza di bit (lunga) da comprimere, dividerla in sub-sequenze con la stessa dimensione. Prendere la sub-sequenza iniziale e considerarla come lo stato iniziale di una cellula automata (di dimensioni da decidere). Sviluppare una regola, tramite un algoritmo genetico, che permetta alla cellula automata, partendo dalla sub-sequenza iniziale, di evolvere in tutte le altre sub-sequenze nel minor tempo possibile (con il minor numero di stati necessari).
Quindi la sequenza compressa dovrà contenere soltanto:
1) La regola della cellula automata
2) La prima sub-sequenza
3) una sequenza di numeri che serve al processo di decompressione per sapere quanti stati saltare(per giungere allo stato utile successivo).
Così, a prima vista, che ne pensate? E' un approccio troppo ingenuo?
PS: Un approccio simile sarebbe interessante (e forse ancora più efficiente) per la compressione lossy.
premetto che sono molto appassionato di informatica\matematica, ma non frequento ancora l'università, quindi non sono un esperto. Ieri mi è venuta un'idea che non so giudicare, l'idea di usare la cellula automata per la compressione lossless dei dati, in questo modo:
Avendo una sequenza di bit (lunga) da comprimere, dividerla in sub-sequenze con la stessa dimensione. Prendere la sub-sequenza iniziale e considerarla come lo stato iniziale di una cellula automata (di dimensioni da decidere). Sviluppare una regola, tramite un algoritmo genetico, che permetta alla cellula automata, partendo dalla sub-sequenza iniziale, di evolvere in tutte le altre sub-sequenze nel minor tempo possibile (con il minor numero di stati necessari).
Quindi la sequenza compressa dovrà contenere soltanto:
1) La regola della cellula automata
2) La prima sub-sequenza
3) una sequenza di numeri che serve al processo di decompressione per sapere quanti stati saltare(per giungere allo stato utile successivo).
Così, a prima vista, che ne pensate? E' un approccio troppo ingenuo?
PS: Un approccio simile sarebbe interessante (e forse ancora più efficiente) per la compressione lossy.
Risposte
Compressione e algoritmo genetico sono, ritengo, piuttosto incompatibili. Quando vuoi comprimere vuoi che la tua operazione sia reversibile in modo rapido e deterministico. Inoltre maggiore incertezza si crea al metodo di compressione, maggiori informazioni è necessario aggiungere per permettere la decompressione. Quindi verosimilmente stai proponendo un metodo di compressione che è lentissimo e probabilmente neanche particolarmente efficace.
I metodi di compressione, specialmente quelli lossless usano spesso due cose: informazioni sull'oggetto da comprimere e una teoria statistica molto avanzata. Senza usare le prime esistono dei limiti ben precisi su quanto si possa comprimere un oggetto ed esistono algoritmi che sono abbastanza ottimali. Detto questo, è possibile immagino usare dei metodi genetici per identificare features dell'oggetto (come per esempio il movimento nei video).
Io non sono un esperto del settore, comunque non penso che sia possibile occuparsi di compressione e dire qualcosa di nuovo senza una preparazione adeguata.
I metodi di compressione, specialmente quelli lossless usano spesso due cose: informazioni sull'oggetto da comprimere e una teoria statistica molto avanzata. Senza usare le prime esistono dei limiti ben precisi su quanto si possa comprimere un oggetto ed esistono algoritmi che sono abbastanza ottimali. Detto questo, è possibile immagino usare dei metodi genetici per identificare features dell'oggetto (come per esempio il movimento nei video).
Io non sono un esperto del settore, comunque non penso che sia possibile occuparsi di compressione e dire qualcosa di nuovo senza una preparazione adeguata.
"vict85":
Io non sono un esperto del settore, comunque non penso che sia possibile occuparsi di compressione e dire qualcosa di nuovo senza una preparazione adeguata.
Peccato... Volevo scriverci un articolo sopra e vincere il premio Turing
Ci sono due principali problemi del tuo metodo:
1. Non mi sembra che la compressione possa essere sempre possibile e i tempi di compressione potrebbero essere molto lunghi. Non c'è infatti alcuna garanzia che ci sia una successione di trasformazioni che riesca a generare tutto il file in tempi ragionevoli. Inoltre il metodo di ricerca richiede di analizzare l'intero file in blocco per poter confrontare le diverse regole. Lavorare su tutto il file potrebbe non essere pratico o addirittura fattibile. Lavorare in parti del file separatamente potrebbe aiutare ma il problema non scompare del tutto.
2. La distribuzione statistica dei valori di un file generico non si adatta particolarmente alla struttura di un processo di questo tipo.
3. Il tempo di decompressione dipende dalla capacità della cellular automata di rappresentare il contenuto del file e quindi essere molto veloce o estremamente lento.
Con questo non voglio dire che non sia possibile usare dei cellular automata per la compressione in qualche modo (è possibile che qualcuno ci abbia anche già provato), ma non penso che il tuo metodo sia particolarmente fattibile. Se ti interessa il mondo della compressione ti consiglio di metterti a studiare i metodi esistenti e la teoria alla loro base. Molti metodi sono abbastanza semplici. Puoi per esempio iniziare a vedere cose come LZ77 e varianti successive, la codifica di Huffman, arithmetic coding, bzip2 con la trasformata di Burrows-Wheeler.. Ci sono poi ovviamente anche i formati di compressioni specifici per alcuni tipi di dati come le immagini o l'audio. Esiste insomma un mondo.
Lo stesso discorso vale se vuoi approfondire le cellular automata anche se in questo caso non ti saprei aiutare più di tanto.
1. Non mi sembra che la compressione possa essere sempre possibile e i tempi di compressione potrebbero essere molto lunghi. Non c'è infatti alcuna garanzia che ci sia una successione di trasformazioni che riesca a generare tutto il file in tempi ragionevoli. Inoltre il metodo di ricerca richiede di analizzare l'intero file in blocco per poter confrontare le diverse regole. Lavorare su tutto il file potrebbe non essere pratico o addirittura fattibile. Lavorare in parti del file separatamente potrebbe aiutare ma il problema non scompare del tutto.
2. La distribuzione statistica dei valori di un file generico non si adatta particolarmente alla struttura di un processo di questo tipo.
3. Il tempo di decompressione dipende dalla capacità della cellular automata di rappresentare il contenuto del file e quindi essere molto veloce o estremamente lento.
Con questo non voglio dire che non sia possibile usare dei cellular automata per la compressione in qualche modo (è possibile che qualcuno ci abbia anche già provato), ma non penso che il tuo metodo sia particolarmente fattibile. Se ti interessa il mondo della compressione ti consiglio di metterti a studiare i metodi esistenti e la teoria alla loro base. Molti metodi sono abbastanza semplici. Puoi per esempio iniziare a vedere cose come LZ77 e varianti successive, la codifica di Huffman, arithmetic coding, bzip2 con la trasformata di Burrows-Wheeler.. Ci sono poi ovviamente anche i formati di compressioni specifici per alcuni tipi di dati come le immagini o l'audio. Esiste insomma un mondo.
Lo stesso discorso vale se vuoi approfondire le cellular automata anche se in questo caso non ti saprei aiutare più di tanto.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo