Recherche de texte similaire, ou le fameux « Did you mean » de Google 2

EDIT: Cet article est un repost de l’ancienne version du blog.

Après un mois de silence, dûs au travail sur mon projet de groupe pour SUPINFO, j’ai enfin décidé de refaire un nouvel article, encore sur PHP. Promis, la prochaine fois, je le fais sur autre chose :p .

Aujourd’hui, l’article sera sur la recherche de texte similaire. Vous savez, lorsque vous cherchez sur Google et que vous faites une faute de frappe, il vous propose une expression approchante. Et bien c’est ça. Bien sûr, je ne vais pas faire une fonction aussi étoffée que celle de Google (déjà parce qu’il faut une base de données énorme pour pouvoir sortir un truc comme eux et que je suis pas aussi intelligent que les mecs qui bossent là-bas), mais je vais approcher les bases du concept (enfin de ce que j’ai pu trouver seul, je ne me suis pas documenté là-dessus au préalable).

Présentation des combattants

Tout d’abord, je vous explique pourquoi j’ai eu besoin de faire cet algorithme : c’est encore une fois pour mon MUD, pour pouvoir proposer une correction lorsque le joueur se trompe de commande/de mot (par exemple, lorsqu’il veut prendre un objet, mais qu’il se trompe dans le nom). C’est histoire de faire en sorte que ce soit ergonomique et que le joueur ne soit pas perdu si il tape mal son mot et que le jeu l »aide à trouver ce qu’il cherchait.

Mon algorithme se base sur 2 fonctions : metaphone() et levenshtein().

 

  • levenshtein() permet de calculer la différence entre deux chaînes données, c’est-à-dire le nombre de caractères qu’il faut ajouter/remplacer/supprimer pour que la chaîne 1 devienne la chaîne 2. C’est pratique pour obtenir un indice de similarité.
  • metaphone() est une fonction permettant de cacluer la clé metaphone d’une chaîne de caractère donnée. Une clé metaphone, c’est une autre chaîne de caractère crée en fonction de la prononciation de la première. Cette fonction est donc très utile pour faire des recherches phonétiques sur une chaîne de caractères.

Pour le cas de metaphone(), j’aurais pu aussi utiliser soundex() qui était disponible, et décrite par Donald Knuth dans son TAOCP (vol. 3), mais j’ai décidé de choisir metaphone() car elle est plus précise, notamment sur les mots en anglais (elle intègre plusieurs règles de prononciation anglaise), et permet de faire de la recherche de proximité sur les clés qu’elles renvoie (car soundex() ne renvoie que des clés de 4 caractères, alors que pour metaphone(), ce sont des clés de taille variable qui sont renvoyées).

Bref, au final, l’algorithme fait une recherche de similarité phonétique, puis ensuite (si la recherche n’a rien donné) passe à une recherche lettre-par-lettre.

La recherche phonétique exacte

Avant de commencer, je tiens juste à spécifier une chose : la fonction prendra pour acquis que les deux mots sont différents. Il faudra mettre une condition/boucle avant l’appel à la fonction pour vérifier l’égalité des variables. Enfin bref.

Tout d’abord, on va faire une vérification phonétique exacte, c’est-à-dire que l »on va vérifier si une de nos chaînes en données (i.e. celles dans lesquelles on doit chercher) correspond phonétiquement à la chaîne « mystère ». On va donc utiliser les clés metaphone pour ça, et au final, ça ressemble beaucoup à une recherche d’égalité de chaîne :

$needleMetaphone = metaphone($needle);
$metaphoneKeys = array();
//Analyse phonétique Metaphone
foreach($haystack as $item)
{
 	//C'est pour utiliser plus tard, histoire de pas faire 15 fois les mêmes clés.
	$metaphoneKeys[$item] = metaphone($item);
	if($metaphoneKeys[$item] == $needleMetaphone)
		return $item;
}

Bon, pour le return, faut vous imaginer qu’on utilise ce code dans un contexte de fonction (si si, parce qu »on va rajouter des trucs derrière, donc dans une fonction c’est bien).

Alors ici, rien de plus simple : on calcule les 2 clés metaphone (enfin on en calcule une avant, puis l’autre), et on regarde si elles sont exactes. Le cas échéant, on retourne la valeur demandée. Comme je l’ai commenté dans le code, j’ai mis une petite feature pour les clés metaphone, c’est de les garder en mémoire. En effet, on va s’en servir plus tard, ça ne sert à rien de les recalculer à chaque fois (surtout la clé metaphone de la chaîne recherchée, elle est la même durant toute la fonction).

Bon, maintenant, imaginons que la recherche phonétique exacte ne marche pas : le mec qui fait la recherche sait ni parler, ni écrire, l’algorithme metaphone marche bien sur l’anglais mais moins sur le reste, etc. Nous allons alors élargir un peu notre champ de recherche en incluant la recherche phonétique approximative.

La recherche phonétique approximative

Alors, pour faire de la recherche phonétique approximative, on va encore avoir besoin des clés metaphone des différentes chaînes de caractères que l’on cherche. Voilà pourquoi j’ai fait une « mise en cache » des variables traitées dans la boucle d’au-dessus, elle vont nous éviter de tout recalculer et de perdre du temps pour rien.

Ici, le but sera de juste calculer la distance entre les clés metaphone (la distance Levenshtein, oui, c’est utile pour faire des comparaisons de chaînes de caractères, alors pourquoi pas de clés, qui sont des chaînes de caractères ?), puis de prendre la clé avec la distance la plus petite par rapport à celle cherchée, donc logiquement correspondant à l’entrée la plus proche de la valeur recherchée.

Au final, le code qui permet de gérer ça est juste une simple boucle :

$levenshtein = 0;
$ret = '''';
//Analyse de proximité metaphone
foreach($haystack as $item)
{
	if(!$levenshtein || $levenshtein > levenshtein($metaphoneKeys[$item], $needleMetaphone))
	{
		$ret = $item;
		$levenshtein = levenshtein($metaphoneKeys[$item], $needleMetaphone);
	}
}

Au final, après cette boucle, la variable $ret contiendra la valeur de notre liste la plus approchante de la valeur fournie.

Bon c’est cool, maintenant on peut faire des recherches phonétiques, et donc donner des suggestions aux mecs qui font des fautes d’orthographe, mais on ne peut toujours pas remédier au problème le plus fréquent lors d’une saisie de texte : les fautes de frappe. C’est pourquoi l’on a besoin de rajouter une petite boucle encore pour que la fonction soit plus précise.

Recherche de proximité textuelle pure : Levenshtein

Bon, après les clés metaphone, cette partie c’est de la touchette : le truc, ça va juste être de modifier la partie précédente (qui fait une recherche de similarité sur les clés Metaphone) pour qu’elle fasse une recherche directement sur le texte dont il est question.

Pas besoin d »épiloguer sur le contenu de notre boucle cette fois-ci, je l »ai déjà fait précédemment. Le résultat, c’est ça :

foreach($haystack as $item)
{
	if(!$levenshtein || $levenshtein > levenshtein($item, $needle))
	{
		$ret = $item;
		$levenshtein = levenshtein($item, $needle);
	}
}

Voilà, grâce à cette boucle, $ret contiendra au final la valeur qui est la plus proche au niveau des caractères de $needle (donc la suggestion la plus concordante).

Maintenant qu’on a toutes les parties, le temps est venu de faire un mix de tout ça pour avoir une belle fonction qui nous calcule tout ça automatiquement et nous renvoie la meilleure solution.

La fonction finale : concentré d’awesomeness

Allez, on y va, on colle tout, et j »explique après :

function getMostSimilarString($needle, $haystack)
{
	$needleMetaphone = metaphone($needle);
	$metaphoneKeys = array();

	//Analyse phonétique Metaphone exacte
	foreach($haystack as $item)
	{
		$metaphoneKeys[$item] = metaphone($item);
		if($metaphoneKeys[$item] == $needleMetaphone)
			return $item;
	}

	$levenshtein = 0;
	$ret = '''';
	//Analyse de proximité metaphone
	foreach($haystack as $item)
	{
		if(!$levenshtein || $levenshtein > levenshtein($metaphoneKeys[$item], $needleMetaphone))
		{
			$ret = $item;
			$levenshtein = levenshtein($metaphoneKeys[$item], $needleMetaphone);
		}
	}

	//Analyse de la distance de Levenshtein, si l'analyse de la clé Metaphone n'a rien donné.
	foreach($haystack as $item)
	{
		if(!$levenshtein || $levenshtein > levenshtein($item, $needle))
		{
			$ret = $item;
			$levenshtein = levenshtein($item, $needle);
		}
	}

	return $ret;
}

