[Algorithme] Evaluer la similarité entre 2 chaines

comtois · Message par **comtois** » dim. 01/mars/2009 10:40

J'ai repris ce code sur developpez.com.
Pour faire un quizz tolérant sur l'ortho , ça peut être utile

[EDIT]
Je viens de faire une recherche , l'algo de Levenshtein était déjà sur le forum anglais.

;http://www.developpez.net/forums/d644186/dotnet/contribuez/algorithme-evaluer-similarite-entre-2-chaines/

Procedure Min(a, b, c)
  Min = a
  If b < Min 
    Min = b
  EndIf
  If c < Min
    Min = c
  EndIf 
  ProcedureReturn Min    
EndProcedure

Procedure Max(a, b)
  If a>b
    ProcedureReturn a
  Else
    ProcedureReturn b
  EndIf    
EndProcedure
 
; <summary>
; Computes the Levenshtein distance between 2 strings
; Based on the algorithm described here :
; http://en.wikipedia.org/wiki/Levenshtein_distance
; </summary>
; <param name="a">first string To compare</param>
; <param name="b">second string To compare</param>
; <param name="caseSensitive">true If Case should be considered, false otherwise</param>
; <returns>the Levenshtein distance between the 2 strings</returns>
Procedure ComputeDistance(a.s, b.s, caseSensitive)
  If caseSensitive=0
    a = LCase(a)
    b = LCase(b)
  EndIf 

  m.i = Len(a)
  n.i = Len(b)
  Dim  d(m, n)

  For i = 0 To m
    d(i, 0) = i
  Next i    
  For i = 0 To n
    d(0, i) = i
  Next i    

  For i = 1 To m
    For j = 1 To n
      If Mid(a,i-1, 1) = Mid(b,j-1,1)
        cost = 0
      Else
        cost = 1
      EndIf    
      d(i, j) = Min(d(i - 1, j) + 1, d(i, j - 1) + 1, d(i - 1, j - 1) + cost)
    Next j
  Next i      
  ProcedureReturn d(m, n)
EndProcedure

 
; <summary>
; Computes the correlation coefficient between 2 strings, based on the Levenshtein distance
; </summary>
; <param name="a">first string To compare</param>
; <param name="b">second string To compare</param>
; <param name="caseSensitive">true If Case should be considered, false otherwise</param>
; <returns>The correlation coefficient between the 2 strings. This value can range from 0 (completely different strings) To 1 (identical strings)</returns>
Procedure.d ComputeCorrelation(a.s, b.s, caseSensitive)
  distance = ComputeDistance(a, b, caseSensitive)
  longest = Max(Len(a), Len(b))
  ProcedureReturn  1.0 - distance / longest
EndProcedure

a.s="Purebasic c'est super cool"
b.s="purebasic c super coul"

threshold.d = 0.8
coef.d = ComputeCorrelation(a, b, 0)
If coef > threshold
  MessageRequester("","Bonne réponse !")
Else
  MessageRequester("","Mauvaise réponse !")
EndIf

Kwai chang caine · Message par **Kwai chang caine** » dim. 01/mars/2009 15:28

Merci COMTOIS de ce code tres interessant.

Comme dans mon cas, on ne change pas une equipe qui perd, est il encore besoin de te dire que j'ai pas trop compris comment ça marche

J'ai vu que quand j'enleve une lettre de la phrase, ton super algorythme du Lichtenstein (Joli pays d'ailleurs

), il a tout vu

Mais pourquoi, il laisse passer le fait que le "est" est absent ??

Il travaille sur la comparaison de la phonetique ???

comtois · Message par **comtois** » dim. 01/mars/2009 19:04

Tout est expliqué dans le détail ici

http://fr.wikipedia.org/wiki/Distance_de_Levenshtein

Kwai chang caine · Message par **Kwai chang caine** » dim. 01/mars/2009 19:21

Et bah dis donc

J'te savais drolement intelligent....mais alors la si tu sais tout ça ....

Merci pour le lien

Ollivier · Message par **Ollivier** » dim. 01/mars/2009 22:56

Intéressante cette méthode. Corriger les fautes pour obtenir des ordres formels n'est pas une mince affaire. Le gros problème c'est qu'aucun algo ne peut parvenir à l'exactitude sans une foule de paramètres dont une poignée de 1, 2 voire 3 paramètres, seraient erronés.

Par exemple, un chien peut faire des dicernement d'ordre assez complexes. Seulement, il est limité à des ordres à deux syllabes. Ce qui donne une idée de la complexité de l'algo à créer!

@Kcc

Petite modif...

Code : Tout sélectionner

;http://www.developpez.net/forums/d644186/dotnet/contribuez/algorithme-evaluer-similarite-entre-2-chaines/ 

Procedure Min(a, b, c) 
  Min = a 
  If b < Min 
    Min = b 
  EndIf 
  If c < Min 
    Min = c 
  EndIf 
  ProcedureReturn Min    
EndProcedure 

Procedure Max(a, b) 
  If a>b 
    ProcedureReturn a 
  Else 
    ProcedureReturn b 
  EndIf    
EndProcedure 
  
; <summary> 
; Computes the Levenshtein distance between 2 strings 
; Based on the algorithm described here : 
; http://en.wikipedia.org/wiki/Levenshtein_distance 
; </summary> 
; <param name="a">first string To compare</param> 
; <param name="b">second string To compare</param> 
; <param name="caseSensitive">true If Case should be considered, false otherwise</param> 
; <returns>the Levenshtein distance between the 2 strings</returns> 
Procedure ComputeDistance(a.s, b.s, caseSensitive) 
  If caseSensitive=0 
    a = LCase(a) 
    b = LCase(b) 
  EndIf 

  m.i = Len(a) 
  n.i = Len(b) 
  Dim  d(m, n) 

  For i = 0 To m 
    d(i, 0) = i 
  Next i    
  For i = 0 To n 
    d(0, i) = i 
  Next i    

  For i = 1 To m 
    For j = 1 To n 
      If Mid(a,i-1, 1) = Mid(b,j-1,1) 
        cost = 0 
      Else 
        cost = 1 
      EndIf    
      d(i, j) = Min(d(i - 1, j) + 1, d(i, j - 1) + 1, d(i - 1, j - 1) + cost) 
    Next j 
  Next i      
  ProcedureReturn d(m, n) 
EndProcedure 

  
; <summary> 
; Computes the correlation coefficient between 2 strings, based on the Levenshtein distance 
; </summary> 
; <param name="a">first string To compare</param> 
; <param name="b">second string To compare</param> 
; <param name="caseSensitive">true If Case should be considered, false otherwise</param> 
; <returns>The correlation coefficient between the 2 strings. This value can range from 0 (completely different strings) To 1 (identical strings)</returns> 
Procedure.d ComputeCorrelation(a.s, b.s, caseSensitive) 
  distance = ComputeDistance(a, b, caseSensitive) 
  longest = Max(Len(a), Len(b)) 
  ProcedureReturn  1.0 - distance / longest 
EndProcedure 

a.s="Levenshtein" 
b.s="Lichtenstein" 

threshold.d = 0.8 
coef.d = ComputeCorrelation(a, b, 0) 
Msg.S = a + " = ? = " + b + Chr(13)
Msg + Chr(13)
If coef > threshold
  MessageRequester(StrD(Coef),Msg+"Bonne réponse !") 
Else 
  MessageRequester(StrD(Coef),Msg+"Mauvaise réponse !") 
EndIf

Kwai chang caine · Message par **Kwai chang caine** » lun. 02/mars/2009 9:51

Je sais mon canard ....c'etait pour la rigolage

GeBonet · Message par **GeBonet** » lun. 02/mars/2009 10:42

Ben oui, ces algo, sont intéressants... Et à creuser !
Mais dans notre cas... Remplacez un peu

Code : Tout sélectionner

; Pemière chaine :
a.s="Purebasic c'est super cool"
; Seconde chaine :
b.s="purebasic c super coul"

par

Code : Tout sélectionner

; Première chaine :
a.s="Purebasic c'est super cool"
; Seconde chaine :
b.s="purebasic c super con"

ou "purebasic c'est super nul"...

Il est pas trop contrariant... L'algo !
Et là, tout le monde sera d'accord il ne peut pas laisser passer des affirmations pareilles, non ?

Donc c'est évidement à creuser...
Bon, comme dis Olivier, corriger des fôtes c'est pas facile...

: