Calcul de la distance entre deux fichiers

Posté le Sunday, 06 June 2010 in Programmation

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é1.

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{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;
Version 1 Version 2 Distance
v0.8.1 v0.8.1_services 0.0350740694634633
v0.6.8 v0.6.9 0.132275346477201
v0.8.0 v0.8.1 0.142321125298336
v0.8.0 v0.8.1_services 0.161719318637048
v0.6.5 v0.6.6 0.196933113059686
v0.6.4 v0.6.5 0.231812199675573
v0.6.6 v0.6.7 0.266593999923953
v0.6.10 v0.7.0 0.27412838729727
v0.7.2 v0.8.0 0.312111739912996
v0.6.5 v0.6.7 0.351347925829225
v0.6.4 v0.6.6 0.364115163581424
v0.7.2 v0.8.1 0.386971922637303
v0.7.2 v0.8.1_services 0.401055941017259
v0.7.1 v0.7.2 0.436705836223058
v0.7.0 v0.7.1 0.465121645779551
v0.6.4 v0.6.7 0.468472350726879
v0.8.1_services v0.9.0 0.516795574578859
v0.8.1 v0.9.0 0.51733623689019
v0.8.0 v0.9.0 0.544376861655528
v0.6.7 v0.6.8 0.558824765667689
v0.7.1 v0.8.0 0.560609480175814
v0.6.10 v0.6.9 0.594036969567445
v0.7.1 v0.8.1 0.604226316444666
v0.7.1 v0.8.1_services 0.613613062086946
v0.6.7 v0.6.9 0.622950487834501
v0.7.0 v0.7.2 0.631060763867616
v0.6.10 v0.7.1 0.632444883185258
v0.6.10 v0.6.8 0.637234847328374
v0.6.6 v0.6.8 0.6494052372746
v0.6.9 v0.7.1 0.666200571812458
v0.7.2 v0.9.0 0.678423568871868
v0.6.5 v0.6.8 0.692250570944195
v0.6.8 v0.7.1 0.701063946130892
v0.6.6 v0.6.9 0.701698986545754
v0.6.9 v0.7.0 0.717262408423359
v0.7.0 v0.8.0 0.720311680104721
v0.6.5 v0.6.9 0.738013305804084
v0.6.4 v0.6.8 0.747495551539097
v0.6.10 v0.7.2 0.747929200720491
v0.6.8 v0.7.0 0.748031544518325
v0.7.0 v0.8.1 0.758510349354368
v0.7.0 v0.8.1_services 0.767204482779187
v0.6.4 v0.6.9 0.772451857549627
v0.6.10 v0.8.0 0.796649043913944
v0.7.1 v0.9.0 0.801221496333008
v0.6.9 v0.7.2 0.804765901655414
v0.6.8 v0.7.2 0.819917045496318
v0.6.10 v0.8.1 0.823540395867048
v0.6.10 v0.8.1_services 0.831055117394626
v0.6.10 v0.6.7 0.838850951377793
v0.6.9 v0.8.0 0.849001032539087
v0.6.7 v0.7.1 0.853848016623182
v0.7.0 v0.9.0 0.860291356912217
v0.6.8 v0.8.0 0.86075956509228
v0.6.10 v0.6.6 0.863340151908353
v0.6.9 v0.8.1 0.872265541006983
v0.6.6 v0.7.1 0.873275579233521
v0.6.10 v0.6.5 0.875332023895544
v0.6.9 v0.8.1_services 0.87987037883801
v0.6.7 v0.7.0 0.879941907871053
v0.6.8 v0.8.1 0.881174812987336
v0.6.5 v0.7.1 0.886172606121206
v0.6.8 v0.8.1_services 0.889515283880001
v0.6.10 v0.6.4 0.892364892140999
v0.6.6 v0.7.0 0.894375709613201
v0.6.10 v0.9.0 0.895694726039398
v0.6.7 v0.7.2 0.898582911617307
v0.6.4 v0.7.1 0.902038058337369
v0.6.5 v0.7.0 0.904821831317442
v0.6.6 v0.7.2 0.910637046476578
v0.6.4 v0.7.0 0.918347943544789
v0.6.5 v0.7.2 0.919716704855963
v0.6.9 v0.9.0 0.921714099772221
v0.6.7 v0.8.0 0.924717744438112
v0.6.8 v0.9.0 0.925849165227404
v0.6.4 v0.7.2 0.928888262611658
v0.6.7 v0.8.1 0.933685479216414
v0.6.6 v0.8.0 0.933940067594635
v0.6.7 v0.8.1_services 0.939898268404416
v0.6.5 v0.8.0 0.940789807767177
v0.6.6 v0.8.1 0.94210246370087
v0.6.6 v0.8.1_services 0.946464528845253
v0.6.4 v0.8.0 0.948830071149278
v0.6.5 v0.8.1 0.94922082772201
v0.6.5 v0.8.1_services 0.951278461132112
v0.6.4 v0.8.1 0.955572468114482
v0.6.4 v0.8.1_services 0.95567206186826
v0.6.7 v0.9.0 0.96084453455483
v0.6.6 v0.9.0 0.964619158469125
v0.6.5 v0.9.0 0.965955795849916
v0.6.4 v0.9.0 0.968866861905835

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.


  1. On peut retrouver l'explication de cette formule ici