====== 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 ([[https://fr.wikipedia.org/wiki/Distance_de_Levenshtein|Levenshtein]]).

===== Calcul de distance (Levenshtein/Hamming) =====

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

  * Chaque fois qu'une lettre est substituée, on ajoute 1.
  * Chaque fois qu'une lettre est supprimée, on ajoute 1.
  * Chaque fois qu'une lettre est ajoutée, on ajoute 1.

php est [[http://fr.php.net/manual/en/function.levenshtein.php|fourni en standard]] avec cette fonction. Exemple:

<code php><?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');
?>
</code>

Ce qui donne ceci:
<code>wikipedia->wikipedia : 0
wikepedia->wikipedia : 1
wikepdia->wikipedia : 2</code>

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:

<code php>levenshtein(strtolower($a),strtolower($b));</code>

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:

  * Support plus ou moins bon des particularités des différentes langues.
  * Implémentations supportant ou non l'UTF-8.
  * Consommation CPU.

Liste non exhaustive:

  * [[http://fr2.php.net/manual/fr/function.soundex.php|Soundex]]. Problème: Cet algo est surtout adapté à l'anglais, et il est limité à 4 caractères. Il existe des versions dérivées mieux adaptées au français:
      * [[http://www.roudoudou.com/php/phonetic.php|Phonétique]] par Édouard BERGÉ.
      * [[http://blog.mymind.fr/post/2007/03/15/Soundex-Francais|Soundex Français]] par Florent Bruneau.
      * [[http://web.archive.org/web/20050209205529/http://www.php-help.net/sources-php/a.french.adapted.soundex.289.html|autre version]] d'un soundex adapté au français.
  * [[http://fr2.php.net/manual/fr/function.metaphone.php|metaphone]]
  * [[http://fr.wikipedia.org/wiki/Double_Metaphone|Double-metaphone]], qui est limité à 4 caractères, mais qui est censé être adapté à d'autres langues que l'anglais (langues slaves, germaniques, grec, français, Italien, espagnol, chinois et autres). Particularité: Il renvoie deux racines par mot, ce qui permet de faire des rapprochements. (voir l'[[http://swoodbridge.com/DoubleMetaPhone/|implémentation php]] de Stephen Woodbridge).

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 | 
<hidden Source (cliquer pour voir)><code php><?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>';

?></code></hidden>

\\ 

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:

  * Encodage des mots à comparer en phonétique.
  * Calcul de la distance de levenshtein entre les mots, ramené à la longueur du mot (exemple: distance 2 sur un mot de 7 lettres --> 2/7*100 = 28,5% de différence) 
  * On ne renvoie que les mots qui ont moins de X% de différence.

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

Le seuil est à choisir en fonction:
  * De la précision de l'algo choisi par rapport à la langue.
  * Du nombre de suggestions que vous voulez ramener à l'utilisateur.
  * De votre corpus (distribution des mots variée ou non, mélange de langues, quantité de données...)

===== Exemple =====

Petit exemple de recherche floue. Ce que fait ce programme d'exemple:
  * Il charge en mémoire un dictionnaire français limité de [[http://www.freelang.com/dictionnaire/dic-francais.php|22740 mots]].
  * Il compare le mot entré à ce dictionnaire avec la distance de levenshtein en encodant avec l'algo sélectionné (soundex,metaphone,soundex_fr ou phonétique)
  * Il renvoie les mots ayant au plus 5% de différence avec le mot entré.

Voici le source (:!: **Ce script n'est pas sûr - à ne pas exécuter en environnement de production.**):
<hidden Cliquez pour agrandir><file php 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>';
?>
</file>
</hidden>
\\ Et pour que cela soit plus simple: voici le fichier zip: {{:php:test_phonetique.zip|}}


Exemple d'utilisation:

En cherchant le mot "raté" avec Soundex:
{{ :php:recherche_floue_soundex.png?nolink |}}


Avec metaphone:
{{ :php:recherche_floue_metaphone.png?nolink |}}


Avec soundex_fr:
{{ :php:recherche_floue_soundex_fr.png?nolink |}}


Avec Phonétique:
{{ :php:recherche_floue_phonetique.png?nolink |}}


Comme on peut le constater:

  * **soundex** ne gère pas les accents, donnant d'assez mauvais résultats.
  * **metaphone**, qui n'est pas non plus adapté au français, ne fait guère mieux.
  * **soundex_fr** est déjà nettement plus pertinent, mais étant limité (comme soundex) à 4 phonèmes, il remonte également plein de mots inutiles (//restants, restées//...)
  * **phonétique** est très pertinent (fidèle à la phonétique du mot d'origine), et n'étant pas limité à 4 phonèmes, il ne renvoie pas de mots inutiles. Mais il a un temps de traitement important (plus de 30 secondes là où soundex_fr prend environ 3 secondes).

Le choix de l'algo est un compromis entre la qualité des résultats et la charge CPU. Notez que:
  * On peut réduire (voir annuler) la charge CPU en pré-calculant les phonèmes.
  * On peut choisir d'utiliser un algo moins précis (comme soundex_fr) mais en limitant le nombre de résultats retournés (par exemple 8 maximum) pour éviter de noyer l'utilisateur dans des suggestions inutiles.


===== A voir =====

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

  * **Quand** déclencher la recherche floue (uniquement en cas d'échec de la comparaison brute ?)
  * Support UTF-8
  * comportement avec des langues mélangées dans un même texte.