Albero binario e codici di lunghezza variabile per determinati alfabeti che utilizzano la codifica di Huffman (confusione)

0

La scorsa settimana il nostro insegnante ci ha fatto una domanda sull'Algoritmo di codifica Huffman descritto di seguito.

ALGORITMO DI CODIFICA HUFFMAN:

  1. Considera tutte le coppie:.
  2. Scegli le due frequenze più basse e falle diventare fratelli, con la radice con la frequenza combinata.
  3. Itera.

La domanda era di trovare Final Binary Tree e Variable Length Codes per gli Alfabeti indicati usando l'Algoritmo di codifica Huffman sopra definito:

A | 10

B | 20

C | 30

D | 40

E | 50

F | 60

Ho risolto la domanda ma il mio insegnante ha detto che ho fatto l'albero sbagliato. Si prega di controllare la mia risposta qui sotto e dimmi dove mi sbaglio?

LA MIA RISPOSTA:

Albero binario finale:

Codicelunghezzavariabile:

Gentilmente dimmi dove mi sbaglio? Che cosa ho fatto male durante la creazione del suddetto albero binario?

    
posta Khubaib Khawar 30.01.2018 - 14:12
fonte

1 risposta

1

Choose the two lowest frequencies, and make them brothers, with the root having the combined frequency.

L'hai fatto una volta per A=10, B=20 per un totale di 30, giusto?

Successivamente hai selezionato C=30, D=40 per un totale di 70. Ma c'era una scelta migliore, poiché ci sono due nodi con punteggio di 30 per un totale di soli 60. Uno di questi è C=30 e l'altro? Bene, pensa in modo più dinamico.

    
risposta data 30.01.2018 - 16:23
fonte

Leggi altre domande sui tag