Aquí hay un desglose de los métodos comunes de compresión binaria sin pérdidas:
1. Identificación de redundancia y patrones:
* Repetición: La forma más simple. Si el mismo byte o secuencia de bytes se repite varias veces, el algoritmo los reemplaza con un marcador que indica la secuencia repetida y el número de repeticiones. Esto a menudo se llama codificación de longitud de ejecución (RLE) . Por ejemplo:
* Original:`aaaaabbbcccdd`
* RLE comprimido:`5A3B3C2D` (5 A, 3 B's, 3 C, 2 D'S)
* RLE es más efectivo cuando hay largas ejecuciones de los mismos datos.
* Compresión basada en diccionario: Este método construye un diccionario (o tabla) de secuencias de bytes frecuentes. En lugar de almacenar la secuencia completa cada vez, el algoritmo almacena el índice (o código) que representa esa secuencia en el diccionario.
* LZ77 y LZ78 (y sus variantes LZW, desinflar): Estos son algoritmos basados en el diccionario de piedra angular. Funcionan manteniendo una ventana deslizante de datos vistos recientemente.
* LZ77: Busca secuencias coincidentes * dentro de * la ventana deslizante. Cuando encuentra una coincidencia, almacena un `(distancia, longitud)` par, donde:
* `Distancia`:¿Qué tan lejos en la ventana comienza la coincidencia?
* `Longitud`:cuánto tiempo es la secuencia coincidente.
* LZ78: Construye un diccionario de * nuevas * frases a medida que las encuentre. Codifica cada nueva frase como `(índice, carácter)`, donde:
* `índice`:el índice del prefijo * más largo * de la frase que ya está en el diccionario.
* `Carácter`:el personaje que extiende el prefijo para crear la nueva frase.
* LZW (Lempel-Ziv-Welch): Una mejora de LZ78. Comienza con un diccionario preinicializado que contiene todos los personajes individuales. Construye el diccionario dinámicamente a medida que procesa los datos. LZW es famoso por ser utilizado en el formato de imagen GIF (aunque las patentes en LZW causaron problemas por un tiempo).
* Deflar: Combina LZ77 con Huffman Coding (explicada a continuación) para una compresión aún mejor. Se usa en GZIP, ZLIB y PNG. Es muy común.
2. Codificación estadística (codificación de entropía):
* Estos métodos analizan la frecuencia de diferentes símbolos (bytes) en los datos y asignan códigos más cortos a símbolos más frecuentes y códigos más largos a los menos frecuentes. Esto se basa en la teoría de la información, donde los eventos más probables requieren menos información para transmitir.
* Codificación de Huffman: Un esquema de codificación de longitud variable. Construye un árbol binario basado en las frecuencias de los símbolos. Los símbolos más frecuentes se colocan más cerca de la raíz del árbol, lo que resulta en longitudes de código más cortas.
* El algoritmo genera un código de prefijo, lo que significa que ningún código es un prefijo de otro código, evitando la ambigüedad durante la decodificación.
* codificación aritmética: Representa todo el flujo de datos como un número fraccional único entre 0 y 1. La longitud de la fracción está determinada por las probabilidades de los símbolos. La codificación aritmética a menudo logra una mejor compresión que la codificación de Huffman, especialmente cuando se trata de símbolos que tienen probabilidades muy diferentes. Sin embargo, es más intensivo computacionalmente.
Ejemplo ilustrativo (simplificado):
Imagine que tenemos los siguientes datos:`aabbccccaadddeeefff`
1. RLE: Podría comprimir a `2a3b3c2a3d3e4f` (lo reduce, pero no drásticamente).
2. Huffman Coding:
* Análisis de frecuencia:
* A:5
* B:3
* C:3
* D:3
* E:3
* F:4
* Construcción de árboles de Huffman (ejemplo):
* Combinar menos frecuente:B (3) y C (3) -> Nodo BC (6)
* Combinar D (3) y E (3) -> Nodo de (6)
* Combine BC (6) y De (6) -> Nodo BCDE (12)
* Combinar F (4) y A (5) -> Nodo AF (9)
* Combinar AF (9) y BCDE (12) -> Root (21)
* Asignar códigos (0 para izquierda, 1 para atravesar el árbol) - * ¡Esto puede variar según la implementación! *
* A:00
* B:100
* C:101
* D:110
* E:111
* F:01
* Datos comprimidos:`0000100100100101101101101111111110101010101 (mucho más corto que el original, ¡especialmente para conjuntos de datos grandes!)
Consideraciones clave:
* Complejidad: Diferentes algoritmos tienen diferentes complejidades computacionales. Algunos son más rápidos para codificar/decodificar, pero logran relaciones de compresión más bajas. Otros son más lentos pero logran una mayor compresión.
* Relación de compresión: La relación del tamaño del archivo original al tamaño de archivo comprimido. Una relación más alta indica una mejor compresión.
* Uso de la memoria: Los algoritmos requieren memoria para buffers, diccionarios y estructuras de árboles. El uso de la memoria puede ser un factor limitante, especialmente al comprimir archivos grandes.
* Tipo de datos: Algunos algoritmos son más adecuados para tipos específicos de datos (por ejemplo, texto, imágenes, audio). Por ejemplo, los algoritmos que explotan la localidad espacial son buenos para las imágenes.
En resumen, los algoritmos de compresión binarios funcionan por:
1. Análisis de los datos: Identificación de patrones, repeticiones y frecuencias estadísticas.
2. representando los datos de manera más eficiente: Uso de códigos más cortos para elementos comunes y códigos más largos para elementos raros.
3. Metadatos de almacenamiento: Almacenamiento de información necesaria para descomprimir los datos (por ejemplo, diccionarios, árboles de Huffman).
La elección del algoritmo depende de los requisitos específicos de la aplicación, incluida la relación de compresión deseada, los recursos computacionales disponibles y el tipo de datos que se están comprimiendo. A menudo, los enfoques híbridos (como la deflación) se utilizan para combinar las resistencias de diferentes técnicas.