[TRDT] Entrega 3

Abro un hilo de comentarios para debatir los apartados de la Entrega 3 de esta preciosa asignatura.

Alguna idea con las de Verdadero/Falso?

Opciones de visualización de comentarios

Seleccione la forma que prefiera para mostrar los comentarios y haga clic en «Guardar las opciones» para activar los cambios.

Yo solo digo que Huffman no

Yo solo digo que Huffman no es óptimo porque hay otros códigos óptimos y que por tanto ya no es óptimo por el hecho de haber más. Ahí lo dejo.

No hay otroS códigoS

No hay otroS códigoS optimoS porque si hubiese mas de uno entonces ya no serían optimos. Un código puede ser como mucho tan bueno como Huffman pero nunca mejor, pero por el hecho de que le puedan empatar ya no es optimo.. o eso es lo que entendí yo en clase.

Huecas, no?

Huecas, no?

Yo no tengo ni puñetera

Yo no tengo ni puñetera idea de hacer el 3. Sé que se hace con lo que ha explicado Riera hoy en clase, pero no me enteraba de nada, no aparece en los apuntes del Moodle y tampoco está en el Cover. Una verdadero jodimiento...

Los de verdadero o falso, son bastante inmediatas y están demostradas tal cual en el Cover.

Yo creo que el 3 hay que

Yo creo que el 3 hay que hacerlo mediante condificación RLE, codificando las permanencias. Lo que no se hacer es calcular la longitud media a partir de ese código.

yo no se ni como empezar el

yo no se ni como empezar el 1... como habeis dado las probabilidades a {4,5,2,1,3,6} ???

yo lo que entiendo por distribucion proporcional es {4/21,5/21,2/21,1/21,3/21,6/21} pero no estoy seguro... ademas si lo hago de esta forma no me cuadra que nos den los numeros desordenados, pq contra mayor sea el numero, mayor su probabilidad y menor su long de palabra codigo...

se me ha ocurrido hacerlo con lo de {1/2, 1/4, 1/8, 1/16, 1/32, 1/32} pero eso no tiene nada de proporcional...

asi que no se, estoy hecho un lio... ayuda por favor

Evidentemente...

Evidentemente...

asi me gusta... una

asi me gusta... una respuesta constructiva...

Es lo primero que has dicho.

Es lo primero que has dicho. Lo de que nos los den desordenados es una paja mental que te estás haciendo, los ordenas tú para hacer Huffman cuando te pidan y listo xD

ok gracias

ok gracias

La distribución de

La distribución de probabilidades siempre debe sumar 1.

Cuando dice "proporcional a" se entiende que debes normalizar los valores, es decir, dividir cada uno por la suma de todos ellos.

Yo estoy perdida en el

Yo estoy perdida en el segundo. Cuando dice q son símbolos A, B y C y q los codifiques con símbolos individuales se refiere a 0 , 1 y 2?xq entonces el apartado b) es un regalo...yo hay cosas q no entiendo de estos enunciados, creo q los ponen confusos aposta para nos acabemos suicidando

Se refiere a que halles un

Se refiere a que halles un código con una palabra para representar A, otra para B y otra para C. Por ejemplo, un código huffman...

Pero Huffman binario o

Pero Huffman binario o ternario?

Da igual, en pricipio

Da igual, en pricipio binario, pero como no te especifican... Con uno ternario saldría un error similar.

Pues yo lo hago binario, y

Pues yo lo hago binario, y la longitud media me das mas del 5% de H(x), y por tanto no lo cumple y como Huffman supuestamente es el que mas se acerca a la Entropia.... puffff que asco!

Sí, sale un 12%, por eso te

Sí, sale un 12%, por eso te dice luego que lo hagas de otra manera.

¿Para qué n os sale que lo

¿Para qué n os sale que lo cumple?

Pero en el enunciado no dice

