Table des matières

Recherche floue

Dans différentes applications on a besoin d'effectuer des recherches. Il peut parfois être utile de retourner des résultats dont l'orthographe ou la phonétique sont proches (par exemple, retourner "wikipedia" pour "wikipdia", ou "sceau" pour "sot").

Il existe différentes méthodes. La plus utilisée combine un encodage phonétique (soundex ou autres) et un calcul de distance (Levenshtein).

Calcul de distance (Levenshtein/Hamming)

Cette méthode consiste à calculer la distance entre deux mots.

php est fourni en standard avec cette fonction. Exemple: 

<?php
header('content-type: text/plain');
 
function distance($a,$b)
{
    echo $a.'->'.$b.' : '.levenshtein($a,$b)."\n";
}
 
distance('wikipedia','wikipedia');
distance('wikepedia','wikipedia');
distance('wikepdia','wikipedia');
?>

Ce qui donne ceci: 

wikipedia->wikipedia : 0
wikepedia->wikipedia : 1
wikepdia->wikipedia : 2

Attention: Cette fonction est sensible à la casse. Ainsi la distance entre 'wikipedia' et 'WIKIPEDIA' est de 9. Il convient donc de tout passer en minuscules avant de calculer la distance: 

levenshtein(strtolower($a),strtolower($b));

Toutefois, levenshtein ne règle pas le problème des mots ayant la même sonorité mais avec une orthographe différente. Il convient alors d'encoder phonétiquement les mots.

Encodage phonétique

Il existe différentes méthodes. Elles ont toutes leurs contraintes:

Liste non exhaustive:

Voici quelques exemples d'encodages phonétiques:

Mot soundex soundex_fr
(Florent Bruneau) 		Phonetique
(Édouard BERGÉ) 		metaphone doubleMetaphone (primary) doubleMetaphone (secondary)
sceau S000 SO SO S S S
seau S000 SO SO S S S
sot S300 SO SO ST ST ST
saut S300 SO SO ST ST ST
wikipedia W213 VKPD OUIKIPEDIA WKPT AKPT FKPT
éléphant L153 ELF ELEFAN LFNT LFNT LFNT
anticonstitutionnellement A532 ATKO ANTIKONSTITUSION ANTKNSTTXNLMNT ANTK ANTK
athmosphérique A352 AT0F ATMOSFERIK A0MSFRK A0MS ATMS
comportement C516 KOPO KONPORTEMAN KMPRTMNT KMPR KMPR

Source (cliquer pour voir)

Source (cliquer pour voir) 

<?php 
header('content-type: text/html');
 
require 'phonetic.php';
require 'double_metaphone_class_1-01.php';
require 'soundex_fr.php';
 
function encode($t)
{
    $dmp = new DoubleMetaPhone($t);
    $dmp_prim = $dmp->primary;
    $dmp_sec = $dmp->secondary;
    return array($t,soundex($t),trim(soundex_fr($t)),phonetique($t),metaphone($t),$dmp_prim,$dmp_sec);
}
 
echo <<<EOF
<table border="1">
<thead><tr>
<td>Mot</td><td>soundex</td><td>soundex_fr</td><td>phonetique</td>
<td>metaphone</td><td>doubleMetaphone (primary)</td><td>doubleMetaphone (secondary)</td>
</tr></thead>
EOF;
 
$mots = array('sceau','seau','sot','saut','wikipedia','éléphant','anticonstitutionnellement','athmosphérique','comportement');
 
foreach($mots as $mot)
{
    echo '<tr><td>'.implode('</td><td>',encode($mot)).'</td></tr>';
}
echo '</table>';
 
?>


Il devient alors intéressant de calculer la distance levenshtein sur ces codes.

On voit clairement que les algos adaptés aux français donnent de meilleurs résultats. Les autres bottent en touche, généralement, en supprimant les voyelles (accentuées ou non), ce qui leur donne un taux de réussite correcte malgré tout (même si, comme on le voit, elles ne gèrent pas les consonnes sourdes, comme le "t" dans le mot "sot").

Notez que (heureusement), ces algos ignorent les différences minuscules/majuscules.

Combinaison

Ce qui est généralement pratiqué pour la recherche floue: 

$phon1 = soundex_fr($mot1);
$phon2 = soundex_fr($mot2);
$pourcentage = levenshtein($phon1,$phon2)*100/strlen($mot1);
if ($pourcentage<=25) echo $mot2.' est proche de '.$mot1

Le seuil est à choisir en fonction:

Exemple

Petit exemple de recherche floue. Ce que fait ce programme d'exemple:

Voici le source (:!: Ce script n'est pas sûr - à ne pas exécuter en environnement de production.):

Cliquez pour agrandir

Cliquez pour agrandir

index.php
<?php 
// Test de recherche floue
error_reporting(-1);
require 'phonetic.php';
require 'soundex_fr.php';
echo <<<HTML
<html><head><style>body {font:12pt sans-serif;}</style></head>
<body>Essai de recherche floue<br>
<form action="" method="get">Entrez un mot: <input name="mot" type="text" />
<input type="submit" value="Chercher"/>
<br>Algo: <input 
<input type="radio" name="algo" value="soundex" checked> soundex</input>
<input type="radio" name="algo" value="metaphone"> metaphone</input>
<input type="radio" name="algo" value="phonetique"> phonetique</input>
<input type="radio" name="algo" value="soundex_fr"> soundex_fr</input>
</form>
HTML;
 
function getTime()
    {
    $a = explode (' ',microtime());
    return(double) $a[0] + $a[1];
    }
$Start = getTime(); 
 
# Chargement de la liste des mots.
$liste=array();
$filename='liste_francais.txt';
$fp = @fopen($filename, 'r'); 
if ($fp) { $liste = explode("\n", fread($fp, filesize($filename))); }
echo count($liste)." mots chargés.<hr>";
 
// Compare un mot ($mot) à une liste ($liste)
// en utilisant la fonction ($fonction).
// Exemple: $resultats = filtre($mot,$liste,'soundex');
function filtre($mot,$liste,$fonction)
{
    $resultat = array();
    $mot_p = call_user_func($fonction,$mot);
    foreach($liste as $m)
    {
        $p = call_user_func($fonction,$m);
        $pourcentage = levenshtein($mot_p,$p)*100/strlen($mot);
        if ($pourcentage<=5) $resultat[]=$m;
    }
    return $resultat;
}
 
if (!empty($_GET['mot']) && !empty($_GET['algo']))
{
    $mot = $_GET['mot'];
    $algo = $_GET['algo'];
    echo '<br>Recherche du mot <b>'.htmlspecialchars($mot)."</b> avec l'algo <b>".htmlspecialchars($algo).'</b><br>';
    echo 'Mots proches: <b>'.implode(', ',filtre($mot,$liste,$algo)).'</b>';
}
$End = getTime();
echo "<hr>Temp d'exection: ".number_format(($End - $Start),2)." secs"; 
echo '</body></html>';
?>


Et pour que cela soit plus simple: voici le fichier zip: test_phonetique.zip

Exemple d'utilisation:

En cherchant le mot "raté" avec Soundex:

Avec metaphone:

Avec soundex_fr:

Avec Phonétique:

Comme on peut le constater:

Le choix de l'algo est un compromis entre la qualité des résultats et la charge CPU. Notez que:

A voir

A prendre en considération (non traité ici)