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 , particularmente cuando se requieren historiales de archivo de cambios (por ejemplo, en el software de control de revisiones ).
Las diferencias se registran en archivos discretos llamados "deltas" o "diffs". En situaciones donde las diferencias son pequeñas, por ejemplo, el cambio de algunas palabras en un documento grande o el cambio de algunos registros en una tabla grande, la codificación delta reduce en gran medida la redundancia de datos. Las colecciones de deltas únicas son sustancialmente más eficientes en el 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; consulte la entropía relativa . La diferencia entre valores idénticos (bajo alguna equivalencia ) a menudo se llama 0 o el elemento neutral .
Ejemplo simple
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í. 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 uso de bits más bajo 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. Desafortunadamente, ni siquiera todas las muestras de sonido de 8 bits se comprimen mejor cuando se codifican en 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 la codificación 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 utilizan en prácticamente todos los códec de compresión de video .
Definición
Un delta se puede definir de 2 formas, delta simétrico y delta dirigido . Un delta simétrico se puede expresar como
dónde y representan dos versiones.
Un delta dirigido , también llamado cambio, es una secuencia de operaciones de cambio (elementales) que, cuando se aplican a una versión, da otra versión (tenga en cuenta la correspondencia con los registros de transacciones en las bases de datos). En las implementaciones de computadora, generalmente toman la forma de un lenguaje con dos comandos: copiar datos de v1 y escribir datos literales .
Variantes
Una variación de la codificación delta que codifica las diferencias entre los prefijos o sufijos de cadenas se denomina codificación incremental . Es particularmente eficaz para listas ordenadas con pequeñas diferencias entre cadenas, como una lista de palabras de un diccionario .
Problemas de implementación
La naturaleza de los datos que se codificarán 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 está disponible una única copia del archivo 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 .
Ejemplo de código C
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 < longitud ; i ++ ) { unsigned char current = buffer [ i ]; búfer [ i ] = actual - último ; último = actual ; } }void delta_decode ( unsigned char * buffer , int length ) { unsigned char last = 0 ; for ( int i = 0 ; i < longitud ; i ++ ) { unsigned char delta = buffer [ i ]; búfer [ i ] = delta + último ; último = búfer [ i ]; } }
Ejemplos de
Codificación delta en HTTP
Otro ejemplo de uso de la codificación delta es 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 que el cliente ya tiene una entrada de caché. La investigación ha demostrado que tales 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 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 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.
Copia delta
La copia delta es una forma rápida de copiar un archivo que se ha modificado parcialmente, cuando hay una versión anterior en la ubicación de destino. Con la copia delta, solo se copia la parte modificada de un archivo. Por lo general, se utiliza en software de copia de seguridad o copia 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]
Copia de seguridad en línea
Muchos de los servicios de respaldo en línea adoptan esta metodología, a menudo conocida simplemente como deltas , para brindar a sus usuarios versiones anteriores del mismo archivo de respaldos anteriores. Esto reduce los costos asociados, no solo en la cantidad de datos que deben almacenarse como versiones diferentes (ya que la totalidad de cada versión modificada de un archivo debe ofrecerse para que los usuarios accedan), sino también los costos de carga (y a veces, la descarga) de cada archivo que se ha actualizado (simplemente teniendo que usar el delta más pequeño, en lugar de todo el archivo).
Actualizaciones de Delta
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.
Diferencia
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ínea.
Git
El sistema de control de código fuente de Git emplea compresión delta en una operación auxiliar " git repack ". Los objetos del repositorio que aún no se han comprimido en 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 utilizando métodos. En casos de uso común, donde los archivos de origen o de datos se cambian gradualmente entre confirmaciones, esto puede resultar en ahorros de espacio significativos. La operación de reempaquetado se realiza normalmente como parte del proceso " git gc ", que se activa automáticamente cuando la cantidad de objetos sueltos o archivos de paquete exceden 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]
VCDIFF
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.
GDIFF
El formato de diferencia genérico (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
Bsdiff es un programa de diferencias binarias que utiliza la clasificación de sufijos . Para los ejecutables que contienen muchos cambios en las direcciones de puntero, funciona mejor que las codificaciones de "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 al permitir coincidencias de "copia" con errores, que luego se corrigen utilizando una matriz adicional de "agregar" de diferencias de bytes. Dado que esta matriz es en su mayoría valores cero o repetidos para los 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 función deltarpm del Administrador de paquetes RPM se basa en un bsdiff muy modificado que puede usar una tabla hash para hacer coincidir. [8] FreeBSD también usa bsdiff para actualizaciones. [9]
Desde el lanzamiento 4.3 de bsdiff en 2005, se han producido varias mejoras o correcciones para él. Google mantiene varias versiones del código para cada uno de sus productos. [10] FreeBSD acepta muchos de los cambios compatibles de Google, principalmente una corrección de vulnerabilidades y un cambio a la divsufsort
rutina 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]
Ver también
- Diferenciación de datos
- Delta intercalado
- Sistema de control de código fuente
- Problema de corrección de cuerda a cuerda
- Xdelta : codificador delta de código abierto
Referencias
- ^ "rproxy: introducción" . rproxy.samba.org .
- ^ http://www.2brightsparks.com/bb/viewtopic.php?t=4473
- ^ https://www.bvckup2.com/support/forum/topic/739
- ^ http://www.eggheadcafe.com/software/aspnet/33678264/delta-copying.aspx [ enlace muerto permanente ]
- ^ "Git - Documentación en formato pack" . Documentación de Git . Consultado el 13 de enero de 2020 .
- ^ Especificación de formato de diferencia genérica
- ^ Colin Percival, diferencias ingenuas de código ejecutable, http://www.daemonology.net/bsdiff/ , 2003.
- ^ "rpmdelta / delta.c" . gestión-de-software-rpm. 3 de julio de 2019 . Consultado el 13 de enero de 2020 .
- ^ Anónimo (mayo de 2016). "ATAQUES NO CRIPTANALÍTICOS CONTRA LOS COMPONENTES DE ACTUALIZACIÓN DE FREEBSD" . GitHub Gist .
- ^ "xtraeme / bsdiff-chromium: README.chromium" . GitHub . 2012.; "calabacín / tercera_parte / bsdiff / README.chromium - cromo / src" . Git en Google .; "android / plataforma / externo / bsdiff /" . Git en Google .
- ^ "Historial de freebsd / usr.bin / bsdiff" . GitHub .
- ^ "Paquete: bsdiff" . Rastreador de parches de Debian .
- ^ Klode, Julian. "julian-klode / ddelta" . GitHub . Consultado el 13 de enero de 2020 .
enlaces externos
- RFC 3229 - Codificación delta en HTTP