Ejercicio:

Implementaremos en Java un codificador Huffmann de propósito general. Debe cumplir las siguientes especificaciones.

• Formato de entrada de datos:
• Tabla de símbolos originales: una estructura de datos 2xN que contenga N parejas de “símbolo” y su correspondiente probabilidad (en %).
• Formato de salida de datos:
• Tabla de traducción Huffmann: una estructura de datos 2xN que contenga N parejas en las que se indique el “símbolo original” y el nuevo código Huffmann asignado.
• Los códigos Huffmann serán binarios y se codificarán como una String binaria constituida por caracteres “1” y cero “0”.
Tareas:

a) Implementad el codificador Huffman descrito anteriormente y comprobad que el programa genera correctamente códigos Huffman válidos para el siguiente conjunto de símbolos (usados en el ejercicio anterior).
diamante = 30% ; K = 20% ; Q = 20% ; J = 15% ; 10 = 10% ; 9 = 5%

b) Modificad el programa para que a partir de una tabla de símbolos originales, sea capaz de traducir al código Huffman correspondiente un mensaje cualquiera que contenga únicamente ese conjunto de símbolos originales.
c) Generad ahora una secuencia larga y aleatoria que contenga los símbolos del apartado a) y codificadla en Huffmann mediante el algoritmo implementado en el apartado b). Ayuda: Podéis generar bits aleatorios con Math.round(Math.random()), pero aseguraos que los símbolos aparecen con la frecuencia/probabilidad prevista en la tabla de símbolos originales; si no, evidentemente la compresión no funcionará.
d) Ejecutad el programa con diversas secuencias aleatorias, suficientemente largas (>1000 símbolos). ¿Qué factor de compresión alcanzáis? ¿Qué relación tiene éste con la entropía calculada teóricamente para el conjunto de símbolos del apartado a)?

Ejemplo de run:

Symbol/Frequency table: {Q=0.2, D=0.3, T=0.1, 9=0.05, J=0.15, K=0.2}

Bits needed to encode each character without compression: 3
Entropy of this table: 2.408695

We are now Creating a Tree from the frequency table!
Those are the nodes of our tree:
Node 0, with frequency: 0.05, and Symbol: 9
Node 1, with frequency: 0.1, and Symbol: T
Node 2, with frequency: 0.15, and Symbol: J
Node 3, with frequency: 0.15
Node 4, with frequency: 0.2, and Symbol: Q
Node 5, with frequency: 0.2, and Symbol: K
Node 6, with frequency: 0.3
Node 7, with frequency: 0.3, and Symbol: D
Node 8, with frequency: 0.4
Node 9, with frequency: 0.6
Node 10, with frequency: 1.0

Resulting Code table of our tree: {Q=11, T=0100, D=00, 9=0101, J=011, K=10}

Bits needed after compression: 2.45


Sequence number 0: DDTKDDQQJDJKDJQJJQQ9KTDTQ9Q9DJJK9KJDKTDDDDDDKKDQDQKTQK9DD9JKQJQQQDKQDKKDKDQJJTKQTDKDKDDDKTKJQQDDQDDDJQJTKDKQDK9QQJQKDJDQJDJDQDKD9DJJKKDQDJQQDQKJDJDDDKKT9KKTKJQDJQQTDJKDKJDKDKQQKJDKKKQDJJDDDJDDJ9KQKDJDQDTQQQDDQK9QQDJJTD9DKQQDQKTDJKKDDDKQDDKJDKQKTTJDQDTQKKKDKDKDKQDJTTQDDKDKDDQDJQKTQKTDJDDT9JD9TTK99JD9QQKDKQJQDJKKQDKDKKQQQK9JQQKDKQDDDQQJTQDDDDQJDKTDQTDDKQDKDKJDQDJQJ9DDKDJDKKJQTDKDDDDKQDKKDDQDJDTDTQDTDQKJQKQDTDJJJDQDQJDDKD9JDJDKQJ9JJQK9DJJDDJDDDJDDDJQTKDTDDDKKDQKJDQQKKJQJKDJJDKTKKJDDQQKJTJ9DQQDKJDQKQKQJDDQQJD9JDDJDKKDKD9DDQQT9KJQQQJQJJKDTT9DDKKK9KQKQTDQDTK9JTDDDK9DKKDKJKDTQTTDKQ9JKJJDQKDKDQKKTDQ9QDKQJTKDDTDKQKQKDQJTDTKQDKQKQDDDJKTTQJJDKTQJDKQKKQ99JDQD9TDQJDDQDDDKKDJJQQ9KDQTDQJJDDKJDKKTDKKJDJDDKKKTQJTKDDKDTKDKDQTTDDQJTTKDDD9DDKQD9KKQJDKJDJQDQJJTQDJTTDDQ9TKKJTDD9DD9DQJQJDQDQDQ9QDDDJ9DDD9K9JJJDTTKTDKKQKJQDDKJDDJTDDDDKQTKDDKJDQJDDQKDDKKQKKDDQQJKTTDQKQDQDKJTJJDJDJDQDQDJQDDJKQKKD9KDQTDDQQKQQKDKJDQJQKDDJTDDDQDDDQQTKTDTQQDQQKDK9TJJDDKDD9DJQDKKDJJDQKDQKKQDJJJQJKQTKKKDKDQKDKKDDTTDJDJQKJKDDDQDQJTJJKJKQJJQJQDQKJDDKQQQJJKDJDJJJD9KJQKQQTDTQTDDTKK9QJDDTDQQDTJDQJQKJTJKQD9KQDDDJDDDKDDDD9JJDKQDDDKJKDTTQTKDT9K9JTKQ9KQQJJKKJ9J9JKQTDDQKJQDDTQ9QDKQQDDJJTDKJKDDDDJQDTDQJ9KDDKQQDTTKQKKTKTJDQTJ9DQQQKKJJTJD9DTQJ
Total bits needed before compression: 3600.0
New Sequence: 000001001000001111011000111000011110110111111010110010000010011010111010100011011100101100110010010000000000000010100011001110010011100101000001010111011011111111001011001010001000110110110100101101000010001000000010010010011111100001100000001111011010010001011001001011111011111000011001101100011001100100001010001101110100011000111111001110011000110000001010010001011010010010011110001111110100000111000100110010001011111001100101010110001101100000001100000110101101110000110011000100111111000011100101111100011011010000010100101111001110010000011101000000010110000100110010111001000100011001100010011101010001000100010110001101000100110000100010000011000111110010011100100000110000010001010110001010100010010010101010110001011111100010110111100011101011001000101011111110010101111111000101100000011110110100110000000011011001001000011010000001011001000100110011000111101101010000100001100101001111010000100000000010110010100000110001100010000010011000100001110011111011000100000110110110011001101100001000010101100011001011011010101101111100101000110110000011000000011000000011110100100001000000001010001110011001111101001111011100001101100100100101001100001111100110100011010100111100100110011101110110110000111101100010101100000110010100010000101000011110100010110011111111011110110111000010001000101000010101001011011101101000011000100100101011010000000010010100101000100111000010011010001000010110101011100110110011100010001110100100001101011100101101101001000000100001011101110001101101000001001011001011101100000001110010001001101101100100100110110010111010110101010101100110001010100001101100001100000010100001101111110101100011010000110110110000100110010100100001010011000110000101010010011011010010000010000100100010001101000100000011011010001001000000001010000101100010110101101100100110001111001101101101001100011010001000000110101010010100110100000001010000010100110111101100110011001101011100000001101010000000101100101011011011000100010010010000101011100111100001001100000110100000000001011010010000010011001101100001110000010101110100000111101110010001000011101100110010011010001101100011000110011001100011110000011101110100001011000110100000011111011111000100110011011111000000110100000000110000001111010010010000010011110011111000100101010001101100001000000101000111100101000011011001110001110101100011011011110111011010010101000100011100010100000010001000001100011111001110000000110011011010001101110011101101101111011110011100110000101111110110111000011000110110110001011001111101111010000010011010000000100101001011101100000100001111000100011001101111100110100011101100010110110000000110000001000000000010101101100101100000010011100001000100110100100001000101100101011010010110101101111011011101001101010110101011101101000000111001111000001001101011100101111000001101101000010011100000000001111000100001101101011000001011110001000100101110100100100100011001101000110101001111111010011011010001100010100010011011
Total bits after compression: 2934.0
Compression Ratio: 1.2269939