Come devo comprimere un file con più byte uguali a quelli di Huffman?

Naviga le tue risposte
1

Sulla mia grande ricerca per la compressione / decompressione di file con un'implementazione Java della codifica di Huffman ( link ) per un incarico scolastico , Ora sono al punto di creare un elenco di codici prefisso . Tali codici vengono utilizzati durante la decompressione di un file. Fondamentalmente, il codice è composto da zero e uno, che sono usati per seguire un percorso in un albero di Huffman (a sinistra oa destra) per, in definitiva, trovare un byte.

In questa immagine di Wikipedia, per raggiungere il carattere m il codice prefisso sarebbe 0111

L'ideaèchequandocomprimiilfile,inpraticaconvertituttiibytedelfileinprefissi(tendonoadesserepiùpiccolidi8bit,quindic'èunguadagno).

Quindiognivoltacheilcaratteremappareinunfile(cheinbinarioèinrealtà1101101),saràsostituitoda0111(seabbiamousatol'alberosopra).

Pertanto,1101101110110111011011101101diventa0111011101110111nelfilecompresso.

Stobeneconquello.Macosasuccedesesuccede:

  • Nelfiledacomprimereesisteunsolobyteunivoco,adesempio1101101.
  • Cisono1000ditalebyte.

Tecnicamente,ilcodiceprefissoditalebytesarebbe...nessuno,perchénonc'èalcunpercorsodaseguire,giusto?Vogliodire,esistecomunqueunsolouniquebyte,quindil'alberohaunsolonodo.

Pertanto,seilcodiceprefissoènessuno,nonsareiingradodiscrivereilcodiceprefissonelfilecompresso,perché,beh,nonc'ènientedascrivere.

Cheportaquestoproblema:comecomprimere/decomprimeretalefileseèimpossibilescrivereuncodiceprefissodurantelacompressione?(usandolacodificadiHuffman,acausadelleregolediassegnazionedellascuola)

Questotutorialsembraspiegareunpo'meglioicodiciprefisso: link ma non sembra affrontare anche questo problema.

    
posta Omega 22.11.2012 - 01:30
fonte

1 risposta

2

In realtà useresti la codifica run-length in una situazione del genere. In sostanza, memorizzi il simbolo e il numero di ripetizioni.

Tuttavia, se continui ad insistere sull'uso della codifica di Huffman, puoi scegliere uno o zero per rappresentare il simbolo nell'albero. Questo non causa alcun problema. Il tuo albero afferma semplicemente che il simbolo x è rappresentato dal bit m . Quindi hai n numero di ripetizioni del m codificato come dati. Potresti anche applicare RLE sopra riportato sui dati effettivi (che è essenzialmente una corsa di bit uguali di lunghezza n ) per comprimere ulteriormente.

    
risposta data 22.11.2012 - 01:33
fonte

Leggi altre domande sui tag

Quale telecamera scegliere per l'utilizzo con JMF (Java Media Framework) Esiste un modo migliore per gestire l'astrazione dei dati in questo esempio?