Compresión de datos
En el procesamiento de señales , la compresión de datos , fuente de codificación , [1] o reducción de velocidad binaria es el proceso de codificar la información usando un menor número de bits de que la representación inicial. [2] Cualquier compresión en particular tiene pérdida o no tiene pérdida . La compresión sin pérdida 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] Normalmente, 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 origen; codificación realizada en la fuente de los datos antes de que se almacenen o transmitan. [4] La codificación de origen 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 entre la complejidad del espacio y el 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 ser visto mientras se descomprime, y la opción de descomprimir el video por completo antes de verlo puede ser inconveniente o requerir almacenamiento adicional. El diseño de esquemas de compresión de datos implica compensaciones entre varios factores, incluido el grado de compresión, la cantidad de distorsión introducida (cuando se usa la 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érdida suelen aprovechar la redundancia estadística para representar datos sin perder información , de modo que el proceso sea reversible. La compresión sin pérdida es posible porque la mayoría de los datos del mundo real presentan 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 ; Existen muchos esquemas para reducir el tamaño de los archivos 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 de elección para la mayoría de los sistemas de compresión de uso 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í está a menudo codificada por Huffman . Los códigos basados en la gramática como este pueden comprimir la entrada altamente repetitiva de manera extremadamente efectiva, por ejemplo, una colección de datos biológicos de la misma especie o de una especie cercanamente relacionada, una gran colección de documentos versionados, archivos 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 gramatical incluyen Sequitur y Re-Pair.
