Trouver les faux doublons

What ? Mais si c’est des faux doublons alors ce n’est pas des doublons !

On se calme ! Commençons par le commencement, ceci est le premier article étiqueter « Xubuntu mon amour » (je suis un romantique) et c’est un article technique (dont tous les exemples ci-dessous devraient fonctionner sur n’importe quelle distribution GNU/linux). Je sais ça vous avait manqué !

Déjà qu’est-ce qu’on appelle un doublon ? C’est un fichier rigoureusement identique à un autre fichier, en général le nom de fichier sera le même sur les deux fichiers (mais pas obligatoirement), le md5sum sera identique (c’est-à-dire que l’empreinte numérique des deux fichiers sera la même), la taille sera identique. Il est probable que vous n’ayez pas besoin de ce fichier en double et que vous souhaitiez le supprimer pour faire du ménage ou récupérer un peu d’espace disque.

Qu’est-ce que j’appelle un faux doublon ? A l’heure de l’explosion des données, on télécharge tout et dans tous les sens : vidéos, musique, images. On ne les range pas, on ne les trie pas, on les sauvegarde et on se retrouve à la fin incapable de savoir ce que l’on a et où ça se trouve. Quand vient l’heure de faire du tri et du ménage, on est assez ennuyé.

Le problème c’est que les formats (de compression, d’images, vidéos) se sont multipliés : .mp3, .wav, .mp4, .avi, .mkv, .jpg, etc. On peut se retrouver ainsi avec une même vidéo de différentes qualités, en .avi et .mkv avec un nom de fichier différent. C’est ça que j’appelle un faux doublon puisque ce n’est pas un doublon mais pourtant nous avons bien le même « contenu » et on serait ravi de pouvoir supprimer les « contenus » dupliqués. Un « faux » doublon peut donc avoir un nom de fichier différent, un md5sum différent, une taille différente mais un même « contenu ».

Je vais donc vous poser la question qui me taraude : Comment trouver les faux doublons ? Je vais vous présenter comment je fais à l’heure actuelle et vous remettre en mémoire les quelques utilitaires en CLI pour retrouver ces vils fichiers. En avant la musique !

FDUPES

fdupes est probablement l’utilitaire le plus à même de trouver des (« vrais ») doublons. C’est pourtant l’outil que j’utilise le moins pour la recherche de « faux » doublons. Une rapide présentation est disponible chez La vache libre.

apt-get install fdupes ou aptitude install fdupes # On installe fdupes
fdupes -r /home/babar/grosdossiertipiaksecret # On lance fdupes qui va parcourir de manière récursive notre répertoire
fdupes -r /home/babar/grosdossiertipiaksecret > ~/Bureau/Doublons.txt # On lance fdupes qui va parcourir de manière récursive notre répertoire et on envoie la sortie dans le fichier Doublons.txt sur notre bureau
fdupes -v # La version de fdupes
fdupes -h # Le help de fdupes

Le help de fdupes étant simple à comprendre (bien qu’en Anglais) je ne m’attarderai pas sur les options. Il est cependant utile de rappeler comment fonctionne exactement fdupes afin d’en voir ses limites. D’après Wikipédia, fdupes vérifie si la taille entre les fichiers est identique et si oui il continue, il vérifie partiellement si la signature MD5 est identique et si oui il continue, il vérifie si la signature MD5 complète est identique et si oui il continue, enfin il vérifie si les fichiers correspondent bit à bit et si oui, ces sont des doublons. On peut aisément comprendre que sur une grande quantité de fichiers (disons un disque de 1 To avec 1000 fichiers), ça puisse être relativement long et dans notre problématique de trouver des « faux » doublons, ce ne sera pas du tout productif.

Pour résumer : Lent mais on est sûr que le fichier est identique.

LS et FIND

ls et find sont bien connus de tous, nous allons juste rappeler comment lister les fichiers d’un dossier dans le but de trouver nos « faux » doublons.

ls -AR /home/babar/grosdossiertipiaksecret > ~/Bureau/Listing1.txt # Lister tous les fichiers du répertoire (récursivement, juste les noms des fichiers, tri par défaut donc par ordre alphabétique)
ls -ARsh /home/babar/grosdossiertipiaksecret > ~/Bureau/Listing2.txt # Lister tous les fichiers du répertoire (récursivement, affichage du nom des fichiers et taille en human readable, tri par défaut donc par ordre alphabétique)
ls -ARshS /home/babar/grosdossiertipiaksecret > ~/Bureau/Listing3.txt # Lister tous les fichiers du répertoire (récursivement, affichage du nom des fichiers et taille en human readable, tri par taille du fichier du plus grand au plus petit

