Antes de empezar a hablar de los distintos algoritmos y códigos de compresión de datos, es importante destacar que existen principalmente tres tipologías de compresión de la información:
Sin pérdidas reales: es decir, transmitiendo toda la entropía del mensaje (toda la información básica e irrelevante, pero eliminando la redundante).
Subjetivamente sin pérdidas: es decir, además de eliminar la información redundante se elimina también la irrelevante.
Subjetivamente con pérdidas: se elimina cierta cantidad de información básica, por lo que el mensaje se reconstruirá con errores perceptibles pero tolerables.
Habiendo aclarado esto, se puede introducir los principales algoritmos y códigos de compresión que se emplean en la actualidad:
- Algoritmo de Huffman
El código de Huffman se refiere al uso de una tabla de códigos de longitud variable para codificar un determinado símbolo (como puede ser un carácter en un archivo), donde la tabla ha sido rellenada de una manera específica basándose en la probabilidad estimada de aparición de cada posible valor de dicho símbolo.
Ahora bien, el algoritmo de Huffman toma un alfabeto de n símbolos, junto con sus frecuencias de aparición asociadas, y produce un código de Huffman para ese alfabeto y esas frecuencias.
Para hacerlo se basa en 3 pasos:
1. Se crean varios árboles, uno por cada uno de los símbolos del alfabeto, consistiendo cada uno de los árboles en un nodo sin hijos, y etiquetado cada uno con su símbolo asociado y su frecuencia de aparición.
2. Se toman los dos árboles de menor frecuencia, y se unen creando un nuevo árbol. La etiqueta de la raíz será la suma de las frecuencias de las raíces de los dos árboles que se unen, y cada uno de estos árboles será un hijo del nuevo árbol. También se etiquetan las dos ramas del nuevo árbol: con un 0 la de la izquierda, y con un 1 la de la derecha.
3. Se repite el paso 2 hasta que sólo quede un árbol.
- Algoritmo LZW:
La clave del método LZW reside en que es posible crear sobre la marcha, de manera automática y en una única pasada un diccionario de cadenas que se encuentren dentro del texto a comprimir mientras al mismo tiempo se procede a su codificación. Dicho diccionario no es transmitido con el texto comprimido, puesto que el descompresor puede reconstruirlo usando la misma lógica con que lo hace el compresor y, si está codificado correctamente, tendrá exactamente las mismas cadenas que el diccionario del compresor tenía.
El diccionario comienza pre-cargado con 256 entradas, una para cada carácter (byte) posible más un código predefinido para indicar el fin de archivo. A esta tabla se le van agregando sucesivos códigos numéricos por cada nuevo par de caracteres consecutivos que se lean (esto no es literalmente cierto, según se describe más adelante), aun cuando todavía no sea posible prever si ese código se reutilizará más adelante o no.
- Codificación RLE
La codificación RLE o “Run Length encoding” realizan una lectura en zig-zag de la matriz de símbolos. Utiliza un método de lectura en diagonal en lugar de recorrerlo por filas o columnas como sería lo habitual. RLE realiza una búsqueda de series consecutivas de solo un símbolo dentro de una trama. Posteriormente sustituye la serie por una única instancia del símbolo y un contador con la cantidad de repeticiones.
- Codificación VLC
Se trata de un caso particular de codificación aritmética. La idea básica de los códigos de longitud variable es asignar códigos de palabras de longitudes diferentes en función de la probabilidad de los mensajes. Los mensajes menos probables se codificarán con un mayor nombre de bits que no los mensajes más probables.
-Compresión JPEG
El formato JPEG utiliza habitualmente un algoritmo de compresión con pérdida para reducir el tamaño de los archivos de imágenes. Esto significa que al descomprimir o visualizar la imagen no se obtiene exactamente la misma imagen de la que se partía antes de la compresión.
El algoritmo de compresión JPEG se basa en dos fenómenos visuales del ojo humano: uno es el hecho de que es mucho más sensible al cambio en la luminancia que en la crominancia; es decir, capta más claramente los cambios de brillo que de color. El otro es que nota con más facilidad pequeños cambios de brillo en zonas homogéneas que en zonas donde la variación es grande, por ejemplo en los bordes de los cuerpos de los objetos.
-DCT: Discrete Cosine Transform
La transformada de coseno discreta expresa una secuencia finita de varios puntos como resultado de la suma de distintas señales sinusoidales (con distintas frecuencias y amplitudes). Como la transformada discreta de Fourier (abreviada, DFT) la DCT trabaja con una serie de números finitos, pero mientras la DCT solo trabaja con cosenos la DFT lo hace con exponenciales complejos.
Características útiles para la compresión de imágenes:
· La DCT tiene una buena capacidad de compactación de la energía al dominio transformado, es decir, que la transformada de coseno discreta consigue concentrar la mayor parte de la información en pocos coeficientes transformados tal y como muestra la imagen.
· La transformación es independiente de los datos. El algoritmo aplicado no varia con los datos que recibe, como si sucede en otros algoritmos de compresión.
· Produce pocos errores en los límites de los bloques imagen. La minimización de los errores a los bloques imagen permite reducir el efecto de bloque en las imágenes reconstruidas.
· Tiene una interpretación frecuencial de los componentes transformados. La capacidad de interpretar los coeficientes en el punto de vista frecuencial permite aprovechar al máximo la capacidad de compresión.