Como a prova da propriedade gananciosa do algoritmo de Hoffman começa com a árvore ideal?

Question

em este artigo Reivindicação 1 afirma que x e y são menor probabilidade e há uma árvore ideal em que esses dois caracteres são irmãos na profundidade máxima .Na prova nessa reivindicação, o autor começa com a árvore t que tem b e c na profundidade máxima da árvore.Eu não consigo entender por que a árvore t é chamada ideal, porque se x e y ter pequenas probabilidades, então a árvore t não pode ser ideal porque HoffmanAlgoritmo não vai construir essa árvore.Eu acho que meu problema aqui é com a compreensão do que a árvore ideal significa.

Se alguém vem da CSLR, isso é sobre o Lema 16.2 e prova para isso.

Answer 1

Uma árvore de código é ideal se o comprimento médio de código de código é mínimo. Isso não tem nada a ver com o algoritmo de Huffman. O algoritmo de Huffman é garantido para produzir uma árvore ideal, mas pode haver outras árvores de código. Na verdade, o algoritmo de Huffman poderia produzir diferentes códigos usando diferentes regras de ruptura. Além disso, nem toda árvore de código ideal pode ser produzida usando o algoritmo de Huffman, mesmo com uma regra arbitrária de gravata.

Aqui está uma definição formal de uma árvore de código ideal. Deixe $ \ pi $ ser uma distribuição. A $ \ PI $ -cost de uma árvore de código é o comprimento esperado de uma palavra de código, onde a expectativa é tomada com relação a $ \ pi $ . Uma árvore de código é ideal para $ \ PI $ Se a sua $ \ pi $ -Cost é igual ao mínimo $ \ PI $ -costação de qualquer códigos.