Compresión de la información: Más que hacer archivos más pequeños

La compresión de información, a menudo llamada compresión de datos, es el arte y la ciencia de reducir el número de bits necesarios para representar datos. Es una piedra angular de la informática moderna, lo que permite que todo desde streaming de vídeo sobre ancho de banda limitado hasta almacenar fotografías de alta resolución en un smartphone. Mientras que el objetivo práctico es reducir el tamaño de archivo, los soportes teóricos están profundamente arraigados en probabilidad y estadísticas. Entender esta conexión no es sólo académicomente interesante diseño.

En su núcleo, la compresión explota la redundancia y la previsibilidad. Si cada personaje en un mensaje fuera igualmente probable e independiente de sus vecinos, no sería posible compresión significativa. Pero los datos naturales – texto, imágenes, audio, vídeo – está lleno de patrones. La letra "e" aparece mucho más a menudo que "z" en inglés. Los píxeles adyacentes en una imagen son generalmente similares.

Probability: The Language of Predictability

Modelos de probabilidad de que se produzcan diferentes símbolos o patrones. Una distribución de probabilidad simple para el texto inglés podría asignar una alta probabilidad a "e" (alrededor del 12,7%), una probabilidad moderada a "t" (9,1%), y una probabilidad muy baja a "z" (0.074%). Un algoritmo de compresión puede utilizar este conocimiento para asignar códigos binarios cortos a símbolos frecuentes y códigos más largos a los raros, un principio conocido como codificación variable-longitud. Esta es la base intuitiva para muchos esquemas de compresión, pero la relación se desarrolla mucho más profundo.

Theorem de codificación de la fuente de Shannon: El límite fundamental

Claude Shannon, padre de la teoría de la información, proporcionó el vínculo definitivo entre probabilidad y compresión en su papel de 1948 Una teoría matemática de la comunicación. Definió el entropía de una fuente discreta como la cantidad promedio de información (en bits) producida por símbolo. Para una fuente que emite símbolos con probabilidades p1, p2, ..., pn, la entropía H se da por H = - ganancia pi log2 pi. Entropy mide la incertidumbre promedio o sorpresa por símbolo. Un tos de moneda justa tiene entropía 1 bit; una moneda sesgada que siempre cabezas de tierra tiene entropy 0 bits.

El teorema de codificación de origen de Shannon (el teorema de codificación sin ruido) afirma que cualquier esquema de compresión sin pérdidas no puede comprimir datos a menos bits que su entropía. En otras palabras, la entropía representa el número mínimo absoluto de bits necesarios para representar cada símbolo. Por el contrario, para cualquier fuente con entropy H, existe un esquema de codificación que puede comprimirlo arbitrariamente cerca de H bitlos por símbolos.

Este resultado es profundo: las distribuciones de probabilidad determinan directamente la mejor relación de compresión teórica. Los datos con alta entropía (por ejemplo, ruido aleatorio) son esencialmente incompresibles, mientras que los datos con baja entropía (por ejemplo, una larga cadena de bytes idénticos) pueden ser comprimidos enormemente. La conexión no es sólo conceptual; es una certeza matemática.

Cómo los algoritmos de compresión usan probabilidad

Los algoritmos de compresión práctica implementan los principios de Shannon de varias maneras. El enfoque más directo es crear un libro de códigos que mapea símbolos a secuencias de bits de longitudes variables, con códigos más cortos asignados a símbolos más probables. entropy coding.

Huffman Coding

Invenido por David A. Huffman en 1952, Huffman coding construye un código óptimo libre de prefijo para un determinado conjunto de probabilidades de símbolo. Un código libre de prefijo significa que ninguna palabra de código es un prefijo de otro, por lo que el bitstream codificado puede descifrarse sin ambigüedad. El algoritmo construye un árbol binario basado en las probabilidades: los símbolos que reciben los formatos más cortos

Codificación Aritmética

El código de codificación de la rítmica es una técnica más sofisticada que puede alcanzar la compresión arbitrariamente cercana al límite de la entropía, incluso para fuentes con probabilidades de símbolos no enteros. En lugar de asignar un código fijo a cada símbolo, la codificación aritmética representa todo el mensaje como un número único de punto flotante en el intervalo [0,1).

Lempel-Ziv (LZ) Family

