Diferenciación de datos

En informática y teoría de la información , la diferenciación de datos o compresión diferencial consiste en producir una descripción técnica de la diferencia entre dos conjuntos de datos: un origen 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).

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 , siendo así una herramienta de diferenciación de propósito general). La diferenciación de archivos binarios generales se incluye en la rúbrica de 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 parches pequeños) es bsdiff, que utiliza bzip2 como un paso de compresión final en el delta generado. ^[1]

Las principales preocupaciones sobre 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 generando el objetivo que se ha incluido en el parche; de ​​manera similar, si el origen y el objetivo tienen el mismo tamaño, se puede crear un parche simple mediante la operación XOR entre el origen y el objetivo. 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.

En el caso de los datos estructurados, en particular, existen otras preocupaciones que se enmarcan en gran medida en la "usabilidad": por ejemplo, si se comparan dos documentos, generalmente se desea saber qué secciones han cambiado o si se han movido algunas secciones; se desea comprender en qué se diferencian los documentos. Por ejemplo, "aquí se cambió 'gato' por 'perro' y el párrafo 13 se movió al párrafo 14". También se puede desear que haya diferencias sólidas ; por ejemplo, si dos documentos A y B difieren en el párrafo 13, se puede desear poder aplicar este parche incluso si se ha cambiado el párrafo 7 de A. Un ejemplo de esto se encuentra en diff, que muestra qué líneas cambiaron y dónde el formato de contexto permite la solidez y mejora la legibilidad humana.

Otras preocupaciones incluyen la eficiencia computacional, ya que en el caso de la compresión de datos, encontrar un parche pequeño puede consumir mucho tiempo y memoria.

Los mejores resultados se obtienen 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 el origen y el destino estén a través de una red uno del otro y la comunicación sea lenta, por lo que minimiza los datos que se deben transmitir; y las actualizaciones para Google Chrome utilizan un algoritmo personalizado para el archivo y el formato ejecutable de los datos del programa. ^{[2] [3]}

La compresión de datos puede considerarse 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 , mientras que la aplicación de parches produce un destino dada una fuente y una diferencia, mientras que la compresión de datos consiste en producir un archivo comprimido dado un destino, y la descompresión consiste en producir un destino 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 (que corresponde a la compresión de datos) como un caso especial de entropía relativa (que corresponde a la diferenciación de datos) sin datos iniciales.

Cuando se desea enfatizar la conexión, se puede utilizar 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 es el siguiente: