Compresión de datos

Compresión de datos
Instancia de proceso técnico  Subclase de procesamento de datos optimización da capacidade  Causa de ficheiro comprimido  Uso transmisión copia de seguranza  Medio usado código algoritmo
Características  Produto ou servizo ficheiro comprimido
Fontes e ligazóns Freebase /m/0279m MeSH D044962 OpenAlex C78548338
Wikidata C:Commons

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

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 ${\mathcal {X}}$ o conxunto de mensaxes posibles e $\{0,1\}^{*}$ o conxunto das cadeas binarias finitas. Un codificador pode modelarse mediante unha aplicación

$E:{\mathcal {X}}\longrightarrow \{0,1\}^{*},$

e o descodificador mediante

$D:\{0,1\}^{*}\longrightarrow {\widehat {\mathcal {X}}}.$

Nun código sen perda esíxese $D(E(x))=x$ para toda mensaxe admisible $x$. En consecuencia, $E$ debe ser inxectivo. Nun código con perda, $D(E(x))={\hat {x}}$ pode diferir de $x$, e a calidade mídese mediante unha función de distorsión $d(x,{\hat {x}})$.

Non é posible que un compresor sen perda reduza todas as cadeas binarias de lonxitude $n$. Hai $2^{n}$ cadeas desa lonxitude, pero só $2^{n}-1$ cadeas de lonxitude menor ca $n$. 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

Curva da entropía binaria entre as probabilidades cero e un, cun máximo dun bit para p igual a un medio.

Se $B_{o}$ é o tamaño orixinal e $B_{c}$ o tamaño comprimido, a razón de compresión pode definirse como

$C={\frac {B_{o}}{B_{c}}}.$

Un valor $C=4$ indica que a representación orixinal ocupa catro veces máis. A fracción de espazo aforrada é

$A=1-{\frac {B_{c}}{B_{o}}}.$

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.

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

$\operatorname {ECM} (x,{\hat {x}})={\frac {1}{N}}\sum _{i=1}^{N}(x_{i}-{\hat {x}}_{i})^{2}.$

En imaxes úsase a miúdo a relación sinal-ruído de pico (PSNR),

$\operatorname {PSNR} =10\log _{10}\left({\frac {L^{2}}{\operatorname {ECM} }}\right),$

onde $L$ é 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.

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 $X$ con resultados $x_{1},\ldots ,x_{m}$ e probabilidades $p_{1},\ldots ,p_{m}$, a entropía de Shannon é

$H(X)=-\sum _{i=1}^{m}p_{i}\log _{2}p_{i}.$

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 ${\bar {L}}$ dun código de Huffman satisfai

$H(X)\leq {\bar {L}}<H(X)+1.$

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.

Para unha fonte binaria con probabilidade $p$ dun dos símbolos,

$H_{2}(p)=-p\log _{2}p-(1-p)\log _{2}(1-p).$

Esta función vale cero para $p=0$ e $p=1$, e alcanza un bit en $p=1/2$. 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 $R(D)$ é a menor taxa media coa que unha fonte pode representarse mantendo unha distorsión esperada non superior a $D$. Formalmente,

$R(D)=\min _{p({\hat {x}}|x):\;\mathbb {E} [d(X,{\hat {X}})]\leq D}I(X;{\hat {X}}),$

onde $I(X;{\hat {X}})$ é 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.

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 $[0,1)$. 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.

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.

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.

Compresión con perda

Cuantización

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

Na codificación preditiva calcúlase unha estimación dunha mostra a partir doutras xa coñecidas e codifícase o residuo. Se a predición é boa, o residuo presenta menor varianza e unha distribución máis concentrada. A predición pode empregarse sen perda, cando o residuo se conserva exactamente, ou con perda, cando se cuantiza.

Na codificación por transformadas, un bloque de mostras exprésase nunha base na que a enerxía ou a información relevante se concentra en poucos coeficientes. Transformadas como a transformada discreta do coseno e as transformadas de ondículas permiten cuantizar con distinta precisión as compoñentes. A transformada é reversible salvo polos arredondamentos; a perda principal prodúcese na cuantización dos coeficientes.

O estándar JPEG para imaxe continua inclúe procesos baseados na transformada discreta do coseno, cuantización e codificación de entropía, ademais dun modo sen perda distinto. A conformidade co estándar determina o fluxo codificado e a descodificación, pero non garante que todos os codificadores produzan a mesma calidade nin a mesma razón de compresión.

Modelos perceptivos

Os codificadores de imaxe, son e vídeo poden explotar propiedades da percepción humana, como a distinta sensibilidade ás frecuencias, ao contraste ou aos erros enmascarados por outros estímulos. Estes modelos permiten concentrar bits onde a distorsión resulta máis visible. Porén, unha métrica perceptiva representa unha aproximación e pode non predicir a calidade para todos os contidos, persoas ou usos.

