comparer avec diff deux gros fichiers compresses

Le
Vincent Lefevre
Bonjour,

Je voudrais savoir s'il y a un moyen de comparer efficacement deux
très gros fichiers compressés, sans utiliser beaucoup de mémoire
(que ce soit en RAM, en swap ou sur disque). Je précise qu'on peut
considérer les deux fichiers en question (enfin, leur contenu avant
compression) comme étant identiques sauf sur de petites parties.

Cela élimine déjà l'utilitaire bzdiff fourni avec bzip2 (au moins
sur Debian), car il commence par décompresser un des deux fichiers
dans un fichier temporaire.

La solution

diff <(bunzip2 -c file1.bz2) <(bunzip2 -c file2.bz2)

ou

diff --speed-large-files <(bunzip2 -c file1.bz2) <(bunzip2 -c file2.bz2)

(sous zsh), où les deux décompressions se font de manière asynchrone,
prend malheureusement beaucoup de place en mémoire (RAM / swap). Mais
je ne sais pas si c'est l'algo de diff qui prend beaucoup de mémoire
ou si ce sont des buffers attribués par le système (ou bibliothèque)
pour stocker les données de sortie temporaires des bunzip2. Dans le
cas de --speed-large-files, je pencherais pour la seconde raison, et
il faudrait un système avec des buffers limités.

--
Vincent Lefèvre <vincent@vinc17.org> - Web: <http://www.vinc17.org/>
100% accessible validated (X)HTML - Blog: <http://www.vinc17.org/blog/>
Work: CR INRIA - computer arithmetic / Arenaire project (LIP, ENS-Lyon)
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
Nicolas George
Le #16530551
Vincent Lefevre wrote in message
(sous zsh), où les deux décompressions se font de manière asynchrone,
prend malheureusement beaucoup de place en mémoire (RAM / swap). Mais
je ne sais pas si c'est l'algo de diff qui prend beaucoup de mémoire



Regarde avec ps quel processus occupe le plus de mémoire.
Stephane CHAZELAS
Le #16531701
2008-08-12, 11:35(+00), Vincent Lefevre:
[...]
diff <(bunzip2 -c file1.bz2) <(bunzip2 -c file2.bz2)

ou

diff --speed-large-files <(bunzip2 -c file1.bz2) <(bunzip2 -c file2.bz2)

(sous zsh), où les deux décompressions se font de manière asynchrone,
prend malheureusement beaucoup de place en mémoire (RAM / swap). Mais
je ne sais pas si c'est l'algo de diff qui prend beaucoup de mémoire
ou si ce sont des buffers attribués par le système (ou bibliothèque)
pour stocker les données de sortie temporaires des bunzip2. Dans le
cas de --speed-large-files, je pencherais pour la seconde raison, et
il faudrait un système avec des buffers limités.



Non, <(...) marche avec des pipes (au max PIPE_BUF dedans, 64kB
chez les Linux recents IIRC), il y a des chances que bunzip2
ecrive moins vite que diff ne lise, donc ca doit pas souvent
remplir le pipe souvent.

Et c'est synchrone, tous les processus (diff et les deux bzip2)
tournent en meme temps.

Donc, si quelquechose stocke, c'est diff.

Si tu veux stocker dans des fichiers temporaires, c'est

diff =(...) =(...)

auquel cas, le bunzip2 seront executés d'abord (l'un apres
l'autre) et diff ensuite.


--
Stéphane
Vincent Lefevre
Le #16542861
Dans l'article Nicolas George
Regarde avec ps quel processus occupe le plus de mémoire.



C'est diff.

--
Vincent Lefèvre 100% accessible validated (X)HTML - Blog: Work: CR INRIA - computer arithmetic / Arenaire project (LIP, ENS-Lyon)
Vincent Lefevre
Le #16542851
Dans l'article Stephane CHAZELAS
Non, <(...) marche avec des pipes (au max PIPE_BUF dedans, 64kB
chez les Linux recents IIRC), il y a des chances que bunzip2
ecrive moins vite que diff ne lise, donc ca doit pas souvent
remplir le pipe souvent.



Enfin ça dépend de l'algo de diff.

Et c'est synchrone, tous les processus (diff et les deux bzip2)
tournent en meme temps.



Ils tournent en même temps, mais il n'y au aucune synchronisation
entre les deux (excepté celle par effet de bord due aux remplissage
des buffers).

Donc, si quelquechose stocke, c'est diff.



Effectivement. J'ai fait le test suivant:

$ perl -e 'for ($i = 1; $i <= 1000000000; $i++) { print "Line $in" }' > file1
$ perl -e 'for ($i = 1; $i
Puis "diff file1 file2" et "diff --speed-large-files file1 file2".
Dans les deux cas, diff prend plusieurs centaines de Mo de mémoire.

Apparemment je ne suis pas le seul à demander un diff pour gros fichiers:

http://groups.google.com/group/gnu.utils.bug/browse_thread/thread/9c155278967396da


Et c'est d'ailleurs dans le TODO de GNU diff:

17.1.5 Handling Files that Do Not Fit in Memory
-----------------------------------------------

`diff' operates by reading both files into memory. This method fails
if the files are too large, and `diff' should have a fallback.

One way to do this is to scan the files sequentially to compute hash
codes of the lines and put the lines in equivalence classes based only
on hash code. Then compare the files normally. This does produce some
false matches.

Then scan the two files sequentially again, checking each match to
see whether it is real. When a match is not real, mark both the
"matching" lines as changed. Then build an edit script as usual.

The output routines would have to be changed to scan the files
sequentially looking for the text to print.


Ceci dit, cela resterait inefficace pour des fichiers avec de
nombreuses lignes.

Mais une fonctionnalité qui m'irait serait de pouvoir fournir une
expression rationnelle indiquant que si deux lignes identiques (dans
chacun des deux fichiers) matchent cette expression (en pratique, de
telles lignes contiennent des MD5 ou autre type de hash), alors on
compare entre elles les deux parties qui précèdent ces lignes, ainsi
que les deux parties qui suivent ces lignes. En gros, cela permet de
découper les deux fichiers en petits blocs, et de comparer les blocs
entre eux.

Ou alors le même genre de chose en cherchant des séquences de n lignes
qui apparaissent de manière identique dans les deux fichiers.

Cela conviendrait très bien pour chercher les différences dans deux
dumps de Subversion censés être quasiment identiques (ce qui était
précisément mon cas).

--
Vincent Lefèvre 100% accessible validated (X)HTML - Blog: Work: CR INRIA - computer arithmetic / Arenaire project (LIP, ENS-Lyon)
Publicité
Poster une réponse
Anonyme