Le coefficient de Dice est une mesure de similarité (Article wikipedia: Dice's coefficient). Ce coefficient est utilisé en statistique pour déterminer la similarité entre deux échantillons. J'avais besoin d'utiliser ce coefficient pour l'un de mes projets, mais n'étant pas disponible de bases avec PHP, j'ai du créer une fonction que je vous livre ici.
Présentation du coefficient de Dice
Le coefficient est toujours compris entre 0 et 1. Il se définit comme le double de l'intersection de deux lots (échantillons de valeurs) divisé par l'union de ces deux lots. La formule ci-dessous résume la méthode de calcul:
Équation coefficient de Dice
Dans cette formule, X et Y sont des lots. Pour calculer le coefficient de Dice de deux chaines, il est possible de définir X et Y comme l'ensemble des bigrammes de chacune des chaines respectives. Un bigramme étant la réunion de deux lettres dans un mot.
Exemple d'utilisation
Prenons l'exemple de deux chaines "hello" et "allo", auquel ont souhaiterais déterminer le coefficient de Dice. Les bigrammes respectifs sont {he,el,ll,lo} (soit 4 bigrammes) et {al,ll,lo} (soit 3 bigrammes). L'intersection des deux lots sont les valeurs {ll,lo}. Ainsi, l'équation devient:
s = 2*2 /(4+3) = 4/7 = 0,57
Grâce à cette valeur de 0,57 il est possible de déterminer que ces deux mots sont à peu près semblables. Plus la valeur est proche de 1 et plus les chaines sont similaires. Si le résultat est égal à 1, cela signifie que les deux chaines sont identiques.
Code PHP du coefficient de Dice
Le code ci-dessous présente la fonction qui permet de calculer le coefficient de Dice avec PHP.
<?php // Calcul du coefficient de Dice // Inspiration: http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Dice%27s_coefficient // Licence: Libre de droit function dice($str1='', $str2='') { $str1_length = strlen($str1); $str2_length = strlen($str2); // Length of the string must not be equal to zero if ( ($str1_length==0) OR ($str2_length==0) ) return 0; $ar1 = array(); $ar2 = array(); $intersection = 0; // find the pair of characters for ($i=0 ; $i<($str1_length-1) ; $i++) $ar1[] = substr($str1, $i, 2); for ($i=0 ; $i<($str2_length-1) ; $i++) $ar2[] = substr($str2, $i, 2); // find the intersection between the two sets foreach ($ar1 as $pair1) { foreach ($ar2 as $pair2) { if ($pair1 == $pair2) $intersection++; } } $count_set = count($ar1) + count($ar2); $dice = (2 * $intersection) / $count_set; return $dice; } echo dice('', 'cdefghi').'<br />'; // test with a null string echo dice('abcdefg', '').'<br />'; // test with a null string echo dice('abcdefg', 'cdefghi').'<br />'; echo dice('night', 'nacht').'<br />'; ?>
La fin du script présente des exemples pour utiliser cette fonction. Avant de terminer, je tiens à préciser que je me suis inspiré d'un code en C++ provenant d'un wiki anglais: "Implementation of Dice's algorithm". Ce wiki présente l'implémentation du coefficient de Dice en C++, Java, Python et Ruby (mais pas en PHP, d'où l'intérêt du code que je viens de vous présenter). Faites-en bon usage.
Le coefficient de Dice est une mesure de similarité (Article wikipedia: Dice's coefficient). Ce coefficient est utilisé en statistique pour déterminer la similarité entre deux échantillons. J'avais besoin d'utiliser ce coefficient pour l'un de mes projets, mais n'étant pas disponible de bases avec PHP, j'ai du créer une fonction que je vous livre ici.
Présentation du coefficient de Dice
Le coefficient est toujours compris entre 0 et 1. Il se définit comme le double de l'intersection de deux lots (échantillons de valeurs) divisé par l'union de ces deux lots. La formule ci-dessous résume la méthode de calcul:
Équation coefficient de Dice
Dans cette formule, X et Y sont des lots. Pour calculer le coefficient de Dice de deux chaines, il est possible de définir X et Y comme l'ensemble des bigrammes de chacune des chaines respectives. Un bigramme étant la réunion de deux lettres dans un mot.
Exemple d'utilisation
Prenons l'exemple de deux chaines "hello" et "allo", auquel ont souhaiterais déterminer le coefficient de Dice. Les bigrammes respectifs sont {he,el,ll,lo} (soit 4 bigrammes) et {al,ll,lo} (soit 3 bigrammes). L'intersection des deux lots sont les valeurs {ll,lo}. Ainsi, l'équation deviens:
s = 2*2 /(4+3) = 4/7 = 0,57
Grâce à cette valeur de 0,57 il est possible de déterminer que ces deux mots sont à peu près semblable. Plus la valeur est proche de 1 et plus les chaines sont similaire. Si le résultat est égal à 1, cela signifie que les deux chaines sont identiques.
Code PHP du coefficient de Dice
dg
01.<span style="color: #ff0000;"><?php</span>02.<span style="color: #008000;">// Calcul du coefficient de Dice03.// Inspiration: http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Dice%27s_coefficient04.// Licence: Libre de droit</span>05. 06.<span style="color: #0000ff;">function</span> dice(<span style="color: #000080;">$str1</span>='', <span style="color: #000080;">$str2</span>='')07.{08.<span style="color: #000080;">$str1_length</span> = strlen(<span style="color: #000080;">$str1</span>);09.<span style="color: #000080;">$str2_length</span> = strlen(<span style="color: #000080;">$str2</span>);10. 11.<span style="color: #008000;">// Length of the string must not be equal to zero</span>12.<span style="color: #0000ff;">if</span> ( (<span style="color: #000080;">$str1_length</span>==0) <span style="color: #0000ff;">OR</span> (<span style="color: #000080;">$str2_length</span>==0) )13.<span style="color: #0000ff;">return</span> 0;14. 15.<span style="color: #000080;">$ar1</span> = <span style="color: #0000ff;">array</span>();16.<span style="color: #000080;">$ar2</span> = <span style="color: #0000ff;">array</span>();17.<span style="color: #000080;">$intersection</span> = 0;18. 19.<span style="color: #008000;">// find the pair of characters</span>20.<span style="color: #0000ff;">for</span> (<span style="color: #000080;">$i</span>=0 ; <span style="color: #000080;">$i</span><(<span style="color: #000080;">$str1_length</span>-1) ; <span style="color: #000080;">$i</span>++)21.<span style="color: #000080;">$ar1</span>[] = substr($str1, $i, 2);22. 23.<span style="color: #0000ff;">for</span> (<span style="color: #000080;">$i</span>=0 ; <span style="color: #000080;">$i</span><(<span style="color: #000080;">$str2_length</span>-1) ; <span style="color: #000080;">$i</span>++)24.<span style="color: #000080;">$ar2</span>[] = substr($str2, $i, 2);25. 26.<span style="color: #008000;">// find the intersection between the two sets</span>27.<span style="color: #0000ff;">foreach </span>(<span style="color: #000080;">$ar1</span> as <span style="color: #000080;">$pair1</span>) {28.<span style="color: #0000ff;">foreach </span>(<span style="color: #000080;">$ar2</span> as <span style="color: #000080;">$pair2</span>) {29.<span style="color: #0000ff;">if </span>(<span style="color: #000080;">$pair1</span> == <span style="color: #000080;">$pair2</span>)30.$intersection++;31.}32.}33. 34.$count_set = count($ar1) + count($ar2);35.$dice = (2 * $intersection) / $count_set;36.<span style="color: #0000ff;">return </span>$dice;37.}38. 39.<span style="color: #0000ff;">echo </span>dice('', 'cdefghi').'<br />'; <span style="color: #008000;">// test avec une chaîne nulle</span>40.<span style="color: #0000ff;">echo </span>dice('abcdefg', '').'<br />'; <span style="color: #008000;">// test avec une chaîne nulle</span>41.<span style="color: #0000ff;">echo </span>dice('abcdefg', 'cdefghi').'<br />';42.<span style="color: #0000ff;">echo </span>dice('night', 'nacht').'<br />';43.<span style="color: #ff0000;">?></span>Inspiration:
http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Dice%27s_coefficient
