Por SkAsI
Hace tiempo que los retos han ido bajando en aparición. Recuerdo con añoranza aquellos posts kilométricos con los retos de infosniper con sus manillas y demás. Lo que yo quiero resucitar es precisamente ese espíritu de equipo de descifradores que se vio en aquellas ocasiones y en otras posteriores y que no se dejó ver del todo con el megarreto ACYNOS de Agustín el Magnífico.
Mi reto es sencillo, o al menos eso he intentado, y se basa en cosas sencillas que todos podemos conocer/buscar. El reto será doble, primero un reto de oscuridad (o caja negra) y después un reto de algoritmo (o caja blanca)... una vez que se descifre el sencillo algoritmo...
La primera parte consiste en un reto de caja negra. Para dicho reto los espías han logrado interceptar un criptograma, su clave y el texto en claro, ya que el enemigo está de pruebas del sistema y siempre envía la misma información. Aquí va:
0000001011010101110100111100000010110011111011011010110111101001111001000110111
1000000111010000000100110011101111010011111011000000000110000101111011011110111
1010011110000010000000111100001010111111101100110101110101111110111011000011111
001100111100001001101011000000010111011001111
huffman
ESTO_ES_SOLO_UN_EJEMPLO_SENCILLO_DE_CRIPTOGRAFIA_CASERA_
Además se conoce que el alfabeto es el estándar de 27 letras más el espacio "_".
Una vez se descubra el pastel del sistema, se irá a por el ataque más serio: romper dicho sistema contando sólo con el criptograma (y puede que con el texto claro u otro tipo de ayuda).
Kriptosaludos.
(Corrección 11-11-2010): Por un error en la copia del mensaje cifrado, he tenido que volver a poner el mismo. Espero me disculpeis.
¡Agustín!
DEDDS22 Noviembre 2010 - 11:37pm
Me ausento un par de dias y mira la que me montas.
¡Enhorabuena!
Si he entendido bien el invento, para crear las frecuencias que dan lugar al HUFFMAN no se usa el texto a comprimir, sino que se usa el combinado alfabeto+clave, ¿no?
Voy a probarlo en cuanto tenga un ratito, que acabo de llegar de lejos y estoy un poco machacado.
Un saludo.
Enhorabuena
SkAsI22 Noviembre 2010 - 1:56pm
Agustín, eres una bestia. Siento la soledad del fin de semana, pero no he podido ni acercarme a nada que pareciera tener un transistor de silicio dentro. Me alegro que a mi regreso la caja negra haya sido reventada. Sin los problemas del Huffman, se habría resuelto en un par de días, como era mi pretensión.
Como bien decías, os lo puse delante para ver si así no pensábais en ello como la solución, pero veo que no ha servido. Como decía, enhorabuena. Ahora toca la caja blanca, en la que me gustaría participar como atacante, ya que es mi engendro, pero es más fácil parir un engendro que matarlo, y creo que eso lo sabe bien Agustín.
Kriptosaludos.
PD: Me alegro que te haya gustado el reto de caja negra.
PD2: (Para admin) No sé si continuar en este hilo o abrir otro para el reto de caja blanca.
Menos mal
Agustín22 Noviembre 2010 - 2:22pm
Empezaba a pensar que te había pasado algo.
Gracias por los parabienes, pero visto ahora el problema parece fácil. Tan solo nestra burricie con el Huffman -y nuestra burricie a secas- lo dificultaba. A ver cómo se nos da lo siguiente
Gracias por el aprendizaje.
No hay duda
admin22 Noviembre 2010 - 2:09pm
Abrimos nuevo hilo, que tengo que cambiar la imagen de la caja ;)
Por cierto...
SkAsI22 Noviembre 2010 - 3:55pm
Muy chula la imagen que acompaña al reto ;)
Kriptosaludos.
Matizando más
Agustín21 Noviembre 2010 - 2:33pm
Me está pareciendo que el problema de detectar los 28 códigos en la ristra de 0s y 1s no va a ser un problema trivial, o sea que de lo que dije antes, nada de nada. Mis respetos, SkAsI. Por cierto, SkAsI sigue sin aparecer. Empiezo a temer que le haya pasado algo o esté enfermo. Claro que tampoco aparecen DEDDS ni los demás. ¡Me han dejado solo! No os habréis puesto todos de acuerdo para gastarme una broma, ¿verdad?
¡¡¡ BUH !!!
infosniper21 Noviembre 2010 - 5:10pm
¿A que te he asustado? Es que te he visto mirando a un lado y a otro, como si estuvieras indefenso y perdido enmedio del bosque, y no he resistido la tentación.
infosniper
http://sites.google.com/site/infosniper/
¡Arf, arf, arf!
Agustín21 Noviembre 2010 - 6:22pm
¡Qué susto! ¿Sabes por dónde queda la salida? Que llevo aquí tres días perdido.
Al fondo a la derecha
infosniper21 Noviembre 2010 - 7:11pm
Por cierto, ¿sabes nadar, no?.
infosniper
http://sites.google.com/site/infosniper/
Caja Blanca (Análisis)
Agustín21 Noviembre 2010 - 1:42pm
Análisis del problema
Como el malvado SkAsI no aparece, me he quedado aquí solo dándole vueltas al magín, pensando ya en lo que vendrá después. Ya no me parece tan difícil resolver el Kripto-Huffman, aun en el caso de que no conozcamos la clave. Nos enfrentaremos a una longaniza de 0s y 1s formada por la concatenación de los códigos asignados a las letras por el árbol de Huffman que, por supuesto, no conoceremos. Pero los códigos cumplen una restricción, y es que ninguno puede ser prefijo de otro. Eso nos permitirá, creo yo, determinarlos con un poco de trabajo de programación. Una vez que tengamos los veintiocho códigos, podremos asignarlos a los 28 símbolos del alfabeto, guiándonos por las frecuencias(*). Nos hallaremos entonces ante un problema de Sustitución Monoalfabética. O sea, caso resuelto. La dificultad fundamental de este cifrado está en conocer el algoritmo, que lo nuestro nos ha costado. SkAsI, yo de ti ni me molestaría, je ,je.
(*) Ya sé lo que estás pensando: No vale que pongas un texto aleatorio.
P.S.
Todo esto es palabrería porque, como se dice, hasta el rabo es toro. Ya veremos cómo se presentan las cosas. Bueno, primero habrá que ver si se presenta SkAsI.
Corrección y Solución
Agustín20 Noviembre 2010 - 1:00pm
Todo lo que dije en el post anterior es válido, salvo que la clave utilizada no es
ESTO_ES_SOLO_UN_EJEMPLO_SENCILLO_DE_CRIPTOGRAFIA_CASERA_HUFFMAN
sino (fue un simple error de cortar-pegar):
ABCDEFGHIJKLMNÑOPQRSTUVWXYZ_HUFFMAN
con el correspondiente árbol y los códigos que tanto nos costó encontrar. El malvado SkAsI nos la ponía ante los ojos para que no la viéramos.
El asunto funciona, pues, de este modo:
1. Con la clave, negociada entre el emisor y el receptor, se construye el famoso árbol y los códigos que caen de él como las hojas muertas en otoño.
2. Para cifrar, se cambia cada letra del mensaje en claro por su correspondiente código arbóreo, con lo que se convierte en una ristra de 0s y 1s
3. Para descifrar, con los códigos se van identificando las letras escondidas en la ristra de 0s y 1s
Resumiendo:
Mensaje cifrado
0000001011010101110100111100000010110011111011011010110111101001111001000110111
1000000111010000000100110011101111010011111011000000000110000101111011011110111
1010011110000010000000111100001010111111101100110101110101111110111011000011111
001100111100001001101011000000010111011001111
Contraseña:
ABCDEFGHIJKLMNÑOPQRSTUVWXYZ_HUFFMAN
Códigos
[A 0110 B 000011 C 000010 D 000001 E 000000 F 0001 G 11111 H 0101 I 11110 J 11101 K 11100 L 11011 M 0100 N 0011 O 11010 P 11001 Q 11000 R 10111 S 10110 T 10101 U 0010 V 10100 W 10011 X 10010 Y 10001 Z 10000 _ 01111 Ñ 01110]
Mensaje en claro:
ESTO_ES_SOLO_UN_EJEMPLO_SENCILLO_DE_CRIPTOGRAFIA_CASERA_
A mí me parece un cifrado muy elegante, sí señor. Le daría la enhorabuena a SkAsI si supiera dónde se esconde.
Voilà.
Matiz
Agustín21 Noviembre 2010 - 2:25am
En realidad, la clave propiamente dicha es, como decía SkAsI: HUFFMAN Lo otro, ABCDEFGHIJKLMNÑOPQRSTUVWXYZ_ no es más que el alfabeto.
¿Resuelto?
Agustín20 Noviembre 2010 - 2:46pm
Aplicando al mensaje cifrado -ya sabéis, los 0s y 1s- del problema, los códigos de Huffman para el mensaje:
ESTO_ES_SOLO_UN_EJEMPLO_SENCILLO_DE_CRIPTOGRAFIA_CASERA
se obtiene el sigiente mensaje "cifrado" con letras
__OOMPS__ORSOOOEECAIDEI_EO__PRCSPSOJ_E_MOOSECAI_JAILOSSEAMMSEOGSRRS_POE__MEA
Obsérvese que la longitud es mayor que el mensaje original, incluso sumándole la clave "HUFFMAN"
Pero si se usan los códigos para el mensaje
ESTO_ES_SOLO_UN_EJEMPLO_SENCILLO_DE_CRIPTOGRAFIA_CASERA_HUFFMAN (Reedición: ver el post siguiente)
a los mismos 0s y 1s, entonces se obtiene:
ESTO_ES_SOLO_UN_EJEMPLO_SENCILLO_DE_CRIPTOGRAFIA_CASERA_
Q.E.D
Espero no haber hecho algo mal
Lo que no acabo de entender es cómo se transmitirían la información el remitente y el receptor. O sea que no lo tengo claro. ¡¡¡SkAsI!!!
Pequeña hipótesis
Lucho.krp20 Noviembre 2010 - 12:30am
Veo dos caminos posibles de funcionamiento del sistema (no descubro nada...):
1) mensaje en claro -> encriptación (clave) -> huffman -> mensaje cifrado
2) mensaje en claro -> huffman -> encriptación (clave) -> mensaje cifrado
Creo que si fuera el segundo, que se reduce a resolver el paso 3, SkAsI nunca hubiera revelado que hay un Huffman en el medio...
Me inclino por el primero. Al aplicarle Huffman a un mensaje cifrado, no conocemos la longitud de este ni las frecuencias aunque tengamos el mensaje en claro, por lo que no tenemos ni una pista para construir el árbol. Por más que el cifrado usado en ese paso sea débil, no hay por donde arrancar. Digamos que este camino explota toda la potencia del algoritmo de Huffman. El único posible ataque que veo es aplicar los métodos conocidos al mensaje en claro, calcular el Huffman y esperar que alguno coincida. Poca cosa...
Otro pasito (fallido)
DEDDS19 Noviembre 2010 - 8:15pm
Por si hubiera reminiscencias de otros retos, se me ocurrío aplicar Vigenere con la clave y codificar el texto resultante. Pero el resultado en número de bits es también mucho más corto que el que plantea el reto.
Esto me lleva a pensar en dos posibles opciones:
1 - la clave se usa para "hacer crecer" el texto en claro, de tal forma que el número de caracteres a codificar sea mayor y, por tanto, el número de bits obtenidos es también mayor.
2 - la clave codificada se usa para hacer crecer el texto codificado (no del estilo del XOR ni de las rotaciones porque mantienen el mismo número de bits)
Yo pienso que puede ser algo creativo, del estilo de "separa el texto claro en grupos del mismo número de letras de la clave. Haz un sandwich gigante metiendo la clave entre los grupos de letras. Coge las letras por columnas en lugar de por filas y aplica la codificación. Pon el resultado en el extremo de un palito y agítalo delante de los 'mindunguis' para que lo sigan" :)
Un saludo.
Los tres mosqueteros
Agustín19 Noviembre 2010 - 9:10pm
Aquí estamos los tres implicados en el efímero DASK, tú, yo, y SkAsI. ¿SkAsI? ¡¿SkAsI?! ¿Dónde se habrá metido? Seguramente pensó que tardaríamos tres meses en aclararnos con el Huffman ése, y se ha ido de crucero por los Mares del Sur.
Un pasito (fallido)
Agustín18 Noviembre 2010 - 11:04pm
Aplicando el algoritmo al mensje inicial, con y sin la clave, obtengo los siguientes resultados:
ESTO_ES_SOLO_UN_EJEMPLO_SENCILLO_DE_CRIPTOGRAFIA_CASERA_
[56 [32 [17 [9 _] [8 [4 L] [4 A]]] [15 [8 [4 [2 T] [2 P]] [4 [2 N] [2 [1 U] [1 M]]]] [7 E]]] [24 [13 [7 [4 [2 [1 J] [1 G]] [2 [1 F] [1 D]]] [3 R]] [6 O]] [11 [6 [3 I] [3 C]] [5 S]]]]
[A 0011 C 1101 D 100011 E 011 F 100010 G 100001 I 1100 J 100000 L 0010 M 010111 N 01010 O 101 P 01001 R 1001 S 111 T 01000 U 010110 _ 000]
0111110100010100001111100011110100101010000101100101000001110000001101011101001001010100011101101
0101101110000100010101000100011011000110110011100010010100010110000110010011100010110000110001101
001111101110010011000
ESTO_ES_SOLO_UN_EJEMPLO_SENCILLO_DE_CRIPTOGRAFIA_CASERA_HUFFMAN
[[63 [37 [20 [11 [6 [3 F] [3 C]] [5 S]] [9 _]] [17 [9 [5 A] [4 L]] [8 [4 [2 U] [2 T]] [4 [2 P] [2 M]]]]] [26 [14 [7 E] [7 [4 [2 [1 J] [1 H]] [2 [1 G] [1 D]]] [3 R]]] [12 [6 O] [6 [3 N] [3 I]]]]]
[A 0100 C 00001 D 101011 E 100 F 00000 G 101010 H 101001 I 1111 J 101000 L 0101 M 01111 N 1110 O 110 P 01110 R 1011 S 0001 T 01101 U 01100 _ 001]
1000001011011100011000001001000111001011100010110011100011001010001000111101110010111000100011001
1100000111110101010111000110101110000100001101111110111001101110101010101101000000011110100001000
0101000001100101101000011010010110000000000000111101001110
HUFFMAN_ESTO_ES_SOLO_UN_EJEMPLO_SENCILLO_DE_CRIPTOGRAFIA_CASERA_
[[64 [38 [21 [11 [6 [3 F] [3 C]] [5 S]] [10 _]] [17 [9 [5 A] [4 L]] [8 [4 [2 U] [2 T]] [4 [2 P] [2 M]]]]] [26 [14 [7 E] [7 [4 [2 [1 J] [1 H]] [2 [1 G] [1 D]]] [3 R]]] [12 [6 O] [6 [3 N] [3 I]]]]]]
A 0100 C 00001 D 101011 E 100 F 00000 G 101010 H 101001 I 1111 J 101000 L 0101 M 01111 N 1110 O 110 P 01110 R 1011 S 0001 T 01101 U 01100 _ 001]
1010010110000000000000111101001110001100000101101110001100000100100011100101110001011001110001100
1010001000111101110010111000100011001110000011111010101011100011010111000010000110111111011100110
1110101010101101000000011110100001000010100000110010110100001
Incluso he probado con:
ESTO_ES_SOLO_UN_EJEMPLO_SENCILLO_DE_CRIPTOGRAFIA_CASERA_HUFFMAN_
[64 [38 [21 [11 [6 [3 F] [3 C]] [5 S]] [10 _]] [17 [9 [5 A] [4 L]] [8 [4 [2 U] [2 T]] [4 [2 P] [2 M]]]]] [26 [14 [7 E] [7 [4 [2 [1 J] [1 H]] [2 [1 G] [1 D]]] [3 R]]] [12 [6 O] [6 [3 N] [3 I]]]]]
[A 0100 C 00001 D 101011 E 100 F 00000 G 101010 H 101001 I 1111 J 101000 L 0101 M 01111 N 1110 O 110 P 01110 R 1011 S 0001 T 01101 U 01100 _ 001]
1000001011011100011000001001000111001011100010110011100011001010001000111101110010111000100011001
1100000111110101010111000110101110000100001101111110111001101110101010101101000000011110100001000
0101000001100101101000011010010110000000000000111101001110001
No sé cómo obtener el cifrado inicial
¿Tal vez haciendo alguna operación lógica con el código del mensaje (ver arriba) y el de la clave?
HUFFMAN
[[7 [4 [2 F] [2 [1 N] [1 M]]] [3 [2 [1 H] [1 A]] [1 U]]]]
[A 101 F 00 H 100 M 011 N 010 U 11]
100110000011101010 (*op*)
0111110100010100001111100011110100101010000101100101000001110000001101011101001001010100011101101
0101101110000100010101000100011011000110110011100010010100010110000110010011100010110000110001101
001111101110010011000 =
0000001011010101110100111100000010110011111011011010110111101001111001000110111
1000000111010000000100110011101111010011111011000000000110000101111011011110111
1010011110000010000000111100001010111111101100110101110101111110111011000011111
001100111100001001101011000000010111011001111
No parece un XOR, desde luego
************************************************************************************
(Reedición)
¿DASK?
Tampoco sería raro que el malvado SkAsI hubiera jugado con los bits, girándolos a derecha o izquierda... esas cositas que hicimos con DASK. Esto de la criptografía es como torear vaquillas, que en cada nueva capea saben más que en la anterior, y al final te pillan.
¿Y ahora?
Agustín18 Noviembre 2010 - 8:36pm
Ya coincidimos en el árbol y en los códigos. No sabes cómo te agradezco que nos hayas hecho aprender el Huffman ese.
[35 [19 [11 [7 [4 [2 [1 E] [1 D]] [2 [1 C] [1 B]]] [3 F]] [4 [2 U] [2 N]]] [8 [4 [2 M] [2 H]] [4 [2 A] [2 [1 Ñ] [1 _]]]]] [16 [8 [4 [2 [1 Z] [1 Y]] [2 [1 X] [1 W]]] [4 [2 [1 V] [1 T]] [2 [1 S] [1 R]]]] [8 [4 [2 [1 Q] [1 P]] [2 [1 O] [1 L]]] [4 [2 [1 K] [1 J]] [2 [1 I] [1 G]]]]]]
[A 0110 B 000011 C 000010 D 000001 E 000000 F 0001 G 11111 H 0101 I 11110 J 11101 K 11100 L 11011 M 0100 N 0011 O 11010 P 11001 Q 11000 R 10111 S 10110 T 10101 U 0010 V 10100 W 10011 X 10010 Y 10001 Z 10000 _ 01111 Ñ 01110]
Y ahora ¿cuál es el siguiente paso, que me he perdido?
Ahora
DEDDS18 Noviembre 2010 - 9:07pm
Agustín, es cuando empieza la criptografía de verdad ;)
Un saludo.
Ya
Agustín18 Noviembre 2010 - 9:41pm
Pero, ¿la cuála?
Si ha costado un mes aprender a coger la azada, imagínate para hacer la zanja.
Tachín, Tachín
DEDDS18 Noviembre 2010 - 7:53pm
¡Por fin! Ya he sido capaz de cuadrarlo para obtener el mismo resultado que SkAsI.
El fallo estaba en que yo usaba como frecuencia de aparición de las letras precisamente la "frecuencia", es decir, Nº de veces que aparece la letra dividido entre el Nº total de letras (expresado como un número redondeado a cuatro decimales). Con este criterio obtenía los valores mencionados en comentarios anteriores.
Al cambiar el criterio de "frecuencia" y usar directamente el Nº de veces que aparece la letra, ya obtengo los resultados esperados. :P
Lo que has escrito lucho.krp (que te preguntas si tiene utilidad) ha servido por ejemplo para que pueda comparar lo que yo obtengo al pasar el texto por el algoritmo y lo que tu obtienes. El resultado es idéntico (salvo el pequeño detalle de que se te ha colado un "0" de más en una de las cadenas).
Creo que podemos decir que poquito a poquito vamos progresando, ¿no?.
Un saludo.
Mi aporte
Lucho.krp18 Noviembre 2010 - 2:00am
Hola, esta es mi primera intervención en Kriptópolis. Suelo seguir los retos, pero me quedo a mitad de camino (más bien mucho antes), porque mis conocimientos de criptografía y matemática son nulos y muy básicos respectivamente. En este caso, me atrajo el desafío de hacer el algoritmo que SkAsI propuso y obtener sus mismos resultados. Finalmente lo logré, así que comparto lo que obtuve al aplicarlo al mensaje original:
011 111 01000 101 000 011 111 000 111 101 0010 101 000 010110 01010 000 011 100000 011 010111 01001 0010 101 000 111 011 01010 1101 1100 0010 0010 101 000 1000110 011 000 1101 1001 1100 01001 01000 101 100001 1001 0011 100010 1100 0011 000 1101 0011 111 011 1001 0011 000Otros datos, por si a alguien le sirven:
Longitud: 216 (el cifrado tiene 288)
Distribución de bits (por letra):
Ahora les dejo a los que saben la parte de dilucidar cómo se llega de esto al mensaje cifrado...
Una duda con respecto a las reglas que dio SkAsI para el algoritmo: en 2c, ¿tiene sentido "se compara primero el hijo izquierdo con el hijo izquierdo y después el hijo derecho con el hijo derecho"? Yo solo comparé los hijos izquierdos, ya que en algún momento (usando las otras reglas) se llega a un resultado (es decir, ¿cuándo necesitaría comparar los hijos derechos?).
Optimización
SkAsI18 Noviembre 2010 - 1:59pm
Primero de todo, gracias por participar, aunque sigo dándole vueltas a los resultados que has dado. Me gustaría que explicaras un poco más de dónde salen los resultados, ya que no entiendo bien la información que das.
Lo que comentas de la regla 2c es interesante. Al final, caminando por los hijos izquierdos vas a llegar a una situación de terminal vs no terminal, caso que se resuelve en favor del no terminal, o por el contrario te encontrarás comparando dos terminales, caso en el que siempre uno de los dos será menor que el otro.
Dicho esto, tienes razón al afirmar que basta con comparar los hijos izquierdos y de hecho en la práctica nunca se compararán los hijos derechos, pero quería que la regla tuviera completitud, así que incluí a ambos hijos.
Kriptosaludos.
Explicación
Lucho.krp18 Noviembre 2010 - 3:28pm
El "resultado" que doy es lo que el algoritmo produce a partir del texto
Si tiene utilidad o no, yo mismo me lo pregunto :)
Creo que permite saber algunas cosas, como por ejemplo que el sistema no consiste en aplicar el algoritmo de Huffman y luego una transposición. El texto está "envenenado" antes de aplicar el algoritmo.
¿¿¿Emparejamientos???
DEDDS16 Noviembre 2010 - 8:01pm
Querido amigo SkAsI:
Veo cosas raras en los emparejamientos que nos has dado. Me explico.
Estudio de los terminales (de 1 a 11) -> aparecen las letras del alfabeto menos las que forman parte de la primera clave (huffman)
Primeros no terminales (de 12 a 16) -> se colocan nada más las parejas obtenidas en el paso anterior salvo el último par (Ñ_) que se queda descolgado por ser el número de parejas impar.
Terminales y no terminales (de 17 a 19) -> se coloca la pareja suelta del paso anterior con las primeras cinco letras de la clave ordenada de mayor a menor (UNMHA). (La "F" queda fuera porque al aparecer dos veces es la que más frecuencia tiene, y por tanto "la mayor", y queda desemparejada)
Restantes ( de 20 al final) se añade la "F" que nos quedó suelta como nodo terminal al resto de los nodos no terminales obtenidos en los pasos anteriores, y se aplican las reglas de formación hasta obtener el árbol completo.
Y mi pregunta es: ¿es este el reto de la caja negra que nos tenías preparado? Porque si es un ejemplo para ponernos de acuerdo en un árbol la verdad es que es un poco bastante enrevesado.
De todas las maneras aún tengo otra duda. Este "ejemplo" que nos pones, en cada paso estudia siempre todas las parejas posibles y al terminar es cuando reordena de nuevo los nodos obtenidos. No es así como yo entendía que había que hacerlo. Yo pensaba que el proceso se hacía de la siguiente forma:
1. Se ordenan los nodos siguiendo las reglas descritas.
2. Se toman los dos de menor valor para obtener un nuevo nodo no terminal que los sustituye, cuya frecuencia es la suma de las frecuencias de los nodos (terminales o no terminales) que lo componen.
3. Se repiten los dos pasos anteriores hasta que solamente queda un nodo no terminal, que es la raiz del árbol.
De esta forma es como yo he obtenido la codificación de las letras.
Ejemplo:
Primera ordenación de los nodos terminales del alfabeto:
|Ñ|_|Z|Y|X|W|V|U|T|S|R|Q|P|O|N|M|L|K|J|I|H|G|F|E|D|C|B|A|
Se toma como derecho el menor -> "A"
Se toma como izquierdo el menor -> "B"
Se forma el nodo no terminal [BA], que sustituye a los otros dos:
|Ñ|_|Z|Y|X|W|V|U|T|S|R|Q|P|O|N|M|L|K|J|I|H|G|F|E|D|C|BA|
Se ordena de nuevo. Como el nodo [BA] es ahora el de mayor frecuencia pasa a ser el primero de la lista:
|BA|Ñ|_|Z|Y|X|W|V|U|T|S|R|Q|P|O|N|M|L|K|J|I|H|G|F|E|D|C|
Se repite el proceso.
Pedazo de texto me ha salido. Ustedes perdonen. :)
Un saludo.
Emparejamientos reloaded
SkAsI17 Noviembre 2010 - 3:37pm
Paso a comentar las rarezas que mencionas:
Es normal, ya que justo las letras de la primera clave (huffman) tienen una frecuencia de aparición superior a las que no están que tienen frecuencia 1. No veo problemas aquí.
Esto es correcto, al ser un número de parejas impar, el último queda descolgado en el grupo siguiente, no veo problemas.
Correcto, tampoco veo problemas aquí.
La respuesta a tu pregunta es que pensaba que el algoritmo de Huffman no iba a dar estos problemas y que iba a ser algo más estándar (cosa que se ha demostrado rotundamente falsa). El descubrimiento del algoritmo era una parte de la caja negra, pero como no quiero que os desaniméis por una cosa que es culpa de mi poca previsión, prefiero ayudar con esta parte. No obstante, una vez que se generen los árboles, aún no se ha descifrado nada de nada.
El ejemplo que muestras está bien en el algoritmo que muestras, pero te olvidas de las frecuencias para ordenar. Pones como nodos iniciales:
|Ñ|_|Z|Y|X|W|V|U|T|S|R|Q|P|O|N|M|L|K|J|I|H|G|F|E|D|C|B|A|
Cuando tendrían que ser:
|3F|2U|2N|2M|2H|2A|1Ñ|1_|1Z|1Y|1X|1W|1V|1T|1S|1R|1Q|1P|1O|1L|1K|1J|1I|1G|1E|1D|1C|1B|
Así, el primer paso que se da es:
|3F|2U|2N|2M|2H|2A|2(CB)|1Ñ|1_|1Z|1Y|1X|1W|1V|1T|1S|1R|1Q|1P|1O|1L|1K|1J|1I|1G|1E|1D|
Y así se continúa sucesivamente.
Partiendo de este segundo alfabeto y teniendo en cuenta en todo momento las frecuencias de los nodos, tendría que salirte la misma codificación que yo he puesto.
Espero vuestras noticias, ánimo. Kriptosaludos.
PD: Si hace falta, puedo poner el ejemplo que indico aquí completo de cabo a rabo si lo consideráis necesario.
Persevero
DEDDS18 Noviembre 2010 - 10:05am
Quiero agradecerte la paciencia que tienes con nosotros. Como digo en el título, persevero en mis intentos.
Un saludo.
Yo también
Agustín16 Noviembre 2010 - 9:58pm
Yo también lo veo así, por lo que he leído, aunque la ordenación de partida era por orden de frecuencias y alfabético, ambos crecientes. Y el árbol mayor se colocaba siempre a la derecha.
De todas maneras, da igual. Vale lo que acordemos, pero tengo que retocar los procedimientos
Gracias, SkAsI
Agustín16 Noviembre 2010 - 12:13pm
por enseñarnos el Huffman ese. Ya sabemos crear el árbol y los códigos. Aún hay divergencias. Me gustaría que mostraras el árbol, además de los códigos, porque en mi caso creo que lo ordeno mal.
Mensaje
ABCDEFGHIJKLMNÑOPQRSTUVWXYZ_HUFFMAN
Árbol
[35 [17 [6 [4 [2 A] [2 H]] [2 [1 _] [1 Ñ]]] [11 [4 [2 [1 Y] [1 Z]] [2 [1 W] [1 X]]] [7 [5 [2 U] [3 F]] [2 [1 T] [1 V]]]]] [18 [10 [4 [2 [1 R] [1 S]] [2 [1 P] [1 Q]]] [6 [4 [2 M] [2 N]] [2 [1 L] [1 O]]]] [8 [4 [2 [1 J] [1 K]] [2 [1 G] [1 I]]] [4 [2 [1 D] [1 E]] [2 [1 B] [1 C]]]]]]
Para aclararnos:
35
17 - 18 (creo que debería ser al revés
6 11 - 10 8
etc.
(Sí creo que está mal ordenado)
Códigos
[_ 0010 A 0000 B 11110 C 11111 D 11100 E 11101 F 01101 G 11010 H 0001 I 11011 J 11000 K 11001 L 10110 M 10100 N 10101 Ñ 0011 O 10111 P 10010 Q 10011 R 10000 S 10001 T 01110 U 01100 V 01111 W 01010 X 01011 Y 01000 Z 01001]
Creo que tengo un problema de CASEIGNORE. A veces considera "_" anterior a la "A".
Y creo que tego el árbol ordenado al revés.
Pero también es UN huffman, ¿no?
MUY optimista
DEDDS16 Noviembre 2010 - 9:21am
Pero eso no va a impedir que al final nos aclaremos (y aprendamos, que es de lo que se trata).
Con el nuevo alfabeto la codificación de las letras cambia ligeramente, pero sigo obteniendo longitudes máximas de 5 bits. Eso significa que todavia hay algo que no hago bien. :(
Pongo la nueva codificación para ver si avanzamos un poco.
[H:00000] [A:00001] [F:0001] [Ñ:00100] [_:00101] [Z:00110] [Y:00111]
[X:01000] [W:01001] [V:01010] [T:01011] [S:01100] [R:01101] [Q:01110]
[P:01111] [O:10000] [L:10001] [K:10010] [J:10011] [I:10100] [G:10101]
[E:10110] [D:10111] [C:11000] [B:11001] [U:1101] [N:1110] [M:1111]
Se me ha ocurrido también que, a la vista de las desavenencias, a lo mejor tendríamos que intentar las pruebas empezando por un texto más corto y si vemos que va bien ir aumentando progresivamente la longitud (o el número de letras diferentes). ¿Como lo ves, SkAsI?.
Un saludo.
P.S.- No nos hemos olvidado del criptoreto, pero de momento podemos dejarlo hibernado hasta que resolvamos estas "pequeñas dificultades iniciales". :P
Emparejamientos
SkAsI16 Noviembre 2010 - 11:51am
Me parece bien la idea de dejar la criptografía a un lado de momento pero mi intención es que no os aburrais antes de llegar a ella. Voy a poner la lista de emparejamientos que voy obteniendo para ver si así vamos avanzando un poco más. Primero el nodo izquierdo y después el derecho, Recordar que de la lista de nodos pendientes, se coge el menor como hijo derecho y después se vuelve a coger el menor de los que queden como hijo izquierdo, por eso el hijo derecho siempre es menor que el izquierdo:
1. childL: (1, u'C') ; childR: (1, u'B')
2. childL: (1, u'E') ; childR: (1, u'D')
3. childL: (1, u'I') ; childR: (1, u'G')
4. childL: (1, u'K') ; childR: (1, u'J')
5. childL: (1, u'O') ; childR: (1, u'L')
6. childL: (1, u'Q') ; childR: (1, u'P')
7. childL: (1, u'S') ; childR: (1, u'R')
8. childL: (1, u'V') ; childR: (1, u'T')
9. childL: (1, u'X') ; childR: (1, u'W')
10. childL: (1, u'Z') ; childR: (1, u'Y')
11. childL: (1, u'\xd1') ; childR: (1, u'_')
Hasta aquí los terminales, vamos con no terminales:
12. childL: (2, (1, u'E'), (1, u'D')) ; childR: (2, (1, u'C'), (1, u'B'))
13. childL: (2, (1, u'K'), (1, u'J')) ; childR: (2, (1, u'I'), (1, u'G'))
14. childL: (2, (1, u'Q'), (1, u'P')) ; childR: (2, (1, u'O'), (1, u'L'))
15. childL: (2, (1, u'V'), (1, u'T')) ; childR: (2, (1, u'S'), (1, u'R'))
16. childL: (2, (1, u'Z'), (1, u'Y')) ; childR: (2, (1, u'X'), (1, u'W'))
Hasta aquí hemos comparado no terminales iguales, diferenciándolos por el nodo izquierdo. El siguiente caso empareja terminal y no terminal (recordad que no terminal es menor que terminal):
17. childL: (2, u'A') ; childR: (2, (1, u'\xd1'), (1, u'_'))
18. childL: (2, u'M') ; childR: (2, u'H')
19. childL: (2, u'U') ; childR: (2, u'N')
A partir de aquí más de lo mismo, comparaciones entre no terminales y no terminales. Se va comparando en depth-first por el nodo izquierdo hasta encontrar una comparación terminal-no_terminal o una terminal-terminal:
20. childL: (4, (2, (1, u'E'), (1, u'D')), (2, (1, u'C'), (1, u'B'))) ; childR: (3, u'F')
21. childL: (4, (2, (1, u'Q'), (1, u'P')), (2, (1, u'O'), (1, u'L'))) ; childR: (4, (2, (1, u'K'), (1, u'J')), (2, (1, u'I'), (1, u'G')))
22. childL: (4, (2, (1, u'Z'), (1, u'Y')), (2, (1, u'X'), (1, u'W'))) ; childR: (4, (2, (1, u'V'), (1, u'T')), (2, (1, u'S'), (1, u'R')))
23. childL: (4, (2, u'M'), (2, u'H')) ; childR: (4, (2, u'A'), (2, (1, u'\xd1'), (1, u'_')))
24. childL: (7, (4, (2, (1, u'E'), (1, u'D')), (2, (1, u'C'), (1, u'B'))), (3, u'F')) ; childR: (4, (2, u'U'), (2, u'N'))
25. childL: (8, (4, (2, (1, u'Z'), (1, u'Y')), (2, (1, u'X'), (1, u'W'))), (4, (2, (1, u'V'), (1, u'T')), (2, (1, u'S'), (1, u'R')))) ; childR: (8, (4, (2, (1, u'Q'), (1, u'P')), (2, (1, u'O'), (1, u'L'))), (4, (2, (1, u'K'), (1, u'J')), (2, (1, u'I'), (1, u'G'))))
26. childL: (11, (7, (4, (2, (1, u'E'), (1, u'D')), (2, (1, u'C'), (1, u'B'))), (3, u'F')), (4, (2, u'U'), (2, u'N'))) ; childR: (8, (4, (2, u'M'), (2, u'H')), (4, (2, u'A'), (2, (1, u'\xd1'), (1, u'_'))))
27. childL: (19, (11, (7, (4, (2, (1, u'E'), (1, u'D')), (2, (1, u'C'), (1, u'B'))), (3, u'F')), (4, (2, u'U'), (2, u'N'))), (8, (4, (2, u'M'), (2, u'H')), (4, (2, u'A'), (2, (1, u'\xd1'), (1, u'_'))))) ; childR: (16, (8, (4, (2, (1, u'Z'), (1, u'Y')), (2, (1, u'X'), (1, u'W'))), (4, (2, (1, u'V'), (1, u'T')), (2, (1, u'S'), (1, u'R')))), (8, (4, (2, (1, u'Q'), (1, u'P')), (2, (1, u'O'), (1, u'L'))), (4, (2, (1, u'K'), (1, u'J')), (2, (1, u'I'), (1, u'G')))))
Y por último el árbol final completo:
F. (35, (19, (11, (7, (4, (2, (1, u'E'), (1, u'D')), (2, (1, u'C'), (1, u'B'))), (3, u'F')), (4, (2, u'U'), (2, u'N'))), (8, (4, (2, u'M'), (2, u'H')), (4, (2, u'A'), (2, (1, u'\xd1'), (1, u'_'))))), (16, (8, (4, (2, (1, u'Z'), (1, u'Y')), (2, (1, u'X'), (1, u'W'))), (4, (2, (1, u'V'), (1, u'T')), (2, (1, u'S'), (1, u'R')))), (8, (4, (2, (1, u'Q'), (1, u'P')), (2, (1, u'O'), (1, u'L'))), (4, (2, (1, u'K'), (1, u'J')), (2, (1, u'I'), (1, u'G'))))))
Dicho árbol genera los siguientes códigos:
[A:0110] [C:000010] [B:000011] [E:000000] [D:000001] [G:11111] [F:0001]
[I:11110] [H:0101] [K:11100] [J:11101] [M:0100] [L:11011] [O:11010]
[N:0011] [Ñ:01110] [P:11001] [S:10110] [R:10111] [U:0010] [T:10101]
[W:10011] [V:10100] [Y:10001] [X:10010] [Z:10000] [_:01111] [Q:11000]
Espero que con esto podamos converger a una implementación común para todos.
Kriptosaludos.
¿Aburrirnos?
DEDDS16 Noviembre 2010 - 2:25pm
Ju, ju, ju... con lo interesante que está esto y lo bien que escurre las meninges no creo que eso vaya a ocurrir. ;)
Necesito "un ratito" para mirar el árbol que has puesto, asi que paciencia compañero.
Un saludo.
Las normas
Agustín15 Noviembre 2010 - 1:22pm
Como a otros compañeros, no me salen los mismos códigos. Vamos a repasar las normas.
Para empezar, según lo que he leído por ahí, ordeno las letras por dos cirterios:
1. Su frecuencia
2. Su orden alfabético creciente (A < B)
En mi entorno de programación "_" < "A", ¿es correcto?
Y la "Ñ" ¿habrá que introducirla "a mano" entre la "N" y la "O"?
1. Comparación por frecuencia.
OK. Nada que objetar
2. A igual frecuencia, aplican las siguientes reglas:
2a. Comparando un terminal con otro, se compara lexicograficamente (es decir 'A' menor que 'B').
OK. Nada que objetar
2b. Comparando un terminal con un no terminal (un subarbol), no terminal menor que terminal.
¿Pero esto se hace sin profundizar en el sub-árbol? Es decir, si tengo dos nodos como
[15 C] y [15 [12 A][3 A]]
¿he de tomar como menor a [15 C]?
2c. Comparando no terminal con no terminal, se compara primero el hijo izquierdo con el hijo izquierdo y después el hijo derecho con el hijo derecho aplicando las reglas 1, 2a y 2b.
Si tengo los nodos
[15 [12 X][3 B]] y [15 [12 A][3 [2 C][1 D]]
en el siguiente paso tendremos que comparar
[12 X] con [12 A]
por un lado, y
[3 B] con [3 [2 C][1 D]]
por el otro. La pregunta es ¿Debo considerar como menor el primer nodo porque X < A, o mayor, porque [3 B] es terminal?
Una vez tenemos claras las reglas de ordenación, veamos como construye mi algoritmo el árbol:
1. Coge el menor nodo como hijo derecho.
2. Coge el menor nodo como hijo izquierdo.
Yo creía que era al revés, los menores por la izquierda
etc...
Ya sé, ya sé, qué ignorante soy. Pero es lo que hay.
Más aclaraciones
SkAsI15 Noviembre 2010 - 2:09pm
Puff, si que va a ser complicado esto del Huffman, y eso que no pretendía que lo fuera. Voy a seguir con las aclaraciones, que entre las que se me olvidaron y las nuevas que veo, lo veo muy necesario.
Lo primero de todo es que se me olvidó colocar el alfabeto según lo ordeno yo:
ABCDEFGHIJKLMNOPQRSTUVWXYZ_Ñ
Duda 1:
[15 C] y [15 [12 A][3 A]]
Aplicando 2b, no terminal ([15 [12 A][3 A]]) es menor que terminal ([15 C]). Sin entrar a comparar nada más. Sólo en el caso de tratar con elementos del mismo tipo, sean terminales o no terminales, es cuando aplicamos las reglas 2a y 2c respectivamente.
Duda 2:
[15 [12 X][3 B]] y [15 [12 A][3 [2 C][1 D]]
Aplicando 2c, tenemos que comparar los hijos izquierdos primero (supongo que son los que indico a continuación):
[12 X] y [12 A]
Aplicando 2a tenemos que [12 A] es menor que [12 X] y ahí terminaría la comparación.
Duda 3:
Es una cuestión de implementación, la verdad es que no me planteé implementar un algoritmo "puro", así que puede que no sea el algoritmo estándar Huffman, pero desde luego es "un" algoritmo Huffman.
Kriptosaludos.
Optimista
Agustín15 Noviembre 2010 - 6:58pm
Es que tú no sabes las cosas que algunos podemos llegar a no saber. Como decía usrdxt Me parece complicado hasta atarme los cordones. Por eso uso mocasines, je je.
Las normas "revisited"
DEDDS15 Noviembre 2010 - 1:58pm
Yo no lo he considerado de esa forma, puesto que siempre hemos puesto el "_" detrás de la "Z" (esto es, al final del alfabeto), por lo que ahora pasa a ser el mayor de todos.
Yo para este caso no veo dificultad en hacerlo así.
Si te das cuenta, estamos ordenando siempre al revés, es decir, mayor a la izquierda y menor a la derecha.
Un saludo.
Ley y Orden
DEDDS15 Noviembre 2010 - 9:56am
Se me ha ocurrido que a lo mejor era interesante poner el orden en el que se van comparando las letras/grupos de letras por frecuencias a medida que avanzan las comparaciones, según las leyes dictadas por SkAsI, así que ahí van.
|F|U|N|M|H|A|_|Z|Y|X|W|V|T|S|R|Q|P|O|Ñ|L|K|J|I|G|E|D|C|B|
|F|CB|U|N|M|H|A|_|Z|Y|X|W|V|T|S|R|Q|P|O|Ñ|L|K|J|I|G|E|D|
|F|ED|CB|U|N|M|H|A|_|Z|Y|X|W|V|T|S|R|Q|P|O|Ñ|L|K|J|I|G|
|F|IG|ED|CB|U|N|M|H|A|_|Z|Y|X|W|V|T|S|R|Q|P|O|Ñ|L|K|J|
|F|KJ|IG|ED|CB|U|N|M|H|A|_|Z|Y|X|W|V|T|S|R|Q|P|O|Ñ|L|
|F|ÑL|KJ|IG|ED|CB|U|N|M|H|A|_|Z|Y|X|W|V|T|S|R|Q|P|O|
|F|PO|ÑL|KJ|IG|ED|CB|U|N|M|H|A|_|Z|Y|X|W|V|T|S|R|Q|
|F|RQ|PO|ÑL|KJ|IG|ED|CB|U|N|M|H|A|_|Z|Y|X|W|V|T|S|
|F|TS|RQ|PO|ÑL|KJ|IG|ED|CB|U|N|M|H|A|_|Z|Y|X|W|V|
|F|WV|TS|RQ|PO|ÑL|KJ|IG|ED|CB|U|N|M|H|A|_|Z|Y|X|
|F|YX|WV|TS|RQ|PO|ÑL|KJ|IG|ED|CB|U|N|M|H|A|_|Z|
|F|_Z|YX|WV|TS|RQ|PO|ÑL|KJ|IG|ED|CB|U|N|M|H|A|
|HA|F|_Z|YX|WV|TS|RQ|PO|ÑL|KJ|IG|ED|CB|U|N|M|
|NM|HA|F|_Z|YX|WV|TS|RQ|PO|ÑL|KJ|IG|ED|CB|U|
|CBU|NM|HA|F|_Z|YX|WV|TS|RQ|PO|ÑL|KJ|IG|ED|
|IGED|CBU|NM|HA|F|_Z|YX|WV|TS|RQ|PO|ÑL|KJ|
|ÑLKJ|IGED|CBU|NM|HA|F|_Z|YX|WV|TS|RQ|PO|
|RQPO|ÑLKJ|IGED|CBU|NM|HA|F|_Z|YX|WV|TS|
|WVTS|RQPO|ÑLKJ|IGED|CBU|NM|HA|F|_Z|YX|
|_ZYX|WVTS|RQPO|ÑLKJ|IGED|CBU|NM|HA|F|
|HAF|_ZYX|WVTS|RQPO|ÑLKJ|IGED|CBU|NM|
|CBUNM|HAF|_ZYX|WVTS|RQPO|ÑLKJ|IGED|
|ÑLKJIGED|CBUNM|HAF|_ZYX|WVTS|RQPO|
|WVTSRQPO|ÑLKJIGED|CBUNM|HAF|_ZYX|
|HAF_ZYX|WVTSRQPO|ÑLKJIGED|CBUNM|
|ÑLKJIGEDCBUNM|HAF_ZYX|WVTSRQPO|
|HAF_ZYXWVTSRQPO|ÑLKJIGEDCBUNM|
|HAF_ZYXWVTSRQPOÑLKJIGEDCBUNM|
La primera línea son las letras ordenadas por frecuencia de mayor a menor.
En la segunda línea vemos colocado en su sitio el par "CB" en función de la suma de sus frecuencias.
Y así sucesivamente.
Espero que sea útil.
Un saludo.
¡Por fin!
DEDDS15 Noviembre 2010 - 9:33am
Ya he podido construir un árbol para el ejemplo "ABCDEFGHIJKLMNÑOPQRSTUVWXYZ_HUFFMAN". Pero al igual que a sqrmatrix no me salen los mismos códigos que a SkAsI (curiosamente yo también obtengo el código más largo de 5 bits).
Los pongo a continuación para que podamos compararlos.
[H:00000][A:00001][F:0001][_:00100][Z:00101][Y:00110][X:00111]
[W:01000][V:01001][T:01010][S:01011][R:01100][Q:01101][P:01110]
[O:01111][Ñ:10000][L:10001][K:10010][J:10011][I:10100][G:10101]
[E:10110][D:10111][C:11000][B:11001][U:1101][N:1110][M:1111]
Un saludo.
El árbol
Agustín13 Noviembre 2010 - 5:24pm
Para el mensaje
ESTO_ES_SOLO_UN_EJEMPLO_SENCILLO_DE_CRIPTOGRAFIA_CASERA_
Obtengo este árbol (notación LISP-LOGO)
56 [24 [11 [S 5] [6 [C 3] [I 3]]] [13 [O 6] [7 [R 3] [4 [P 2] [T 2]]]]] [32 [15 [E 7] [8 [A 4] [L 4]]] [17 [8 [4 [2 [D 1] [F 1]] [N 2]] [4 [2 [M 1] [U 1]] [2 [G 1] [J 1]]]] [_ 9]]]
Ahora a por los códigos.(* Reedición:
Puede verse que el código de "_" será "1" ¿OK?
*)P.S.
Estamos aprendiendo. No te impacientes.
Aclaraciones
SkAsI12 Noviembre 2010 - 1:17pm
Voy a aclarar algunos puntos de como he empleado el algoritmo de Huffman, que parece que es lo que más quebraderos de cabeza está dando y no es ese justo el punto que quiero tratar en el reto. Lo primero, las reglas de comparación:
1. Comparación por frecuencia.
2. A igual frecuencia, aplican las siguientes reglas:
2a. Comparando un terminal con otro, se compara lexicograficamente (es decir 'A' menor que 'B').
2b. Comparando un terminal con un no terminal (un subarbol), no terminal menor que terminal.
2c. Comparando no terminal con no terminal, se compara primero el hijo izquierdo con el hijo izquierdo y después el hijo derecho con el hijo derecho aplicando las reglas 1, 2a y 2b.
Una vez tenemos claras las reglas de ordenación, veamos como construye mi algoritmo el árbol:
1. Coge el menor nodo como hijo derecho.
2. Coge el menor nodo como hijo izquierdo.
3. Construye un nodo no terminal compuesto de la suma de frecuencias de los hijos, el hijo izquierdo y el hijo derecho.
4. Vuelve a 1 mientras quede más de un nodo.
Por último recordar que el hijo izquierdo es '0' al seguir el árbol hasta los terminales y el hijo derecho es '1'.
Podeis ayudaros del ejemplo (ABCDEFGHIJKLMNÑOPQRSTUVWXYZ_HUFFMAN) que puse para ver si seguis bien las reglas o no.
Kriptosaludos.
Algo no me cuadra
sqrmatrix13 Noviembre 2010 - 1:09pm
No me salen los mismos códigos que en el ejemplo con "ABCDEFGHIJKLMNÑOPQRSTUVWXYZ_HUFFMAN". Esto puede achacarse a un error mío. El problema es que la máxima longitud de códigos que obtengo es de 5, mientras que en el ejemplo es de 6. Si codificásemos la cadena con la codificación dada en el ejemplo, obtenemos un código de 162 bits, mientras que con los códigos que he obtenido es de 152 (estos cálculos, si no me he equivocado). Se me ocurren dos posibilidades: o bien la implementación que has hecho de la codificación Huffman no es del todo correcta, o bien este supuesto error forma parte del criptosistema (esto último lo digo por la frase que pusiste en el ejemplo: "Espero arrojar más luz que oscuridad con esta información", que no sé si interpretarla como una pista más).
Con ese ejemplo
usrdxt13 Noviembre 2010 - 2:43pm
la B aparece 1 vez con el código 111110 y la D otra vez con el código 111111, por lo menos en mis cálculos, que no sé si serán correctos.
Menor que
DEDDS12 Noviembre 2010 - 2:22pm
Entiendo entonces por las explicaciones que el orden por frecuencias es
mayor frecuencia ------> menor frecuencia
y el orden alfabético es también inverso
_ZY ....... CBA
A ver si tengo un ratito y puedo trabajar con el ejemplo que has puesto.
Un saludo.
Despiste
Agustín11 Noviembre 2010 - 11:54pm
A ver si nos aclaramos. Una vez ordenadas las frecuencias del mensaje:
ESTO_ES_SOLO_UN_EJEMPLO_SENCILLO_DE_CRIPTOGRAFIA_CASERA_
[D 1] [F 1] [G 1] [J 1] [M 1] [U 1] [N 2] [P 2] [T 2] [C 3] [I 3] [R 3] [A 4] [L 4] [S 5] [O 6] [E 7] [_ 9]
obtendríamos el árbol y los códigos. Se puede imaginar que si añadimos una clave al texto, se modificaría todo. Es decir, si procesamos el mensaje
ESTO_ES_SOLO_UN_EJEMPLO_SENCILLO_DE_CRIPTOGRAFIA_CASERA_HUFFMAN
obtendremos otros códigos, que podría ser el mensaje cifrado. Lo que no veo es cómo podría el receptor "restar" las frecuencias de la clave. Por ello deduzco que este método no sirve. A menos que el árbol mantenga algún tipo de orden alfabético, es decir, no esté optimizado. Qué líoooo.
Una pequeña duda
DEDDS11 Noviembre 2010 - 10:56pm
Una vez que hemos calculado las frecuencias de las letras, las ordenamos de mayor a menor y empezamos a construir el "arbol de Huffman". Para ello empezamos tomando las dos menores y las sumamos. Vamos a tomar como base la última nota de usrdxt (con permiso del autor, por supuesto) y vemos que las dos últimas letras de la lista son "G" y "F", que tienen la misma frecuencia de aparición. Al sumar sus frecuencias para obtener un nuevo nodo, una de las letras será la rama izquierda y la otra la rama derecha. Y aquí viene la duda: ¿con que criterio?
Pongamos por caso que el malvado SkAsI haya seguido un criterio de ordenación alfabético (a frecuencias iguales, se entiende). Entonces usrdxt tendría una codificación equivocada porque su "G" correspondería con una "F" en el texto original.
Si vamos un paso más allá, podemos suponer que el nuevo nodo obtenido de la suma "GF" coincide en frecuencia, por ejemplo, con la letra "S". ¿Cual colocamos en la rama izquierda y cual en la derecha?
A mi modo de ver es algo que hay que tomar en consideración porque puede trastocar por completo cualquier cálculo que hagamos. ¡Y todavía no hemos empezado con la criptografía! ;-)
Perdón por el "tocho", pero espero haberme explicado un poco.
Un saludo.
P.S.- Por lo que he podido leer, parece universalmente aceptado que la rama izquierda se codifica con "0" (cero) y la rama derecha con "1" (uno). Pero... ¿quien dice que SkAsI lo haya hecho así?
Tienes permiso
usrdxt12 Noviembre 2010 - 12:08am
faltaría más ;)
Simplemente me he limitado a aportar eso. También puedo poner el árbol que he hecho yo, por si a alguien le vale.
Reto Huffman
SamC11 Noviembre 2010 - 2:56am
Los pares (letra y código) seria parecido a este, aún no comprendo que lógica se esta usando para la clave, si inteligencia intercepta otro mensaje tal vez las cosas sean mas claras.
Falta la Ñ, esto puede ser por la clave que la estaría moviendo a otra posición o... estoy realmente perdido?
Voy a dejar mi granito
usrdxt11 Noviembre 2010 - 2:22pm
que seguro que no vale para gran cosa, pero bueno, al final logré armar mi arbol. Si a alguien le sirve...
_ (9 apariciones, 111, 5f)
E (7 apariciones, 011, 45)
O (6 apariciones, 001, 4f)
S (5 apariciones, 000, 53)
L (4 apariciones, 1010, 4c)
A (4 apariciones, 1100, 41)
R (3 apariciones, 0100, 52)
C (3 apariciones, 0101, 43)
I (3 apariciones, 1000, 49)
N (2 apariciones, 10010, 4e)
T (2 apariciones, 10110, 54)
P (2 apariciones, 11011, 50)
U (1 aparicion, 100110, 55)
J (1 aparicion, 100111, 4a)
M (1 aparicion, 101110, 4d)
D (1 aparicion, 101111, 44)
G (1 aparicion, 110100, 47)
F (1 aparicion, 110101, 46)
Magnífico
Agustín11 Noviembre 2010 - 1:20pm
Aunque no sé lo que pensará SkAsIsKi. Pero yo tenía entendido que las letras más frecuentes requerían menos bits para su representación. Creo que me he vuelto a perder.
Tienes razón
SkAsI11 Noviembre 2010 - 2:09pm
La representación es variable, por eso funciona y comprime. La aportación de SamC deberá ser revisada, aunque me gusta empezar a ver actividad de la buena y primeros y tímidos resultados. Como ejemplo, vamos a ver los codigos Huffman para el texto:
Los códigos quedarían de la siguiente manera (siguiendo la sintaxis de SamC):
Espero arrojar más luz que oscuridad con esta información.
Kriptosaludos.