Codificación delta

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; de manera más general, esto se conoce como diferenciación de datos . La codificación delta a veces se denomina compresión delta , en particular cuando se requieren historiales de archivos de cambios (por ejemplo, en software de control de versiones ).

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 son sustancialmente más eficientes en términos de 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 (véase entropía relativa ) . La diferencia entre valores idénticos (bajo alguna equivalencia ) se suele denominar 0 o elemento neutro.

Quizás el ejemplo más simple es almacenar valores de bytes como diferencias (deltas) entre valores secuenciales, en lugar de los valores en sí 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 con delta, y la usabilidad de la codificación delta es incluso menor para muestras de 16 bits y mejores. Por lo tanto, los algoritmos de compresión a menudo eligen codificar con delta solo cuando la compresión es mejor que sin ella. Sin embargo, en la compresión de video , los cuadros delta pueden reducir considerablemente el tamaño del cuadro y se usan en prácticamente todos los códecs de compresión de video .

Un delta se puede definir de dos maneras: delta simétrico y delta dirigido . Un delta simétrico se puede expresar como

${\displaystyle \Delta (v_{1},v_{2})=(v_{1}\setminus v_{2})\cup (v_{2}\setminus v_{1}),}$

donde y representan dos versiones.$estilo de visualización v_{1}$$estilo de visualización v_{2}$

Un delta dirigido , también llamado cambio, es una secuencia de operaciones de cambio (elementales) que, cuando se aplican a una versión , generan otra versión (nótese la correspondencia con los registros de transacciones en las bases de datos). En las implementaciones informáticas, suelen adoptar la forma de un lenguaje con dos comandos: copiar datos de v1 y escribir datos literales .$estilo de visualización v_{1}$$estilo de visualización v_{2}$

Una variación de la codificación delta que codifica las diferencias entre los prefijos o sufijos de las cadenas se denomina codificación incremental . Es especialmente 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 clasificar, puede haber poca o ninguna compresión posible con este método.

En la transmisión con codificación delta a través de una red en la que solo hay una única 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 continua basado en la suma de comprobación adler-32 de Mark Adler .

El siguiente código C realiza una forma simple de codificación y decodificación delta en una secuencia de caracteres:

void delta_encode ( unsigned char * buffer , int length ) { unsigned char last = 0 ; for ( int i = 0 ; i < length ; i ++ ) { unsigned char current = buffer [ i ]; buffer [ i ] = current - last ; last = current ; } }                                  void delta_decode ( unsigned char * buffer , int length ) { unsigned char last = 0 ; for ( int i = 0 ; i < length ; i ++ ) { unsigned char delta = buffer [ i ]; buffer [ i ] = delta + last ; last = buffer [ 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 puedan enviar páginas web actualizadas en forma de diferencias entre versiones (deltas), lo que debería reducir el tráfico de Internet, ya que la mayoría de las páginas cambian lentamente con el tiempo, en lugar de ser reescritas 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 ligeramente modificadas de recursos para los que el cliente ya tiene una entrada en 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 estos 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 la nueva instancia completa del recurso.

[...] Creemos que podría ser posible soportar rsync usando 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 proxies 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 ha sido modificado parcialmente, cuando existe una versión anterior en la ubicación de destino. Con la copia delta, solo se copia la parte modificada de un archivo. Se suele utilizar en software de copia de seguridad o de copia de archivos , a menudo para ahorrar ancho de banda al copiar entre ordenadores a través de una red privada o de 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 ofrecer a sus usuarios versiones anteriores del mismo archivo de copias de seguridad anteriores. Esto reduce los costos asociados, no solo en la cantidad de datos que deben almacenarse como versiones diferentes (ya que se debe ofrecer a los usuarios la totalidad de cada versión modificada de un archivo para que puedan acceder a ella), sino también los costos de carga (y, a veces, de descarga) de cada archivo que se ha actualizado (ya que solo se debe utilizar el delta más pequeño, en lugar del archivo completo).

En el caso de paquetes de software de gran tamaño, normalmente se modifican pocos datos 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 , context y unified , proporcionan líneas de contexto adicionales que permiten tolerar cambios en el número de línea.

El sistema de control de código fuente de Git emplea la compresión delta en una operación auxiliar de "git repack". Los objetos del repositorio que aún no han sido comprimidos con 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 empaquetado" que luego se comprime utilizando métodos convencionales. En casos de uso comunes, donde los archivos de origen o de datos se modifican de forma incremental entre confirmaciones, esto puede resultar en un ahorro de espacio significativo. La operación de repack se realiza normalmente como parte del proceso "git gc", que se activa automáticamente cuando la cantidad de objetos sueltos o archivos de empaquetado supera los umbrales configurados.

El formato está documentado en la página pack-format 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 diferenciación genérica (GDIFF) es otro formato de codificación delta dirigida. Fue presentado al W3C en 1997. ^[6] En muchos casos, VCDIFF tiene una mejor tasa de compresión que GDIFF.

Bsdiff es un programa de comparación binaria que utiliza la clasificación por sufijos . Para los ejecutables que contienen muchos cambios en las direcciones de los punteros, funciona mejor que las codificaciones de "copia y literal" de tipo VCDIFF. La intención es encontrar una forma de generar una pequeña comparación sin necesidad de analizar el código ensamblador (como en Courgette de Google). Bsdiff logra esto al permitir coincidencias de "copia" con errores, que luego se corrigen utilizando una matriz "add" adicional de diferencias byte a byte. Dado que esta matriz es principalmente cero o valores repetidos para los cambios de desplazamiento, ocupa poco espacio después de la compresión. ^[7]

Bsdiff es útil para actualizaciones delta. Google utiliza bsdiff en Chromium y Android. La función deltarpm del gestor de paquetes RPM se basa en un bsdiff muy modificado que puede utilizar una tabla hash para la comparación. ^[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 para el programa. Google mantiene varias versiones del código para cada uno de sus productos. ^[10] FreeBSD incorpora muchos de los cambios compatibles de Google, principalmente una corrección de vulnerabilidad y un cambio a la divsufsortrutina de ordenación de sufijos más rápida. ^[11] Debian ha realizado una serie de ajustes de rendimiento para 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 consumo de memoria y CPU. ^[13]

• Diferenciación de datos  : método para comprimir los cambios a lo largo del tiempo
• Deltas intercalados  : método utilizado por SCCS para almacenar todas las revisiones de un archivoPáginas que muestran descripciones de wikidata como alternativa
• Sistema de control de código fuente  : sistema de control de versiones diseñado para rastrear cambios en el código fuentePáginas que muestran descripciones de wikidata como alternativa
• Problema de corrección de cadena a cadena
• Xdelta : codificador delta de código abierto

• RFC 3229 – Codificación delta en HTTP