Qual è il concetto alla base della compressione zip? Posso capire il concetto di rimuovere lo spazio vuoto ecc., Ma presumibilmente qualcosa deve essere aggiunto per dire quanto/dove lo spazio libero deve essere aggiunto di nuovo durante la decompressione?Qual è il concetto alla base della compressione zip?
Qual è il processo di base per la compressione di un flusso di byte?
Un buon punto di partenza sarebbe la ricerca dello schema di compressione Huffman. L'idea alla base di huffman è che in un determinato file alcuni byte appaiono più frequentemente di altri (in un file di testo in chiaro molti byte non appariranno affatto). Piuttosto, spendi 8 bit per codificare ogni byte, perché non utilizzare una sequenza di bit più breve per codificare i caratteri più comuni e sequenze più lunghe per codificare i caratteri meno comuni (queste sequenze sono determinate creando un albero di huffman).
Una volta che hai imparato a usare questi alberi per codificare/decodificare i file in base alla frequenza dei caratteri, immagina di iniziare a lavorare sulla frequenza delle parole - invece di codificare "loro" come una sequenza di 4 caratteri, perché non considerarlo essere un singolo personaggio a causa della sua frequenza, permettendogli di assegnargli la propria foglia nell'albero degli huffman. Questo è più o meno la base di ZIP e altra compressione di tipo lossless: cercano le "parole" comuni (sequenze di byte) in un file (incluse sequenze di 1 solo byte se abbastanza comuni) e usano un albero per codificarle. Il file zip deve quindi includere solo le informazioni sull'albero (una copia di ciascuna sequenza e il numero di volte in cui appare) per consentire la ricostruzione dell'albero e la decodifica del resto del file.
Follow up:
Per rispondere meglio alla domanda iniziale, l'idea alla base di compressione senza perdita di dati, non è tanto quello di rimuovere lo spazio vuoto, ma per rimuovere redundent informazioni.
Se hai creato un database per archiviare i testi musicali, potresti trovare molto spazio per memorizzare il coro che si ripete più volte. Invece di usare tutto quello spazio, potresti semplicemente posizionare la parola CHORUS prima della prima istanza delle linee di chorus, e poi ogni volta che il chorus deve essere ripetuto, usa CHORUS come segnaposto (in realtà è più o meno l'idea dietro la compressione LZW - in LZW ogni riga della canzone dovrebbe avere un numero mostrato prima.Se una riga si ripete più avanti nella canzone, invece di scrivere l'intera riga viene mostrato solo il numero)
Ottimo modo per fornire un riassunto della risposta con collegamenti a ulteriori letture piuttosto che semplicemente inviando l'OP a wiki/google. – EBGreen
Un'altra compressione di base è probabilmente la compressione RLE, ma non spiega molto sui tipi più avanzati. –
Come risorsa aggiuntiva, è possibile aggiungere un collegamento o menzionare Security Now! podcast. Nell'episodio # 205, Steve Gibson parla della teoria della compersione e di come si è evoluta nel tempo. Ecco un link alla trascrizione: http://www.grc.com/sn/sn-205.txt – EBGreen
Il concetto tra compressione è fondamentalmente statistico. Se hai una serie di byte, la possibilità che il byte N sia X in pratica dipende dalla distribuzione del valore dei byte precedenti 0..N-1. Senza compressione, si assegnano 8 bit per ogni possibile valore X. Con la compressione, la quantità di byte allocati per ciascun valore X dipende dalla probabilità p (N, X) stimata.
Ad esempio, data una sequenza "aaaa", un algoritmo di compressione può assegnare un valore alto a p (5, a) e valori inferiori a p (5, b). Quando p (X) è alto, la bitstring assegnata a X sarà breve, quando p (X) è basso viene utilizzato un lungo bitstring. In questo modo, se p (N, X) è una buona stima, allora la bitstring media sarà più breve di 8 bit.
Il concetto di base è che anziché utilizzare otto bit per rappresentare ciascun byte, si utilizzano rappresentazioni più brevi per byte o sequenze di byte con frequenza più frequente.
Per esempio, se il file è costituito esclusivamente della 0x41 byte (A) ripetute sedici volte, poi invece di rappresentare come la sequenza di 8-bit 01000001 accorciarlo alla sequenza 1 bit 0. Quindi il file può essere rappresentato da 0000000000000000 (sedici 0 s).Quindi il file del byte 0x41 ripetuto sedici volte può essere rappresentato dal file costituito dal byte 0x00 ripetuto due volte.
Quindi quello che abbiamo qui è che per questo file (0x41 ripetuto sedici volte) i bit 01000001 non trasmettere tutte le informazioni supplementari sopra il bit 0. Quindi, in questo caso, gettiamo via i bit estranei per ottenere una rappresentazione più breve.
Questa è l'idea alla base della compressione.
Come altro esempio, si consideri il modello otto byte
0x41 0x42 0x43 0x44 0x45 0x46 0x47 0x48
e ora ripeterlo 2048 volte. Un modo per seguire l'approccio sopra è rappresentare i byte usando tre bit.
000 0x41
001 0x42
010 0x43
011 0x44
100 0x45
101 0x46
110 0x47
111 0x48
Ora possiamo rappresentare il modello di byte di cui sopra da 00000101 00111001 01110111 (questo è il modello a tre byte 0x05 0x39 0x77) ripetuto 2048 volte.
Ma un approccio ancora migliore è quello di rappresentare il modello di byte
0x41 0x42 0x43 0x44 0x45 0x46 0x47 0x48
dal singolo bit 0. Quindi possiamo rappresentare il modello di byte sopra per 0 ripetuto 2048 volte che diventa il byte 0x00 ripetuto 256 volte. Ora abbiamo solo bisogno di memorizzare il dizionario
0 -> 0x41 0x42 0x43 0x44 0x45 0x46 0x47 0x48
e il modello di byte 0x00 ripetuto 256 volte e abbiamo di compressione del file da 16.384 byte (Modulo dizionario) 256 byte.
Che, in poche parole, è come funziona la compressione. L'intera attività si riduce alla ricerca di rappresentazioni brevi ed efficienti dei byte e delle sequenze di byte in un determinato file. Questa è l'idea semplice, ma i dettagli (trovare la rappresentazione) possono essere abbastanza impegnativi.
Vedi per esempio:
Sembra a me come avete bisogno di andare a wikip edia e fai un po 'di lettura. – skaffman
Facile! Converti in binario e rimuovi gli zeri –
http://www.howstuffworks.com/file-compression.htm –