moteur de recherche et erreurs

28 août 2010 à 3:37:34

Bonjour les ZérOs,

J'ai une base contenant des données sur la population par ville. J'aimerais que, quand on entre des données sur une ville déjà existante, le lien se fasse correctement malgré des fautes de frappe ou une mauvaise orthographe. J'ai donc dans l'idée de faire une requête AJAX pour vérifier la présence d'une ville dans la base et si besoin alerter l'auteur - par exemple "est-ce que vous vouliez écrire PARIS ?" ou "PARRIS n'existe pas dans la base. L'ajouter ?"

En réfléchissant j'ai vu qu'il y avait plusieurs possibilités :

- générer en PHP un tableau de mots altérés sur le modèle de fautes d'orthographe et de frappe communes et interroger la base pour chaque mot généré.
- j'ai vu qu'on pouvait utiliser des regexp dans une requête : est-ce qu'on peut écrire une regexp qui dit "trouver ce mot à 3 caractères près" ? ce qui autoriserait trois mauvaises lettres dans le mot. ça me parait suffisant.

Je ne sais pas si l'un est plus performant que l'autre et c'est ma première question. En suite, il y en a peut-être parmi vous qui ont déjà fait ça : qu'avez-vous fait ?

Merci !

Kromkrom

30 août 2010 à 11:14:18

Bonjour,

Ta première solution demanderait beaucoup de temps (par exemple pour Paris : Pari, Parri, Parris, on peut en imaginer plein, et tu ne pourras jamais avoir tous les orthographes possibles et inimaginables que les gens rentreront).

"Trouver ce mot à 3 caractères près", cela pourrait te donner des regex complexes je pense, car les 3 caractères près peuvent aussi bien représenté un ajout de lettre (un 'r' dans 'Paris'), une faute de frappe (Pareis, certains ont de gros doigts !), ou un oubli de lettre (Pari). Bien que cela soit surement faisable, pour ma part j'aurais plus fait quelque chose dans le style :
Je cherche les lettres "P", "a", "r", "i", dans un mot de 6 lettres maximum, et j'en conclus que l'utilisateur a voulu taper "Paris". Après, si tu as plusieurs fois la même regex (après tout, les noms de certaines villes se ressemblent beaucoup), rien ne t'empêche de faire une liste déroulante avec les différentes villes que l'utilisateur aurait pu vouloir taper.

En espérant t'avoir aidé

GeoffreyZéro

30 août 2010 à 11:56:34

Oui ça m'aide : surtout le coup de casser mon nom de ville et de faire une recherche pour les lettres qui le composent.

J'irai refaire un tours dans le tuto regexp pour me rafraîchir la mémoire, mais en gros je dois récupérer le mot tapé, compter le nombre de caractères, et rechercher un mot contenant au moins n-1 des lettres énoncée, en sachant que les lettres ne peuvent se répéter qu'une fois, das un mot de mettons 3 à n+1 lettres.

sicilien007

30 août 2010 à 14:40:23

bonjour, en plus de la solution proposée il est bon d'ajouter une comparaison avec soundex() qui existe au moins pour Oracle, MySQL, SQL Server. Elle est basée sur la phonétique de la langue anglaise donc en français elle est à utiliser avec précaution (nos lettres non prononcées) mais elle est un complément utile.

GeoffreyZéro

30 août 2010 à 17:01:44

Merci beaucoup. J'ai regardé un peu sur le net et j'ai vu que pas mal de programmeurs avaient créé un soundex francophone (conversion des accents, cédilles et règles différentes pour les consonnes) en PHP.

<?php

// par F. Bouchery 