Pero en el enunciado no dice que A,B y C sean mensajes o palabras q puedas codificar...si no q son símbolos independientes..a mi eso es lo q m pierde. Probablemente le esté dando demasiado importancia a alguna mierda q no tiene relevancia XD

El enunciado dice que una

El enunciado dice que una fuente emite los simbolos A, B y C, luego esos son los tres mensajes que quieres codificar. Primero te pide que lo hagas individualmente y luego agrupándolos de 2 en 2, etc. Por lo menos así lo veo yo

Aaaa ok ok muchas gracias :)

Aaaa ok ok muchas gracias :)

oye, para el codigo shannon

oye, para el codigo shannon elias fano, como se pone en binario un numero decimal?

Multiplicando por

Multiplicando por dos...mientras te siga quedan 0 coma algo...pones un cero, y cuando salga uno coma algo pones 1 y sigues multplicando la parte decimal.Es decir, por ejemplo 0.1875 sería:
0.1875x2->0.375---------------->0
0.375x2->0.75------------------->0
0.75x2->1.5---------------------->1
0.5x2->1------------------------->1
Es decir, el número en binario sería 0,0011
Si no quedara exacto seguirías multiplicando, de hecho en el ejercicio 1 quedan todos periódicos.

Cuando te pidan hacerlo en

Cuando te pidan hacerlo en la segunda parte del 2, hazlo con una calculadora porque si no te mueres. La de Ubuntu sí que tiene para cambiar de base con decimales, pero en la de Windows no veo cómo...

Lo digo porque te quedan longitudes de hasta 8 símbolos, imagínate el coñazo que es.

Alguna idea para el tercero?

Alguna idea para el tercero? El primer apartado como dicen por arriba debe ser con Run-Length, pero luego cuando metes vocales y consonantes ya no puedes hacerlo así. Hemos pensado en que tal vez sea con Lempel-Ziv, pero no sé...

En el 2 cuando dicen lo de

En el 2 cuando dicen lo de la extension de fuente se refiere a codificar grupos de simbolos? Es decir para n=2, las opciones son x1=AA, x2=AB, x3=AC, x4=BA, x5=BB, x6=BC, x7=CA, x8=CB, x9=CC.

Luego p(AA)=p(A)*p(A) por ser independientes.

Se calcula asi con todos los simbolos xi y despues se normaliza. Se calcula la entropia debla fuente, se hace Huffman. Se calcula su long.media y se compara con la H(X). Si excede maximo en un 5% ya vale. Sino se agrupa de 3 en tres pudiendo repetirse y las combinaciones se disparan a medida que sube n.

En que valor se cumple lo del 5%?

Que locura.

por suerte se cumple con

por suerte se cumple con n=2
tienes q compararla con la entropía de la nueva fuente, no con la de la fuente sin extensión

Ahhhhh ya decia yo....joder

Ahhhhh ya decia yo....joder vaya fallo mas tonto.

Ahora si que sale. Estaba yo haciendo las cuentas con n=3, y he tardao un buen rato en calcular todos los putos logaritmos.

Y no me daba. Algo habia hecho mal tambien en n=3.

Eso, eso es lo que habia hecho mal lo mismo que en n=2. Si no me llego a dar cuenta voy el lunes con n=10 y tengo que llevar el matlab a clase cuando me saque Huecas a la pizarra.

JAJAJA Me lo estoy

JAJAJA Me lo estoy imaginando. xD

¿Porque lo normalizas, si

¿Porque lo normalizas, si da uno la suma?
Muchas Gracias!

eso digo yo, no hace falta

eso digo yo, no hace falta normalizar no? y a mi me da un 5,4% de diferencia...con eso se puede dejar asi o habría que seguir con n=3?

A mi me da menos del 1% con

A mi me da menos del 1% con n=2

en serio? pues yo no se...:S

en serio? pues yo no se...:S a mi me sale H(x) = 2.3135 y me L (c)= 2.44 bits/ simbolo :S

