È Huffman codifica sempre ottimale?

Question

Il requisito della codifica sia prefix libero determina grandi alberi a causa dell'albero dover essere completa. Esiste una soglia in cui lunghezza fissa di memorizzazione non codificato dei dati sarebbe più efficiente di codifica dei dati?

Answer 1

Il H(A) entropia per questo problema è 1.998. Sia codifica di Huffman e lunghezza fissa che codifica per questo problema ha lunghezza codeword medio come 2. E FYI la codifica che avete ottenuto utilizzando Huffman codifica è sbagliata. Huffman Codifica produce anche codici simili ai lunghezza fissa per questo problema. Esso utilizza approccio avidi. Quindi a non ottiene un codice come 0 ma invece diventa 00. Rework sull'albero si genera utilizzando codifica di Huffman. L'albero si dovrebbe ottenere è:

Answer 2

Sì, è sempre ottimale.

No, non esiste una soglia dove sarebbe utilizzare meno spazio per utilizzare i dati non codificati lunghezza fissa.

Ho trovato un certo numero di prove sul Web, ma non v'è discussione sufficiente l'articolo di Wikipedia codifica di Huffman .

Ciò comprende anche altre tecniche che conseguono maggiore compressione (lavora fuori dello spazio per cui il codice Huffman è ottimale).

Answer 3

codifica di Huffman approssima la distribuzione della popolazione, con potenze di due probabilità. Se la vera distribuzione non sono costituiti da potenze di due probabilità (ed i simboli di ingresso sono completamente non correlati), codifica di Huffman è ottimale. In caso contrario, si può fare meglio con la codifica gamma. E 'comunque ottimale tra tutti codifica insiemi specifici assegnare di bit ai simboli specifici nell'input.