Un manual sobre compresión de datos

Teoría y estrategia de representación de datos

Este artículo es un iniciador sobre los tipos básicos de compresión de datos que incluye una explicación introductoria de las matemáticas y de los algoritmos que se incluyen en las técnicas de compresión. Se proporcionan ejemplos y consideraciones breves para ayudar a evaluar qué tipo de herramientas de compresión y qué técnicas son las adecuadas para sus propias aplicaciones. Se proporcionan indicaciones para discusiones teóricas más avanzadas y herramientas de compresión listas para usar y bibliotecas.

David Mertz, Presidente, Gnosis Software, Inc.

David MertzDavid Mertz cree que los lenguajes artificiales son perfectamente naturales pero los lenguajes naturales parecen un poco artificiales. Es posible contactar a David en mertz@gnosis.cx; podrá investigar todos los aspectos de su vida en su página Web personal. Vea su libro, Text Processing in Python (Procesamiento de Texto en Python). Las sugerencias y recomendaciones sobre las columnas pasadas o futuras son bienvenidas.



05-11-2012 (Primera publicación 05-11-2012)

Desarrolle habilidades de este tema

Este contenido es parte de un knowledge path progresivo para avanzar en sus habilidades. Vea XML y compresión de datos (en inglés)

La compresión de datos se utiliza en gran medida en una gran variedad de contextos de programación. Todos los sistemas operativos populares y los lenguajes de programación tienen varias herramientas y bibliotecas para tratar la compresión de datos de varios tipos. La elección correcta de herramientas de compresión y de bibliotecas para una aplicación determinada depende de las características de los datos y de la aplicación en cuestión: transmisión y archivo; patrones esperados y regularidades en los datos; importancia relativa del uso del CPU, uso de la memoria, demandas de canales y requisitos de almacenamiento; y otros factores.

Y, entonces... ¿Qué es la compresión de datos? La respuesta corta es que la compresión de datos elimina la redundancia de los datos; en términos teóricos de información, la compresión aumenta la entropía del texto comprimido. Pero estas afirmaciones son esencialmente verdades por definición. La redundancia se presenta de muchas formas. Las secuencias de bit repetidas (11111111) son un tipo. Las secuencias de byte repetidas son otro (XXXXXXXX). Sin embargo, más a menudo, las redundancias tienden a aparecer a mayor escala, ya sea que las regularidades del conjunto de datos se consideran como un todo o las secuencias de variación de las longitudes que son relativamente comunes. Básicamente, el propósito de la compresión de datos consiste en encontrar transformaciones algorítmicas de representaciones de datos que producirán representaciones más compactas debido a los conjuntos de datos "típicos". Si esta descripción parece un poco compleja para ser desempaquetada, continúe con la lectura para encontrar ilustraciones más prácticas.

Compresión son pérdidas y compresión con pérdidas

En realidad, hay fundamentalmente dos "estilos" diferente de compresión de datos: con pérdidas y sin pérdidas. En general, este artículo abarca las técnicas de compresión sin pérdidas, pero, primero que nada, es útil conocer esta distinción. La compresión sin pérdidas implica una transformación de la representación de un conjunto de datos, entonces es posible reproducir exactamente el mismo conjunto de datos originales al realizar la transformación por descompresión. La compresión con pérdidas es una representación que le permite reproducir algo "bastante parecido" al conjunto de datos original. Una ventaja de las técnicas con pérdidas es que pueden producir con frecuencia representaciones de datos más compactas que las técnicas de compresión sin pérdidas. Más a menudo, las técnicas de compresión con pérdidas se utilizan para imágenes, archivos de audio y video. La compresión con pérdidas podría ser la adecuada en aquellas áreas en las que los observadores humanos no perciben un patrón de bits literal de una imagen o sonido digital, sino que características gestálticas generales de la imagen/sonido subyacente.

Desde el punto de vista de los datos "normales", la compresión con pérdidas no es una opción. No queremos un programa que haga "prácticamente lo mismo" que el que escribimos. No queremos una base de datos que contenga "prácticamente el mismo" tipo de información que la que incluimos. Al menos, no para la mayoría de los propósitos (y si conozco algunos usos prácticos de la compresión con pérdidas fuera que lo que ya son las representaciones miméticas aproximadas del mundo real, como imágenes y sonidos).