function soundex2( $sIn )
{
   // Si il n'y a pas de mot, on sort immédiatement
   if ( $sIn === '' ) return '    ';
   // On met tout en minuscule
   $sIn = strtoupper( $sIn );
   // On supprime les accents
   $sIn = strtr( $sIn, 'ÂÄÀÇÈÉÊËŒÎÏÔÖÙÛÜ', 'AAASEEEEEIIOOUUU' );
   // On supprime tout ce qui n'est pas une lettre
   $sIn = preg_replace( '`[^A-Z]`', '', $sIn );
   // Si la chaîne ne fait qu'un seul caractère, on sort avec.
   if ( strlen( $sIn ) === 1 ) return $sIn . '   ';
   // on remplace les consonnances primaires
   $convIn = array( 'GUI', 'GUE', 'GA', 'GO', 'GU', 'CA', 'CO', 'CU', 'Q', 'CC', 'CK' );
   $convOut = array( 'KI', 'KE', 'KA', 'KO', 'K', 'KA', 'KO', 'KU', 'K','K', 'K' );
   $sIn = str_replace( $convIn, $convOut, $sIn );
   // on remplace les voyelles sauf le Y et sauf la première par A
   $sIn = preg_replace( '`(?<!^)[EIOU]`', 'A', $sIn );
   // on remplace les préfixes puis on conserve la première lettre
   // et on fait les remplacements complémentaires
   $convIn = array( '`^KN`', '`^(PH|PF)`', '`^MAC`', '`^SCH`', '`^ASA`', '`(?<!^)KN`', '`(?<!^)(PH|PF)`', '`(?<!^)MAC`',
                    '`(?<!^)SCH`','`(?<!^)ASA`' );
   $convOut = array( 'NN', 'FF', 'MCC', 'SSS', 'AZA', 'NN', 'FF', 'MCC', 'SSS', 'AZA' );
   $sIn = preg_replace( $convIn, $convOut, $sIn );
   // suppression des H sauf CH ou SH
   $sIn = preg_replace( '`(?<![CS])H`', '', $sIn );
   // suppression des Y sauf précédés d'un A
   $sIn = preg_replace( '`(?<!A)Y`', '', $sIn );
   // on supprime les terminaisons A, T, D, S
   $sIn = preg_replace( '`[ATDS]$`', '', $sIn );
   // suppression de tous les A sauf en tête
   $sIn = preg_replace( '`(?!^)A`', '', $sIn );
   // on supprime les lettres répétitives
   $sIn = preg_replace( '`(.)\1`', '$1', $sIn );
   // on ne retient que 4 caractères ou on complète avec des blancs
   return substr( $sIn . '    ', 0, 4);
}
?>

Je crois que je peux le convertir en JS. C'est peut-être mieux de voler quelques ms à *un* seul utilisateur.

J'ajouterais à ma table `villes` une colonne avec leur soundex francophone, convertirais le nom tapé par l'utilisateur en soundex francophone avant la requête, puis ferais un SELECT pour cette colonne uniquement.

Je crois que je peux même mettre un index sur la colonne du soundex pour améliorer la performance du SELECT, mais j'aimerais confirmation pour ce point : est-ce que ça ne va pas bouffer ÉNORMÉMENT de ressources d'avoir un index sur une table qui risque d'être très grande ?

Et si oui, est-ce que les performances du serveur seront affectées simplement uniquement à l'ajout d'une nouvelle entrée (puisqu'il faut refaire l'index) ou est-ce que c'est plus chiant que ça ?

sicilien007

1 septembre 2010 à 4:05:01

bonjour,
pour les index MySQL ne donne pas la formule pour calculer la taille de l'index en fonction du nombre d'entrées et de la taille de la colonne. Oracle la donnait à une époque.
En revanche ce qu'il est possible de faire avec la commande explain c'est de comparer les accès avec ou sans index.
Pour le coût de la réorganisation de l'index cela dépend de son taux de mise à jour.
Et merci pour l'info sur Soundex2.
Mais j'ai essayé ça

<?php
echo soundex2("Paris") . "<br/>";
echo soundex2("Pari") . "<br/>";
echo soundex2("Prix") . "<br/>";
echo soundex2("Pris") . "<br/>";
?>

et ça me donne des résultats étranges!

GeoffreyZéro

1 septembre 2010 à 9:06:10

J'ai pas encore testé sur ma table mais si je fais une comparaison j'obtiens ça :

ville  	sdx2	sdx1

Paris  	PR	P620
Pari   	PR	P600
Pary   	PR	P600
Paaris 	PR	P620
Pris   	PR	P620
Prix   	PRX	P620
Pali   	PL	P400

Pour moi la supériorité de ce soundex2 ne fait pas de doute : on voit que soundex() considère que "Paris", "Pary" et "Pari" ne sont pas le même son. Et il fait deux faux positifs avec "Prix" et "Pris".

Il y aurait encore plus performant (reconnaissance des assonances), par contre pour convertir en JS ça me paraît plus fastidieux vu que les deux langages se ressemblent moins.

//-------------------------------------------------------------------------
// FONCTION PHONEX : copyright Frédéric BROUARD
//-------------------------------------------------------------------------
//function phonex(sIn : string) : integer;
function phonex(sIn : string) : double;
Type
   TabSonAI = array[1..4] of string;
   tabCarPhon = array[0..21] of char;
Const
    SonAIA : TabSonAI = ('aina','eina','aima','eima');
    SonAIE : TabSonAI = ('aine','eine','aime','eime');
    SonAII : tabSonAI = ('aini','eini','aimi','eimi');
    SonAIO : tabSonAI = ('aino','eino','aimo','eimo');
    SonAIU : tabSonAI = ('ainu','einu','aimu','eimu');
    CarPhon : TabCarphon = ('1','2','3','4','5','e','f','g','h','i','k','l','n','o','r','s','t','u','w','x','y','z');
var
   i,j,k     : integer;
   car   : char;
   p     : integer;
   let, sin2 : string;
   sOut : array[1..10] of integer;
begin
// cas trivial : la chaîne est vide
if sIn = ''
then
begin
//   result := 0;
result := 0.0;
   exit;
end;

// mise en minuscules
sIn := lowerCase(sIn);

// remplacement des y par des i
sIn := SearchReplace(sIn, 'y', 'i');

// remplacement des lettres accentuées
for i:= 1 to length(sIn)
do
begin
     car := sIn[i];
     CASE car of
        'â','ä','à','Â','Ä','À' : car := 'a';
        'ç','Ç' :                 car := 's';
        'ë','œ','Ë','Œ' :         car := 'e';
        'ï','î','Î','Ï' :         car := 'i';
        'ô','ö','Ô','Ö' :         car := 'o';
        'ù','û','ü','Ù','Û','Ü' : car := 'u';
        'é','ê','È','É','Ê' :     car := 'y';
     END;
     sIn[i] := car;
end;

// on retire les h muets
for i := 1 to length(sIn)
do
begin
  p := pos('h',sIn);
  if p = 1
  then
    sIn := copy(sIn,2, length(sIn)-1)
  else
    if not((sIn[p-1] = 'c') or (sIn[p-1] = 's'))
    then
      if p<length(sIn)
      then
        sIn := copy(sIn,1,p-1)+copy(sIn,p+1,length(sIn)-p)
      else
        sIn := copy(sIn,1,p-1);
end;

// remplacement des ph par des h
sIn := SearchReplace(sIn, 'ph', 'f');

// rempacement de g qui sonnent k devant an, am, ain, aim
sIn := searchReplace(sIn,'gan','kan');
sIn := searchReplace(sIn,'gain','kain');
sIn := searchReplace(sIn,'gam','kam4');
sIn := searchReplace(sIn,'gaim','kaim');

// remplacement du son AI
for i := 1 to 4
do
begin
  sIn := searchReplace(sIn,SonAIA[i],'yna');
  sIn := searchReplace(sIn,SonAIE[i],'yne');
  sIn := searchReplace(sIn,SonAII[i],'yni');
  sIn := searchReplace(sIn,SonAIO[i],'yno');
  sIn := searchReplace(sIn,SonAIU[i],'ynu');
end;

// remplacement des groupes de 3 lettres
sIn := searchReplace(sIn,'eau','o');
sIn := searchReplace(sIn,'oua','2');
sIn := searchReplace(sIn,'ein','4');
sIn := searchReplace(sIn,'ain','4');

// remplacement du son é
sIn := searchReplace(sIn,'ai','y');
sIn := searchReplace(sIn,'ei','y');
sIn := searchReplace(sIn,'er','yr');
sIn := searchReplace(sIn,'ess','yss');
sIn := searchReplace(sIn,'et','yt');
sIn := searchReplace(sIn,'ez','yz');

// remplacement des groupes de 2 lettres sauf si voyelle ou son (1 à 4)
Sin := SRSaufVoyelle(sIn,'an','1');
Sin := SRSaufVoyelle(sIn,'am','1');
Sin := SRSaufVoyelle(sIn,'en','1');
Sin := SRSaufVoyelle(sIn,'em','1');
Sin := SRSaufVoyelle(sIn,'in','4');

// remplacement du sch
Sin := searchReplace(sIn,'sch','5');

// remplacement du s si précédé et suivi d'une voyelle ou son (1 à 4)
sin := SRSauf2Voyelle(sIn,'s','z');

// remplacement des groupes de 2 lettres divers
Sin := searchReplace(sIn,'oe','e');
Sin := searchReplace(sIn,'eu','e');
Sin := searchReplace(sIn,'au','o');
Sin := searchReplace(sIn,'oi','2');
Sin := searchReplace(sIn,'oy','2');
Sin := searchReplace(sIn,'ou','3');
Sin := searchReplace(sIn,'ch','5');
Sin := searchReplace(sIn,'sh','5');
Sin := searchReplace(sIn,'ss','s');
Sin := searchReplace(sIn,'sc','s');

// remplacement du c par s s'il est suivi d'un e ou d'un i
Sin := searchReplace(sIn,'ce','se');
Sin := searchReplace(sIn,'ci','si');

// remplacement divers
Sin := searchReplace(sIn,'c','k');
Sin := searchReplace(sIn,'q','k');
Sin := searchReplace(sIn,'qu','k');

Sin := searchReplace(sIn,'ga','ka');
Sin := searchReplace(sIn,'go','ko');
Sin := searchReplace(sIn,'gu','ku');
Sin := searchReplace(sIn,'gy','ky');
Sin := searchReplace(sIn,'g2','k2');
Sin := searchReplace(sIn,'g1','k1');
Sin := searchReplace(sIn,'g3','k3');

Sin := searchReplace(sIn,'a','o');
Sin := searchReplace(sIn,'d','t');
Sin := searchReplace(sIn,'p','t');
Sin := searchReplace(sIn,'j','g');
Sin := searchReplace(sIn,'b','f');
Sin := searchReplace(sIn,'v','f');
Sin := searchReplace(sIn,'m','n');

// suppression des lettres dupliquées
let := copy(sIn,1,1);
sIn2 := let;
for i := 2 to length(Sin)
do
begin
  if sIn[i] = let
  then
      continue;
  let := sIn[i];
  Sin2 := Sin2 + sIn[i];
end;
sIn := sIn2;

// suppression des terminaisons
sIn2 := copy(sIn,length(sIn),1);
if (sIn2 = 't') or (sIn2 = 'x') or (sIn2 = 's') or (sIn2 = 'z')
then
    sIn := copy(sIn,1,length(sIn)-1);

// suppression des caractères non autorisés
j := 10;
for i := 1 to length(sIn)
do
begin
  if j<1
  then
      break;
  for k:=0 to 21
  do
    if sIn[i] = carPhon[k]
    then
    begin
         sout[j] := k;
         j := j-1;
    end;
end;

// conversion en flottant
result := 0.0;
for j := 10 downTo 1
do
  result := result+sout[j]*pow(j-1,22);

end;

end.

Après, ça ne résout pas le problème des fautes de frappes, parce que si le soundex n'est pas très sensible aux voyelles, il suffit d'une erreur de consonne pour que ça ne fonctionne plus.

