Génération de correctifs binaires en C#

Question

Quelqu'un a-t-il ou connaît-il une implémentation d'algorithme de génération de correctifs binaires en C# ?

En gros, comparez deux fichiers (désignés vieux et nouveau), et produisez un fichier de correctif qui peut être utilisé pour mettre à niveau le vieux fichier pour avoir le même contenu que le nouveau déposer.

La mise en œuvre devrait être relativement rapide et fonctionner avec des fichiers volumineux.Il doit présenter des environnements d'exécution O(n) ou O(logn).

Mes propres algorithmes ont tendance à être soit mauvais (rapides mais produisent d'énormes correctifs), soit lents (produisent de petits correctifs mais ont un temps d'exécution O(n^2)).

Tout conseil ou indication de mise en œuvre serait le bienvenu.

Plus précisément, l'implémentation sera utilisée pour maintenir les serveurs synchronisés pour divers fichiers de données volumineux pour lesquels nous disposons d'un serveur maître.Lorsque les fichiers de données du serveur maître changent, nous devons également mettre à jour plusieurs serveurs hors site.

L'algorithme le plus naïf que j'ai réalisé, qui ne fonctionne que pour les fichiers pouvant être conservés en mémoire, est le suivant :

1. Récupérez les quatre premiers octets du vieux fichier, appelez-le le clé
2. Ajoutez ces octets à un dictionnaire, où clé -> position, où position est la position où j'ai récupéré ces 4 octets, 0 pour commencer
3. Sautez le premier de ces quatre octets, récupérez-en 4 autres (3 chevauchements, 1 un) et ajoutez-les au dictionnaire de la même manière
4. Répétez les étapes 1 à 3 pour tous les blocs de 4 octets du vieux déposer
5. Dès le début du nouveau fichier, récupérez 4 octets et essayez de le rechercher dans le dictionnaire
6. S'il est trouvé, trouvez la correspondance la plus longue s'il y en a plusieurs, en comparant les octets des deux fichiers
7. Encodez une référence à cet emplacement dans le vieux fichier et ignorez le bloc correspondant dans le nouveau déposer
8. S'il n'est pas trouvé, encodez 1 octet du nouveau fichier et ignorez-le
9. Répétez les étapes 5 à 8 pour le reste du nouveau déposer

C'est un peu comme la compression, sans fenêtrage, donc cela utilisera beaucoup de mémoire.Il est cependant assez rapide et produit des correctifs assez petits, à condition que j'essaie de minimiser la sortie des codes.

Un algorithme plus économe en mémoire utilise le fenêtrage, mais produit des fichiers de correctifs beaucoup plus volumineux.

Il y a plus de nuances dans l'algorithme ci-dessus que j'ai ignorées dans cet article, mais je peux publier plus de détails si nécessaire.Cependant, je pense que j'ai besoin d'un algorithme complètement différent, donc améliorer l'algorithme ci-dessus ne me mènera probablement pas assez loin.

---

Modifier #1:Voici une description plus détaillée de l'algorithme ci-dessus.

Tout d’abord, combinez les deux fichiers pour obtenir un seul gros fichier.N'oubliez pas le point de coupure entre les deux fichiers.

Deuxièmement, fais ça récupérez 4 octets et ajoutez leur position au dictionnaire étape pour tout dans l'ensemble du fichier.

Troisièmement, d'où le nouveau Le fichier démarre, effectuez la boucle en essayant de localiser une combinaison existante de 4 octets et de trouver la correspondance la plus longue.Assurez-vous que nous considérons uniquement les postes de l'ancien fichier ou de plus tôt dans le nouveau fichier que nous en sommes actuellement.Cela garantit que nous pouvons réutiliser le matériel de l'ancien et du nouveau fichier lors de l'application du correctif.

---

Modifier #2: Code source de l'algorithme ci-dessus

Vous pourriez recevoir un avertissement indiquant que le certificat rencontre des problèmes.Je ne sais pas comment résoudre ce problème, alors pour le moment, acceptez simplement le certificat.

La source utilise de nombreux autres types du reste de ma bibliothèque, donc ce fichier ne suffit pas, mais c'est l'implémentation de l'algorithme.

---

@lomaxx, j'ai essayé de trouver une bonne documentation sur l'algorithme utilisé dans Subversion, appelé xdelta, mais à moins que vous ne sachiez déjà comment fonctionne l'algorithme, les documents que j'ai trouvés ne me disent pas ce que j'ai besoin de savoir.

Ou peut-être que je suis juste stupide...:)

J'ai jeté un rapide coup d'œil à l'algorithme de ce site que vous avez donné, et il n'est malheureusement pas utilisable.Un commentaire du fichier de comparaison binaire dit :

Trouver un ensemble optimal de différences nécessite un temps quadratique par rapport à la taille d'entrée, il devient donc très rapidement inutilisable.

Mes besoins ne sont cependant pas optimaux, je recherche donc une solution plus pratique.

Merci pour la réponse, j'ai ajouté un signet à ses utilitaires si jamais j'en ai besoin.

Modifier #1:Notez que je vais regarder son code pour voir si je peux trouver des idées, et je lui enverrai également un e-mail plus tard avec des questions, mais j'ai lu ce livre auquel il fait référence et bien que la solution soit bonne pour trouver des solutions optimales, son utilisation n'est pas pratique en raison des exigences de temps.

Modifier #2:Je vais certainement rechercher l'implémentation de python xdelta.

Answer 1

Désolé, je ne pourrais pas être plus utile.Je continuerais certainement à regarder xdelta car je l'ai utilisé à plusieurs reprises pour produire des différences de qualité sur plus de 600 Mo de fichiers ISO que nous avons générés pour la distribution de nos produits et il fonctionne très bien.

Answer 2

bsdiff a été conçu pour créer de très petits correctifs pour les fichiers binaires.Comme indiqué sur sa page, cela nécessite max(17*n,9*n+m)+O(1) octets de mémoire et s'exécute dans O((n+m) log n) temps (où n est la taille de l'ancien fichier et m est la taille du nouveau fichier).

L'implémentation originale est en C, mais un portage C# est décrit ici et disponible ici.

Answer 3

Avez-vous vu VCDiff?Il fait partie d'une bibliothèque Divers qui semble assez active (dernière version r259, 23 avril 2008).Je ne l'ai pas utilisé, mais j'ai pensé que cela valait la peine d'être mentionné.

Answer 4

Cela vaut peut-être la peine de vérifier ce que font certains des autres gars dans cet espace et pas nécessairement dans l'arène C# non plus.

Ceci est une bibliothèque écrite en c#

SVN a également un algorithme de différence binaire et je sais qu'il existe une implémentation en python même si je n'ai pas pu la trouver avec une recherche rapide.Ils pourraient vous donner quelques idées sur les moyens d'améliorer votre propre algorithme.

Answer 5

S'il s'agit d'une installation ou d'une distribution, avez-vous envisagé d'utiliser le SDK Windows Installer ?Il a la capacité de patcher les fichiers binaires.

http://msdn.microsoft.com/en-us/library/aa370578(VS.85).aspx

Answer 6

Il s'agit d'une ligne directrice approximative, mais ce qui suit concerne l'algorithme rsync qui peut être utilisé pour créer vos correctifs binaires.

http://rsync.samba.org/tech_report/tech_report.html