Disculpa, intento aclarar.
El ejercicio 5.25 del libro:
"Although the codeword lengths of an optimal variable
length code are complicated functions of the message probabilities {p1, p2, . . . , pm}, it
can be said that less probable symbols are encoded into longer codewords. Suppose
that the message probabilities are given in decreasing order p1 > p2 >= · · · >= pm .
parte a):
Prove that for any binary Huffman code, if the most probable message symbol has
probability p1 > 2/5 , then that symbol must be assigned a codeword of length 1."
Se intenta probar por el absurdo.
Asume que el largo del codigo mas probable c1 es l1=L(c1) >=2. Luego se arma un árbol binario cuyo largo a la hoja c1=00 es l1=2.
Luego restan 3 clases C01,C10, y C11 de palabras codificadas que son los códigos que empiezan con 01,10,11. Todos esos códigos tienen largo >=2.
Pero luego, transforma ese árbol, achicando el código c1 de 00 a 0, o sea l1=1 de la clase C0. El nuevo árbol tendrá otras 3 clases C10 con L>=2, C110 y C111 con L>=3.
Entonces las probabilidades de las clases de códigos quedan:
Pr(C0)<2/5
Pr(C10)+Pr(C110)+Pr(C111) > 3/5 ==> Pr(C10) > 1/5 ==> Pr(C110)+Pr(C111) <=2/5. Entonces logramos obtener un supuesto código mejor con el largo l(c1)=1. Pero por qué ese código es mejor? <=========== ESA ES MI DUDA.
Espero haberme expresado mejor! gracias!
Nota sobre Pr(C110)+Pr(C111) <=2/5 en el nuevo mejor código:
Las probabilidades totales mantienen este orden.
PR(C0) > PR(C10) >= PR(C110) >= PR(C111)
Dijimos que en el nuevo mejor código Pr(C110) + Pr(C111) <=2/5
Si fuera Pr(C110)+Pr(C111) > 2/5 ==> Pr(C110) > 1/5 ==>
PR(C0) + PR(C10) + PR(C110) + PR(C111) > 1 lo cual es absurdo
>2/5 >1/5 ambos > 2/5 > 1
El ejercicio 5.25 del libro:
"Although the codeword lengths of an optimal variable
length code are complicated functions of the message probabilities {p1, p2, . . . , pm}, it
can be said that less probable symbols are encoded into longer codewords. Suppose
that the message probabilities are given in decreasing order p1 > p2 >= · · · >= pm .
parte a):
Prove that for any binary Huffman code, if the most probable message symbol has
probability p1 > 2/5 , then that symbol must be assigned a codeword of length 1."
Se intenta probar por el absurdo.
Asume que el largo del codigo mas probable c1 es l1=L(c1) >=2. Luego se arma un árbol binario cuyo largo a la hoja c1=00 es l1=2.
Luego restan 3 clases C01,C10, y C11 de palabras codificadas que son los códigos que empiezan con 01,10,11. Todos esos códigos tienen largo >=2.
Pero luego, transforma ese árbol, achicando el código c1 de 00 a 0, o sea l1=1 de la clase C0. El nuevo árbol tendrá otras 3 clases C10 con L>=2, C110 y C111 con L>=3.
Entonces las probabilidades de las clases de códigos quedan:
Pr(C0)<2/5
Pr(C10)+Pr(C110)+Pr(C111) > 3/5 ==> Pr(C10) > 1/5 ==> Pr(C110)+Pr(C111) <=2/5. Entonces logramos obtener un supuesto código mejor con el largo l(c1)=1. Pero por qué ese código es mejor? <=========== ESA ES MI DUDA.
Espero haberme expresado mejor! gracias!
Nota sobre Pr(C110)+Pr(C111) <=2/5 en el nuevo mejor código:
Las probabilidades totales mantienen este orden.
PR(C0) > PR(C10) >= PR(C110) >= PR(C111)
Dijimos que en el nuevo mejor código Pr(C110) + Pr(C111) <=2/5
Si fuera Pr(C110)+Pr(C111) > 2/5 ==> Pr(C110) > 1/5 ==>
PR(C0) + PR(C10) + PR(C110) + PR(C111) > 1 lo cual es absurdo
>2/5 >1/5 ambos > 2/5 > 1