Ce serait bien plus parlant avec des exemples malheureusement l’article serait bien trop long, je vous invite donc à tester pour voir les différences. Vous verrez alors que la sortie de ces commandes risquent de ne pas vous convenir. En effet ls affiche dossier par dossier les fichiers alors qu’il est probable que vous désirez une liste de tous les fichiers peu importe le sous-dossier où ils se trouvent afin de pouvoir comparer tous les noms et toutes les tailles des fichiers à l’intérieur d’un répertoire. Pour cela il faut se tourner vers find.

find /home/babar/grosdossiertipiaksecret -type f > ~/Bureau/Listing4.txt # Chercher tous les fichiers du répertoire (récursivement, juste les noms des fichiers, aucun tri)
find /home/babar/grosdossiertipiaksecret/sound -type f -name "*.mp3" > ~/Bureau/Listing5.txt # Chercher tous les fichiers terminant par ".mp3" dans le dossier sound (récursivement, juste les noms des fichiers, aucun tri)
find /home/babar/grosdossiertipiaksecret/sound -type f -iname "*metallica*" > ~/Bureau/Listing6.txt # Chercher tous les fichiers contenant le mot metallica dans le dossier sound (récursivement, insensible à la casse c'est-à-dire sans différencier les majuscules et les minuscules, juste les noms des fichiers, aucun tri)
find /home/babar/grosdossiertipiaksecret/sound -type f -iname "*metallica*" -printf '%h%d%pn' | sort -t '' -n | awk -F '' '{print $3}' > ~/Bureau/Listing7.txt # Chercher tous les fichiers contenant le mot metallica dans le dossier sound (récursivement, insensible à la casse, juste les noms des fichiers, tri par ordre alphabétique)
find /home/babar/grosdossiertipiaksecret/sound -type f -iname "*metallica*" | sort > ~/Bureau/Listing8.txt # Chercher tous les fichiers contenant le mot metallica dans le dossier sound (récursivement, insensible à la casse, juste les noms des fichiers, tri par ordre alphabétique). Dans beaucoup d'exemples vous verrez cette notation, elle fait le même travail que l'exemple précédent mais le tri alphabétique est légèrement différent, c'est tout de même celle que je recommande car beaucoup plus simple à retenir (mais je préfère tout de même la précédente personnellement hi, hi, hi)
find /home/babar/grosdossiertipiaksecret/ -type f -iname "*mkv" -print0 | xargs -0 du -b | sort -rn > ~/Bureau/Listing9.txt # Chercher tous les fichiers mkv (récursivement, insensible à la casse, affichage du nom des fichiers et taille en octets, tri par taille du fichier du plus grand au plus petit)

Étudions le dernier exemple dans le détail. La première complexité est -print0, je vous invite à faire man find et aller consulter les exemples. Vous y verrez une ligne avec printf et la suivante avec print0 avec cette explication : « en veillant à ce que les noms de fichiers ou de répertoires qui contiennent des retours à la ligne, des guillemets simples ou doubles ou des espaces soient correctement traités ». L’option -print0 sert donc surtout pour éviter les ennuis avec les espaces dans les noms de fichiers ou répertoires.

xargs (Construire et exécuter des lignes de commandes à partir de l’entrée standard) reçoit via un tube (pipe) le résultat du find. Nous utilisons l’option -0 (voir man xargs) : « Utile quand des arguments sont susceptibles de contenir des espaces blanches, des marques de protection ou des antislashs. L’option -print0 de GNU find produit une sortie convenant à ce mode ». Donc pour les fichiers trouvés par find nous lançons la commande du -b qui nous donne la taille en octets de chaque fichier. Enfin nous trions par ordre numérique inversé via sort -rn.

FIND, XARGS, SORT, UNIQ

Je vais en complexifiant comme vous pouvez le constater. On a vu dans l’exemple précédent comment avoir une liste par taille et par ordre numérique inversé des fichiers d’un dossier. Oui mais maintenant tant qu’à faire on voudrait seulement avoir les fichiers ayant la même taille ou la même signature MD5. On va jouer avec uniq.

find /home/babar/grosdossiertipiaksecret/ -type f -print0 | xargs -0 md5sum | sort | uniq -w32 -D > ~/Bureau/Doublons_md5sum.txt # Chercher tous les fichiers dont le md5sum est identique (récursivement, affichage du md5sum et du nom des fichiers, tri limité sur les 32 premiers caractères par ordre croissant)

