Discussion :

[arkandias]

Mon problème est tout simple :

J'ai deux chaines str1 et str2 composées de 0 et de 1, de tailles pas forcément égales.

Par exemple :

str1 = 101101000;
str2 = 1010;

Je veux connaître la similarité entre ces deux chaines (c'est pour du PHP au passage).

J'ai entendu parler de l'algorithme de Levenshtein mais je ne le trouve pas très efficace dans ce cas...

Je suis un peu perdu en fait, quelqu'un saurait-il me conseiller ? Merci

[PRomu@ld]

En fait, tout dépend de ce que tu appelles similarité. Tu as par exemple la distance d'édition qui comptabilise le nombre de changements à effectuer pour passer d'une chaîne à une autre (en nombre d'opérations)

[arkandias]

Pour être plus exact, la première chaine str1 est fixe : c'est celle du serveur, elle est de 6 chiffres maximal.

La deuxième str2 est variable, c'est celle que le client envoie, elle est d'un nombre de chiffres indéterminé.

Je veux comparer str2 à str1, et de leur degré de ressemblance dépendra la suite de mon programme...

Que dois-je donc utiliser ?

[Jedai]

On recommence : qu'appelles-tu "degré de ressemblance" ? Il faut lui donner une définition formelle, sinon tu ne pourras rien programmer. On t'as déjà proposé la distance de Levenshtein (distance d'édition) par exemple, il y a d'autres type de distance, mais il faut faire un choix.

--
Jedaï

[arkandias]

Je voudrais celle qui donne le meilleur résultat

Admettons, quels sont les algorithmes de la distance de Levenstein et de la distance d'édition ?

Je vais les tester pour voir ce qui me va le mieux

[Jedai]

Je voudrais celle qui donne le meilleur résultat

Ca ne veut rien dire, tout dépend de ce que tu appelles "similaire".

Fait un effort et cherche "Distance de Levenshtein" sur Google, un zeste d'indépendance ne peut pas faire de mal à un programmeur...

Tu peux aussi chercher "Damerau-Levenshtein" pour un raffinement.

--
Jedaï

[PRomu@ld]

En fait, je viens de regarder et la distance de Levenshtein et la distance d'éditions sont en fait les mêmes distances, je ne connaissais pas le nom de Levenshtein.

L'algo est relativement simple.

Le tout c'est de construire une matrice M(n,m) (où m et n sont les longueurs de tes chaînes). A chacune des cases i,j tu as la distance entre le mot composé des i premiers caractères de s1 et le mot composé des j premiers caractères de s2. La distance entre les deux mots est donc la case M(n,m).

Pour remplir les cases de ta matrice, il faut utiliser la formule suivante :

M(i,j) = min( M(i-1,j) + 1 , M(i,j-1) + 1 , M(i-1,j-1) + d(s1(i),s2(j)) )

où d( s1(i) , s2(j) ) te donne la distance entre la i ème lettre de s1 et la j-ème lettre de s2. Ca vaut 0 si s1(i) = s2(j) 1 sinon.

Il ne reste plus qu'à faire attention aux initialisations : M(0,0) = 0 , M(i,0) = i et M(0,j) = 1.

Il y a moyen de ne pas stocker toute la matrice mais tu verras si tu en as besoin ou pas.

[arkandias]

En fait j'ai fait comme me l'a conseillé Jedai : j'ai cherché sur Google et j'ai trouvé l'algo en PHP directement sur Wikipédia

Je l'ai mis sur mon programme et ca marche pas trop mal, donc je vais utiliser ca !

Merci beaucoup pour votre aide en tout cas