A compresión de datos é o proceso de representar unha información mediante unha cantidade menor de datos ca na súa representación orixinal. Un sistema de compresión consta dun codificador, que transforma os datos de entrada nunha representación comprimida, e dun descodificador, que reconstrúe a información a partir dela. A compresión emprégase para reducir o espazo de almacenamento e a taxa de transmisión, mais introduce custos de cálculo, memoria e latencia que dependen do método utilizado.
Distínguense dous réximes principais. Na compresión sen perda, a descodificación recupera exactamente os datos iniciais; é necesaria para texto, programas, bases de datos e calquera información na que un cambio dun só símbolo poida alterar o significado. Na compresión con perda, o resultado é unha aproximación controlada do orixinal, o que permite reducións maiores en imaxes, son ou vídeo cando se acepta certa distorsión.
Os límites fundamentais da compresión proceden da teoría da información. A entropía dunha fonte mide a taxa media mínima á que pode representarse sen perda baixo un modelo probabilístico, mentres que a teoría taxa-distorsión caracteriza o compromiso óptimo entre o número de bits e o erro permitido na reconstrución.
Historia miniatura|256x256px|Claude Shannon En 1948, Claude Shannon formulou a entropía e os teoremas de codificación de fonte que estableceron límites matemáticos para a representación eficiente da información. En 1952, David Huffman publicou un método para construír códigos de prefixo de redundancia mínima.
Jacob Ziv e Abraham Lempel presentaron en 1977 e 1978 algoritmos universais baseados en coincidencias e dicionarios incrementais, que deron lugar a numerosas variantes e formatos de uso xeral. A codificación aritmética proporcionou outra vía para aproximarse á entropía sen asignar necesariamente un número enteiro de bits a cada símbolo.
Desde finais do século XX, a normalización de formatos de imaxe, son e vídeo combinou estas ideas con predición, transformacións, cuantización e modelos perceptivos. Os estándares especifican a interoperabilidade do fluxo, mais a selección de parámetros e as decisións do codificador continuaron evolucionando de maneira independente.
Modelo básico
Codificador e descodificador
Sexa o conxunto de mensaxes posibles e o conxunto das cadeas binarias finitas. Un codificador pode modelarse mediante unha aplicación
e o descodificador mediante
Nun código sen perda esíxese para toda mensaxe admisible . En consecuencia, debe ser inxectivo. Nun código con perda, pode diferir de , e a calidade mídese mediante unha función de distorsión .
Non é posible que un compresor sen perda reduza todas as cadeas binarias de lonxitude . Hai cadeas desa lonxitude, pero só cadeas de lonxitude menor ca . Polo principio do pombal, se algunhas entradas se representan con menos bits, outras deben manter o tamaño ou medrar. A utilidade práctica da compresión depende, pois, de que os datos reais presenten regularidades ou de que o seu modelo asigne maior probabilidade a unhas mensaxes ca a outras.
Redundancia e irrelevancia
Os métodos sen perda eliminan redundancia: repeticións, predicibilidade estatística, correlación entre mostras ou estruturas que poden reconstruírse. Por exemplo, unha secuencia longa do mesmo símbolo pode substituírse polo símbolo e o número de repeticións, e unha mostra de son pode predicirse aproximadamente a partir das anteriores codificando só o residuo da predición.
Os métodos con perda tamén eliminan información considerada irrelevante para unha finalidade ou un modelo perceptivo. Un codificador de imaxe pode descartar precisión en coeficientes de alta frecuencia e un codificador de son pode asignar menos bits a compoñentes pouco perceptibles. Esta irrelevancia non é absoluta: depende da tarefa, do dispositivo, da distancia de observación e do observador, polo que unha configuración axeitada para consumo audiovisual pode non selo para análise científica, diagnóstico ou conservación documental.
Medidas de rendemento alt=A entropía dunha fonte binaria é máxima cando os dous símbolos son equiprobables e diminúe cando un deles se volve predicible.|miniatura|277x277px|Curva da entropía binaria entre as probabilidades cero e un, cun máximo dun bit para p igual a un medio. Se é o tamaño orixinal e o tamaño comprimido, a razón de compresión pode definirse como
Un valor indica que a representación orixinal ocupa catro veces máis. A fracción de espazo aforrada é
Tamén se empregan a taxa de bits, expresada en bits por segundo, e taxas normalizadas como bits por símbolo, bits por mostra ou bits por píxel. Cómpre indicar sempre se o tamaño inclúe cabeceiras, metadatos, dicionarios e índices, pois eses elementos poden dominar o resultado en ficheiros pequenos.<ref name="Sayood2017" />
Na compresión con perda cómpre medir tamén a distorsión. Para datos numéricos, unha medida frecuente é o erro cadrático medio
En imaxes úsase a miúdo a relación sinal-ruído de pico (PSNR),
onde é o maior valor posible dunha mostra. Nin o erro cadrático medio nin a PSNR reproducen por completo a calidade percibida; dúas reconstrucións coa mesma medida poden presentar artefactos moi diferentes.<ref name="Sayood2017" />
Outros criterios de enxeñaría son o tempo de codificación e descodificación, o consumo de memoria e enerxía, a latencia, a posibilidade de acceso aleatorio, a capacidade de procesamento en fluxo e a tolerancia a erros. Non existe, polo tanto, un único algoritmo óptimo para todos os tipos de datos e condicións de uso.
Fundamentos da teoría da información
Entropía e límite sen perda
Para unha variable aleatoria discreta con resultados e probabilidades , a entropía de Shannon é
Un resultado de probabilidade cero non contribúe á suma. A entropía exprésase en bits por símbolo e aumenta cando a fonte é menos predicible. Para códigos binarios de prefixo, a desigualdade de Kraft relaciona as lonxitudes das palabras código coa existencia dun código descodificable de maneira instantánea. Se as probabilidades son coñecidas, a lonxitude media dun código de Huffman satisfai
O teorema de codificación de fonte de Shannon mostra que, ao codificar bloques longos dunha fonte estacionaria, a taxa media pode achegarse á entropía, pero non baixar dela mantendo unha probabilidade de erro arbitrariamente pequena.<ref name="Shannon1948" />
Para unha fonte binaria con probabilidade dun dos símbolos,
Esta función vale cero para e , e alcanza un bit en . Así, a mera presenza de dous símbolos non determina o límite de compresión: importa a súa distribución e, en fontes con memoria, tamén a dependencia entre símbolos sucesivos.
Compromiso taxa-distorsión
Na compresión con perda, a función taxa-distorsión é a menor taxa media coa que unha fonte pode representarse mantendo unha distorsión esperada non superior a . Formalmente,
onde é a información mutua entre a fonte e a reconstrución. A función é non crecente e convexa: admitir máis distorsión non require unha taxa maior. Trátase dun límite teórico; un códec concreto pode quedar por riba debido ás restricións do algoritmo, á lonxitude finita dos bloques e ao custo da información auxiliar.
Compresión sen perda
Codificación por repeticións
A codificación por lonxitude de series (RLE) substitúe cada serie de símbolos iguais por un par formado polo símbolo e a súa lonxitude. É eficaz en datos con series longas, como máscaras binarias ou determinadas imaxes sintéticas, pero pode aumentar o tamaño cando os símbolos cambian con frecuencia. Por iso adoita combinarse con transformacións que agrupan valores semellantes ou reservarse para rexións nas que resulta vantaxosa.
Códigos de entropía
A codificación de Huffman constrúe un código de prefixo combinando repetidamente os dous símbolos ou nodos de menor probabilidade. Os símbolos frecuentes reciben palabras curtas e os infrecuentes, palabras máis longas. O algoritmo produce un código de prefixo de lonxitude media mínima entre os que asignan a cada símbolo un número enteiro de bits. alt=Árbore binaria de Huffman con cinco símbolos nas follas, probabilidades nos nodos e ramas etiquetadas con cero e un.|miniatura|253x253px|Exemplo dunha árbore de Huffman. O código de cada símbolo obtense seguindo desde a raíz as ramas etiquetadas con 0 e 1; neste exemplo a lonxitude media é 2,2 bits por símbolo. A codificación aritmética representa unha secuencia completa mediante un subintervalo do intervalo . Cada símbolo subdivide o intervalo actual segundo o modelo probabilístico. A lonxitude do número necesario para identificar o intervalo pode achegarse á información da secuencia sen a restrición dun número enteiro de bits por símbolo, aínda que unha implementación real debe controlar a precisión finita, o reescalado e o modelo de probabilidades.
Os códigos de entropía non crean por si sós un bo modelo. Se as probabilidades estimadas non se corresponden cos datos, as palabras ou intervalos asignados poden ser ineficientes. Os compresores adaptativos actualizan o modelo durante a codificación para non ter que transmitir unha táboa completa, pero codificador e descodificador deben realizar exactamente as mesmas actualizacións.
Métodos de dicionario
Os algoritmos de Lempel e Ziv substitúen fragmentos repetidos por referencias. LZ77 mantén unha xanela sobre os datos xa procesados e describe unha coincidencia mediante a distancia ata unha aparición anterior e a súa lonxitude. LZ78 crea un dicionario incremental de frases e emite referencias ás entradas xa coñecidas.<ref name="ZivLempel1978"></ref>
Estes métodos son universais en sentidos matemáticos precisos: poden aproximar a taxa alcanzable para clases amplas de fontes sen coñecer previamente a súa distribución. Iso non significa que compriman por igual calquera ficheiro nin que unha implementación concreta alcance o límite en bloques pequenos.<ref name="ZivLempel1977" />
O formato DEFLATE combina unha procura de coincidencias baseada en LZ77 con códigos de Huffman. Divide o fluxo en bloques que poden estar sen comprimir ou usar táboas de Huffman fixas ou transmitidas no propio bloque. A especificación permite procesar fluxos arbitrariamente longos cunha cantidade acoutada de memoria intermedia.
Transformacións e modelos de contexto
Algunhas técnicas reorganizan os datos antes da codificación. A transformada de Burrows–Wheeler permuta reversiblemente un bloque para agrupar símbolos con contextos semellantes; adoita combinarse cunha transformación move-to-front, RLE e un código de entropía. A transformación non reduce por si soa o número de bits.
Os modelos de contexto estiman a probabilidade dun símbolo a partir dos símbolos anteriores ou doutra información lateral. Un contexto máis longo pode capturar máis estrutura, pero require máis memoria e pode producir estimacións pouco fiables cando hai poucos datos. Os sistemas prácticos combinan contextos, suavizado e adaptación para equilibrar precisión e complexidade.<ref name="Sayood2017" />
Compresión con perda
Cuantización alt=Curva suave comparada cunha reconstrución en chanzos sobre niveis discretos; varios segmentos verticais indican o erro entre ambas.|miniatura|382x382px|A cuantización aproxima os valores dun sinal mediante un conxunto finito de niveis. A diferenza entre o valor orixinal e o reconstruído é o erro de cuantización. A cuantización substitúe un conxunto amplo ou continuo de valores por un número finito de niveis. Nun cuantizador escalar, cada mostra procésase individualmente; nun cuantizador vectorial, codifícanse conxuntamente bloques de mostras. O paso de cuantización controla de maneira directa o compromiso entre precisión e taxa: niveis máis separados requiren menos información, pero aumentan o erro de reconstrución. Predición e codificación por transformadas