Algoritmos como LZ77 y LZ78 (y sus derivados LZW, LZSS, Deflate) toman un enfoque diferente: construyen un diccionario de secuencias previamente vistas y reemplazan ocurrencias repetidas con referencias cortas. Mientras que no son explícitamente modelos probabilidades, su eficiencia depende de la probabilidad de encontrar patrones repetidos.

Modelo y predicción de contexto

Los esquemas de compresión modernos van más allá estimando las probabilidades de símbolo condicional en el contexto – los símbolos anteriores. Por ejemplo, en la compresión de texto, la probabilidad de la letra 'u' es mucho más alta después de una 'q' que después de una 'z'. Manteniendo un modelo de probabilidad que se adapta a la entrada, estos esquemas pueden acercarse mucho más de cerca. Este es el principio detrás de predicción por coincidencia parcial (PPM) y context tree weighting (CTW)Los compresores de última generación como PAQ o ZPAQ utilizan modelos de contexto sofisticados y codificación aritmética para lograr ratios de compresión que rompen el registro, aunque a un alto costo computacional.

Compresión perdida: probabilidad de tracción para la calidad perceptual

Mientras que la compresión sin pérdidas preserva cada bit de datos originales, la compresión perdida permite que cierta información sea descartada a cambio de tasas de bits mucho más bajas. La idea clave es que no toda la información es igualmente importante para el observador humano – se define por una distribución de probabilidad perceptual. Los codecs de audio como MP3 y AAC usan modelos psicoacústicos para identificar sonidos que se enmascaran por sonidos temporales más fuertes y pueden ser descartados.

En compresión, probabilidad y estadísticas de pérdida se utilizan para diseñar distorsión de la tasa optimización: dado un presupuesto de bits objetivo, el algoritmo decide qué partes de la señal para preservar más precisamente y que aproximar más gruesamente. Los cuantitativos en JPEG (coeficientes de transformación cosina descretos) o en codecs basados en el aprendizaje profundo se ajustan a la distribución estadística de los datos de imagen. La conexión entre probabilidad y compresión va más allá de la simple entropía; amplía la teoría de los modelos perceptuales.

Tasa de distorsión Teoría

La teoría de la distorsión de tarifas, también fundada por Shannon, extiende el teorema de codificación fuente a situaciones perdidas. Define la tasa mínima de bits necesaria para alcanzar un determinado nivel de distorsión (o viceversa). El intercambio se rige por la información mutua entre la fuente y su reconstrucción, que es una cantidad probabilística. Los códecs prácticos tratan de operar en la frontera de Pareto de la curva de distorsión de tarifas, utilizando sus opciones de probabilidad.

Aplicaciones de la Compresión Probabilística en el Mundo Real

El matrimonio de probabilidad y compresión toca cada rincón de la tecnología.

  • Compresión de imagen: JPEG utiliza codificación Huffman después de cuantificar coeficientes de frecuencia. JPEG 2000 utiliza codificación aritmética con una transformación de onda. WebP y AVIF combinan predictores avanzados con codificación entropía.
  • Flujo de vídeo: Netflix y YouTube dependen de codecs como H.264, H.265 y AV1, que realizan estimación de movimiento (predecir marcos futuros de los anteriores) y luego comprime los residuos de predicción utilizando codificación aritmética. La estimación de movimiento es una búsqueda probabilística: el algoritmo asigna mayor probabilidad a los movimientos pequeños y locales.
  • Compresión de audio: MP3 utiliza la codificación Huffman en datos de dominio de frecuencia después de aplicar un modelo psicoacústico que enmascara componentes inaudibles. Opus utiliza un híbrido de códecs SILK (habla) y CELT (música), ambos fuertemente impulsados por probabilidad.
  • Almacenamiento de datos: Los sistemas de archivos y las herramientas de respaldo utilizan compresores basados en LZ (como zstd o LZ4) para intercambiar espacio por tiempo. Las bases de datos utilizan la compresión para reducir las huellas de almacenamiento; las bases de datos columnares a menudo codifican valores repetidos consecutivos de larga duración – una forma sencilla de compresión basada en la probabilidad.
  • Aprendizaje de la máquina: La compresión de la información tiene vínculos profundos con el aprendizaje. El principio de longitud de descripción mínima (MDL) establece que el mejor modelo para un conjunto de datos es el que minimiza la longitud de descripción combinada del modelo y los datos dados al modelo. Se trata de una perspectiva de compresión probabilística sobre sobre el sobreajuste y la generalización. Distancias basadas en la compresión (por ejemplo, distancia normalizada de compresión) utilizan compresores para computar similidad entre objetos sin etiquetado humano.
  • Biología y genómica: Las secuencias de ADN se comprimen utilizando algoritmos especializados que explotan la alta probabilidad de motivos repetidos (por ejemplo, islas CG) y correlaciones de largo alcance. Herramientas como CRAM comprime archivos FASTQ utilizando predicción basada en referencia y codificación de entropía, permitiendo que se almacenen de manera eficiente vastos conjuntos de datos genómicos.

