La codificación delta es una forma de almacenar o transmitir datos en forma de diferencias (deltas) entre datos secuenciales en lugar de archivos completos; En términos más generales, esto se conoce como diferenciación de datos . La codificación delta a veces se denomina compresión delta , particularmente cuando se requieren historiales de cambios archivados (por ejemplo, en el software de control de revisiones ).
Las diferencias se registran en archivos discretos llamados "deltas" o "diffs". En situaciones en las que las diferencias son pequeñas (por ejemplo, el cambio de unas pocas palabras en un documento grande o el cambio de unos pocos registros en una tabla grande), la codificación delta reduce en gran medida la redundancia de datos. Las colecciones de deltas únicos ocupan mucho más espacio que sus equivalentes no codificados.
Desde un punto de vista lógico, la diferencia entre dos valores de datos es la información necesaria para obtener un valor del otro (ver entropía relativa) . La diferencia entre valores idénticos (bajo alguna equivalencia ) a menudo se denomina 0 o elemento neutro.
Quizás el ejemplo más simple sea almacenar valores de bytes como diferencias (deltas) entre valores secuenciales, en lugar de los valores mismos. Entonces, en lugar de 2, 4, 6, 9, 7, almacenaríamos 2, 2, 2, 3, −2. Esto reduce la varianza (rango) de los valores cuando las muestras vecinas están correlacionadas, lo que permite un menor uso de bits para los mismos datos. El formato de sonido IFF 8SVX aplica esta codificación a los datos de sonido sin procesar antes de aplicarles compresión. Ni siquiera todas las muestras de sonido de 8 bits se comprimen mejor cuando se codifican delta, y la usabilidad de la codificación delta es aún menor para muestras de 16 bits y mejores. Por lo tanto, los algoritmos de compresión a menudo eligen la codificación delta sólo cuando la compresión es mejor que sin ella. Sin embargo, en la compresión de vídeo , los fotogramas delta pueden reducir considerablemente el tamaño del fotograma y se utilizan en prácticamente todos los códecs de compresión de vídeo .
Un delta se puede definir de dos maneras: delta simétrico y delta dirigido . Un delta simétrico se puede expresar como
donde y representan dos versiones.
Un delta dirigido , también llamado cambio, es una secuencia de operaciones de cambio (elementales) que, cuando se aplica a una versión , produce otra versión (tenga en cuenta la correspondencia con los registros de transacciones en las bases de datos). En las implementaciones informáticas, normalmente toman la forma de un lenguaje con dos comandos: copiar datos de v1 y escribir datos literales .
Una variación de la codificación delta que codifica las diferencias entre los prefijos o sufijos de cadenas se llama codificación incremental . Es particularmente eficaz para listas ordenadas con pequeñas diferencias entre cadenas, como una lista de palabras de un diccionario .
La naturaleza de los datos a codificar influye en la eficacia de un algoritmo de compresión particular.
La codificación delta funciona mejor cuando los datos tienen una variación pequeña o constante; para un conjunto de datos sin ordenar, es posible que haya poca o ninguna compresión posible con este método.
En la transmisión codificada delta a través de una red donde solo hay una copia del archivo disponible en cada extremo del canal de comunicación, se utilizan códigos de control de errores especiales para detectar qué partes del archivo han cambiado desde su versión anterior. Por ejemplo, rsync utiliza un algoritmo de suma de comprobación móvil basado en la suma de comprobación adler-32 de Mark Adler .
El siguiente código C realiza una forma sencilla de codificación y decodificación delta en una secuencia de caracteres:
void delta_encode ( carácter sin firmar * búfer , longitud int ) { carácter sin firmar último = 0 ; for ( int i = 0 ; i < longitud ; i ++ ) { corriente de carácter sin signo = buffer [ i ]; buffer [ i ] = actual - último ; último = actual ; } } void delta_decode ( carácter sin firmar * búfer , longitud int ) { carácter sin firmar último = 0 ; for ( int i = 0 ; i < longitud ; i ++ ) { char delta sin firmar = buffer [ i ]; buffer [ i ] = delta + último ; último = búfer [ i ]; } } Otro ejemplo de uso de la codificación delta es el RFC 3229, "Codificación delta en HTTP", que propone que los servidores HTTP deberían poder enviar páginas web actualizadas en forma de diferencias entre versiones (deltas), lo que debería disminuir el tráfico de Internet, como la mayoría. Las páginas cambian lentamente con el tiempo, en lugar de reescribirse por completo repetidamente:
Este documento describe cómo se puede admitir la codificación delta como una extensión compatible con HTTP/1.1.
Muchas solicitudes HTTP (Protocolo de transporte de hipertexto) provocan la recuperación de instancias de recursos ligeramente modificadas para las cuales el cliente ya tiene una entrada de caché. Las investigaciones han demostrado que estas actualizaciones de modificación son frecuentes y que las modificaciones suelen ser mucho más pequeñas que la entidad real. En tales casos, HTTP haría un uso más eficiente del ancho de banda de la red si pudiera transferir una descripción mínima de los cambios, en lugar de toda la nueva instancia del recurso.
[...] Creemos que podría ser posible admitir rsync utilizando el marco de "manipulación de instancias" que se describe más adelante en este documento, pero esto no se ha resuelto en detalle.
El marco sugerido basado en rsync se implementó en el sistema rproxy como un par de servidores proxy HTTP. [1] Al igual que la implementación básica basada en vcdiff, ambos sistemas rara vez se utilizan.
La copia delta es una forma rápida de copiar un archivo que está parcialmente modificado, cuando hay una versión anterior presente en la ubicación de destino. Con la copia delta, sólo se copia la parte modificada de un archivo. Generalmente se utiliza en software de copia de seguridad o de archivos , a menudo para ahorrar ancho de banda al copiar entre computadoras a través de una red privada o Internet. Un ejemplo notable de código abierto es rsync . [2] [3] [4]
Muchos de los servicios de copia de seguridad en línea adoptan esta metodología, a menudo conocida simplemente como deltas , para brindar a sus usuarios versiones anteriores del mismo archivo de copias de seguridad anteriores. Esto reduce los costos asociados, no sólo en la cantidad de datos que deben almacenarse en diferentes versiones (ya que cada versión modificada de un archivo debe ofrecerse para que los usuarios puedan acceder a ella), sino también los costos de carga (y a veces la descarga) de cada archivo que se ha actualizado (debiendo usarse solo el delta más pequeño, en lugar de todo el archivo).
Para paquetes de software grandes, generalmente hay pocos datos modificados entre versiones. Muchos proveedores optan por utilizar transferencias delta para ahorrar tiempo y ancho de banda.
Diff es un programa de comparación de archivos, que se utiliza principalmente para archivos de texto. De forma predeterminada, genera deltas simétricos que son reversibles. Dos formatos utilizados para parches de software , contexto y unificado , proporcionan líneas de contexto adicionales que permiten tolerar cambios en el número de líneas.
El sistema de control de código fuente de Git emplea compresión delta en una operación auxiliar de "reempaquetado de git". Los objetos en el repositorio que aún no han sido comprimidos delta ("objetos sueltos") se comparan con un subconjunto elegido heurísticamente de todos los demás objetos, y los datos comunes y las diferencias se concatenan en un "archivo de paquete" que luego se comprime usando métodos convencionales. métodos. En casos de uso comunes, donde los archivos de origen o de datos se cambian de forma incremental entre confirmaciones, esto puede generar importantes ahorros de espacio. La operación de reempaquetado generalmente se realiza como parte del proceso "git gc", que se activa automáticamente cuando la cantidad de objetos sueltos o archivos empaquetados excede los umbrales configurados.
El formato está documentado en la página de formato de paquete de la documentación de Git. Implementa un delta dirigido. [5]
Un formato general para la codificación delta dirigida es VCDIFF, descrito en RFC 3284. Las implementaciones de software libre incluyen Xdelta y open-vcdiff.
El formato de diferencia genérico (GDIFF) es otro formato de codificación delta dirigida. Fue enviado al W3C en 1997. [6] En muchos casos, VCDIFF tiene una mejor tasa de compresión que GDIFF.
Bsdiff es un programa de diferenciación binaria que utiliza clasificación por sufijos . Para ejecutables que contienen muchos cambios en las direcciones de los punteros, funciona mejor que las codificaciones "copia y literal" de tipo VCDIFF. La intención es encontrar una manera de generar una pequeña diferencia sin necesidad de analizar el código ensamblador (como en Courgette de Google). Bsdiff logra esto permitiendo coincidencias de "copia" con errores, que luego se corrigen utilizando una matriz adicional de diferencias de bytes "agregadas". Dado que esta matriz es en su mayoría cero o valores repetidos para cambios de compensación, ocupa poco espacio después de la compresión. [7]
Bsdiff es útil para actualizaciones delta. Google usa bsdiff en Chromium y Android. La característica deltarpm del Administrador de paquetes RPM se basa en un bsdiff muy modificado que puede usar una tabla hash para realizar coincidencias. [8] FreeBSD también utiliza bsdiff para las actualizaciones. [9]
Desde la versión 4.3 de bsdiff en 2005, se han producido varias mejoras o correcciones. Google mantiene múltiples versiones del código para cada uno de sus productos. [10] FreeBSD adopta muchos de los cambios compatibles de Google, principalmente una corrección de vulnerabilidad y un cambio a la divsufsortrutina más rápida de clasificación de sufijos. [11] Debian tiene una serie de ajustes de rendimiento en el programa. [12]
ddelta es una reescritura de bsdiff propuesta para su uso en las actualizaciones delta de Debian. Entre otras mejoras de eficiencia, utiliza una ventana deslizante para reducir el costo de memoria y CPU. [13]