Bon, alors on remarque bien les 3 blocs, et on voit bien maintenant que la mise en mémoire lors de la première boucle des clés metaphone est utile, vu qu’on a pas à les recalculer lors de la seconde boucle. Ensuite, je dois m’expliquer sur la raison pour laquelle j’ai mis l »analyse approximative metaphone avant l’analyse textuelle approximative (l’analyse allant normalement du plus précis au plus vague, l’ordre aurait dû être inversé).

Les raisons pour lesquelles j’ai fait ça, c »est tout d’abord parce que j’ai souhaité mettre en valeur la phonétique avant la rigueur d’écriture. Je l’ai fait aussi parce que metaphone, comme indiqué sur la doc’ PHP, est une fonction programmée avec les règles de prononciation anglaise (en tout cas metaphone simple, apparement, double metaphone serait capable de comprendre le français, mais je divague). Enfin, je l’ai fait parce que je souhaitais donner une priorité à la recherche directe de caractère par rapport à la recherche phonétique, mais seulement si celle-ci est plus concluante (ce qui peut être le cas lors des fautes de frappe), car, comme une clé metaphone est plus courte que le mot (j’ai compté environ 2 lettres par syllabe), il faut que le nombre de lettres d’écarts entre la suggestion et le mot mal orthographié soit relativement petite (et que la différence phonétique soit énorme) pour qu’elle prenne le pas.

Le mot de la fin

Voilà, c’est fini. J’espère que vous avez appris quelques trucs (au moins autant que j’ai appris en écrivant cette petite fonction) en lisant cet article.

Sinon, le point hors-sujet du jour : la semaine dernière, je suis allé au Hellfest, c’était juste trop génial. Les concerts de groupes trop awesome (notamment Maximum The Hormone), voir les copains bourrés, l’ambiance qui tue, discuter avec des étrangers qui ont la même passion… Mais bon mon compte en banque n’a pas trop aimé lui (150€ en tout pour 1 jour, ça fait mal). Maintenant, je vais devoir faire des économies, et, qui sait, peut-être que l’année prochaine, j’irai encore :D .

Bref, je vous dis à une prochaine fois.

2 thoughts on “Recherche de texte similaire, ou le fameux « Did you mean » de Google

  1. Reply Docteur Batcher août 11, 2014 1 h 46 min

    tu pourrais nous donner un exemple d’utilisation comme l’intégrer dans un script de recherche ?

  2. Reply yohann août 12, 2014 1 h 06 min

    Cela dépend de la façon dont ton script de recherche est constitué, mais perso, je ferais d’abord une recherche sur le terme que l’utilisateur à entré (pour le cas où il ait rentré un truc correct), puis si cette recherche ne donne rien, alors je fais tourner mon script de recherche similaire pour trouver un terme de recherche (dans un dictionnaire/une base de données de recherches déjà effectuées) correspondant, et je conseille l’utilisateur sur le terme trouvé le cas échéant.

    Après, pour un exemple, regarde dans le MUD que j’avais commencé sur mon serveur IRC (la fonction eventTake() dans le fichier mudevents.php contient l’exemple) : https://github.com/ylorant/PHPIRCd/tree/master/plugins

Leave a Reply to Docteur Batcher Cancel Reply