Codificación delta

La diferencia de valores numéricos se define directamente mediante la resta, como se muestra en el ejemplo anterior. Debido a la propiedad de las operaciones aritméticas, la diferencia numérica es simétrica : si el último valor es igual a cero, entonces es igual a cero.${\displaystyle b}$Se sabe que es posible aplicar el delta.${\displaystyle ba}$en sentido inverso para obtener el valor anterior${\displaystyle a}$.

También es posible producir un "delta de deltas" numérico. Esto puede ser útil si los datos subyacentes se generan mediante un proceso similar a${\displaystyle f(x)=ax+b}$, ya que el delta de segundo orden aplanaría los datos a una cadena de ceros. Las marcas de tiempo a menudo se comportan de esta manera. ^{[ 1 ]} Incluso los deltas de orden superior pueden ser útiles para datos de la vida real: por ejemplo, la distancia medida ( pseudorango ) a un satélite de navegación a lo largo del tiempo se comprime mejor utilizando un delta de tercer orden, un "delta de deltas de deltas". ^{[ 2 ]}

Además de la resta, la operación XOR (o exclusiva ) a nivel de bits también produce una diferencia simétrica. Las bases de datos de series temporales suelen utilizar la operación XOR como diferencia entre números de coma flotante, ya que produce diferencias fácilmente compresibles que consisten principalmente en bits cero. ^{[ 1 ]}

Otra variación consiste en cambiar la distancia entre los elementos utilizados para la operación delta: en lugar de calcular${\displaystyle ba}$en la secuencia${\displaystyle (a,b,c,d)}$, un delta de "distancia-2" calcularía${\displaystyle ca}$Esto se observa en el filtro "delta" de xz . ^{[ 3 ]}

void encode ( uint8_t buffer [], size_t length ) { uint8_t last = 0 ; for ( size_t i = 0 ; i < length ; ++ i ) { uint8_t current = buffer [ i ]; buffer [ i ] = current - last ; last = current ; } }void decode ( uint8_t buffer [], size_t length ) { uint8_t last = 0 ; for ( size_t i = 0 ; i < length ; ++ i ) { uint8_t delta = buffer [ i ]; buffer [ i ] = delta + last ; last = buffer [ i ]; } }

Para la diferencia entre secuencias o conjuntos de valores (por ejemplo, cadenas de caracteres e imágenes), se puede definir un delta de dos maneras: delta simétrico y delta dirigido . Un delta simétrico entre dos conjuntos incluye suficiente información para que sea reversible:

${\displaystyle \Delta ({\mathit {versión}}_{1},{\mathit {versión}}_{2})=({\mathit {versión}}_{1}\setminus {\mathit {versión}}_{2})\cup ({\mathit {versión}}_{2}\setminus {\mathit {versión}}_{1}).}$

La diferencia entre dos secuencias se define de forma análoga, excepto que se añade información para localizar las adiciones y eliminaciones. En las implementaciones informáticas, se ejemplifica con la salida de diff (en los modos predeterminado, unificado y de contexto): instrucciones en forma de "en la posición${\displaystyle x}$, reemplazar (contenido antiguo) con (contenido nuevo)".

Un delta dirigido , también llamado cambio, es una secuencia de operaciones de cambio (elementales) que, cuando se aplican a${\displaystyle {\mathit {version}}_{1}}$, produce otro,${\displaystyle {\mathit {version}}_{2}}$(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${\displaystyle {\mathit {version}}_{1}}$y escribir datos literales . Un ejemplo es la salida de diff en el modo de edición de script .

Otro ejemplo del 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, 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 Transferencia 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 modificatorias son frecuentes y que las modificaciones suelen ser mucho menores que la entidad original. 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 admitir rsync utilizando el marco de "manipulación de instancias" que se describe más adelante en este documento, pero esto no se ha desarrollado en detalle.

El marco sugerido basado en rsync se implementó en el sistema rproxy como un par de proxies HTTP. ^{[ 5 ]} Al igual que la implementación básica basada en vcdiff, ambos sistemas se utilizan con poca frecuencia.

La copia delta es una forma rápida de copiar un archivo parcialmente modificado, cuando existe una versión anterior en la ubicación de destino. Con la copia delta, solo se copia la parte modificada del 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 internet. Un ejemplo notable de código abierto es rsync . ^{[ 6 ] [ 7 ] [ 8 ]}

Diff es un programa de comparación de archivos, utilizado principalmente para archivos de texto. Por defecto, genera diferencias simétricas 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 Git emplea compresión delta en una operación auxiliar llamada " git repack ". Los objetos del repositorio que aún no se han comprimido delta ("objetos sueltos") se comparan con un subconjunto heurísticamente seleccionado de todos los demás objetos, y los datos comunes y las diferencias se concatenan en un "archivo pack", que luego se comprime mediante métodos convencionales. En casos de uso comunes, donde los archivos fuente o de datos se modifican incrementalmente entre confirmaciones, esto puede generar un ahorro de espacio significativo. La operación repack se realiza normalmente como parte del proceso "git gc" ^{[ 9 ]} , que se activa automáticamente cuando la cantidad de objetos sueltos o archivos pack supera los umbrales configurados.

El formato está documentado en la página pack-format de la documentación de Git. Implementa un delta dirigido. ^{[ 10 ]}

Un formato general para la codificación delta dirigida es VCDIFF, descrito en el RFC 3284. Entre las implementaciones de software libre se incluyen Xdelta y open-vcdiff.

El formato de diferencia genérica (GDIFF) es otro formato de codificación delta dirigida. Fue presentado al W3C en 1997. ^{[ 11 ]} En muchos casos, VCDIFF tiene una mejor tasa de compresión que GDIFF.

Bsdiff es un programa de comparación binaria que utiliza ordenación por sufijo . Para ejecutables que contienen muchos cambios en las direcciones de puntero, ofrece un mejor rendimiento que las codificaciones de tipo VCDIFF de "copia y literal". El objetivo es generar una pequeña comparación sin necesidad de analizar el código ensamblador (como en Courgette de Google). Bsdiff lo consigue permitiendo coincidencias de "copia" con errores, que luego se corrigen mediante una matriz adicional de "adición" de diferencias byte a byte. Dado que esta matriz contiene principalmente valores cero o repetidos para los cambios de desplazamiento, ocupa poco espacio después de la compresión. ^{[ 12 ]}

Bsdiff es útil para actualizaciones delta. Google usa bsdiff en Chromium y Android. La función deltarpm del gestor de paquetes RPM se basa en una versión muy modificada de bsdiff que puede usar una tabla hash para la coincidencia. ^{[ 13 ]} FreeBSD también usa bsdiff para actualizaciones. ^{[ 14 ]}

Desde el lanzamiento de bsdiff 4.3 en 2005, se han producido varias mejoras o correcciones para él. Google mantiene múltiples versiones del código para cada uno de sus productos. ^{[ 15 ]} FreeBSD toma 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. ^{[ 16 ]} Debian tiene una serie de ajustes de rendimiento para el programa. ^{[ 17 ]}

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. ^{[ 18 ]}