Via la commande md5sum, je pense que tout le monde aura compris qu’on récupère le md5sum de chaque fichier. On trie ensuite les lignes avec sort. La complexité vient de uniq, on utilise -w32 afin de comparer uniquement les 32 premiers caractères soit uniquement le md5sum (en effet sur Wikipédia on trouve les informations suivantes : « MD5 (Message Digest 5) est une fonction de hachage cryptographique qui calcule, à partir d’un fichier numérique, son empreinte numérique en l’occurrence une séquence de 128 bits ou 32 caractères en notation hexadécimale« ). L’option -D–all-repeated) de uniq affiche tous les groupes de lignes dupliquées (donc dans notre cas toutes les lignes ayant un md5sum identique). Suivant comment on désire le formatage de la sortie on pourra utiliser également --all-repeated=separate qui est bien plus lisible, c’est l’option que j’utilise à la place de -D.

Pour résumer : Assez lent (le calcul du md5sum prend du temps), il y a juste une vérification sur le md5sum, la sortie est triée sur le md5sum.

cd /home/babar/grosdossiertipiaksecret/ && find . -type f -printf "%sn" | sort -rn | uniq -d | sudo xargs -I{} find -type f -size {}c -print0 | xargs -0 du -b > ~/Bureau/Doublons_taille.txt # Chercher tous les fichiers dont la taille est identique (récursivement, affichage du nom des fichiers et taille en octets, tri par taille du fichier du plus grand au plus petit)

Contrairement à ce que l’on pourrait croire c’est le tri par taille du fichier qui est le plus compliqué et peut-être la notation la moins propre. La complexité est qu’on doit utiliser uniq sur une taille de fichiers qui est donc changeante en terme de longueur excluant le recours à l’option -w de uniq. On doit donc trouver un moyen pour n’afficher que la taille des fichiers, utiliser uniq pour trouver les doublons sur la taille des fichiers puis afficher à la fin la taille des fichiers mais également les noms des fichiers.
cd /home/babar/grosdossiertipiaksecret/ : On commence par se placer dans notre dossier, ceci est rendu nécessaire par l’option -I de xargs
-printf "%sn" : On imprime uniquement la taille du fichier ce qui est rendu obligatoire si on veut pouvoir jouer avec uniq et ne ressortir que les lignes dupliquées
sort -rn : On trie par ordre numérique inversé
uniq -d : On n’affiche que les lignes dupliquées
sudo xargs -I{} find -type f -size {}c -print0 : Remarquez le sudo que je vous conseille sinon vous aurez des « Permission non accordée » en pagaille. Voici l’explication de l’option -I tirée de man xargs : « Remplacer les occurrences de chaîne-remplacement dans les paramètres initiaux par les noms lus sur l’entrée standard » en human readable (hi, hi, hi) ça veut dire qu’on récupère un par un les résultats de l’entrée standard (ce qui ressort de uniq -d) et on s’en sert pour le rebalancer dans une ligne de commande. On en a besoin pour jouer avec -size {}c qui va ici nous ressortir les noms des fichiers alors qu’en sortie de uniq -d on avait que la taille des fichiers sans les noms des fichiers
xargs -0 du -b : On lance la commande du -b qui nous donne la taille en octets de chaque fichier

Pour résumer : Très rapide, il y a juste une vérification sur la taille, tri par taille du fichier du plus grand au plus petit.

cd /home/babar/grosdossiertipiaksecret/ && find . -type f -printf "%sn" | sort -rn | uniq -d | sudo xargs -I{} find -type f -size {}c -print0 | xargs -0 md5sum | sort | uniq -w32 --all-repeated=separate > ~/Bureau/Doublons_taille_md5sum.txt # Chercher tous les fichiers dont la taille est identique puis dont le md5sum est identique (récursivement, affichage du md5sum et du nom des fichiers, tri limité sur les 32 premiers caractères par ordre croissant)

cd /home/babar/grosdossiertipiaksecret/ : On commence par se placer dans notre dossier, ceci est rendu nécessaire par l’option -I de xargs
-printf "%sn" : On imprime uniquement la taille du fichier ce qui est rendu obligatoire si on veut pouvoir jouer avec uniq et ne ressortir que les lignes dupliquées
sort -rn : On trie par ordre numérique inversé
uniq -d : On n’affiche que les lignes dupliquées
sudo xargs -I{} find -type f -size {}c -print0 : Remarquez le sudo que je vous conseille sinon vous aurez des « Permission non accordée » en pagaille. Voici l’explication de l’option -I tirée de man xargs : « Remplacer les occurrences de chaîne-remplacement dans les paramètres initiaux par les noms lus sur l’entrée standard » en human readable (hi, hi, hi) ça veut dire qu’on récupère un par un les résultats de l’entrée standard (ce qui ressort de uniq -d) et on s’en sert pour le rebalancer dans une ligne de commande. On en a besoin pour jouer avec -size {}c qui va ici nous ressortir les noms des fichiers alors qu’en sortie de uniq -d on avait que la taille des fichiers sans les noms des fichiers
xargs -0 md5sum : On récupère le md5sum de chaque fichier
sort : On trie
uniq -w32 --all-repeated=separate : on utilise -w32 afin de comparer uniquement les 32 premiers caractères soit uniquement le md5sum et grâce à --all-repeated=separate on affiche tous les groupes de lignes dupliquées délimités par une ligne vide (pour une lecture plus lisible)

