[zxspectrum] Re: Loader huffman a 4 valori: tentativo #9
- From: Paolo Ferraris <pieffe8@xxxxxxxxx>
- To: zxspectrum@xxxxxxxxxxxxx
- Date: Fri, 29 Mar 2013 20:02:59 -0700
On 3/29/2013 1:47 AM, Antonio S. wrote:
Grazie Paolo.
Non ho capito una cosa del tuo loader: dei quattro valori, due hanno
durata doppia rispetto agli altri, il che mi sembra non sia previsto
dalla codifica di H. Il risultato è + o - efficiente di una codifica
H. a due valori, e perché?
Dal punto di vista teorica il mio loader e` sicuramente non meno
efficiente, dato che puo` caricare tranquillamente un albero di Huffman
a due valori. Infatti con il mio loader ogni nodo non terminale
dell'albero puo` avere dai 2 ai 4 figli.
Il fatto che possa essere piu` efficiente si puo` vedere per esempio se
vuoi codificare la
stringa
ABCD.
Con Huffman tradizionale avresti un albero bilanciato a due livelli,
cioe` con due bit per simbolo ed un totale di 8 bit per la stringa intera.
Nel caso di 4 valori un livello e` sufficiente, anche se per due dei
quattro simboli la durata e` doppia. In totale la durata della codifica
e` 6 "bits", con un risparmio del 25% rispetto all'Huffman tradizionale.
Inoltre si posso associare simboli piu` ricorrenti ai segnali piu`
corti. Per esempio in
AABBCD
sia A che B avrebbero durata 1, e C e D durata 2. La durata totale e` 8,
contro i 12 dell'Huffman tradizionale (risparmio del 33%).
Dire fino a quanto sia piu` efficiente e` una domanda difficile, perche`
non credo che - a differenza dell'Huffman tradizionale - si possa
trovare l'albero ottimale in tempo polinomiale. Per Manic Miner sono
riuscito ad ottenere un risparmio sui tempi di caricamento del 30%, (con
circa 3/4 dei nodi a quattro figli) ma onestamente non so quanto di
meglio si possa ottenere.
Comunque ho un'idea che renderebbe tutto quello che ho detto obsoleto,
ottenendo 4 valori nella stessa unita` di tempo. Ma prima voglio
risolvere i problemi con il loader che ho adesso.
-p
Other related posts:
