[PHP] Coefficient de Dice

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.