Discussion :

[MaxLaMenaX]

Salut,

J'ai pour but de développer un logiciel Java qui me trouverait tous les doublons d'un Système de fichier ou d'un répertoire ( on rentrerait le répertoire racine de la recherche en ligne de commande...)...

Me facteurs de qualité qui m'intéresse étant la rapidité de l'execution, car parcourir déja toute la hierarchie d'un disque dur c'est déjà assez long ...

Comment peux t'on comparer deux fichiers ? :
- méthode de hashage ?
- methode hash() sur l'objet File ?
- checksum ?
- comparaison du nom fichier concaténé a la taille ? (exemple : test.gif-3457)...

La derniere solution dans un premier temps est suffisante, car il y a peu de chance que l'on est des fichiers de même nom et de même taille qui soient identique ...

Bref je cherche dans un premier temps, une méthode rapide, qui pourrait ne pas être exacte...
C'est à dire qui puisse traiter un grand nombre de fichier dans une grande hierarchie rapidement et me donne à la fin une liste des fichiers susceptiblement identique...

Dans un deuxième temps, une méthode peut être plus lente mais vraiment carré, basé sur le checksum ou autre chose, qui ne nécessiterait pas de vérification manuelle pour vérifier si les fichiers sont vraiment identiques ...

3eme point : trouvér deux fichiers identiques, ayant un contenu identique, mais pas le même nom ?


Pour finir, la methode length() de File sur un directory, je crois me rends une taille multiple de 4096...

ET je cherche la taille du fichier réelle et non celle qu'elle prends sur le disque ...

Y a t'il une methode ou des apis qui font cela ?

Merci à vous, pour vos idées conseils et idées !

[dinobogan]

Comment peux t'on comparer deux fichiers ? :
- méthode de hashage ?
- methode hash() sur l'objet File ?
- checksum ?
- comparaison du nom fichier concaténé a la taille ? (exemple : test.gif-3457)...

Tu mélanges "fichier sur disque" et "objet File".

3eme point : trouvér deux fichiers identiques, ayant un contenu identique, mais pas le même nom ?

traite directement les tailles des fichiers, sans prendre en compte leurs noms.
Une fois la liste établie, tu tries les tailles. Pour celles identiques, tu construis un checksum en utilisant par exemple java.util.zip.CheckedInputStream.
Si le checksum est différent, alors les fichiers sont différents.
Par contre, si le checksum est identique, cela signifie que les fichiers sont peut-être identiques. Une lecture octet par octet sera nécessaire.
Si tu dois tester uniquement deux fichiers, autant les lire octets par octets. Par contre, si tu dois en tester plusieurs et qu'ils sont volumineux, alors le checksum te fera gagner du temps puisqu'il est à calculer une fois pour toute pour un fichier donné.

Pour finir, la methode length() de File sur un directory, je crois me rends une taille multiple de 4096...

Ce n'est pas ce que dit la javadoc.
Fait un simple test en créant un fichier d'un seul octet. Tu seras vite fixé.

[MaxLaMenaX]

Salut dinobogan ! Merci pour tes réponses ...

Oui en fait, actuellement j'utilise l'objet Java File, qui peut être soit un "dir" soit un "file"...

Je me demandais si il n'existait pas une API ou un objet Java qui permettrait de récupérer les mêmes données que lorsque on "clique droit>>propriétés" sur un fichier ou un répertoire... (dans windows)

Peut être l'objet FileSystem (je sais pas)...

J'ai regardé dans les objets Java, j'avais trouvé "FileDescriptor", le nom me semblait correspondre au besoin mais au final, cela ne m'a pas aidé.

Ce que je sais c'est que pour un fichier sur le disque, dans les propriétés windows on a la taille réelle et la taille disque multiple de 4Ko ou 8Ko en fonction du découpage que l'on a fait de son disque...

Je n'ai pas encore pu tester (mais je le ferais) si File.length() retourne la taille réelle ou la taille disque ?
Et File.length() si File est un repertoire me donne t'il la taille totale du repertoire ? ou juste la taille du repertoire, à tester mais je crois pas qu'il me donne la taille totale du repertoire ...

