Forum général.cherche-logiciel Trouver des fichiers à nom similaires

• # Calcul de distance

  Posté par jigso le 04 juin 2008 à 11:34. Évalué à 5.

  

  http://fr.wikipedia.org/wiki/Distance_de_Levenshtein
  
  Par exemple entre Attila.doc et Atila.doc, la distance est de 1
  entre "mon projet.pdf" ou "projet.pdf", la distance est 4.
  
  Donc en calculant toutes les distances, et en fixant un seuil il est possible d'avoir un liste de nom probablement proches. Par contre ça ne marche pas à tous les coups :
  "Beethoven - Concerto n°1.mp3" et "Beethoven - Concerto no.1 en la mineur.mp3" => ~15 (à la louche).
  Essaye peut-être en divisant la distance par la longueur de la chaine, mais bon est-ce que 15/44 = 36% signifie que les chaines sont proches ou pas ? si on augmente le seuil, on risque d'avoir de faux positifs...
  Peut-être qu'en pondérant différement les ajouts dans le calcul de la distance, on peut avoir qqe chose de plus efficace pour ces cas.

  • [^] # Re: Calcul de distance

    Posté par jigso le 04 juin 2008 à 11:51. Évalué à 4.

    

    Et donc pour répondre à la question, je ne connais pas d'outil tout fait. Par contre il existe en Perl des modules pour calculer cette distance.
    Il suffit d'enrober tout ça. Par ex pour avoir la liste des noms de fichiers qui ont la distance la plus courte :
    
    
/usr/bin/perl
use strict;
use Text::Levenshtein qw/distance/;
use List::Util qw/min/;
my $f = shift or die "missing filename\n";
opendir my $dir , '.';
my @files = readdir $dir;
closedir $dir;
my %d;
push @{$d{distance($f, $_)}}, $_ foreach @files;
print map { "$_\n" } @{$d{min keys %d}};


  • [^] # Re: Calcul de distance

    Posté par 태 (site web personnel) le 04 juin 2008 à 18:49. Évalué à 5.

    

    La distance de Levenshtein, si elle est en théorie parfaite ne répond pas du tout à la question, je pense.
    
    Attila et Atila se ressemblent parce qu'ils se prononcent de la même façon, ce qui me fait plutôt penser à une distinction phonétique, du style soundex ou metaphone qui donnent des classes d'équivalence, qui ont également des modules perl.
    
    Pour les autres exemples, il y a d'une part des caractères équivalents ('_' et ' ', '°' et 'o') et d'autres part des mots peu informatifs (mon, en, la), mais mineur n'en est pas un...
    
    Enfin, je serais intéressé par quels sont les "algorithmes pour faire ça" auxquels pense LeBonobo Bono.

    • [^] # Re: Calcul de distance

      Posté par jigso le 05 juin 2008 à 11:39. Évalué à 1.

      

      Il est toujours possible de normaliser les chaines avant, puis de faire un calcul de distance de levenshtein. Ici la question demandait juste une recherche de mots "similaires" : effectivement il faut peut-être affiner la définition de "similaire".
      Mais comme en exemple il y a "Beethoven - Concerto n°1.mp3" et "Beethoven - Concerto no.1 en la mineur.mp3", je pense que la définition est encore plus large qu'une simple distinction phonétique.

      • [^] # Re: Calcul de distance

        Posté par LeBonobo Bono le 05 juin 2008 à 15:15. Évalué à 1.

        

        Merci pour vos réponses !
        
        Le module Perl est intéressant, ça évite de réécrire l'algorithme.
        Concernant les algorithmes j'avais effectivement trouvé la distance de Levenstein, soundex et metaphone. En utilisant un de ces algorithmes après suppression de caractères inutiles je pense que l'on peut obtenir des résultats intéressants. Du moins qui donnent une liste triée qui permette de finir le tri à la main.
        
        Des cas encore plus durs à résoudre sont "Klavierkonzert Nr. 5" et "Concerto n°5". Et l'impossible : un film avec son titre français et son titre anglais.

      • [^] # Re: Calcul de distance

        Posté par Mildred (site web personnel) le 05 juin 2008 à 17:51. Évalué à 2.

        

        A mon avis, la normalisation est nécessaire avant. Du style convertir tous les caractères qui ne sont pas des lettres en espaces. Peut être aussi, convertir les caractères accentués (au sens UTF-8 je suppose) en caractères non accentués, les majuscules en minuscule.
        
        Et je pense que lors du calcul de la distance de Levinstein, il faudrait aussi compter les ajouts de plusieurs caractères à la suite comme ayant un coût de 1 seulement. Voire un coût nul si on rajoute un mot complet.
        
        Et ça doit pouvoir donner des résultats intéressants.
        Ce serait bien que ce soit intégré à find ou grep aussi. Ou quelque chose qui puisse lire du find [-print0] et qui puisse être compris par xargs [-0]. Qu'on puisse faire des lignes de commande du style:
        
        find Documents -print0 | similar -z "Mon document.pdf"
find Documents -print0 | similar -zZ "Mon document.txt" | xargs -0 grep 'pattern'
        
        (Bien entandu dans ces cas là, il serait intelligent de ne prendre en compte que le basename.)
        
        Si quelqu'un fait quelque chose, et qu'il arrive à quelque chose, se serait sympa de nous tenir au courant (astuce ou journal). Perso, je suis en plein partiels, donc pas maintenant :)

Suivre le flux des commentaires

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