Come la prova di Hoffman Algorithm Greedy Property inizia con l'albero ottimale T?

Question

in Questo documento rivendicazione 1 afferma che x e y sono più piccole probabilità e c'è un albero di codice ottimale in cui questi due caratteri sono fratelli alla profondità massima .Nella prova a tale reclamo, l'autore inizia con l'albero t che ha b e c alla massima profondità dell'albero.Non riesco a capire perché l'albero t è chiamato ottimale, perché se x e y hanno più piccole probabilità, allora l'albero t non può essere ottimale perché HoffmanL'algoritmo non costruirà tale albero.Penso che il mio problema qui sia con capillare quale albero ottimale significa.

Se qualcuno viene da CSLR, questo riguarda Lemma 16.2 e la prova a questo.

Answer 1

Un albero di codice è ottimalmente se la lunghezza media del codice è minima. Questo non ha nulla a che fare con l'algoritmo di Huffman. L'algoritmo di Huffman è garantito per produrre un albero di codice ottimale, ma potrebbero esserci altri alberi di codice. In effetti, l'algoritmo di Huffman potrebbe produrre diversi alberi di codice usando diverse regole di rottura del legame. Inoltre, non ogni albero di codice ottimale può essere prodotto utilizzando l'algoritmo di Hufman, anche con una regola arbitraria.

Ecco una definizione formale di un albero di codice ottimale. Let $ \ P $ Sii una distribuzione. La $ \ P $ -cost di un albero di codice è la lunghezza prevista di un codice, in cui viene presa l'aspettativa rispetto a < class="Math-Container"> $ \ PI $ . Un albero di codice è ottimale per $ \ PI $ se la sua $ \ P $ -Cost è uguale al minimo $ \ PI $ -Cost di qualsiasi albero di codice.