Différenciation des données - Data differencing

En informatique et en théorie de l'information , la différenciation des données ou la compression différentielle produit une description technique de la différence entre deux ensembles de données – une source et une cible. Formellement, un algorithme de différenciation des données prend en entrée des données source et des données cibles, et produit des données de différence telles qu'étant donné les données source et les données de différence, on peut reconstruire les données cibles (" patcher " la source avec la différence pour produire la cible) .

Exemples

L'un des exemples les plus connus de différenciation des données est l' utilitaire diff , qui produit des différences ligne par ligne de fichiers texte (et dans certaines implémentations, des fichiers binaires , étant ainsi un outil de différenciation à usage général). La différenciation des fichiers binaires généraux passe sous la rubrique de l' encodage delta , avec un exemple largement utilisé étant l'algorithme utilisé dans rsync . Un format de différenciation générique standardisé est VCDIFF , implémenté dans des utilitaires tels que Xdelta version 3. Un programme de différenciation à haute efficacité (petits fichiers de correctifs) est bsdiff, qui utilise bzip2 comme étape de compression finale sur le delta généré.

Préoccupations

Les principales préoccupations pour la différenciation des données sont la convivialité et l'efficacité de l'espace (taille du patch).

Si l'on souhaite simplement reconstruire la cible à partir de la source et du patch, on peut simplement inclure la cible entière dans le patch et "appliquer" le patch en supprimant la source et en sortant la cible qui a été incluse dans le patch ; de même, si la source et la cible ont la même taille, on peut créer un simple patch par XORing source et cible. Dans ces deux cas, le patch sera aussi grand que la cible. Comme le montrent ces exemples, si la seule préoccupation est la reconstruction de la cible, cela se fait facilement, au détriment d'un grand patch, et la principale préoccupation de la différenciation binaire à usage général est de réduire la taille du patch.

Pour les données structurées en particulier, on a d'autres préoccupations, qui relèvent en grande partie de la « convivialité » – par exemple, si l'on compare deux documents, on souhaite généralement savoir quelles sections ont changé, ou si certaines sections ont été déplacées – on souhaite comprendre en quoi les documents diffèrent. Par exemple, "ici 'chat' a été remplacé par 'chien', et le paragraphe 13 a été déplacé vers le paragraphe 14". On peut également souhaiter avoir des différences solides - par exemple, si deux documents A et B diffèrent au paragraphe 13, on peut souhaiter pouvoir appliquer ce correctif même si l'on a modifié le paragraphe 7 de A. Un exemple de ceci est dans diff , qui montre quelles lignes ont changé et où le format de contexte permet la robustesse et améliore la lisibilité humaine.

D'autres préoccupations concernent l'efficacité des calculs, comme pour la compression des données – la recherche d'un petit correctif peut prendre beaucoup de temps et de mémoire.

Les meilleurs résultats sont obtenus lorsque l'on connaît les données comparées et d'autres contraintes : diff est conçu pour les fichiers texte orientés ligne, en particulier le code source, et fonctionne mieux pour ceux-ci ; l' algorithme rsync est utilisé sur la base du fait que la source et la cible se trouvent sur un réseau l'une de l'autre et que la communication est lente, il minimise donc les données qui doivent être transmises ; et les mises à jour pour Google Chrome utilisent un algorithme personnalisé pour l'archive et le format exécutable des données du programme.

Connexion avec compression de données

La compression de données peut être considérée comme un cas particulier de différenciation de données - la différenciation de données consiste à produire une différence en fonction d' une source et d'une cible , le patch produisant une cible en fonction d' une source et d'une différence, tandis que la compression de données consiste à produire un fichier compressé en fonction d'un cible, et la décompression consiste à produire une cible à partir d'un fichier compressé uniquement. Ainsi, on peut considérer la compression de données comme des données différenciant des données sources vides, le fichier compressé correspondant à une "différence par rapport à rien". Cela revient à considérer l' entropie absolue (correspondant à la compression des données) comme un cas particulier d' entropie relative (correspondant à la différenciation des données) sans données initiales.

Lorsque l'on souhaite mettre l'accent sur la connexion, on peut utiliser le terme compression différentielle pour désigner la différenciation des données.

Un dictionnaire traduisant entre la terminologie des deux domaines est donné comme :

Les références