Forum Programmation.c++ Calculer le taux de modification

Posté par (page perso) .
Tags : aucun
1
9
fév.
2010
Bonjour,

J'ai deux versions de mon logiciel et je cherche à obtenir le taux de similitude entre ces deux versions.

Cette information est là plus à titre d'amusement. Cela fait plus d'un an que je modifie le logiciel (par rapport à la dernière version sortie) et j'ai l'impression d'avoir réécris quasiment l'intégralité de l'application et j'aurais voulu vérifier ce point par des chiffres.

Apparemment il existe la distance de Levenshtein : http://fr.wikipedia.org/wiki/Distance_de_Levenshtein pour comparer deux chaines de caractères.
Si j'ai bien compris :
(le nombre de caractère - la distance) / le nombre de caractère
devrait donner le taux de similitude.

Mais ici, mon but est de comparer deux dossier (où les fichiers on pu être renommé, les dossiers on pu être renommé, ...) et un renommage de fichier ne constitue pas une réécriture complète du fichier.

Bref, connaissez-vous un logiciel qui me permettrait d'obtenir le taux de similitude (ou de différence) entre deux dossier (ou entre deux version d'un logiciel). Si cela peut aider le logiciel est géré sur SubVersion.

Comme cela je pourrais sortir une annonce du style, voici une nouvelle version qui est si tardif car 95% du logiciel a été réécrite (en sachant derrière si c'est vrai ou uniquement un impression).

Merci d'avance
  • # diif

    Posté par . Évalué à 3.

    un diff recursive te dira ce que a été changé

    ensuite tu comptes les changements dans le diff
    le nombre de + (ajout)
    le nombre de - (retrait)
    divisé par le total de ligne de code
    • [^] # Re: diif

      Posté par (page perso) . Évalué à 1.

      Le problème de cette méthode c'est qu'elle ne prend pas en compte le changement de nom d'un dossier (Au pire tu considère que tous les fichiers on été modifié alors que tu as juste renommé le dossier).
      • [^] # Re: diif

        Posté par . Évalué à 1.

        et puisque tu utilises SVN

        tu as fait un man svn ?
        je ne crois pas, car sinon tu aurais vu une commande qui t'interesse...
        svn diff

        par exemple :
        svn diff -r 3000:3500

        qui t'indiquerait les changements entre le commit 3000 et 3500

        de la tu dois pouvoir compter les changements et faire une division par rapport à la taille totale du projet.

        plus d'infgos dans le SVN Book
        http://svnbook.red-bean.com/en/1.5/svn-book.html

        et plus particulierement
        http://svnbook.red-bean.com/en/1.5/svn-book.html#svn.ref.svn(...)
        • [^] # Re: diif

          Posté par (page perso) . Évalué à 4.

          Non : je viens de vérifier, si un fichier a été renommé dans la révision 106, alors avec svn diff -r 105:107 je vois un fichier avec l'ancien nom supprimé, et un fichier avec le nouveau nom ajouté. Avec --no-diff-deleted, je vois uniquement un ajout de fichier (on va dire que ça divise par deux l'erreur commise, mais si il y a eu de vraies suppressions à prendre en compte, ça va les zapper :-/).
          • [^] # Re: diif

            Posté par (page perso) . Évalué à 1.

            J'ai le même résultat sur les fichiers renommé, ou même les dossiers renommé.
  • # Utilise gzip, luke !

    Posté par . Évalué à 4.

    Cet article, que j'avais lu dans un numéro de Pour La Science de il y a longtemps :

    http://interstices.info/jcms/c_21828/classer-musiques-langue(...)

    t'explique l'utilisation d'un compresseur pour détecter plus ou moins automatiquement les séquences similaires. Regarde plus précisément le premier paragraphe "Compression de données" après l'intro.

    Pour résumer : tu as un répertoire A contenant la version 1 et B contenant la version 2.
    soit la fonction c(Rep) = len(gzip(tar(Rep) qui te donne la longueur du fichier Rep.tar.gz (ou bzip2, si tu préfères).

    alors on définit la distance de similitude entre A et B :
    d(A, B) = 1 – {c(A) + c(B) – c(AB)} / min{c(A),c(B)}

    elle vaut 0 quand A = B et 1 quand A est complètement différent de B.

    J'avais déjà testé cette méthode fut un temps et elle m'avait donné de bons résultats...

    Mes deux euros...
    • [^] # Re: Utilise gzip, luke !

      Posté par . Évalué à 2.

      Pour c(AB), il faut bien sûr comprendre la longueur de la compression des deux répertoires concaténés, et donc dans notre cas :

      c(AB) = len(gzip(cat{tar(A),tar(B)}))

      rapide efficace et pas cher
      • [^] # Re: Utilise gzip, luke !

        Posté par (page perso) . Évalué à 1.

        Je doute de l'efficacité :'(

        Je viens de faire :
        C(A)
        C(B)
        C(AB)
        et
        C(AA)

        TAR(AA) correspond bien à environ TAR(A) + TAR(A)
        TAR(AB) correspond bien à environ TAR(A) + TAR(B)

        Une fois compressé, C(AB) >>> C(A) et C(AA) >>> C(A)

        En faite le calcul me donne d = 0,97 (soit proche de 1) pour C(AB) et plus pour C(AA).

        Le plus étrange c'est ceci (bzip2 ou gzip ne sont peut-être pas assez efficace, comme on en parle ci-dessous) :

        tar -c trunk/* > trunk.tar
        tar -c v0.8.1/* > v0.8.1.tar
        tar -c trunk/* v0.8.1/* > common.tar
        tar -c trunk/* trunk/* > common2.tar

        puis je bzip2 chaque fichier :

        1043899 fév 10 15:31 common2.tar.bz2
        975668 fév 10 15:26 common.tar.bz2
        521470 fév 10 15:26 trunk.tar.bz2
        465741 fév 10 15:25 v0.8.1.tar.bz2

        Le fichier common2 est plus gros que common pourtant tout les fichiers sont en double ... alors que common contient A et B

        PS : Le TAR d'un dossier (comme par exemple trunk) non compressé fait 4,3 Mo
        • [^] # Re: Utilise gzip, luke !

          Posté par (page perso) . Évalué à 2.

          Par contre l'utilisation de p7zip change la donne :

          468800 fév 10 15:52 common2.tar.7z
          547562 fév 10 15:53 common.tar.7z
          468164 fév 10 15:53 trunk.tar.7z
          413518 fév 10 15:53 v0.8.1.tar.7z

          Soit donc

          d(A,A) = 0.001
          d(A,B) = 0.192

          Si je comprend bien mes programmes on 19% de différence (ou autrement, j'ai réécris 19% de mon application)
          • [^] # Re: Utilise gzip, luke !

            Posté par (page perso) . Évalué à 1.

            A priori, j'ai une asymptote à .7430750703
            Quand je prend deux programme complétement différent mais tous les deux écris en C++ et Qt, c'est le nombre que je trouve, et c'est le plus grand nombre que j'ai réussi à obtenir.

            Cela doit venir de la redondance des mots clé du language et de la spécificité à Qt (utilisation des QHash, ...)

            Est-ce que cela veut dire que je peux faire une règle de trois et ajuster mon pourcentage de 19% à 26% ? (de toute facon c'est approximatif).

            A moins que la courbe n'est vraiment pas linéaire (même pas entre 0.001 et 0.7430) et donc je ne peux pas vraiment estimer mon pourcentage de différence mais juste une distance (qui est moins parlant).
            • [^] # Re: Utilise gzip, luke !

              Posté par . Évalué à 1.

              Je me suis trompé dans la formule : il faut diviser par max{c(A),c(B)} et non pas par le min...

              donc dans ton cas ça donne d(A,B) = 0.286
              recommence tes autres tests pour voir si tu as une nouvelle "asymptote" pour deux programmes c++/qt quelconques...

              sinon, effectivement, d(A,B) vaut 1 pour deux flux A et B totalement décorrélés.

              Là, A et B ont une prédominance de [a-zA-Z], de blancs, tabulation, fins de ligne et signes de ponctuation et autres opérateurs. Et en plus, on retrouve forcément les mots-clés du c++ et les définitions de qt, de la STL, et de la libc.

              Forcément, ils ont une corrélation intrinsèque.

              Après, te dire si la courbe est linéaire, je n'en sais fouchtre rien... tout ça ne reste qu'une estimation des distances dans une certaine unité (restons bien vague). Au moins ça te donne un outil, à toi de voir si ça t'es utile ou pas.
    • [^] # Re: Utilise gzip, luke !

      Posté par (page perso) . Évalué à 3.

      Si les séquences communes (typiquement, une fonction déplacée d'un fichier à l'autre) sont "loin" les unes des autres (>32ko, d'après [1]), elles ne seront pas détectées, si ? Et donc, cela veut dire que si le .tar des sources fait >16ko, on risque de passer à côté de recoupements... Or, 16ko de sources, ce n'est pas grand'chose...

      Ceci dit, c'est éblouissant de simplicité et d'élégance :-)

      [1] http://www.gzip.org/algorithm.txt
      • [^] # Re: Utilise gzip, luke !

        Posté par . Évalué à 1.

        ben dans ce cas, utilise bzip2, qui utilise des blocs d'un maximum de 900 ko. C'est pas encore la taille des sources du noyau mais on s'en approche.

        http://en.wikipedia.org/wiki/Bzip2

        sinon, effectivement l'intérêt de la méthode c'est qu'elle fait deux lignes de code et qu'elle approxime assez bien une véritable distance pour peu que l'algorithme de compression soit efficace sur les objets traités (pour un répertoire de sources, va faire ton marché sur http://mattmahoney.net/dc/text.html )
  • # git

    Posté par (page perso) . Évalué à 3.

    Je viens de faire un commit sous git, et l'outil m'a donné la ligne suivante :

    2 files changed, 380 insertions(+), 419 deletions(-)
    rewrite file.c (62%)


    J'ai repensé à ce thread. Je ne sais pas d'où git sors ce chiffre, mais c'est peut etre interressant de creuser dans cette direction.
    En tout cas, une solution serait d'utiliser git :)

Suivre le flux des commentaires

Note : les commentaires appartiennent à ceux qui les ont postés. Nous n'en sommes pas responsables.