Codificación Huffman y RLE: Técnicas de Compresión de Datos

Codificación Huffman: Una Visión Detallada

La Codificación Huffman es un método general de codificación y compresión diseñado para minimizar el número medio de bits necesarios para transmitir un símbolo cuando se deben transmitir varias copias independientes y estadísticamente equivalentes de dicho símbolo. Este método determina cómo los distintos valores del símbolo deben representarse como cadenas binarias. Requiere no usar ningún tipo de separador entre los valores.

Supongamos que tenemos que enviar el símbolo X que puede tomar valores {x₁, ... xi} con probabilidad.

Ejemplo: x₁ (0.5), x₂ (0.3), x₃ (0.15), x₄ (0.05). Si se usan 00, 01, 10 y 11 necesitaremos siempre 2 bits para el valor de X. Si se usan las palabras 0, 10, 110, 111 necesitaremos como término medio 1.7 bits (menos de 2).

Pasos para la codificación Huffman:

1. Escoger los dos símbolos con probabilidad más pequeña: Xi, Xj
2. Se las reemplaza por e Y₀, Y₁
3. Se borra y de la lista y se añade con probabilidad.
4. Volver al paso 1 hasta finalizar.

Run Length Encoding (RLE): Compresión Eficiente para Señales FAX

Run Length Encoding (RLE) es el método para comprimir señales FAX más simple y más eficiente. Para transmitir una página FAX, la máquina escruta la página línea a línea midiendo la intensidad de la luz reflejada en puntos regularmente espaciados a lo largo de cada línea. Esto resulta en una secuencia de bits que indican si los puntos en las líneas son negros o blancos: 1 ó 0 respectivamente. Si la máquina da un barrido de 200 líneas por pulgada y mide 200 puntos por línea a lo largo de cada página, y si el tamaño de página es 8.5x11 pulgadas, se la representa por 200*200*8.5*11=3.73*10⁶ bits. Con un módem de 9600 bps se tardarían 6,5 minutos en enviarlo. Si lo podemos reducir 20 veces el número de bits, se tardarían 20 segundos. Para alcanzar este factor de compresión, la máquina transmite el número de 0s sucesivos entre dos 1s en vez de una larga secuencia de 0s. Por ejemplo, la cadena 10ⁱ10ⁱ10ⁱ10ⁱ con 0 representando i ceros consecutivos se codifica como ABCDi donde I es la representación binaria de i. Luego si i=600 entonces A=1001011000 y 600 ceros se reemplazan por 10 bits.