Shadoware.Org

Moi, mes idées, mes logiciels ...

Aller au contenu | Aller au menu | Aller à la recherche

En ce moment sur Shadoware.Org

6 juin 2010

Calcul de la distance entre deux fichiers

Par Ulrich Van Den Hekke le dimanche, juin 6 2010, 11:40 - Logiciels libres

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 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;
v0.8.1v0.8.1_services0.0350740694634633
v0.6.8v0.6.90.132275346477201
v0.8.0v0.8.10.142321125298336
v0.8.0v0.8.1_services0.161719318637048
v0.6.5v0.6.60.196933113059686
v0.6.4v0.6.50.231812199675573
v0.6.6v0.6.70.266593999923953
v0.6.10v0.7.00.27412838729727
v0.7.2v0.8.00.312111739912996
v0.6.5v0.6.70.351347925829225
v0.6.4v0.6.60.364115163581424
v0.7.2v0.8.10.386971922637303
v0.7.2v0.8.1_services0.401055941017259
v0.7.1v0.7.20.436705836223058
v0.7.0v0.7.10.465121645779551
v0.6.4v0.6.70.468472350726879
v0.8.1_servicesv0.9.00.516795574578859
v0.8.1v0.9.00.51733623689019
v0.8.0v0.9.00.544376861655528
v0.6.7v0.6.80.558824765667689
v0.7.1v0.8.00.560609480175814
v0.6.10v0.6.90.594036969567445
v0.7.1v0.8.10.604226316444666
v0.7.1v0.8.1_services0.613613062086946
v0.6.7v0.6.90.622950487834501
v0.7.0v0.7.20.631060763867616
v0.6.10v0.7.10.632444883185258
v0.6.10v0.6.80.637234847328374
v0.6.6v0.6.80.6494052372746
v0.6.9v0.7.10.666200571812458
v0.7.2v0.9.00.678423568871868
v0.6.5v0.6.80.692250570944195
v0.6.8v0.7.10.701063946130892
v0.6.6v0.6.90.701698986545754
v0.6.9v0.7.00.717262408423359
v0.7.0v0.8.00.720311680104721
v0.6.5v0.6.90.738013305804084
v0.6.4v0.6.80.747495551539097
v0.6.10v0.7.20.747929200720491
v0.6.8v0.7.00.748031544518325
v0.7.0v0.8.10.758510349354368
v0.7.0v0.8.1_services0.767204482779187
v0.6.4v0.6.90.772451857549627
v0.6.10v0.8.00.796649043913944
v0.7.1v0.9.00.801221496333008
v0.6.9v0.7.20.804765901655414
v0.6.8v0.7.20.819917045496318
v0.6.10v0.8.10.823540395867048
v0.6.10v0.8.1_services0.831055117394626
v0.6.10v0.6.70.838850951377793
v0.6.9v0.8.00.849001032539087
v0.6.7v0.7.10.853848016623182
v0.7.0v0.9.00.860291356912217
v0.6.8v0.8.00.86075956509228
v0.6.10v0.6.60.863340151908353
v0.6.9v0.8.10.872265541006983
v0.6.6v0.7.10.873275579233521
v0.6.10v0.6.50.875332023895544
v0.6.9v0.8.1_services0.87987037883801
v0.6.7v0.7.00.879941907871053
v0.6.8v0.8.10.881174812987336
v0.6.5v0.7.10.886172606121206
v0.6.8v0.8.1_services0.889515283880001
v0.6.10v0.6.40.892364892140999
v0.6.6v0.7.00.894375709613201
v0.6.10v0.9.00.895694726039398
v0.6.7v0.7.20.898582911617307
v0.6.4v0.7.10.902038058337369
v0.6.5v0.7.00.904821831317442
v0.6.6v0.7.20.910637046476578
v0.6.4v0.7.00.918347943544789
v0.6.5v0.7.20.919716704855963
v0.6.9v0.9.00.921714099772221
v0.6.7v0.8.00.924717744438112
v0.6.8v0.9.00.925849165227404
v0.6.4v0.7.20.928888262611658
v0.6.7v0.8.10.933685479216414
v0.6.6v0.8.00.933940067594635
v0.6.7v0.8.1_services0.939898268404416
v0.6.5v0.8.00.940789807767177
v0.6.6v0.8.10.94210246370087
v0.6.6v0.8.1_services0.946464528845253
v0.6.4v0.8.00.948830071149278
v0.6.5v0.8.10.94922082772201
v0.6.5v0.8.1_services0.951278461132112
v0.6.4v0.8.10.955572468114482
v0.6.4v0.8.1_services0.95567206186826
v0.6.7v0.9.00.96084453455483
v0.6.6v0.9.00.964619158469125
v0.6.5v0.9.00.965955795849916
v0.6.4v0.9.00.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 logiciel attaché à ce billet.

