Similarité et Duplicate content : L'indice de Jaccard

Un algorithme qui permet de détecter la similarité entre deux textes mais certainement pas le duplicate content

indice de jaccard, indice jaccard, fonction jaccard, indice de similarite de jaccard, de similarite de jaccard, php de jaccard, similarite jaccard, similarite de mot, algorithme de jaccard, jaccard simhash, de l indice de similarite de jaccard, coefficient de jaccard, calcul de l indice de similarite de jaccard, de indice de similarite de jaccard, content calcul similarite

Date de publication : 2011-07-27 16:55:56

Depuis la modification de mon spinner de texte et suite à la lecture de l'article Algorithme de Simhash: Script PHP de calcul de similarité de @lemoussel j'ai étudié les différentes méthodes pour détecter la similarité entre deux textes.

Aujourd'hui je vais vous présenter un algorithme basé sur l'Indice de Jaccard.

L'indice de Jaccard : Principe

Le principe est un des plus simple et beaucoup de personnes utilisent cet indice sans le savoir pour la détection de duplicate. Prenez deux textes. Texte 1 :

Le moteur de recherche idéal doit comprendre exactement l'objet de la recherche pour fournir exactement les informations demandées

et Texte 2 :

Le moteur de recherche parfait doit comprendre le but de la recherche pour apporter les réponses exactes à la question

L'indice de Jaccard appliqué à un texte correspond aux rapport entre le nombre de mots présent dans les deux textes (l'intersection) et le nombre de mots des deux textes (l'union). L'indice de Jaccard est normalisé (entre 0 et 1), plus il est proche de 1 (ou 100%) plus les deux textes comparés sont similaires.

Normalisation de texte

Derrière le mot normalisation se cache une méthode simple : nettoyer les textes de tout qui pourrait nuire à la comparaison des textes. Pour cela j'utilise la fonction suivante qui supprime les accents, met les caractères en minuscule et remplace tout ce qui n'est pas une lettre par un espace.

Calcul des vecteurs d'occurence

Afin de se facilité la vie (et coder proprement) on va dans un premier utiliser une fonction qui calcule la fréquence des mots. Cette fonction retourne un tableau (vecteur) qui contient en index les mots et en valeur le nombre d’occurrence du mot (ou sa fréquence d'apparition).

Par exemple dans la Texte 1, le mot "recherche" apparait deux fois on lui affecte la valeur deux, le mot "moteur" apparait une seule fois on lui affecte la valeur 1 ...

Voici les deux tableaux pour les textes précédents :
Texte 1 :

array(16) {
  ["le"]=>
  int(1)
  ["moteur"]=>
  int(1)
  ["de"]=>
  int(2)
  ["recherche"]=>
  int(2)
  ["ideal"]=>
  int(1)
  ["doit"]=>
  int(1)
  ["comprendre"]=>
  int(1)
  ["exactement"]=>
  int(2)
  ["l"]=>
  int(1)
  ["objet"]=>
  int(1)
  ["la"]=>
  int(1)
  ["pour"]=>
  int(1)
  ["fournir"]=>
  int(1)
  ["les"]=>
  int(1)
  ["informations"]=>
  int(1)
  ["demandees"]=>
  int(1)
}

Texte 2 :

array(16) {
  ["le"]=>
  int(2)
  ["moteur"]=>
  int(1)
  ["de"]=>
  int(2)
  ["recherche"]=>
  int(2)
  ["parfait"]=>
  int(1)
  ["doit"]=>
  int(1)
  ["comprendre"]=>
  int(1)
  ["but"]=>
  int(1)
  ["la"]=>
  int(2)
  ["pour"]=>
  int(1)
  ["apporter"]=>
  int(1)
  ["les"]=>
  int(1)
  ["reponses"]=>
  int(1)
  ["exactes"]=>
  int(1)
  ["a"]=>
  int(1)
  ["question"]=>
  int(1)
}

Calcule de l'indice de Jaccard en php

Maintenant que vous avez toutes les fonctions de traitement base il ne manque plus que le code pour calculer l'indice de jaccard :

function jaccard($v1,$v2)
{
	/*Nombre d’éléments contenus dans les deux vecteurs (intersection)*/
	$i = 0;
	/*Nombre d’éléments total des deux vecteurs (union)*/
	$u = 0;
	/*On parcourt le premier vecteur d’occurrence*/
	foreach ($v1 as $w=>$c)
	{
		/*On ajoute le nombre d’occurrence du mot à l'union*/
		$u += $c;
		/*Si le mot est présent dans le second vecteur on ajoute le nombre d’occurrence à l'intersection*/
		if(isset($v2[$w]))
		{
			$i += $c + $v2[$w];
		}
	}
	/*On parcourt le second vecteur d’occurrence pour ajouter les occurrences à l'union*/
	foreach ($v2 as $w=>$c)
	{
		$u += $c;
	}
	/*On retourne l'Indice de Jaccard*/
	return $i/$u;
}

Pour les deux textes de l'exemple on obtient une similarité de :

float(0.615384615385)

Critique de l'Indice de Jaccard

Utiliser un indice de Jaccard dans le but de détecter le duplicate content ou de limiter la similarité de textes spinnés est une première étape. Malheureusement, comme le fait remarquer Papy's spinning dans Ne pas confondre similarité et duplication de contenus, si les moteurs de recherche utilisaient un algo aussi simple beaucoup d'articles dans la même thématique seraient détectés en tant que duplicate.

L'indice de Jaccard est donc un moyen simple (mais couteux) pour détecter le duplicate que personnellement je n'utiliserai pas. Le taux de faux dupliqué est trop important.

Afin de conclure cet article on peut dire que l'indice de Jaccard est un bon moyen de calculer la similarité entre deux textes mais qu'il n'est pas suffisant pour être utilisé dans une problématique de détection de duplicate content.

Ce que je n'ai pas dit dans cet article

• Merci à Papy's spinning pour ses remarques pertinantes.
• Merci à Didier Sampaolo pour m'avoir rappelé que cet algo pouvait intéresser des gens.
• Merci à Lemoussel pour sa vulgarisation du SimHash.
• Cdillat préfère écrire des algos que copuler.