En vídeo, ademais da redundancia espacial de cada fotograma, aprovéitase a redundancia temporal mediante predición entre fotogramas e compensación de movemento. Os estándares híbridos combinan predición, transformación, cuantización, filtros e codificación de entropía. A Recomendación H.264/AVC define a sintaxe e os procesos de descodificación, mentres deixa marxe para que os codificadores escollan modos e parámetros.

Formatos e estándares

Un algoritmo describe un procedemento de compresión; un formato define como se organizan os bits, metadatos e parámetros; e un contedor pode reunir fluxos codificados, índices e información adicional. Un mesmo formato pode permitir varios métodos e un contedor pode transportar diferentes códecs. Confundir estes niveis leva, por exemplo, a atribuír ao contedor unha propiedade que depende realmente do códec seleccionado.

Exemplos de formatos e técnicas

Formato ou estándar	Tipo habitual	Datos	Técnicas principais
DEFLATE	Sen perda	Uso xeral	Coincidencias LZ77 e códigos de Huffman
PNG	Sen perda	Imaxe rasterizada	Filtros por liña e DEFLATE
JPEG	Xeralmente con perda; admite un proceso sen perda	Imaxe continua	Predición ou transformada, cuantización e codificación de entropía
FLAC	Sen perda	Son PCM	Descorrelación entre canles, predición e codificación do residuo
H.264/AVC	Habitualmente con perda	Vídeo	Predición espacial e temporal, transformación, cuantización e codificación de entropía

As extensións de ficheiro non abondan para determinar o método nin os seus parámetros. Ademais, a mesma familia pode conter perfís, niveis e opcións con requisitos distintos. Para interoperabilidade e conservación cómpre identificar a versión da especificación e conservar os metadatos necesarios para a descodificación.

Deseño e elección dun compresor

O rendemento depende do tipo de datos e do obxectivo. Un compresor xeral baseado en dicionario pode funcionar ben en texto e programas, mentres que un códec especializado aproveita modelos de sinal, como a correlación entre mostras de son ou entre fotogramas. Comprimir de novo datos xa comprimidos adoita ofrecer pouca mellora e pode aumentar o tamaño pola información de control. Se a segunda etapa é con perda, tamén pode acumular artefactos.

Os bloques grandes permiten captar dependencias afastadas e amortizar cabeceiras, pero requiren máis memoria, aumentan a latencia e dificultan o acceso aleatorio. Os bloques independentes, puntos de reinicio e índices melloran a busca e a recuperación tras un erro a cambio dunha taxa maior. En sistemas en tempo real, a velocidade e a latencia de descodificación poden importar máis ca un pequeno incremento da razón de compresión.

Unha comparación reproducible debe especificar o corpus, as versións dos programas, os parámetros, o equipamento, o número de execucións e as métricas. Escoller só ficheiros favorables ou comparar configuracións con calidades distintas produce conclusións enganosas. Para métodos con perda débese presentar conxuntamente a taxa e a calidade, non unha delas illada.

Robustez e seguridade

A compresión elimina redundancia que tamén podería axudar a tolerar erros. Unha corrupción pequena nun fluxo comprimido pode impedir interpretar moitos datos posteriores, especialmente cando altera unha táboa, unha referencia ou a sincronización. Por iso os formatos poden incorporar sumas de comprobación, marcadores de reinicio ou bloques independentes. DEFLATE recomenda que os sistemas proporcionen un mecanismo para validar a integridade dos datos comprimidos.

Unha bomba de descompresión é unha entrada pequena deseñada para expandirse ata consumir unha cantidade desproporcionada de memoria, almacenamento ou tempo. Os descodificadores que procesan datos non fiables deben limitar o tamaño de saída, a profundidade de aniñamento, a memoria e o tempo de execución, e validar as dimensións e lonxitudes antes de reservar recursos.

O tamaño comprimido tamén pode actuar como canle lateral. Se un atacante pode introducir texto que se comprime no mesmo contexto ca un segredo e observar a lonxitude resultante, as coincidencias poden revelar información sobre ese segredo. Na compresión de cabeceiras HTTP/2, a especificación HPACK contempla este risco e permite marcar campos sensibles para que nunca se indexen.

Véxase tamén

Bibliografía

• Cover, Thomas M.; Thomas, Joy A. (2006). Elements of Information Theory (en inglés) (2ª ed.). Wiley-Interscience. ISBN 978-0-47124195-9. doi:10.1002/047174882X. 
• Sayood, Khalid (2017). Introduction to Data Compression (en inglés) (5ª ed.). Morgan Kaufmann. ISBN 978-0-12-809474-7. 

Outros artigos

• Teoría da información
• Entropía da información
• Codificación de Huffman
• Codificación aritmética
• LZ77 e LZ78
• JPEG
• PNG
• FLAC

Ligazóns externas

• Especificación de DEFLATE no RFC Editor.

• Especificación de PNG, terceira edición no W3C.
• Recomendación T.81 da ITU-T.