Temas avanzados: Inferencia Bayesiana y Compresión Universal

Los marcos de compresión más sofisticados tratan la codificación como un problema de inferencia Bayesiana. Mantienen una distribución de probabilidad sobre posibles secuencias condicionadas a los datos vistos hasta ahora, y utilizan esa distribución para conducir un códice aritmético. codificación adaptable o universal – el algoritmo no necesita saber las estadísticas de origen de antemano; las aprende sobre la marcha.

Por ejemplo, el Burrows-Wheeler transform (utilizado en bzip2) reordena datos de entrada para producir carreras de símbolos idénticos, haciendo que los datos sean más compresibles por un códice posterior entropía. La transformación depende de la propiedad estadística que las cadenas a menudo comparten contexto local. Transformaciones de onda Gram-Schmidt decorrelate datos para que los coeficientes resultantes tengan menor entropía.

Otra técnica avanzada es Sensación comprimida, que explota el hecho de que muchas señales naturales son escasas en alguna base (la mayoría de los coeficientes cerca de cero, por lo tanto alta probabilidad de ser insignificante). Mediante mediciones lineales aleatorizadas, la detección comprimida puede recuperar la señal original de mucho menos muestras que la tasa de Nyquist sugiere, realizando efectivamente la detección y compresión simultáneas. El algoritmo de reconstrucción utiliza la probabilidad (por ejemplo, L1 de medición de mínimo plaus)

Desafíos y futuras orientaciones

Mientras que el vínculo entre probabilidad y compresión es bien entendido, muchos problemas abiertos permanecen. Un desafío es lograr la compresión universal que funciona bien en todos los tipos de datos sin afinación manual. Otro es el manejo de conjuntos de datos masivos con requisitos de baja latencia; los compresores más rápidos de hoy como zstd y LZ4 sacrificar cierta relación de compresión para la velocidad, pero los modelos probabilísticos que usan son relativamente simples.

Los compresores basados en redes neuronales son un área de investigación activa. Los modelos de aprendizaje profundo pueden aprender distribuciones de probabilidad muy complejas sobre datos de alta dimensión (por ejemplo, imágenes o audio) y utilizarlos para alcanzar tasas de compresión de última generación. aprendidas clavecs A menudo utilizan modelos hiperprior y mapas de importancia para asignar bits según la incertidumbre local (entropía) de la señal. Representan una fusión directa de aprendizaje de máquina y teoría de la información, donde el modelo probabilístico no es artesanal sino descubierto a partir de datos.

La teoría de la información cuántica promete también nuevas ideas, aunque la compresión cuántica práctica está lejos de la realidad. Los conceptos de la codificación de origen cuántica y entropía de von Neumann generalizan las ideas de Shannon a estados cuánticos, insinuando conexiones aún más profundas entre probabilidad, física y compresión.

Conclusión: Por qué esta conexión importa

La relación entre probabilidad y compresión de información no es simplemente una curiosidad teórica; es el motor detrás de casi todas las tecnologías digitales que utilizamos diariamente. Desde la foto JPEG que viste por última vez a la canción MP3 que transmitiste, los modelos de probabilidad determinaron cómo de manera eficiente se almacenaron y transmitieron los datos. Entender esta conexión ayuda a los ingenieros a diseñar mejores codecs, los científicos de datos aprecian los límites de sus representaciones, y los investigadores empujan los límites de lo que es posible.

La probabilidad proporciona la materia prima para la compresión – las expectativas sobre qué símbolos aparecerán y cómo se relacionan entre sí. La compresión, a su vez, ofrece una medida concreta y operativa de la aleatoriedad y la estructura en los datos. Juntos, forman un marco unificado para pensar en información, complejidad y eficiencia. A medida que los volúmenes de datos explotan, la importancia de la compresión probabilística sólo crecerá, lo que lo hará una parte cada vez más esencial de la edad de la información.

Recursos externos: