Algorithme pour diffing efficace des fichiers énormes

Question

Je dois stocker deux fichiers A et B qui sont tous deux très grandes (comme 100Go). Cependant B est susceptible d'être similaire dans les grandes pièces à A si je pouvais stocker A et diff (A, B). Il y a deux aspects intéressants à ce problème:

1. Les fichiers sont trop volumineux pour être analysés par une bibliothèque diff je connais parce qu'ils sont en mémoire
2. Je ne fait pas besoin d'un diff - un diff a généralement des insertions, modifications et suppressions, car il est destiné à être lu par les humains. Je peux sortir avec moins d'informations. Je ne ai besoin « nouvelle gamme d'octets » et « octets de copie de fichier ancien de décalage arbitraire »

Je suis actuellement à une perte sur la façon de calculer le delta de A à B dans ces conditions. Quelqu'un sait-il d'un algorithme pour cela?

Encore une fois, le problème est simple:. Écrivez un algorithme qui permet de stocker les fichiers A et B avec aussi quelques octets que possible compte tenu du fait que les deux sont tout à fait similaires

Informations complémentaires: Bien que de grandes parties pourraient être identiques, ils sont susceptibles d'avoir des compensations et être hors d'usage. Le dernier fait est la raison pour laquelle une diff classique pourrait ne pas économiser beaucoup.

Answer 1

Jetez un oeil à l'algorithme de RSYNCs, comme il a été conçu à peu près à faire exactement cela pour qu'il puisse efficacement copier deltas. Et l'algorithme est assez bien documenté, je me souviens bien.

Answer 2

Vous pouvez utiliser rdiff, qui fonctionne très bien avec des fichiers volumineux. Ici, je crée un diff de deux gros fichiers A et B:

1. Créer une signature d'un fichier, avec par exemple.

   rdiff signature A sig.txt
   

2. en utilisant le fichier de signature généré sig.txt et l'autre grand dossier, créez le delta:

   rdiff delta sig.txt B delta
   

3. delta contient toutes les informations dont vous avez besoin pour recréer le fichier B lorsque vous avez à la fois A et delta. Pour recréer B, exécutez

   rdiff patch A delta B
   

Dans Ubuntu, lancez simplement sudo apt-get install rdiff pour l'installer. Il est assez rapide, je reçois environ 40 Mo par seconde sur mon PC. Je viens d'essayer sur un fichier de 8 Go et la mémoire utilisée par rsync était d'environ 1Mo.

Answer 3

C'est exactement le problème connu sous le nom « la déduplication des données » . L'approche la plus couramment utilisée est:

• Relisez les fichiers en blocs:
  • Split les données des soi-disant « morceaux ». L'approche la plus souvent utilisée est appelée « Content définie en utilisant la méthode Chunking Rabins Fingerprinting » ( code ). En utilisant cette approche Chunking conduit à une meilleure déduplication des données sur la plupart ensemble puis en utilisant des morceaux de taille statiques (par exemple montré ).
  • empreintes digitales Les morceaux en utilisant un procédé de prise d'empreinte cryptographique, par exemple SHA-256.
  • Conserver les empreintes digitales dans un index et recherche pour chaque morceau si l'empreinte est déjà connue. Si l'empreinte est connue, il n'y a pas besoin de stocker le morceau une deuxième fois. Seulement lorsque l'empreinte est pas connue, les données doivent être stockées.

Un tel algorithme de déduplication de données ne sont pas aussi exacte que par exemple xdelta , mais il est plus rapide et plus évolutive pour les grands ensembles de données. Le chunking et les empreintes digitales est réalisée avec environ 50 Mo / s par noyau (Java). La taille de l'index dépend des licenciements, la taille du morceau et la taille des données. Pour 200 Go, il devrait tenir dans la mémoire pour les tailles de morceau de par exemple 16KB.

Bentleys et l'approche de compression de Mciloys est très similaire (utilisé par exemple par googles BigTable), mais je ne suis pas au courant des outils hors la ligne de commande de la boîte en utilisant la technique de compression.

Le "fs-c" projet open source contient la plupart du code est nécessaire. Cependant, fs-c s'essaie seulement de mesurer les redondances et les fichiers analzye en mémoire ou en utilisant un cluster de Hadoop .

Answer 4

une question est quelle est la taille de l'enregistrement dans vos fichiers, à savoir les décalages peuvent changer octet par octet ou faire les fichiers se composent de, disons, blocs 1024B. En supposant que les données octet par octet, vous pouvez effectuer les opérations suivantes:

1. Créer un tableau de suffixe du fichier A. Ce tableau est une permutation de toutes les valeurs d'index dans le fichier A. Si A a 2 ^ 37 octets, alors le tableau d'index est plus facile représenté par des entiers 64 bits, donc chaque octet (décalage dans le fichier) correspond à 8 octets dans le réseau d'indice, de sorte que le réseau d'indice est de 2 ^ 40 octets de long alors. Par exemple. 800 Go, par exemple. Vous pouvez indexer également que chaque emplacement 1024ème, par exemple, de réduire la taille du tableau d'index. Ce detoriates alors la qualité de l'emballage en fonction de la durée des tirages moyens de fragments sont copiables.

2. Maintenant pour emballer avidement le fichier B vous commencez à partir de son début à l'offset o = 0 puis utilisez le tableau d'index pour trouver le plus long match A qui correspond aux données à partir de « o ». Vous sortie la paire dans le fichier compressé. Cela prend dans votre cas sans codage 16 octets, donc si la course est <16 octets vous perdez en fait l'espace. Ceci peut être facilement résolu en utilisant ensuite un codage de niveau bit et en utilisant un marqueur de bits pour marquer si vous encoder un octet isolé (marqueur + 8 bits = 9 bits) ou une paire de décalage / longueur (marqueur + 40 bits + 40 bits = 81 bits), dit. Après l'emballage le plus long fragment à o, o augmenter à l'octet suivant après le fragment et répétez jusqu'à à la fin du fichier.

La construction et l'utilisation d'un tableau de suffixe est facile et vous devriez trouver des références facilement. Dans les applications à grande vitesse les gens utilisent les arbres suffixe ou suffixe tente plutôt, qui sont plus complexes à manipuler, mais de fournir plus rapidement recherche. Dans votre cas, vous allez avoir le tableau sur le stockage secondaire et si la vitesse de défilement de la phase d'emballage n'est pas un problème un tableau de suffixe devrait être suffisant.

Answer 5

En fonction de vos exigences de performance, vous pouvez vous en sortir avec l'échantillonnage des morceaux que vous empreintes digitales et leur culture quand ils correspondent. De cette façon, vous n'avez pas d'exécuter une somme de contrôle sur votre fichier entier grand.

Si vous avez besoin d'alignements d'octets arbitraires et vous vraiment à la performance, regardez la simhash < a href = "http://svcs.cs.pdx.edu/gitweb/simhash.git" rel = "nofollow noreferrer"> algorithme , et l'utiliser pour trouver des blocs semblables mais non alignés.