Car si je veux avoir le moins de doublon possible, il faudrait mieux que j'ai la taille réélle!

traite directement les tailles des fichiers, sans prendre en compte leurs noms.
Une fois la liste établie, tu tries les tailles. Pour celles identiques, tu construis un checksum en utilisant par exemple java.util.zip.CheckedInputStream.
Si le checksum est différent, alors les fichiers sont différents.

Ca ok c'est un peu comme j'avais procédé... sauf que je n'utilisais pas le checksum, n'ayant jamais utilisé ce type de classe...
Mais là je vais essayer...
Et aussi est ce qu'on peut faire un checksum sur un repertoire ? comme ca ca m'aiderait aussi à trouver les repertoires identiques, je suppose que oui puisque checksum est utilisé pour créer les zip.

Par contre, si le checksum est identique, cela signifie que les fichiers sont peut-être identiques. Une lecture octet par octet sera nécessaire.
Si tu dois tester uniquement deux fichiers, autant les lire octets par octets. Par contre, si tu dois en tester plusieurs et qu'ils sont volumineux, alors le checksum te fera gagner du temps puisqu'il est à calculer une fois pour toute pour un fichier donné.

Une lecture par octet ? euh oui mais ça se réalise comment ça ? je vois le principe mais dans la pratique je suis pas trop ...

Enfin je pense que le checksum sera suffisant... car ce qui m'intéresse c'est de trouver tous les doublons ou triplons ou plus dans un disque ...

[dinobogan]

Et File.length() si File est un repertoire me donne t'il la taille totale du repertoire ? ou juste la taille du repertoire, à tester mais je crois pas qu'il me donne la taille totale du repertoire ...

Il suffit de lire la javadoc

Et aussi est ce qu'on peut faire un checksum sur un repertoire ? comme ca ca m'aiderait aussi à trouver les repertoires identiques, je suppose que oui puisque checksum est utilisé pour créer les zip.

Un checksum se fait sur des données. Faire un checksum sur un répertoire n'a aucun sens. Un checksum est une simple formule appliquée sur des entiers.

Une lecture par octet ? euh oui mais ça se réalise comment ça ? je vois le principe mais dans la pratique je suis pas trop ...

Tu ouvres les deux fichiers à comparer, tu lis octet par octet les deux fichiers. Dès qu'un octet du premier fichier est différent de l'octet du second fichier, les deux fichiers sont différents.

Enfin je pense que le checksum sera suffisant... car ce qui m'intéresse c'est de trouver tous les doublons ou triplons ou plus dans un disque ...

Non, si tu veux faire ça proprement, tu dois vérifier le contenu des fichiers. Le principe du checksum est de savoir si deux fichiers sont différents, pas s'ils sont identiques. La différence est subtile mais primordiale. Tu pourrais te retrouver avec des faux positifs.

[MaxLaMenaX]

ok merci dinobogan, ouais la javadoc c'est bien !