Pour résumer : Rapide, il y a une vérification sur la taille puis sur le md5sum, la sortie est triée sur le md5sum.

On retombe ainsi sur la ligne de commandes la mieux notée dans le cadre de la recherche de fichiers dupliqués sur commandlinefu.com.

find -not -empty -type f -printf "%sn" | sort -rn | uniq -d | xargs -I{} -n1 find -type f -size {}c -print0 | xargs -0 md5sum | sort | uniq -w32 --all-repeated=separate

De mon côté j’ai viré le -not -empty qui sert à exclure les fichiers vides mais qui dans la réalité ne sert jamais. J’ai ajouté le sudo devant xargs -I{}. J’ai viré le -n1 qui n’est pas réellement utile.

BONUS

sed -i '/gif/Id;/jpg/Id;/bmp/Id;/zip/Id;/html/Id;/pdf/Id;/png/Id;/xml/Id;/wav/Id;/txt/Id' ~/Bureau/Doublons.txt # Supprimer toutes les lignes du document Doublons.txt contenant certains mots (I pour insensible à la casse et d pour delete)
find /home/babar/grosdossiertipiaksecret/sound -type f ( -iname *.jpg -o -iname *.html -o -iname thumbs.db -o -iname desktop.ini ) -print0 | xargs -0 /bin/rm # Supprimer tous les fichiers contenant certains mots ou extensions du dossier sound (insensible à la casse)

Ces différentes méthodes pour retrouver des doublons sont suffisantes et complémentaires. En revanche il n’y a aucune solution pour identifier les « faux » doublons que vous désirez supprimer car c’est votre choix, il faut obligatoirement lire les fichiers.

Vous l’aurez compris trouver des « faux » doublons est un faux débat. Je vous ai donné de quoi retrouver toute extension ou mot au sein d’un même dossier, de quoi lister tous les fichiers puis les trier par nom ou par taille, de quoi supprimer des fichiers ou extensions en grand nombre, de quoi purger un fichier texte des informations inutiles avec sed enfin de quoi retrouver les « vrais » doublons et les « faux » doublons par taille, nom, md5. On ne peut guère faire mieux, c’est en tout cas comme ça que je trouve les doublons sur mon poste aujourd’hui. Si quelqu’un a une meilleure méthode, je suis fort intéressé !

Ce qu’il faudrait c’est un système à la YouTube capable de reconnaître une même musique ou des images identiques (un même « contenu ») à l’intérieur de plusieurs fichiers. Je ne connais hélas pas d’application sur GNU/Linux qui fasse cela. Les applications graphiques les plus connues sur GNU/Linux pour trouver des doublons sont FSlint et dupeGuru. Concernant FSlint on peut constater dans la FAQ qu’il n’est pas en mesure de reconnaître du contenu. Concernant dupeGuru, je ne suis pas arrivé à trouver comment il compare les fichiers (ce qui s’en rapproche le plus est ici). J’ai en revanche fait un test. J’ai copié une vidéo, je l’ai renommé et j’ai supprimé les 5 dernières secondes (oui je sais faire ça je suis un crack). Il n’a pas été capable de la retrouver donc sans trop de risques je pense que dupeGuru fonctionne sensiblement de la même manière que FSlint et que les divers exemples décrits dans cet article. Je n’ai en revanche pas essayer dupeGuru Picture Edition et Music Edition étant donné que c’est « spécialisé » il y a peut-être un algorithme pour trouver du contenu dupliqué. Je vous invite à tester, je vais pas tout faire quand-même

Pour installer FSlint : apt-get install fslint ou aptitude install fslint
Pour installer dupeGuru il faut installer le PPA de Ubuntu 14.10 car dupeGuru n’est pas dans les dépôts de Ubuntu 15.04 : apt-get install dupeguru-se ou aptitude install dupeguru-se

Sources intéressantes sur la différence entre sort -u et uniq :
http://unix.stackexchange.com/questions/76049/what-is-the-difference-between-sort-u-and-sort-uniq
http://stackoverflow.com/questions/3382936/sort-uniq-in-linux-shell