Calcul de la distance entre deux fichiers

Présentation

Suite à un billet sur LinuxFR, où je demandais comment calculer la distance (ou le pourcentage de similitude entre deux logiciels), j'ai obtenu la formule suivante :

distance = 1 - ( C(A) + C(B) - C(AB) ) / Max(C(A), C(B))

où C(X) est la taille du fichier X compressé¹.

Après avoir testé les formats gzip, bzip2 et lzma, j'ai conclu que le format de compression le plus performant pour le calcul, est le format lzma, car le dictionnaire avec la mise en commun était le plus gros, et donc le calcul de distance est plus efficace.

Le programme

J'ai donc décidé d'écrire un programme parcourant un dossier (avec plusieurs milliers de fichiers) et de calculer pour toutes les combinaisons des fichiers la distance entre chaque fichier. Ce programme consommant énormément de mémoire, il se peut que pour un grand nombre de fichier, le programme se plante avec une erreur d'allocation de mémoire.

Ce programme permet de pouvoir faire une cartographie de ces fichiers et ainsi de pouvoir les classer. Testé sur des fichiers textes (sources de logiciels), le programme est assez efficace.

Testé sur des images, ou des vidéos, les fichiers sont considérés comme tous éloignés les uns des autres, même s'ils sont identiques à compression différente près, ou s'ils sont identiques à un mouvement près sur la photo (du genre une photo où une même personne se tient dans une position différente).

Si vous avez une idée sur comment calculer la distance entre deux fichiers déjà compressés (avec perte qui plus est), ca m'intéresse. :)

Comme l'exécution est très lente (compression lzma niveau 9), le programme peut être arrêté et redémarré.

Pour démarrer le programme, il faut exécuter la commande :

./calcul_distance /mon/dossier

Le programme va alors créer un fichier {5ac1fd3c-504f-4110-9f7e-d6fc89e57bdb}.db où {5ac1fd3c-504f-4110-9f7e-d6fc89e57bdb} est différent à chaque nouveau lancement.

Pour reprendre le traitement où il était, il suffit alors de lancer :

./calcul_distance --uuid {5ac1fd3c-504f-4110-9f7e-d6fc89e57bdb}

Si on veut ajouter un dossier au traitement après coup :

./calcul_distance /nouveau/dossier --uuid {5ac1fd3c-504f-4110-9f7e-d6fc89e57bdb}

Exemple

Par exemple soit les différentes versions d'un logiciel, mis dans des archives tar. Pour ne prendre que le code source des versions, on va supprimer tous les fichiers suivants de l'archive tar : *.jpg, *.png, *.ico, *.qm, *.db, ... les sources externes à l'application. On ne garde donc que les fichiers textes dont nous avons la possession.

Après le nettoyage des dossiers :

$ for i in `ls` ; do
> tar -c $i/* 
> $i.tar
> done
$ ls -l
-rw-r--r-- 1 phoenix phoenix 2,5M  6 juin  13:24 v0.6.10.tar
-rw-r--r-- 1 phoenix phoenix 440K  6 juin  13:24 v0.6.4.tar
-rw-r--r-- 1 phoenix phoenix 530K  6 juin  13:24 v0.6.5.tar
-rw-r--r-- 1 phoenix phoenix 610K  6 juin  13:24 v0.6.6.tar
-rw-r--r-- 1 phoenix phoenix 690K  6 juin  13:24 v0.6.7.tar
-rw-r--r-- 1 phoenix phoenix 1,2M  6 juin  13:24 v0.6.8.tar
-rw-r--r-- 1 phoenix phoenix 1,3M  6 juin  13:24 v0.6.9.tar
-rw-r--r-- 1 phoenix phoenix 2,9M  6 juin  13:24 v0.7.0.tar
-rw-r--r-- 1 phoenix phoenix 2,2M  6 juin  13:24 v0.7.1.tar
-rw-r--r-- 1 phoenix phoenix 3,3M  6 juin  13:24 v0.7.2.tar
-rw-r--r-- 1 phoenix phoenix 3,3M  6 juin  13:24 v0.8.0.tar
-rw-r--r-- 1 phoenix phoenix 3,1M  6 juin  13:24 v0.8.1_services.tar
-rw-r--r-- 1 phoenix phoenix 3,1M  6 juin  13:24 v0.8.1.tar
-rw-r--r-- 1 phoenix phoenix 3,8M  6 juin  13:24 v0.9.0.tar
$ cd ..
$ calcul_distance ./xinx/
Step 0 : Create database
Step 1 : Create file list
Step 2 : Compress single file                       
Step 3 : Compress pair file
$ ls 
{051b93a0-d9a9-4778-ac73-81ee01a3905d}.db
xinx
$ sqlite3 {051b93a0-d9a9-4778-ac73-81ee01a3905d}.db

Nous allons maintenant faire une requête dans la base de données sqlite :

$ .TABLES
distances  files 
$ SELECT files1.path, files2.path, distances.distance FROM distances, files files1, files files2 WHERE distances.id1=files1.id AND distances.id2=files2.id ORDER BY distance ASC;

On peut ainsi voir d'après ce tableau, les versions ayant peu de différences et celles qui ont fait des plus gros bonds en avant.

On voit ainsi qu'il y a plus de différences entre la version 0.8.0 et la 0.9.0, qu'il y en a eu entre la version 0.6.8 et la 0.6.9. On peut également voir que les versions 0.6.4 et 0.9.0 n'ont plus rien à voir entre elles.

Vous pouvez télécharger le programme attaché à ce lien.