En informática y teoría de la información , la diferenciación o compresión diferencial de datos produce una descripción técnica de la diferencia entre dos conjuntos de datos: una fuente y un destino. Formalmente, un algoritmo de diferenciación de datos toma como entrada datos de origen y datos de destino, y produce datos de diferencia de modo que, dados los datos de origen y los datos de diferencia, se pueden reconstruir los datos de destino (" parcheando " el origen con la diferencia para producir el destino) .
Ejemplos de
Uno de los ejemplos más conocidos de diferenciación de datos es la utilidad diff , que produce diferencias línea por línea de archivos de texto (y en algunas implementaciones, archivos binarios , por lo que es una herramienta de diferenciación de propósito general). La diferenciación de archivos binarios generales se incluye en la rúbrica de la codificación delta , siendo un ejemplo ampliamente utilizado el algoritmo utilizado en rsync . Un formato de diferenciación genérico estandarizado es VCDIFF , implementado en utilidades como Xdelta versión 3. Un programa de diferenciación de alta eficiencia (archivos de parche pequeños) es bsdiff, que usa bzip2 como paso de compresión final en el delta generado. [1]
Preocupaciones
Las principales preocupaciones para la diferenciación de datos son la usabilidad y la eficiencia del espacio (tamaño del parche).
Si uno simplemente desea reconstruir el objetivo dado el origen y el parche, puede simplemente incluir el objetivo completo en el parche y "aplicar" el parche descartando el origen y dando salida al objetivo que se ha incluido en el parche; De manera similar, si la fuente y el destino tienen el mismo tamaño, se puede crear un parche simple mediante XORing en la fuente y el destino. En ambos casos, el parche será tan grande como el objetivo. Como muestran estos ejemplos, si la única preocupación es la reconstrucción del objetivo, esto se hace fácilmente, a expensas de un parche grande, y la principal preocupación para la diferenciación binaria de propósito general es reducir el tamaño del parche.
Especialmente para los datos estructurados, uno tiene otras preocupaciones, que en gran medida caen bajo la "usabilidad"; por ejemplo, si uno está comparando dos documentos, generalmente desea saber qué secciones han cambiado, o si algunas secciones se han movido, uno desea comprender en qué se diferencian los documentos. Por ejemplo, "aquí 'gato' se cambió por 'perro', y el párrafo 13 se trasladó al párrafo 14". También es posible que desee tener diferencias sólidas ; por ejemplo, si dos documentos A y B difieren en el párrafo 13, es posible que desee poder aplicar este parche incluso si se ha cambiado el párrafo 7 de A. Un ejemplo de esto está en diff , que muestra qué líneas cambiaron y dónde el formato de contexto permite robustez y mejora la legibilidad humana.
Otras preocupaciones incluyen la eficiencia computacional, en cuanto a la compresión de datos: encontrar un parche pequeño puede consumir mucho tiempo y memoria.
Los mejores resultados ocurren cuando uno tiene conocimiento de los datos que se están comparando y otras restricciones: diff está diseñado para archivos de texto orientados a líneas, particularmente código fuente, y funciona mejor para estos; el algoritmo rsync se utiliza en función de que la fuente y el destino se encuentren a través de una red y la comunicación sea lenta, por lo que minimiza los datos que deben transmitirse; y las actualizaciones para Google Chrome utilizan un algoritmo personalizado para el archivo y formato ejecutable de los datos del programa. [2] [3]
Conexión con compresión de datos
La compresión de datos puede verse como un caso especial de diferenciación de datos [4] [5] : la diferenciación de datos consiste en producir una diferencia dada una fuente y un destino , con el parcheo produciendo un destino dado una fuente y una diferencia, mientras que la compresión de datos consiste en producir un archivo comprimido dado un objetivo, y la descompresión consiste en producir un objetivo dado solo un archivo comprimido. Por lo tanto, se puede considerar la compresión de datos como una diferenciación de datos con datos de origen vacíos, correspondiendo el archivo comprimido a una "diferencia de la nada". Esto es lo mismo que considerar la entropía absoluta (correspondiente a la compresión de datos) como un caso especial de entropía relativa (correspondiente a la diferenciación de datos) sin datos iniciales.
Cuando se desea enfatizar la conexión, se puede usar el término compresión diferencial para referirse a la diferenciación de datos.
Un diccionario que traduce la terminología de los dos campos se da como:
compresión | diferenciando |
---|---|
ninguno | fuente |
descomprimido | objetivo |
comprimido | diferencia, delta |
compresión | diferenciando |
descompresión | parcheando |
Referencias
- ^ Colin Percival , diferencias ingenuas de código ejecutable, http://www.daemonology.net/bsdiff/ , 2003.
- ^ Blog de Chromium: lo más pequeño es más rápido (y también más seguro)
- ^ Actualizaciones de software: Courgette (The Chromium Projects)
- ^ RFC 3284
- ^ Korn, DG; Vo, KP (1995), B. Krishnamurthy (ed.), Vdelta: Diferenciación y compresión , software práctico reutilizable Unix, John Wiley & Sons