Notes

[1] On peut retrouver l'explication de cette formule ici

une annexe

2 mai 2010

Présentation de XINX

Par Ulrich Van Den Hekke le dimanche, mai 2 2010, 21:55 - XINX

Ce billet fait suite à la sortie de la version 0.9.0 de XINX et va vous décrire ce logiciel. XINX est éditeur de feuille de style XSL (il fait également éditeur JavaScript et CSS mais actuellement moins bien que ce que peuvent faire d'autres).

Il permet l'édition des feuilles de styles en proposant de compléter sur le nom des balises (normal), sur les attributs (normal), sur les valeurs d'attributs : les variables, les paramètres, ... Il propose également automatiquement les différents paramètres lors de l'utilisation d'un call:template.

L'éditeur est fortement tourné vers l'édition de feuille de style XSL pour génération d'HTML mais peut être utilisé pour générer du XML.

XINX Logo

Lire la suite...

21 septembre 2009

[Qt] Transformation d'une vue tableau en une vue hiérarchique

Par Ulrich Van Den Hekke le lundi, septembre 21 2009, 13:50 - Logiciels libres

Pour visualiser des données internes à l'écran, Nokia/Qt nous propose l'architecture MVC à l'aide des classes QAbstractItemModel et de ses sous classes (QAbstractListModel, QAbstractTableModel, ...). Le but de l'architecture MVC est de séparer la représentation mémoire des données, de l'affichage qu'elles auront.

mvc1.png

Si les données sont par exemple issue d'une requête SQL, le modèle QSqlQueryModel permet de représenter la sélection SQL, à l'écran dans un composant QTableView. Ces données sont alors représentées sous forme d'un tableau deux dimensions.

tableau.png

Si l'on veut représenter les dossiers de l'ordinateur, le modèle QDirView permet d'afficher les données de façon hiérarchique.

qdirview.png

Il est également possible d'écrire nos propres modèles pour représenter nos propres données.

Le but de cet article est de présenter l'écriture d'un modèle, transformant une vue plane (tableau deux dimensions) en vue hiérarchique. Pour cela nous allons prendre l'exemple de l'affichage d'une liste de catégorie[1].

Notes

[1] La construction de notre objet s'est basé sur l'analyse de l'objet QSortFilterProxyModel de Nokia.

Lire la suite...

un commentaire 2 annexes

31 mai 2009

Parseur XML

Par Ulrich Van Den Hekke le dimanche, mai 31 2009, 23:13 - Logiciels libres

Bonjours à tous,

L'utilisation des fichiers XML est, à ce jour, un fait dans la plupart des logiciels et est fortement à la mode. Une entreprise qui ne fait pas un peu de XML est souvent has-been. On utilise alors le XML à bon ou mauvais escient.

Lire la suite...

4 commentaires 2 annexes

26 mai 2009

XINX 0.8.1.0

Par Ulrich Van Den Hekke le mardi, mai 26 2009, 08:30 - XINX

Bonjour à tous,

Erratum : La dernière version est numéroté 0.8.1.1. Un petit bug (pouvant être gênant lors de l'ouverture de feuille de style sans utilisation du mode projet) a été corrigé dans la foulé. La page est corrigé en conséquence

Je souhaite vous annoncer la sortie de la version 0.8.1.0 0.8.1.1 de XINX. Pas d'énorme changement pour vous depuis la version 0.8.0.0 (sinon nous serions passés à la version 0.9.0.0) mais de gros changements internes.

Vue Contenue

ContentViewDock.png

En fait, la partie gérant la vue contenue a été complètement ré-écrite. Elle est maintenant parallélisée et partagée entre les différents éditeurs. Au final l'empreinte mémoire, ainsi que la fluidité a chargé les différents fichiers de XINX devrait être amélioré. (Enfin j'espère, car je n'ai pas fait de benchmark). De ce coté le code est lui aussi beaucoup plus propre et plus souple.

XINX étant toujours dans les versions 0.XX, je n'ose vous rappeler que ce n'est pas ce qu'on appelle une version finie, mais une série de bêta ;) . Étant donné le peu de test que j'ai pu faire sur cette version en particulier j'aurais dû la nommer en -rc ou en -beta mais je me suis dit que cela serait redondant, et que si ça ne convenait pas vous ajouteriez un ticket sur ce site pour me prévenir. Enfin j'espère que cette version ne sera pas trop miner. :D

La ré-écriture de la partie Vue Contenue permet donc de préciser dans les propriétés du projet quelques fichiers qui seront pré-chargés au chargement du projet. Ces fichiers étant pré-chargés, l'ouverture des feuilles de styles devrait être accéléré. Si de votre coté, XINX présente quelques faiblesses, merci de me prévenir. La complétion a également été améliorée (avec la suppression des bug, comme l'affichage de balise with-param en double). Lors de vos déplacements dans l'éditeur, la vue contenue vous indique votre emplacement dans la vue contenue.

PreloadedFiles.png

Dictionnaire

Dictionary.png

L'autre nouveau point et l'ajout d'un nouveau Dock par l'intermédiaire des plugins. Ce Dock vous propose l'affichage du dictionnaire dans les versions GCE130 et GCE140. Pour l'instant le seul intérêt de ce dock est l'affichage du dictionnaire à la recherche d'un label. C'est un point de départ pouvant vous servir à faire des tickets sur des améliorations à apporter. (Celle que j'ai en tête est la gestion de la complétion sur les libellés du dictionnaire). Merci de passer par le système de ticket pour proposer d'autres améliorations sur le DOCK Dictionnaire.

