Lunghezza della parola più breve della codifica di Huffman
-
05-11-2019 - |
Domanda
Sotto la codifica di Huffman, se un carattere si verifica più di 1/3 del tempo, è garantito che ci sarà almeno un carattere la cui parola codifica è di lunghezza 1?
Ho pensato a 2 casi in cui questo potrebbe essere vero, ma non sono esattamente prove -
Caso 1: esiste un solo carattere che si verifica più di 1/3 del tempo. In questo caso, un buon schema di codifica Huffman garantirà che questo personaggio corrisponda a una codifica a singolo carattere, perché non ci sono caratteri concorrenti. Anche se potrebbero esserci caratteri che si verificano con elevata probabilità (ma ancora meno di 0,33), devono avere una lunghezza maggiore di 1 per garantire la natura priva di prefisso della codifica.
Caso 2: ci sono più caratteri che si verificano più del 33% delle volte. Possiamo anche fare l'affermazione più forte che in questo caso può esserci solo al massimo 2 di questi personaggi. Ciò può essere ulteriormente suddiviso in casi in cui 1) ci sono un totale di 2 caratteri nello schema di codifica e 2) in cui ci sono più di 2 caratteri nello schema. Nel caso 1), entrambi i caratteri possono corrispondere a uno schema di codifica a singolo carattere (0 e 1 rispettivamente per ciascuno). Nel caso 2), al massimo 1 dei 2 caratteri in gran parte prevalenti/frequenti devono avere una codifica di lunghezza 1 (poiché stiamo prendendo in considerazione un buon schema di codifica Huffman) mentre gli altri caratteri N-1 hanno una lunghezza di almeno 2 .
Temo che questo non sia l'approccio giusto. Per favore qualcuno potrebbe aiutarmi?
Nessuna soluzione corretta