Codificación Huffman Clásica
🔒 VaultSec Bank — Sistema de Auditoría de TransaccionesVaultSec Bank registra eventos de auditoría en su plataforma de banca en línea. Cada evento se clasifica en una de cinco categorías. El equipo de TI ha analizado millones de registros y obtenido la siguiente distribución de probabilidades:
- LOGIN_OK — Autenticación exitosa: p = 0.40
- CONSULTA — Consulta de saldo o movimientos: p = 0.25
- TRANSFER — Transferencia procesada: p = 0.20
- SESION_EXP — Sesión expirada por inactividad: p = 0.10
- LOGIN_FAIL — Autenticación fallida: p = 0.05
Actualmente cada evento se almacena con un código de longitud fija de 3 bits (necesarios para distinguir 5 categorías con código uniforme).
b) Calcule la longitud promedio \(\bar{\ell}\) del código Huffman.
c) Calcule la entropía H(X) de la fuente y compare con \(\bar{\ell}\).
d) Calcule el ahorro en bits respecto al código de longitud fija de 3 bits.
e) ¿Cuál es la eficiencia del código Huffman obtenido?
donde \(\ell(x)\) es la longitud en bits del código asignado al símbolo \(x\).
¿Qué busca el algoritmo de Huffman? Construir un código prefijo (ningún código es prefijo de otro, lo que garantiza decodificación única) donde los símbolos más frecuentes reciben los códigos más cortos y los menos frecuentes los más largos. El árbol binario que se construye de abajo hacia arriba es la estructura que garantiza esta propiedad de forma óptima.
Regla de construcción: en cada paso se fusionan los dos nodos con menor probabilidad acumulada, creando un nodo padre cuya probabilidad es la suma de ambos. Se repite hasta tener un único nodo raíz con probabilidad 1.0. Los códigos se leen desde la raíz hacia las hojas: rama izquierda = 0, rama derecha = 1.
| Símbolo | Probabilidad p(x) | log₂ p(x) | −p(x)·log₂p(x) |
|---|---|---|---|
| LOGIN_OK | 0.40 | −1.322 | 0.5288 |
| CONSULTA | 0.25 | −2.000 | 0.5000 |
| TRANSFER | 0.20 | −2.322 | 0.4644 |
| SESION_EXP | 0.10 | −3.322 | 0.3322 |
| LOGIN_FAIL | 0.05 | −4.322 | 0.2161 |
| TOTAL | 1.00 | — | H(X) = 2.0415 bits |
Nota: log₂(0.40) = ln(0.40)/ln(2) = −0.9163/0.6931 = −1.3219. La última columna muestra la contribución de cada símbolo a la entropía total.
El algoritmo de Huffman comienza con todos los símbolos como nodos hoja. Para facilitar la selección de los dos menores en cada iteración, conviene tenerlos ordenados. En la práctica (y en implementaciones computacionales), se usa una cola de prioridad mínima.
Siempre se seleccionan los dos primeros de la lista (los de menor probabilidad). Nunca se fusionan símbolos al azar — el orden garantiza la optimalidad del código.
Se toman los dos nodos con menor probabilidad y se crea un nodo interno cuya probabilidad es la suma de ambos. Este nodo interno no representa ningún símbolo; es únicamente un punto de bifurcación en el árbol.
El nodo fusionado N₁ = 0.15 se reinserta en la lista en su posición correcta por probabilidad. La lista ahora tiene 4 elementos (pasamos de 5 nodos a 4).
Nuevamente tomamos los dos menores de la lista actualizada: N₁ = 0.15 y TRANSFER = 0.20.
Nótese que N₂ = 0.35 contiene en su interior a N₁ = 0.15, que a su vez contiene a LOGIN_FAIL y SESION_EXP. Vamos construyendo el árbol de hojas hacia la raíz.
Los dos menores ahora son CONSULTA = 0.25 y N₂ = 0.35.
Solo quedan dos nodos en la lista. La próxima fusión producirá la raíz.
Esta es la última fusión. La raíz siempre tiene probabilidad 1.0 porque concentra todos los eventos posibles.
Para un árbol con n hojas, siempre se realizan exactamente n − 1 fusiones. Con 5 símbolos → 4 fusiones.
Se recorre el árbol desde la raíz hacia cada hoja. En cada bifurcación: rama izquierda = 0, rama derecha = 1. El código de cada símbolo es la secuencia de 0s y 1s acumulada al bajar desde la raíz hasta esa hoja.
Verificación del código prefijo: ningún código es prefijo de otro (ej. "0" no es inicio de "10", "110", etc.). Esto garantiza que la decodificación sea siempre única y sin ambigüedad.
| Símbolo | p(x) | Código Huffman | Longitud ℓ(x) | p(x) · ℓ(x) |
|---|---|---|---|---|
| LOGIN_OK | 0.40 | 0 | 1 bit | 0.40 |
| CONSULTA | 0.25 | 10 | 2 bits | 0.50 |
| TRANSFER | 0.20 | 110 | 3 bits | 0.60 |
| SESION_EXP | 0.10 | 1110 | 4 bits | 0.40 |
| LOGIN_FAIL | 0.05 | 11110 | 5 bits | 0.25 |
| Longitud promedio \(\bar{\ell}\) = Σ p(x)·ℓ(x) | 2.15 bits/símbolo | |||
La longitud promedio pondera la longitud de cada código por la frecuencia con que aparece ese símbolo. Los símbolos muy frecuentes (LOGIN_OK con p=0.40, código de solo 1 bit) contribuyen poco al total; los raros contribuyen más en longitud pero compensan porque su ponderación es pequeña.
Esto significa que, en promedio, cada evento de auditoría de VaultSec Bank se codifica con 2.15 bits usando Huffman.
La entropía H(X) es el límite teórico mínimo que ningún código sin pérdida puede cruzar. Ya fue calculada en la tabla de datos; aquí verificamos el cálculo completo término por término.
El código Huffman cumple la garantía del Primer Teorema de Shannon: queda a solo 0.1085 bits por encima de la entropía, es decir, es casi óptimo.
Un código de longitud fija asigna a todos los símbolos el mismo número de bits. Para distinguir 5 categorías se necesitan ⌈log₂(5)⌉ = 3 bits (con 3 bits se representan hasta 8 valores distintos). Huffman aprovecha la desigualdad de probabilidades para reducir ese promedio.
Si VaultSec Bank genera 10 millones de eventos por día, Huffman ahorra 0.85 × 10⁷ = 8.5 millones de bits diarios (~1.06 MB/día) solo en el log de auditoría.
La eficiencia mide qué tan cerca está la longitud promedio obtenida del mínimo teórico posible (la entropía). Una eficiencia del 100% significaría que se ha alcanzado exactamente la entropía, lo cual solo ocurre cuando todas las probabilidades son potencias de 2 (p.ej., 0.5, 0.25, 0.125...).
El código Huffman obtenido usa en promedio solo un 5% más de bits que el mínimo teórico posible. Para la mayoría de aplicaciones prácticas, esta eficiencia es excelente.
La barra verde es el mínimo teórico (entropía). La barra azul oscuro es Huffman — muy cercana al mínimo. La barra roja es el código de longitud fija actual.
Codificación Huffman Avanzada · Adaptativo y por Bloques
🛡 CipherWatch S.A. — Monitor de Alertas en Tiempo RealCipherWatch S.A. recibe un flujo continuo de alertas de seguridad desde sensores distribuidos. No se conocen de antemano las probabilidades de cada tipo de alerta. El sistema registra la siguiente secuencia de eventos durante un intervalo de monitoreo:
A B A C A B A C A B
Donde: A = ACCESO_NORMAL · B = ANOMALIA_LEVE · C = ANOMALIA_CRITICA
b) Calcule la longitud total codificada con Huffman adaptativo.
c) Aplique Huffman por bloques de tamaño 2: identifique los bigramas, asigne códigos y calcule la longitud total.
d) Compare los tres métodos (longitud fija, adaptativo, por bloques) y explique por qué el método por bloques comprime más.
donde \(f(x)\) es la frecuencia absoluta del símbolo \(x\) y \(\ell(x)\) su longitud en bits.
¿Por qué Huffman adaptativo? El Huffman clásico requiere conocer las probabilidades antes de codificar. En flujos de red en tiempo real, esas probabilidades no están disponibles de antemano. El Huffman adaptativo resuelve esto aprendiendo la distribución mientras codifica: comienza con un árbol vacío y lo actualiza tras cada símbolo recibido.
¿Por qué Huffman por bloques? Al agrupar símbolos en pares o secuencias más largas, el algoritmo puede capturar redundancia contextual: la tendencia de ciertos símbolos a aparecer juntos. Si el par AB aparece frecuentemente, tratarlo como una unidad y asignarle un código corto es más eficiente que codificar A y B por separado.
El árbol comienza con un único nodo especial llamado NYT (Not Yet Transmitted). Cuando aparece un símbolo nuevo, se emite primero el código del nodo NYT (que indica "símbolo nuevo sigue") más el símbolo en binario crudo. Cuando aparece un símbolo ya conocido, se emite directamente su código Huffman actual.
En el Huffman adaptativo simplificado que aplicamos aquí, procesamos toda la cadena y registramos cómo evoluciona la tabla de frecuencias. En la práctica, el árbol se reconstruiría tras cada símbolo, pero el resultado final del código viene de la distribución completa aprendida.
| Posición | Símbolo leído | Acción | f(A) | f(B) | f(C) |
|---|---|---|---|---|---|
| 1 | A | Símbolo nuevo — añadir al árbol | 1 | 0 | 0 |
| 2 | B | Símbolo nuevo — añadir al árbol | 1 | 1 | 0 |
| 3 | A | Ya existe — incrementar frecuencia | 2 | 1 | 0 |
| 4 | C | Símbolo nuevo — añadir al árbol | 2 | 1 | 1 |
| 5 | A | Ya existe — incrementar frecuencia | 3 | 1 | 1 |
| 6 | B | Ya existe — incrementar frecuencia | 3 | 2 | 1 |
| 7 | A | Ya existe — incrementar frecuencia | 4 | 2 | 1 |
| 8 | C | Ya existe — incrementar frecuencia | 4 | 2 | 2 |
| 9 | A | Ya existe — incrementar frecuencia | 5 | 2 | 2 |
| 10 | B | Ya existe — incrementar frecuencia | 5 | 3 | 2 |
Tras procesar los 10 símbolos, las frecuencias y probabilidades aprendidas son:
Con los códigos obtenidos de la distribución aprendida, codificamos la cadena completa A B A C A B A C A B:
Con código de longitud fija (2 bits para 3 símbolos): 10 símbolos × 2 bits = 20 bits. Ahorro: 5 bits (25%).
En lugar de codificar cada símbolo individualmente, agrupamos la cadena en pares consecutivos no solapados. La cadena A B A C A B A C A B tiene 10 símbolos → 5 bigramas.
Al segmentar, el "alfabeto" pasa de ser {A, B, C} a ser el conjunto de bigramas observados: {AB, AC}. Si hubieran aparecido combinaciones como AA, BC, CB, etc., también se incluirían.
Contamos cuántas veces aparece cada bigrama en la segmentación:
| Bigrama | Frecuencia | Probabilidad | Interpretación |
|---|---|---|---|
| AB | 3 | 3/5 = 0.60 | Acceso normal seguido de anomalía leve |
| AC | 2 | 2/5 = 0.40 | Acceso normal seguido de anomalía crítica |
El bigrama AB aparece 3 de 5 veces → es el patrón dominante. El algoritmo le asignará el código más corto.
Con solo 2 bigramas, el árbol tiene una única fusión posible. La raíz = 0.60 + 0.40 = 1.00. El bigrama más frecuente (AB = 0.60) queda en la rama izquierda (código 0) y el menos frecuente (AC = 0.40) en la derecha (código 1).
Esto es extraordinariamente eficiente: solo 0.5 bits por símbolo. Ocurre porque hay solo 2 bigramas distintos (distribución casi binaria) y la codificación binaria de 2 elementos requiere exactamente 1 bit.
¿Por qué el método por bloques comprime tanto más? Porque detecta que en esta cadena, A siempre aparece seguido de B o de C. Al tratar los pares como unidades, el código captura esa dependencia contextual. El Huffman símbolo a símbolo no puede ver que A predice que el siguiente símbolo será B o C; el Huffman por bloques sí.
| Método | Bits totales | Bits/símbolo | Ahorro vs. fijo | Diagnóstico |
|---|---|---|---|---|
| Longitud fija (2 bits) | 20 bits | 2.00 | — | Referencia |
| Huffman adaptativo | 15 bits | 1.50 | 25.0% | Bueno |
| Huffman por bloques (k=2) | 5 bits | 0.50 | 75.0% | Óptimo aquí |
Algoritmo LZ77 · Ventana Deslizante
🔐 FortiLog Systems — Compresión de Tráfico de RedFortiLog Systems captura secuencias de eventos de tráfico de red y necesita comprimirlas para su almacenamiento eficiente en logs históricos. Una secuencia típica tiene la siguiente forma (cada letra representa un tipo de paquete):
A B C A B C A B C
Se utilizará el algoritmo LZ77 con una ventana de búsqueda de 6 caracteres y un buffer de anticipación de 4 caracteres.
b) Interprete cada token: ¿qué dice exactamente al decodificador?
c) Calcule el ahorro en caracteres respecto a la representación original.
d) Explique la diferencia conceptual entre LZ77 y Huffman: ¿qué tipo de redundancia explota cada uno?
offset: cuántas posiciones hacia atrás (en la ventana de búsqueda) comienza la coincidencia | longitud: cuántos caracteres coinciden | símbolo_siguiente: el carácter que sigue inmediatamente después de la coincidencia
Cuando no hay ninguna coincidencia en la ventana, se emite offset=0, longitud=0 y el símbolo en crudo.
Intuición de LZ77: Imagine que está redactando un documento y necesita escribir una frase que ya aparece más arriba. En lugar de reescribirla, pondría una nota como "ver párrafo 3, líneas 4-7". LZ77 hace exactamente eso: cuando detecta que una subcadena ya apareció antes en la ventana de búsqueda, emite una "referencia" (offset, longitud) en lugar de repetir los caracteres.
Ventana deslizante: La ventana de búsqueda se desplaza con el cursor de lectura. Contiene solo los últimos W caracteres procesados, no toda la cadena. Esto limita la memoria necesaria y hace el algoritmo eficiente en flujos continuos como el tráfico de red.
En cada paso, la posición del cursor divide la cadena en dos zonas:
| ← ventana de búsqueda (máx 6 chars) → | ← buffer anticipación (máx 4 chars) → | resto |
El algoritmo busca en la ventana la coincidencia más larga posible con el inicio del buffer. Siempre se busca la coincidencia más larga para maximizar la compresión.
Al inicio, la ventana de búsqueda está vacía porque no hay ningún carácter previamente procesado. No puede haber coincidencia. Se emite el símbolo directamente con un token de "sin coincidencia".
El cursor avanza 1 posición (longitud 0 + 1 símbolo siguiente). Ahora la ventana contiene: [A].
La ventana tiene [A]. El buffer comienza con 'B'. Buscamos 'B' en la ventana: no aparece.
Cursor avanza 1. Ventana: [A B].
La ventana tiene [A B]. Buscamos 'C': no aparece en la ventana.
Cursor avanza 1. Ventana: [A B C].
La ventana tiene [A B C]. El buffer comienza con 'A B C A'. Buscamos la coincidencia más larga que empiece por 'A' en la ventana. 'A' está en la ventana en la posición 3 hacia atrás (offset=3). ¿Cuántos caracteres coinciden desde ahí? La ventana tiene A en pos −3, luego B en −2, luego C en −1. El buffer tiene A, B, C, A. Coinciden: A·B·C = 3 caracteres. El siguiente carácter del buffer después de la coincidencia es 'A'.
Este token representa 4 caracteres (3 copiados + 1 símbolo siguiente). El cursor avanza 4 posiciones. Ventana ahora: [A B C A B C] (últimos 6 chars procesados).
Cursor está ahora en la posición 8. Ventana contiene los 6 caracteres anteriores: [A B C A B C]. Buffer de anticipación: [B C] (solo quedan 2 chars). Buscamos la coincidencia más larga que empiece por 'B'.
Nota: cuando se llega al final de la cadena sin un símbolo siguiente, se emite el token sin carácter adicional. Algunos libros lo escriben como (5, 2, ε) o simplemente (5, 2).
| # | Token | Tipo | Decodificación | Chars representados |
|---|---|---|---|---|
| 1 | (0, 0, 'A') | Nuevo símbolo | Emitir 'A' directamente | A |
| 2 | (0, 0, 'B') | Nuevo símbolo | Emitir 'B' directamente | B |
| 3 | (0, 0, 'C') | Nuevo símbolo | Emitir 'C' directamente | C |
| 4 | (3, 3, 'A') | Referencia | Retroceder 3, copiar 3 chars (ABC), luego 'A' | A B C A |
| 5 | (5, 2, '') | Referencia | Retroceder 5, copiar 2 chars (BC) | B C |
La decodificación reconstruye exactamente la cadena original. Para cada token de referencia, el decodificador aplica: "ir offset posiciones hacia atrás en lo ya decodificado, copiar longitud caracteres".
Comparamos el número de tokens necesarios con el número de caracteres originales. En la práctica, cada token requiere bits para codificar offset, longitud y símbolo; aquí analizamos la reducción en unidades lógicas.
El algoritmo gasta tokens "caros" al inicio (cuando la ventana está vacía) pero se vuelve cada vez más eficiente a medida que la ventana se llena con el historial de la cadena.
Estos dos algoritmos operan sobre fundamentos completamente distintos:
Huffman — Redundancia estadística
Explota que ciertos símbolos ocurren con mayor frecuencia. Si LOGIN_OK aparece el 40% del tiempo, se le da un código corto. No importa en qué posición de la cadena aparece; solo importa cuántas veces. Requiere conocer (o aprender) las probabilidades de los símbolos.
LZ77 — Redundancia estructural
Explota que ciertos patrones se repiten dentro de la cadena. No analiza probabilidades: detecta subcadenas que ya aparecieron y las reemplaza por referencias. No necesita conocer la distribución de la fuente; aprende los patrones al vuelo. Ideal para datos con estructura repetitiva (código fuente, logs, ADN).
Algoritmo LZ78 · Diccionario Dinámico
💾 NetShield Consulting — Compresión de Registros de AccesoNetShield Consulting necesita comprimir registros de acceso que contienen secuencias de comandos de sistema. Una muestra del log tiene la siguiente forma (cada letra representa un tipo de comando):
A B A A B A B A
b) Muestre el estado del diccionario al final del proceso.
c) Verifique que la decodificación reconstruye exactamente la cadena original.
d) Compare LZ77 y LZ78: ventajas, desventajas y casos de uso en ciberseguridad.
índice_previo: el índice en el diccionario de la secuencia previa más larga ya conocida (0 si no hay antecedente) | símbolo_nuevo: el carácter que extiende esa secuencia conocida
Intuición de LZ78: Imagine que tiene un glosario al que va añadiendo términos mientras lee un documento. La primera vez que ve una palabra, la añade al glosario. La siguiente vez que la ve, no la transcribe completa: escribe "ver glosario, entrada 3". Si luego ve esa misma palabra seguida de otra nueva, crea una nueva entrada en el glosario para el par. El diccionario de LZ78 funciona así: crece con cada paso, construyendo frases cada vez más largas que puede referenciar eficientemente.
Ventaja sobre LZ77: LZ78 no tiene límite de ventana — puede referenciar un patrón que apareciera al principio de la cadena, sin importar cuánto tiempo atrás. La desventaja es que el diccionario puede crecer indefinidamente (en la práctica se limita su tamaño y se reinicia cuando llega a un máximo).
El diccionario comienza completamente vacío. El índice 0 es un índice especial que significa "sin prefijo previo" — se usa cuando el símbolo que se va a codificar no tiene ningún antecedente en el diccionario. Los índices reales empiezan en 1.
Leemos 'A'. Buscamos 'A' en el diccionario: no existe. Como no hay prefijo previo en el diccionario, el índice_previo es 0. Creamos la entrada 1: "A". Emitimos el token (0, A).
Leemos 'B'. No está en el diccionario. Prefijo previo: ninguno. Nueva entrada: 2 → "B". Emitimos (0, B).
Leemos 'A'. Ahora 'A' SÍ está en el diccionario (entrada 1). Extendemos: leemos el siguiente símbolo 'A'. Buscamos "AA" en el diccionario: no existe. La secuencia conocida más larga es solo "A" (entrada 1). El símbolo nuevo es el segundo 'A'. Creamos la entrada 3: "AA". Emitimos (1, A).
El cursor avanza 2 posiciones (la 'A' conocida + la 'A' nueva). Nos hemos consumido A B A A — quedan: B A B A.
Leemos 'B'. 'B' existe (entrada 2). Extendemos: leemos el siguiente = 'A'. Buscamos "BA" en el diccionario: no existe. Prefijo "B" → índice 2. Nueva entrada: 4 → "BA". Emitimos (2, A).
Consumido hasta ahora: A B A A B A. Quedan: B A.
Leemos 'B'. Existe (entrada 2). Extendemos: leemos 'A'. Buscamos "BA": SÍ existe en el diccionario (entrada 4). Intentamos extender más: ¿hay más caracteres? No — la cadena se termina después de este 'A'. No podemos leer otro símbolo para crear "BAx". Emitimos (4, ε) — algunas implementaciones usan (2, A) para este caso; aquí indicamos que "BA" es el prefijo con índice 4 y no hay símbolo siguiente.
Nota: en muchas implementaciones este último token se trata de forma especial (indicador de fin de cadena) o simplemente no se añade una nueva entrada al diccionario porque no hay símbolo nuevo que añadir.
| Paso | Token | Cadena representada | Nueva entrada diccionario |
|---|---|---|---|
| 1 | (0, A) | A | 1 → A |
| 2 | (0, B) | B | 2 → B |
| 3 | (1, A) | A A | 3 → AA |
| 4 | (2, A) | B A | 4 → BA |
| 5 | (4, ε) | B A | — (fin de cadena) |
Para decodificar, el receptor reconstruye el diccionario exactamente en el mismo orden. Cada token (índice, símbolo) le dice: "toma la cadena del diccionario en esa entrada, luego añade el símbolo nuevo".
El decodificador puede hacer esto sin recibir el diccionario por separado: lo reconstruye de forma local a medida que decodifica los tokens, exactamente igual que lo hizo el codificador.
| Criterio | LZ77 | LZ78 |
|---|---|---|
| Estructura de memoria | Ventana deslizante (tamaño fijo W) | Diccionario dinámico (crece con la cadena) |
| Alcance hacia atrás | Limitado al tamaño de la ventana W | Ilimitado (toda la cadena procesada) |
| Memoria requerida | Acotada y predecible (O(W)) | Variable, puede crecer mucho (O(n)) |
| Tipo de token | (offset, longitud, símbolo) | (índice diccionario, símbolo) |
| Rendimiento en datos cortos | Menor (ventana vacía al inicio) | Menor (diccionario vacío al inicio) |
| Rendimiento en datos largos | Bueno, especialmente con W grande | Muy bueno si los patrones se repiten |
| Variantes conocidas | DEFLATE, gzip, zlib, PNG | LZW (GIF, TIFF, PDF antiguo), LZC |
| Uso en ciberseguridad | Compresión de capturas de paquetes (pcap), logs de flujos de red | Compresión de bases de datos de firmas, registros de auditoría estructurados |
Tabla comparativa — Métodos de compresión sin pérdida
| Método | Tipo de redundancia | Requiere dist. previa | Acercamiento a H(X) | Uso típico en ciberseguridad |
|---|---|---|---|---|
| Huffman clásico | Estadística | Sí | H(X) ≤ ℓ̄ < H(X)+1 | Compresión de logs con distribución conocida |
| Huffman adaptativo | Estadística | No | Se acerca conforme aprende | Flujos de alertas en tiempo real |
| Huffman por bloques | Estadística + contextual | Parcialmente | Mejor que símbolo a símbolo | Logs con patrones de eventos correlacionados |
| LZ77 | Estructural (ventana) | No | Asintóticamente óptimo | Capturas pcap, tráfico de red (gzip, DEFLATE) |
| LZ78 / LZW | Estructural (diccionario) | No | Asintóticamente óptimo | Bases de firmas, registros estructurados |