Algoritmi - Algoritmo di ordinamento e compressione

Forum - Algoritmi - Algoritmo di ordinamento e compressione

Pagine: [ 1 2 ]

TheDarkJuster (Member)
Guru^2

Messaggi: 1620
Iscritto: 27/09/2013

Postato alle 16:53
Domenica, 01/02/2015

Io ho pensato ad un algoritmo di compressione (che forse non coprime ma espande, non saprei, dipende....)

Io pensavo di ordinare i dati con un algoritmo di compressione che effettui MENO SCAMBI POSSIBILI e poi di memorizzare il risultato come
<byte><2byte>

con <byte> che è il byte e <2byte> che è il numero di volte che un byte si ripete (2byte è a 16-bit). Una volta ottenuto questo output dal file si salva prima una lista degli scambi effettuati e poi l'output dell'ordinamento/compressione.

Per decomprimere si ri-espande tutte le sequenze di <byte><2byte> e si ripercorrono gli sbambi al contrario, così da ri-avere la sequenza originale.

Ora, io chiedo: quanto è efficente questo algoritmo (inteso come compressione)? Che algoritmo di sorting dovrei usare (quello che esegue meno scambi)? quanto sarebbe performante la DECOMPRESSIONE? e quanto la decompressione? Ho re-inventato l'acqua calda(sicuramente si, ma intanto io chiedo, visto che non so con che nome è chiamato questo algoritmo)? Quanto sarebbe performante la COMPRESSIONE (questo è il fattore che mi interessa meno)?

Non sarebbe un algoritmo tanto difficile da implementare, e per ciò che sto facendo se la decompressione fosse veloce e il ratio di compressione abbastanza buono sarebbe il top....

pierotofy (Admin)
Guru^2

Messaggi: 6230
Iscritto: 04/12/2003

Postato alle 17:01
Domenica, 01/02/2015

Implementalo e fai qualche benchmark. :k:

Il mio blog: https://piero.dev

TheDarkJuster (Member)
Guru^2

Messaggi: 1620
Iscritto: 27/09/2013

Postato alle 17:46
Domenica, 01/02/2015

Io non so calcolare la complessità di un algoritmo, qualcuno può dirmi qualcosa? O almeno qual'è l'algoritmo di ordinamento che esegue meno scambi?

Ultimo (Member)
Guru

Messaggi: 877
Iscritto: 22/05/2010

Postato alle 19:45
Domenica, 01/02/2015

credo che sia il Quicksort che effettua meno scambi

If ok Then GOTO Avanza else GOTO Inizia

Roby94 (Member)
Guru

Messaggi: 1170
Iscritto: 28/12/2009

Postato alle 20:10
Domenica, 01/02/2015

Testo quotato

Postato originariamente da TheDarkJuster: se la decompressione fosse veloce e il ratio di compressione abbastanza buono sarebbe il top....

Secondo me queste due affermazioni cozzano un po', è vero che si possono ottenere algoritmi sia veloci che preformanti dal punto di vista della compressione, ma se si vuole massimizzare uno dei due parametri bisognerebbe essere disposti a sacrificare in parte o totalmente l'altro, e sottolineo disposti e non costretti!
Comunque prova ad implementarlo e facci sapere il risultato di qualche test.

TheDarkJuster (Member)
Guru^2

Messaggi: 1620
Iscritto: 27/09/2013

Postato alle 20:14
Domenica, 01/02/2015

Sto costruendo una applicazione che ha bisogno di un tempo di decompressione eccellente, comunque con ratio di compressione abbastanza buono intendo 4/5 MB su 100MB, quello che un'altra persona reputerebbe pessimo. Forse avrei dovuto specificarlo un po' prima

TheDarkJuster (Member)
Guru^2

Messaggi: 1620
Iscritto: 27/09/2013

Postato alle 20:26
Domenica, 01/02/2015

Ah, prima che io cominci a scrivere del codice, qualcuno ha idee su come ottimizzare gli scambi? Mi spiego meglio, gli scambi che ho effettuato vanno registrati, ma memorizzarli occupa spazio, come faccio a ottimizzare il numero di scambi mantenendo il risultato finale? In pratica: il quicksort fa il MINIMO INDISPENSABILE di spostamenti sempre e comunque?

P.S. in relazione al tempo di decompressione: se ci mettesse un secondo o mezzo secondo per comprimere un MB andrebbe bene, non deve essere usato per comprimere molto spesso.

Ultima modifica effettuata da TheDarkJuster il 01/02/2015 alle 20:32

Roby94 (Member)
Guru

Messaggi: 1170
Iscritto: 28/12/2009

Postato alle 20:27
Domenica, 01/02/2015

Vedi, tutto è relativo.

Mi permetto di farti notare che la tua implementazioni nel caso peggiore puo triplicare il peso di un byte, per non parlare dell'aggiunta di peso per l'ordinamento.

Ultima modifica effettuata da Roby94 il 01/02/2015 alle 20:30

TheDarkJuster (Member)
Guru^2

Messaggi: 1620
Iscritto: 27/09/2013

Postato alle 20:37
Domenica, 01/02/2015

Devo comprimerci modelli 3D, texture, file ficrati ecc.... Quindi gli ordinamenti saranno molti ma sarà difficile non avere ripetizioni dello stesso byte.....

Pagine: [ 1 2 ]