H(X) = 2,31 y la L(x) = 2,33

H(X) = 2,31 y la L(x) = 2,33 me queda a mí, mételo en Excel los datos, es fácil equivocarse con la calculadora :)

valee me habia confundidoooo

valee me habia confundidoooo muchas gracias =)

Una pregunta, en el código

Una pregunta, en el código de Fano al principio, ¿tenemos que ordenar los símbolos por probabilidad de mayor a menor?. Riera en clase no los ordenó, pero leyendo por internet he visto que sí se ordenan...

Pues según Huecas es un

Pues según Huecas es un paso necesario, pero dijo en clase que en eso tenían discusiones los profesores, algunos decían que no y otros que sí. Yo tengo la entrega con Huecas y los he ordenado.

Vale, muchas gracias. Yo

Vale, muchas gracias. Yo tengo la entrega con Riera pero los voy a ordenar de todas formas.

Yo también los he ordenado

Yo también los he ordenado por probabilidades... se supone que de eso va el tema, de separar en grupos "fijos" en el orden en el que están, además de que en el Cover sí que están ordenados.

Alguien puede comentar

Alguien puede comentar someramente como ha hecho el 3?

Es complicado realmente o parece mas de lo que es?

Podeis comentar como lo habeis resuelto por favor?

Gracias.

.

Si alguien puede ayudar con el 3...

En el 1, ¿Cómo se hace el

En el 1, ¿Cómo se hace el código binario y ternario óptimos?

Usa Huffman. Binario agrupas

Usa Huffman. Binario agrupas los 2 menores. Ternario los 3 menores.

La entropia es log base 3 para los ternarios.

Gracias

Gracias.

Alguna idea para el 3?

Alguna idea para el 3?

Alguna idea para el 3?

Yo estoy igual, no se por donde coger el 3. ¿Algún alma caritativa?

El ejercicio 6 me sale el

El ejercicio 6 me sale el primer código no U.D. y los otros 3 sí U.D.
En el ejercicio 5: la "a" falso (los no prefijos no tienen por qué cumplir Kraft), la "c" verdadero (porque L está entre H(x) y H(x)+2), la "d" falso (se aproxima mucho a H(x), pero no es igual). ¿Pensáis lo mismo? La "b" tengo dudas... sé que con Huffman sí varían en el último bit sólo, ¿pero y en el resto? Lo mismo me pasa para el ejercicio 4, que no tengo muy claro nada.

Y me uno a la propuesta de que alguien nos ilumine en el ejercicio 3 :)

Venga Onir,enróllate con el

Venga Onir,enróllate con el 3

El 3 se hace por RLE. Hay

El 3 se hace por RLE.

Hay que codificar no las palabras en sí, sino las longitudes.

Es un poco largo ponerlo aqui en un mensaje, pero creo que algun profesor subio al moodle unos apuntes sobre RLE.

Se calcula m y se agrupa los segmentos de m en m. Despues cada segmento tiene dentro m opciones. con logm bits se codifica el interior.

¿ Te refieres a los apuntes

¿ Te refieres a los apuntes del Grupo 34?

m os da 4?

m os da 4?

Y cómo has llegado a eso? O

Y cómo has llegado a eso? O dónde puedo encontrar esos apuntes sobre RLE? Gracias :)

Puedes encontrar esos

Puedes encontrar esos apuntes aquí o aquí

alguien entiende esos

alguien entiende esos apuntes? :s

antes habeis dicho esto:

Se calcula m y se agrupa los segmentos de m en m. Despues cada segmento tiene dentro m opciones. con logm bits se codifica el interior.

la m la tengo... pero de donde saco los segmentos? :s

si tienes longitud cuatro

si tienes longitud cuatro codificas dentro cuatro valores por lo que a fuerza bruta te da que te gastas dos bits para esa codificación

Los apuntes no los entiendo

