Compresión de datos
En el procesamiento de señales , la compresión de datos , la codificación de fuentes , [1] o la reducción de la tasa de bits es el proceso de codificación de información utilizando menos bits que la representación original. [2] Cualquier compresión en particular es con pérdida o sin pérdida . La compresión sin pérdidas reduce los bits al identificar y eliminar la redundancia estadística . No se pierde información en la compresión sin pérdidas. La compresión con pérdida reduce los bits al eliminar información innecesaria o menos importante. [3] Por lo general, un dispositivo que realiza la compresión de datos se denomina codificador y uno que realiza la inversión del proceso (descompresión) como decodificador.
El proceso de reducir el tamaño de un archivo de datos a menudo se denomina compresión de datos. En el contexto de la transmisión de datos , se denomina codificación de fuente; codificación realizada en la fuente de los datos antes de que se almacenen o transmitan. [4] La codificación de fuente no debe confundirse con la codificación de canal , para la detección y corrección de errores o la codificación de línea , los medios para mapear datos en una señal.
La compresión es útil porque reduce los recursos necesarios para almacenar y transmitir datos. Los recursos computacionales se consumen en los procesos de compresión y descompresión. La compresión de datos está sujeta a una compensación de complejidad de espacio-tiempo . Por ejemplo, un esquema de compresión para video puede requerir un hardware costoso para que el video se descomprima lo suficientemente rápido como para verlo mientras se descomprime, y la opción de descomprimir el video por completo antes de verlo puede ser un inconveniente o requerir almacenamiento adicional. El diseño de esquemas de compresión de datos involucra compensaciones entre varios factores, incluido el grado de compresión, la cantidad de distorsión introducida (cuando se usa compresión de datos con pérdida), y los recursos computacionales necesarios para comprimir y descomprimir los datos [5]
Los algoritmos de compresión de datos sin pérdidas suelen explotar la redundancia estadística para representar datos sin perder ninguna información , de modo que el proceso sea reversible. La compresión sin pérdidas es posible porque la mayoría de los datos del mundo real exhiben redundancia estadística. Por ejemplo, una imagen puede tener áreas de color que no cambian en varios píxeles; en lugar de codificar "píxel rojo, píxel rojo,..." los datos pueden codificarse como "279 píxeles rojos". Este es un ejemplo básico de codificación de longitud de ejecución ; hay muchos esquemas para reducir el tamaño del archivo eliminando la redundancia.
Los métodos de compresión Lempel-Ziv (LZ) se encuentran entre los algoritmos más populares para el almacenamiento sin pérdidas. [6] DEFLATE es una variación de LZ optimizada para la velocidad de descompresión y la relación de compresión, pero la compresión puede ser lenta. A mediados de la década de 1980, siguiendo el trabajo de Terry Welch , el algoritmo Lempel-Ziv-Welch (LZW) se convirtió rápidamente en el método elegido para la mayoría de los sistemas de compresión de propósito general. LZW se utiliza en imágenes GIF , programas como PKZIP y dispositivos de hardware como módems. [7]Los métodos LZ utilizan un modelo de compresión basado en tablas en el que las entradas de la tabla se sustituyen por cadenas de datos repetidas. Para la mayoría de los métodos LZ, esta tabla se genera dinámicamente a partir de datos anteriores en la entrada. La tabla en sí suele estar codificada por Huffman . Los códigos basados en la gramática como este pueden comprimir entradas altamente repetitivas de manera extremadamente efectiva, por ejemplo, una recopilación de datos biológicos de la misma especie o de especies estrechamente relacionadas, una gran colección de documentos versionados, archivo de Internet, etc. La tarea básica de los códigos basados en la gramática es construir una gramática libre de contexto que deriva de una sola cadena. Otros algoritmos prácticos de compresión de gramática incluyen Sequitur y Re-Pair.
