Discussion :

[Avatar36]

Bonjour,

Je sais pas si je suis au bon endroit pour poser la question, mais dans le doute je poste ici.

Je cherche à faire une fonction qui me renvoie un pourcentage de similarité entre plusieurs chaînes (des titres de films). Je dispose d'un nom de film tiré du nom d'un fichier (donc peu fiable) et d'une liste de titres de films dans laquelle je suis plus ou moins sûr que le titre du film est présent. Je cherche donc à faire une fonction qui me donnera un pourcentage de similitude entre la chaine de base et chaque chaine de la liste.
J'ai déjà regardé la distance de Levenstein mais bien sûr, les titres de films peuvent contenir plusieurs mots et sur wikipedia il est conseillé d'utiliser autre chose comme l'algorithme de Jaccard. Mais là, pas d'exemples, rien sur cet algorithme.
Ma question est: est-ce que la distance de Levenstein donne quand même des résultats assez satisfaisants si il y a plusieurs mots? Existe-t-il des exemple d'autres algorithme plus adaptés à ce que je recherche?
Merci de votre aide.

Cordialement

[Avatar36]

J'ai trouvé ce lien qui montre comment calculer la distance de Jaccard à partir de texte. Mais j'avoue que la méthode à mettre en oeuvre me plaît moyennement.
Je vais plutôt appliquer la distance de rameau Levenstein et l'adapter pour s'occuper de plusieurs mots:
1) compter le nombre de mots i et j des deux chaînes
2) comparer les chaînes avec 1 mots chacune
3) additionner les distances (là il faudra peut-être que je trouve une meilleure solution, comme une moyenne ou un écart type ou les deux car si il y a beaucoup de mots en plus dans une chaîne, la distance va croitre alors que ce n'est pas le but recherché. En effet, on peut oublier des morceaux du titre en écrivant le film)
ça devrait me donner un indice de la proximité des chaînes. Qu'est-ce que vous en pensez?

[tbc92]

J'ai trouvé ce lien qui montre comment calculer la distance de Jaccard à partir de texte. Mais j'avoue que la méthode à mettre en oeuvre me plaît moyennement.
Je vais plutôt appliquer la distance de rameau Levenstein et l'adapter pour s'occuper de plusieurs mots:
1) compter le nombre de mots i et j des deux chaînes
2) comparer les chaînes avec 1 mots chacune
3) additionner les distances (là il faudra peut-être que je trouve une meilleure solution, comme une moyenne ou un écart type ou les deux car si il y a beaucoup de mots en plus dans une chaîne, la distance va croitre alors que ce n'est pas le but recherché. En effet, on peut oublier des morceaux du titre en écrivant le film)
ça devrait me donner un indice de la proximité des chaînes. Qu'est-ce que vous en pensez?

Ce que je ferais :
1) Normaliser les 2 chaines. Ce que j'appelle normaliser, c'est enlever les mots superflus ( les articles, les mots de 1 lettre, les mots comme ET ou DE ...)
2) 2ème étape de la normalisation : Idem, s'il y a des chiffres ou des groupes des chiffres dans un des titres, traiter ces chiffres (Pas tout simple, puisqu'il faut voir que 40 ou quarante, c'est pareil ... )

2) Appliquer la distance de Levenstein sur ces 2 chaines normalisées.
Et je traiterais chaque titre comme 1 mot.
Une fois qu'on a fait cette normalisation, ça ne pose plus de problème.

[yahiko]

L'algo de base qui est implémenté dans les SGBD c'est le soundex ou sa variante le metaphone.

[Avatar36]

@yahiko: je vais voir si ça correspond à ce que je cherche. Mais de ce que j'ai vu, ces fonctions renvoient des strings (mélanges de lettres et de chiffres). Du coup comment on fait pour savoir si les chaînes sont proches ou pas? dans le cas d'une distance, on a un pourcentage mais là....?

@tbc92: oui c'est exactement ce que je pensais faire. Par contre, imaginons que dans un cas j'ai "indiana jones" et "jones indiana" (exemple au pif, c'est pour souligner le problème), dans ce cas la distance vaudrait 0 ou est-ce qu'elle vaudrait un nombre non nul? Dans le cas où c'est non nul, j'avais dans l'idée de comparer les mots un à un, de remplir une espèce de matrice et de calculer un coefficient pondérant l'ordre des mots. Par contre le calcul je n'ai aucune idée de comment m'y prendre pour le moment

[yahiko]

Une fois que tu as encodé tes chaînes avec le Soundex, tu peux appliquer une simple distance de Levensthein entre tes deux chaînes.