mais bon chez moi j'ai pas internet, donc je bosse en local, et donc j'ai pas accès à la javadoc (même si bon j'ai bien une version local de la javadoc sur mon pc, mais faut pas le dire ... )...

Un checksum se fait sur des données. Faire un checksum sur un répertoire n'a aucun sens. Un checksum est une simple formule appliquée sur des entiers.

héhé faut pas t'énerver ! Non mais moi mon but et de trouver les doublons sur un disque ... je prefere que mon logiciel me dise "ouais j'ai un repertoire là qui est identique à celui là ..." plutot que "ouais j'ai 3 fichiers dans un repertoire, qui sont tous les 3 identiques à 3 autre fichier dans un autre repertoire..."

je veux dire c'est plus mieux qu'il puisse et me trouver les fichiers identiques, et les répertoires identiques ... you see what i am saying ?

Donc pour les répertoires, je compare comment si je peux pas avoir le checksum ? juste sur la taille ? le souci c'est que dans ton lien javadoc "length()" n'est utilisé que pour les File.isFile() et pas pour les "Dir"...
ou alors je calcul la taille du répertoire dans ma récursivité et je compare ...
puisque apparement on peut pas avoir la taille du répertoire simplement ...

Tu ouvres les deux fichiers à comparer, tu lis octet par octet les deux fichiers. Dès qu'un octet du premier fichier est différent de l'octet du second fichier, les deux fichiers sont différents.

Ok, compris... ouais comme ça pas la peine qu'il parcourt tout si y'a une différence dès le début du fichier ... par contre c'est quoi les objets jav ou les fonctions pour faire de la lecture octet par octet ? sur un fichier ? Scanner ?

Non, si tu veux faire ça proprement, tu dois vérifier le contenu des fichiers. Le principe du checksum est de savoir si deux fichiers sont différents, pas s'ils sont identiques. La différence est subtile mais primordiale. Tu pourrais te retrouver avec des faux positifs.

Ouais j'ai bien compris que le checksum pouvait être identique à deux fichiers qui sont différents ... mais ca doit être assez rare non ?
Par contre deux fichiers dont les checksum sont différent ne peuvent pas être identique ? ok compris !

Donc je vais faire deux versions, une rapide qui peux me donner des faux positifs ...
et une de qualité mais lente que je ferais tourner la nuit !

Par contre quelle structure de donnée semble la plus efficace pour ce type de truc ?

Collection ? List ? Arraylist ? Sorted List ? hashatble ? hashmap ? etc ?

Actuellement j'utilise ArrayList car c'est celle que j'ai le plus l'habitude d'utiliser...

En fait je fais mon parcours recursif :
-des que j'ai un nouveau fichier, j'ajoute un objet FileScanned (taille, checksum, nom, list (path)) dans une liste

si le fichier suivant n'est pas déjà contenu dans la liste, je l'ajoute, sinon si il est deja contenu, c'est que c'est le meme, donc il trouve l'objet correspondant et ajoute son path ...

Comme ca a la fin du logiciel : j'ai une liste des doublons : ainsi que les chemins ou on été trouvé chaque doublon par fichiers...

donc une liste de liste !

PS : en cherchant des trucs sur checksum j'ai vu quye certain parlait des algorithmes SHA1, et autre CRC32 je crois ... et que selon la rapidité était différente ! t'a des données la dessus ?

[tchize_]

ouais la javadoc c'est bien !

mais bon chez moi j'ai pas internet, donc je bosse en local, et donc j'ai pas accès à la javadoc

Et tu poste sur ce forum par pigeon voyageur? Tu peux très bien aller lire la javadoc avant de poster ton message!

Pour répondre,

Plus l'algorithme de hashage est simple, plus il est rapide. d'un point de vue performance, l'ordre suivant serait à respecter je pense


1) Faire un index de tous les fichiers avec leur taille, en rassemblant les fichier de taille identique
2) Pour les fichier ayant des doublons du point de vue de la taille, discirminer en utilisant un hashage.
3) Pour les fichier toujours identiques (donc taille + hash), faire une lecture octet par octet
4) les fichiers toujours rassemblé sont maintenant de vrai doublons
5) éventuellement passer sur les doublons ainsi trouver pour déterminer les répertoires identiques.


Ainsi, tu ne calcule le hashage que sur une partie des fichiers (et tu évite de lire tout le disque), et tu ne fait de comparaison octet par octet que sur une encore plus petite partie des fichiers. Tu peux même accélérer un peu en calculant déjà en 1, systématiquement, le hash de tout fichier < TAILLE_CRITIQUE, ceux là étant considéré comme ayant beaucoup de chance d'avoir besoin du Hash. TAILLE_CRITIQUE étant à déterminer en fonction de la taille de ta méthode de hashage (4 octets pour CRC32 par exemple :p) et le risque de collisions en étape 1 en fonction de la taille.

Attention cependant, une surprise que t'aura probablemet pas prévue. Pour les fichiers de taille < 2 octets tu risque d'avoir beaucoup de doublons, surtout dans les fichiers vide

PS: pour lire des fichiers, c'est FileInputStream