Ejemplo de un conjunto de datos

Para el propósito de este artículo, comencemos con una representación hipotética y específica de datos. A continuación, se incluye un ejemplo fácil de entender. En la ciudad de Greenfield, MA, los prefijos de teléfono son 772-, 773- y 774-. (Para lectores que no son de los Estados Unidos: En los Estados Unidos, los números de teléfonos locales tienen 7 dígitos, y convencionalmente se los representan con ###-####; los prefijos se asignan en bloques geográficos). También, suponga que el primer prefijo es el más asignado de los tres. Las partes de los sufijos podrían ser otros dígitos, en una distribución bastante parecida. El conjunto de datos en el que estamos interesados es "La lista de todos los números de teléfono que actualmente se encuentran en uso activo". Uno puede imaginar varios motivos porqué estamos interesados para propósitos programáticos, pero aquí no estamos preocupados en eso.

Inicialmente, el conjunto de datos en el que estamos interesados se presenta en una representación de datos determinada: un informe multicolumna (tal vez, generado como resultado de alguna consulta o proceso de compilación). Las primeras líneas de este informe se verían así:

Tabla 1. Informe multicolumna

=============================================================
772-7628     772-8601     772-0113     773-3429     774-9833
773-4319     774-3920     772-0893     772-9934     773-8923
773-1134     772-4930     772-9390     774-9992     772-2314
[...]

Compresión de espacios en blanco

Generalmente, la compresión de espacios en blanco puede caracterizarse como "eliminar lo que no nos interesa". Aunque esta técnica es una técnica de compresión con pérdidas, es útil para muchos tipos de representaciones de datos que encontramos en el mundo real. Por ejemplo, aunque HTML es mucho más legible en un editor de textos si se agregan espacios de indentación o verticales, ninguno de los "espacios en blanco" debería hacer ninguna diferencia en la representación del documento HTML por un navegador web. Si usted sabe que un documento HTML está destinado solo para un navegador web (o para un robot/araña), entonces podría ser una buena idea sacar todos los espacios en blanco para transferirlos más rápidamente y ocupar menos espacio de almacenamiento. En realidad, lo que eliminamos en la compresión de espacios en blanco, nunca tuvo un propósito funcional para comenzar.

En caso de nuestro ejemplo en este artículo, es posible eliminar un poco del informe descrito. La fila de "=" en la parte superior no agrega nada funcional; tampoco '-' dentro de los números, ni los espacios entre ellos. Todos estos son útiles para una persona que lee el informe original, pero no importa una vez que lo pensamos como "datos". Lo que eliminamos no es precisamente "espacio en blanco" en términos tradicionales, sino que el intento es el mismo.

La compresión de espacios en blanco es extremadamente "barato" de realizar. Es simplemente cuestión de leer una transmisión de datos y de excluir algunos valores específicos desde la transmisión de salida. En muchos casos, no se incluye el paso de "descompresión". Pero incluso donde nos gustaría recrear algo parecido al original en algún lugar por debajo de la transmisión de datos, eso requeriría poco en términos de CPU o de memoria. Lo que reproducimos puede o no ser exactamente con lo que empezamos, según qué normas y restricciones se incluían en el original. Una página HTML escrita por un humano en un editor de texto probablemente tendrá el espacio que es idiosincrático. Una vez más, a menudo, las herramientas automatizadas producen una indentación "razonable" y espacio para HTML. En el caso del formato rígido del informe en nuestro ejemplo, no hay motivo por el cual la representación original podría no producirse por parte de un "formateador de descompresión".


Codificación de duración

La codificación de duración (RLE) es la técnica de compresión sin pérdidas más utilizada y simple. Al igual que la compresión de espacios en blanco, es "económica", especialmente para decodificar. La idea de trasfondo es que muchas representaciones de datos consisten de grandes series de bytes repetidos. Nuestro informe de ejemplo incluye esos datos de representación. Comienza con una serie repetida de "=" y tiene series de espacios distribuidos. Más que representar cada caracter con su propio byte, RLE (algunas veces o siempre) tendrá un conteo de iteración seguido por el caracter a repetirse.

Si los bytes repetidos son prominentes dentro de la representación de datos esperada, podría ser adecuado y eficiente que el algoritmo especifique uno o más bytes de conteo de iteración seguido de un caracter. Sin embargo, si tiene lugar una serie caracteres extensa, esa serie requerirá dos (o más) bytes para decodificarlos, es decir, 00000001 01011000 podría ser la transmisión de bits de salida requerida para un ASCII "X" de la transmisión de entrada. Entonces, cien "X" en una fila sería una salida de 01100100 01011000, lo que es bastante bueno.

Lo que se realiza con frecuencia en las variantes RLE consiste en utilizar selectivamente los bytes para indicar los conteos de iterador o bien que los bytes se representen a sí mismos. Al menos un valor de un byte debe reservarse para hacer esto, pero puede liberarse en la salida de datos, si fuese necesario. Por ejemplo, en nuestro informe de números de teléfonos, sabemos que todo en la transmisión de entrada son caracteres planos de ASCII. Específicamente, todos tienen el bit uno de su valor de ASCII como 0. Podríamos usar primero este bit ASCII para indicar que un conteo del iterador estaba siendo representado en lugar de representar un caracter regular. Los siguientes siete bits del byte iterador podrían utilizarse para el conteo del iterador; y el siguiente byte podría representar el caracter a repetirse. Entonces, por ejemplo, podríamos representar la serie "YXXXXXXXX" como:

"Y" Iter(8)  "X"
01001111 10001000 01011000

Este ejemplo no muestra cómo liberar los valores de bytes del iterador ni tampoco permite la iteración de más de 127 ocurrencias de un caracter. Las variaciones en RLE tratan con cuestiones como estas, si es que resulta necesario.


Codificación Huffman

La codificación Huffman considera la tabla del símbolo de un conjunto total de datos. La compresión se realiza al encontrar los "pesos" de cada símbolo en el conjunto de datos. Algunos símbolos aparecen con más frecuencia que otros; entonces, la codificación Huffman sugiere que los símbolos frecuentes no necesitan codificarse con muchos bits como los símbolos menos frecuentes. Hay variaciones de codificación del estilo Huffman, pero la variación original (y frecuente) implica buscar el símbolo más común y codificarlo al usar un bit, es decir, 1. Si encuentra un 0, sabe que están en camino de codificar un símbolo de longitud variable más largo.

Imaginemos que aplicamos una codificación de Huffman a nuestro ejemplo de guía de teléfono local (suponiendo que ya comprimimos el espacio en blanco del informe). Podríamos obtener:

Tabla 2. Resultados de la codificación de Hoffman

Símbolo de codificación
 1           7
 010         2
 011         3
 00000       4
 00001       5
 00010       6
 00011       8
 00100       9
 00101       0
 00111       1

Nuestro conjunto inicial de símbolos de dígitos podría ya estar codificado de forma estrecha (sin compresión) como secuencias de 4 bits (terabit). La codificación de Huffman proporcionar utilizará hasta 5 bits para los símbolos de los peores casos, lo que, obviamente, es peor que la codificación de terabits. Sin embargo, nuestro mejor caso utilizará solo 1 bit; y sabemos que nuestro mejor caso también es el más frecuente al haber escaneado el conjunto de datos. Entonces, podría codificar un número de teléfono determinado como:

772 7628 --> 1 1 010 1 00010 010 00011

La codificación de porciones tomaría 28 bits para representar un número de teléfono; en este caso en particular, nuestra codificación toma 19 bits. Agregué ejemplos en el ejemplo anterior para ser más claro y, de esa forma, puede ver que no hay necesidad de desempaquetar la codificación, dado que la tabla de codificación determinará si alcanzamos el final de un símbolo codificado (pero debe realizar un seguimiento de su lugar en los bits).

La codificación de Huffman aún es económica de codificar, en lo que respecta al ciclo. Pero requiere de una búsqueda de la tabla, entonces no puede ser tan económico como RLE. Sin embargo, el lateral de codificación de Huffman es más costoso; el conjunto total de datos tiene que escanearse y construirse la tabla de frecuencia. En algunos casos, un "atajo" es adecuado con la codificación de Huffman. La codificación estándar de Huffman se aplica a un conjunto de datos determinados que se codifican con la tabla de símbolos específicos de un grupo añadido inicialmente a la transmisión de datos de salida. Sin embargo, si no es simplemente un conjunto de datos, sino el tipo completo de datos codificados, que tiene las mismas regularidades, podemos optar por una tabla global de Huffman. Si tenemos dicha tabla global de Huffman, podemos definir de modo predeterminado la búsqueda en nuestros ejecutables, lo que hace que la compresión y la descompresión sean un poco más económicas (excepto el ejemplo general inicial y la definición de modo predeterminado). Por ejemplo, si supiéramos que nuestro conjunto de datos sería una prosa del idioma inglés, las tablas de frecuencia de mensajes serían reconocidas y bastante consistentes en los conjuntos de datos


Compresión Lempel-Ziv

Probablemente, la técnica de compresión sin pérdidas más significativa es la técnica Lempel-Ziv. Lo que se explica aquí es LZ78, pero LZ77 y otras variantes funcionan de manera similar. La idea en LZ78 es codificar una secuencia de bytes en transferencia con una tabla dinámica. Al inicio de la compresión de un flujo de bits, la tabla LZ se completa con el conjunto real de símbolos junto con lotes en blanco. Se utilizan varios tamaños de tablas, pero para mi ejemplo anterior (compresión de espacios en blanco) sobre los números de teléfono, supongamos que usamos una tabla de 2 entradas (esto debería estar bien para nuestro ejemplo, aunque es demasiado pequeña para la mayoría de los otros tipos de datos). En primer lugar, completamos los primeros diez lotes con nuestro alfabeto (numérico). A medida que ingresan los nuevos bytes, primero generamos una entrada existente que graba la secuencia más larga posible, luego completamos el siguiente lote disponible con la secuencia de extensión N+1. En el peor de los casos, utilizamos 5 bits en lugar de 4 bits para un solo símbolo, pero dejamos de utilizar 5 bits para símbolos múltiples en muchos casos. Por ejemplo, la máquina podría hacer esto (un lote de la tabla se resalta con corchetes):

7 --> Lookup: 7 found       --> nothing to add    --> keep looking
7 --> Lookup: 77 not found  --> add '77' to [11]  --> output [7]=00111
2 --> Lookup: 72 not found  --> add '72' to [12]  --> output [7]=00111
7 --> Lookup: 27 not found  --> add '27' to [13]  --> output [2]=00010
6 --> Lookup: 76 not found  --> add '76' to [14]  --> output [7]=00111
2 --> Lookup: 62 not found  --> add '62' to [15]  --> output [6]=00110
8 --> Lookup: 28 not found  --> add '28' to [16]  --> output [2]=00010

Hasta el momento, no obtuvimos nada, pero continuemos con el siguiente número de teléfono:

7 --> Lookup: 87 not found  --> add '87 to [17]   --> output [8]=00100
7 --> Lookup: 77 found      --> nothing to add    --> keep looking
2 --> Lookup: 772 not found --> add '772' to [18] --> output [11]=01011
8 --> Lookup: 28 found      --> nothing to add    --> keep looking
6 --> Lookup: 286 not found --> add '286' to [19] --> output [16]=10000
....

Los pasos deberían ser suficientes como para mostrar el patrón. Aún no hemos alcanzado ninguna compresión, pero tenga en cuenta que ya pudimos utiliza el lote 11 y el 16, por lo que obtuvimos dos símbolos con una salida de datos en cada caso. También hemos acumulado la secuencia muy útil de bytes 772 en el lote 18 que, más tarde se probaría la utilizada en la transmisión.

Lo que hace LZ78 es completar una tabla de símbolos con entradas útiles (con suerte), luego escribirla, borrarla y comenzar una nueva. En lo que a esto respecta, una tabla de símbolos de 32 entradas probablemente sea demasiado pequeña, dado que lo borraremos antes de que se alcance un lote de re utilización de 772 y similar. Pero la tabla de símbolos pequeña es fácil de ilustrar.

En los conjuntos de datos típicos, las variantes de Lempel-Ziv alcanzan niveles de compresión mucho mejores que Huffman o RLE. Por otro lado, las variantes de Lempel-Ziv son muy costosas en lo que respecta al ciclo y pueden utilizar tablas grandes en la memoria. La mayoría de las herramientas de compresión de la vida real y las bibliotecas utilizan una combinación de técnicas de Lempel-Ziv y Huffman.


Solucionar el problema correcto

A menudo, seleccionar el algoritmo correcto puede crear mejoras de gran magnitud en algoritmos incorrectos demasiado optimizados y seleccionar la representación de datos correcta es más importante que los métodos de compresión (que siempre son una suerte de optimización post hoc de las funciones deseadas). El ejemplo simple del conjunto de datos utilizado en este artículo es un caso perfecto donde volver a conceptualizar el problema sería realmente un mejor intento que utilizar cualquiera de las técnicas de compresión ilustradas.

Piense de nuevo en lo que representan nuestros datos. No es una recopilación muy general de los datos y las restricciones rígidas a priori nos permiten re formular nuestro problema en su totalidad. Lo que tenemos es un máximo de 30.000 números de teléfono (7720000 hasta 7749999), algunos de los cuales se encuentran activos y otros no. Tenemos el "deber", por así decirlo, de producir una representación completa de cada número de teléfono que está activo, pero simplemente para indicar el hecho binario que está activo. Al pensar en el problema de esta manera, simplemente podemos asignar 30.000 bits de memoria y almacenamiento, y que cada bit indique "sí" o "no" ante la presencia de un número telefónico. El ordenamiento de los bits en el conjunto de bits puede ser en orden simple ascendente desde el número de teléfono más bajo al más alto en rango.

La solución de conjunto de bits es la mejor en casi todos los puntos de vista. Asigna exactamente 3750 bites para representar el conjunto de datos; las múltiples técnicas de compresión utilizarán una cantidad variada de almacenamiento según los dos números de teléfono en el conjunto y la eficiencia de la compresión. Pero, si 10.000 de 30.000 números de teléfono posibles se encuentran activos e incluso una técnica de compresión muy eficiente requiere de varios bites por número de teléfono, entonces el conjunto de bits es una mejor orden de magnitud. En términos de las demandas de los CPU, el conjunto de bits no es solo mejor que cualquiera de los métodos de compresión discutidos, sino que también es mejor que un método sin compresión y sin modificaciones de la lista de todos los números como series. Pasar a un conjunto de bits e incrementar un contador de "números de teléfono actuales" puede realizarse de forma efectiva y, principalmente, dentro de un caché incorporado en el chip de un CPU moderno.

La lección que se aprende a partir de este ejemplo simple es ciertamente que no todos los problemas tienen un atajo mágico (como lo tiene este). Sinceramente, muchos problemas requieren una memoria significante, un ancho de banda, almacenamiento y recursos de CPU; y en muchos de esos casos, las técnicas de compresión pueden ayudar a traspasar o modificar estas barreras. Pero, podría sugerirse una lección más moderada: Antes de que se apliquen las técnicas de compresión, es una buena idea asegurarse de que su conceptualización inicial de la representación de datos sea buena.

En honor a Claude Shannon

Recursos

Comentarios

developerWorks: Ingrese

Los campos obligatorios están marcados con un asterisco (*).


¿Necesita un IBM ID?
¿Olvidó su IBM ID?


¿Olvidó su Password?
Cambie su Password

Al hacer clic en Enviar, usted está de acuerdo con los términos y condiciones de developerWorks.

 


La primera vez que inicie sesión en developerWorks, se creará un perfil para usted. La información en su propio perfil (nombre, país/región y nombre de la empresa) se muestra al público y acompañará a cualquier contenido que publique, a menos que opte por la opción de ocultar el nombre de su empresa. Puede actualizar su cuenta de IBM en cualquier momento.

Toda la información enviada es segura.

Elija su nombre para mostrar



La primera vez que inicia sesión en developerWorks se crea un perfil para usted, teniendo que elegir un nombre para mostrar en el mismo. Este nombre acompañará el contenido que usted publique en developerWorks.

Por favor elija un nombre de 3 - 31 caracteres. Su nombre de usuario debe ser único en la comunidad developerWorks y debe ser distinto a su dirección de email por motivos de privacidad.

Los campos obligatorios están marcados con un asterisco (*).

(Por favor elija un nombre de 3 - 31 caracteres.)

Al hacer clic en Enviar, usted está de acuerdo con los términos y condiciones de developerWorks.

 


Toda la información enviada es segura.


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=90
Zone=Linux
ArticleID=844324
ArticleTitle=Un manual sobre compresión de datos
publish-date=11052012