Los apuntes no los entiendo muy bien, pero gracias!!! :)
A ver, la m la tengo, me sale 4 (probabilidad de repetir es 5/6). Ahora ponemos una columna que van a ser las distintas longitudes "n" (de 1 para alante). A cada una de esas "n"s se le asigna una palabra código (porque se codifican longitudes).

Como m=4, vamos a dividir las palabras código en conjuntos o segmentos de 4 en 4 (es decir, el primer segmento o grupo está formado por las palabras código de longitudes n=1, n=2, n=3 y n=4; el segundo grupo está formado por las palabras código de longitudes n=5, n=6, n=7 y n=8, y así cada grupo o segmento).

Cada una de las palabras código estará formada por 2 bits a la derecha (para que sea posible que m=4 tienen que ser, como digo, 2 bits, 2^2=4). A la izquierda de esos dos bits (que, por cierto, van a ir rotando cíclicamente entre 00, 01, 10, 11) van a ir otros bits, los cuales son:

-Para el primer segmento (n=1, n=2, n=3 y n=4): 0
-Para el segundo segmento (n=5, n=6, n=7 y n=8): 10 (se añade un 1 a la izquierda)
-Para el tercer segmento (n=9, n=10, n=11 y n=12): 110 (se añade un 1 a la izquierda)

Así, las columnas serían:
---------------------------------------------------
Longitud n=1 ----> palabra código: 0 00
Longitud n=2 ----> palabra código: 0 01
Longitud n=3 ----> palabra código: 0 10
Longitud n=4 ----> palabra código: 0 11
---------------------------------------------------
Longitud n=5 ----> palabra código: 10 00
Longitud n=6 ----> palabra código: 10 01
Longitud n=7 ----> palabra código: 10 10
Longitud n=8 ----> palabra código: 10 11
---------------------------------------------------
Longitud n=9 ----> palabra código: 110 00
Longitud n=10 ---> palabra código: 110 01
Longitud n=11 ---> palabra código: 110 10
Longitud n=12 ---> palabra código: 110 11
.
.
.

La longitud media es la suma de la longitud del sufijo (como he dicho, por ser m=4, esta longitud es 2) más la longitud del prefijo (1/(1-(p^m))=1,93). En total, la longitud media es 3,93 bits.

Que alguien me corrija si me equivoco, porque si está mal igual alguno se lo apunta mal...

A mi me da igual todo, pero

A mi me da igual todo, pero lo que no entiendo es porque los segmentos siguen el patron de 0 , 10 , 110 .....

Para que ninguno de los

Para que ninguno de los siguientes tenga un prefijo anterior.

Pensad que si codificais segun Huffman, por el "basico" (Letra=0, Separador=1), una cadena de 100000 simbolos seguidos ocuparia 100000 bits.

Pero si se busca un patron a la hora de saber cual es la aparicion media de letras seguidas en una palabra, Y NO SE DIFERENCIAN LETRAS, pues a lo mejor esa frase de 100000 simbolos (letras+separadores), se puede COMPRIMIR en solo 20000 si a priori conoces la probabilidad de que una letra se repita, es decir, la longitud media de una palabra (numero de letras).

Si tú tienes:Letra=1, Separador =0. Y tienes: 1111111011111011111011111110. Son 27 bits,

Pero poniendo 7557, te ocupa menos bits. Se trata de buscar un codigo que para decir "7 letras seguidas" uses por ejemplo 01.

Sabiendo las longitudes mas probables (media), asignas un codigo de menos bits.

Pues esa es basicamente la base.

Muchas Gracias por la

Muchas Gracias por la aclaración

A mi me da igual todo, pero

A mi me da igual todo, pero lo que no entiendo es porque los segmentos siguen el patron de 0 , 10 , 110 .....

en el c) hayq sacar la

en el c) hayq sacar la entropia de todo eso?? :s

y el d) y e) alguna idea?