Je medis que je peux mélanger deux idées : faire mon tableau de mots altérés, trouver leur soundex, fusionner les soundex similaires et faire ma requête

Si je prends un mot un peu compliqué genre "afghanistan" j'obtiens ces résultats

Inversions de lettres:

    * faghanistan
    * agfhanistan
    * afhganistan
    * afgahnistan
    * afghnaistan
    * afghainstan
    * afghansitan
    * afghanitsan
    * afghanisatn
    * afghanistna

Lettres voisines:

    * &fghanistan
    * éfghanistan
    * zfghanistan
    * qfghanistan
    * arghanistan
    * adghanistan
    * acghanistan
    * agghanistan
    * afthanistan
    * affhanistan
    * afvhanistan
    * afhhanistan
    * afgyanistan
    * afgganistan
    * afgbanistan
    * afgjanistan
    * afgh&nistan
    * afghénistan
    * afghznistan
    * afghqnistan
    * afghajistan
    * afghabistan
    * afgha,istan
    * afghan_stan
    * afghanustan
    * afghankstan
    * afghanostan
    * afghançstan
    * afghaniztan
    * afghaniqtan
    * afghaniwtan
    * afghanidtan
    * afghanis(an
    * afghanisran
    * afghanisgan
    * afghanisyan
    * afghanis-an
    * afghanist&n
    * afghanistén
    * afghanistzn
    * afghanistqn
    * afghanistaj
    * afghanistab
    * afghanista,

Si je prends leur soundex2 et que je fusionne les résultats similaires j'obtiens 19 résultats

AFGN
FGNS
AGFN
AFKN
EFGN
ZFGN
KFGN
ARGN
ADGN
ACGN
AGNS
AFTN
AFNS
AFVN
AFGK
AFGB
AFGJ
AFGZ
AFGS

19 requêtes c'est peut-être encore un peu beaucoup même sur une colonne indexée non ? Je me rends pas du tout compte en fait. Par contre ces requêtes ne seraient faites que si le mot tapé n'a donné aucun résultat (deux aller-retour).

sicilien007

1 septembre 2010 à 14:26:35

bonjour, merci pour le retour et je vois que ça avance bien.
Mais si je crois que l'encodage en JS est assez proche et le gain me semblerait minime. Il faudra toujours extraire dans la table. En revanche en fonction de ton interface, si tu choisis une liste de suggestions type Google, alors Ajax s'imposerait, donc du JS appelant PHP/MySQL.

GeoffreyZéro

1 septembre 2010 à 17:16:29

la raison pour laquelle je veux traduire en JS plutôt que de faire du PHP c'est que je préfère que le serveur n'ait à assurer que les requêtes vers la base de données, et pas toute la partie gestion de fautes de frappe/orthographe.

Après, si le gain est vraiment minime, pourquoi pas du PHP, mais sur le principe j'aime bien économiser du temps d'exécution sur le client quand celui-ci n'est pas très sensible.

J'utilise déjà de l'AJAX avec JQuery. La reconnaissance de la ville permet entre autres de pré-remplir des champs, même si son principal but est de ne pas avoir de doublons.

nightmat

1 septembre 2010 à 17:29:45

Pour ce qui est des problèmes de prononciation toussa ; la méthode à utiliser serait pas plutôt la distance de Levenshtein ?

Ce n'est pas parce que vous ne savez pas vous servir d'un marteau qu'il faut planter des clous au tournevis.

GeoffreyZéro

1 septembre 2010 à 18:41:39

Sur le principe c'est vrai que ta proposition est la plus proche de ma demande de départ.

Seulement, ce genre de fonction doit avoir les deux chaînes en paramètre : ça voudrait dire que je dois lire toutes les lignes de la table et exécuter la fonction pour chaque ligne. je me trompe ?

Il y a plus de 32000 villes de plus de 100 habitants en France. Je ne dis pas que ma base a vocation à être aussi grande, mais en tout cas exécuter une fonction sur chaque ligne a l'air bien plus long que de vérifier une égalité pour 20 lignes.