Pré-visualisation

Enfin, dernière évolution intéressante, est l'affichage de la pré-visualisation de la page. Cette fonctionnalité est à noter comme extrêmement expérimental,et n'évoluera peut-être pas (selon les demandes qui sont faites dessus, ainsi que suivant les problèmes techniques rencontrés), et ne fonctionnera peut-être pas avec les prochaines versions de GCE. (En version 140, les libellés ne sont pas remplacés).

CustomWebPlugin.png

Pour faire fonctionner la prévisualisation, vous devez renseigner l'emplacement de la ServletControl, configurer, dans les propriétés du plugin WEB, le parseur à utiliser[1] et de configurer le lecteur (je vous conseille Webkit).

De là, lors des développements de feuille de style en mode projet, si vous sélectionnez un flux de présentation XML (dans le dock associé) et appuyé sur F9, vous devriez avoir la prévisualisation de votre feuille de style.

Le même principe peut-être appliqué pour une page HTML. Là, pas besoin de parseur, ni de flux de présentation. Vous pouvez avoir directement la prévisualisation de votre page HTML.

ParseXsl.png

Gestion des plugins

Enfin, la gestion des plugins n'a cessé de s'améliorer. Il est de plus en plus facile d'étendre 'XINX'. Ceci par l'intermédiare de Script ou de Plugins. Si une fonctionnalité vous manque, vous pouvez donc non seulement la proposer, mais aussi l'écrire en script, ou si le script est trop limité, vous pouvez aussi écrire le plugin. Les plugins permettent donc d'ajouter des actions à XINX, des Docks, des éditeurs, des gestionnaires de version, des pages de configuration du projet, ...

D-BUS

Alors que D-BUS avait été ajouté dans les précédentes versions afin de permettre une plus grande interopérabilité, ce dernier a été retiré pour cette version. Ainsi XINX est maintenant indépendant de D-BUS. Il a été décidé de retirer D-BUS pour plusieurs raisons : Simplification de la compilation, source de problème sous MS/Windows. Il devient maintenant beaucoup plus simple de compiler XINX sous Windows. L'interface avec D-BUS reviendra dans une future version mais sera alors optionnel.

Je vous souhaite une bonne installation.

Téléchargement

Sous Debian, ajout du dépôt :
deb http://apt.shadoware.org/ sid main

Notes

[1] je vous conseille celui d'Oracle, Il est plus long à se lancer mais permet de gérer les noms de domaine Generix.

- page 1 de 11

haut de page