Ecriture d'une fonction de reconnaissance phonétique pour MySQL

Mots-clés: MySQL, C, fonction UDF, librairie partagée

L'objectif de cet article est de vous montrer la simplicité avec laquelle il est possible d'étendre le SGBD MySQL pour lui ajouter de nouvelles fonctions directement appelables à partir de requêtes SQL.

Pour illustrer ces techniques, nous vous proposons de coder une fonction de "reconnaissance phonétique".

1.Notre besoin:

Imaginez que vos disposiez d'une vaste base documentaire et que vous proposiez à vos utilisateurs un formulaire Web pour interroger la base. Il est facile de retrouver des informations dont le contenu est exactement celui indiqué par les utilisateurs : il suffit d'écrire des requêtes SQL qui ressemblent par exemple à :

SELECT * FROM table WHERE champ1 = 'valeur1' AND champ2 = 'valeur2';

Les utilisateurs peuvent se tromper ou bien ne pas connaitre exactement les valeurs exactes à rechercher. Dans ce cas, on peut utiliser une clause LIKE [MYSQL1], par exemple :

SELECT * FROM table WHERE champ1 LIKE 'val%' AND champ2 LIKE 'v__';

Dans cet exemple, le caractère '%' est un substitut pour "une chaine quelconque", tandis que le caractère '_' remplace une occurrence de n'importe quel caractère.
Nous avons fait un pas vers les recherches approximatives, mais nous nous heurtons à plusieurs limitations :

  • comment retrouver la chaine 'VALEUR' stockée dans la base alors que l'utilisateur a indiqué 'VOLEUR' dans le formulaire ?
    Faut-il essayer les modèles '_ALEUR', puis 'V_LEUR', puis 'VA_EUR', etc... ? D'autant plus que les recherches utilisant ces caractères spéciaux ne peuvent pas toujours utiliser d'index !
  • le deuxième problème vient donc du manque de performance de ce type de requêtes dès qu'un caractère spécial apparait ailleurs qu'en fin de chaine

Il existe une solution qui semble séduisante et qui met en oeuvre la fonction SQL appelée SOUNDEX() :
cette fonction accepte une chaine en paramètre et retourne une chaine sur 4 caractères qui correspond à sa valeur phonétique.
Malheureusement, l'algorithme utilisé par SOUNDEX() utilise les règles de la prononciation anglaise (qui en doutait ?). Et cette fonction n'est pas "localisée" dans la langue de Molière.

Exemples:

  • en Anglais :

    mysql> SELECT SOUNDEX("steer"),SOUNDEX("stir");
    +------------------+-----------------+
    | SOUNDEX("steer") | SOUNDEX("stir") |
    +------------------+-----------------+
    | S360             | S360            |
    +------------------+-----------------+

  • en Français :

    mysql> SELECT SOUNDEX("seau"),SOUNDEX("sot");
    +-----------------+----------------+
    | SOUNDEX("seau") | SOUNDEX("sot") |
    +-----------------+----------------+
    | S000            | S300           |
    +-----------------+----------------+

Nous décidons alors d'écrire notre propre fonction qui s'appelera PHONEX et qui sera adaptée à notre langue.

2.Conception de la fonction PHONEX

Notre fonction accepte 2 paramètres :

  • une chaine dont il faut calculer la valeur "phonétique"
  • un drapeau capable d'influer sur l'algorithme implémenté afin de conférer un peu de souplesse à la fonction

La fonction retourne une valeur réelle (REAL). Ce choix est la conséquence d'un besoin de performances : il est plus rapide de comparer des réels que des chaines - sans compter le gain en terme de stockage !

Mais il ne tiendra qu'à vous de la modifier pour qu'elle retourne une chaine !

Exemple d'utilisation :

Soit la table suivante :

CREATE TABLE Personne (
    nom CHAR(64) NOT NULL DEFAULT "",
    prenom CHAR(32) NOT NULL DEFAULT "",
    matricule CHAR(8) NOT NULL DEFAULT ""
)

Puisque nous allons rechercher des noms ou des prénoms grâce è une approximation phonétique, nous allons précalculer le valeur phonétique associée à chacun des champs sur lesquels vont porter les recherches.

Nous ajoutons donc 2 champs et la table devient :

CREATE TABLE Personne (
    nom CHAR(64) NOT NULL DEFAULT "",
    pex_nom REAL NOT NULL,
    prenom CHAR(32) NOT NULL DEFAULT "",
    pex_prenom REAL NOT NULL,
    matricule CHAR(8) NOT NULL DEFAULT ""
)

L'insertion d'une ligne dans la table s'écrit alors:

INSERT INTO Personne VALUES ("Doe",PHONEX("Doe"),"John",PHONEX("John"),"matr0001")

La recherche d'une personne dans la table peut alors s'écrire :

SELECT * FROM Personne WHERE pex_prenom = PHONEX("Jean")

3.Règles de reconnaissance phonétiques

Probablement la partie la plus difficile, cette étape consiste à élaborer les règles qui permettent de réduire un mot en un réel en se basant sur sa prononciation phonétique.

Pour écrire ces règles, je me suis inspiré de l'article [BROUARD] ainsi que de mes souvenirs de grammaire française ! Et rien ne vaudra des tests concrets pour vérifier et affiner le fonctionnement de notre algorithme.

L'idée consiste, grâce à des passes multiples (une quinzaine) à simplifier le mot original pour le réduire à ses sons essentiels. Puis, on applique une formule de conversion de la chaine finale en un réel.

L'implémentation est faite en langage C, sans utilisation de recherches de sous-chaines dans des chaines, ni expressions régulières pour obtenir un maximum d'efficacité.

Les règles de calcul pour associer une "valeur" phonétique à une chaine sont basées sur la similitude des sons. Il nous faut donc simplifier les chaines pour en extraire une représentation abstraite d'un point de vue sonore. Si vous êtes un adepte du langage "SMS" vous savez ce que retranscription phonétique signifie !

Les règles adoptées sont les suivantes (et j'engage tout le monde à les améliorer !) :

Règle Description Exemples
R1
  • substitution des caractères accentués par les voyelles "simples"
  • remplacement du "ç" par "ss"
  • remplacement du "y" par un "i"
  • tous les caractères sont convertis en minuscules
Pyrénées -> pirenees
hameçon -> hamesson
R2 remplacement du son "ph" par un simple "f" éléphant -> elefant
R3 suppression des "h" muets, c'est à dire ceux qui ne sont ni précédés d'un "c" ni d'un "s" hache -> ache
R4 remplacement du "g" par "k" devant "an/am/ain/aim" gamin -> kamin
R5
  • remplacement de aina,eina,aima,eima par yna
  • remplacement de aine,eine,aime,eime par yne
  • remplacement de aini,eini,aimi,eimi par yni
  • remplacement de aino,eino,aimo,eimo par yno
  • remplacement de ainu,einu,aimu,eimu par ynu
chaine -> chyne
rainure -> rynure
R6
  • remplacement de eau par o
  • remplacement de oua par 2
  • remplacement de ein par 4
  • remplacement de ain par 4
seau -> so
rein -> r4
bain -> b4
couac ->c2c
R7
  • remplacement de ai par y
  • remplacement de ei par y
  • remplacement de ee par y
  • remplacement de er par yr
  • remplacement de ess par yss
  • remplacement de et par yt
  • remplacement de ez par yz
altesse -> altysse
nez -> nyz
R8 suppression des lettres doublées pelle -> pele
benne -> bene
R9
  • remplacement de "an" par "1"
  • remplacement de "am" par "1"
  • remplacement de "en" par "1"
  • remplacement de "em" par "1"
  • remplacement de "in" par "4"

à condition que ces modèles ne soient ni suivis d'une voyelle ni d'un son "1" à "4"

patient -> pati1t
incorrect -> 1correct
R10 remplacement du "z" par "s" s'il est en tête de mot ou précédé et suivi d'une voyelle ou d'un son "1" à "4" zebu -> zebu
azteque -> azteque
bizarre -> bisarre
R11
  • remplacement de "oe" par "e"
  • remplacement de "eu" par "e"
  • remplacement de "au" par "o"
  • remplacement de "oi" par "2"
  • remplacement de "ou" par "3"
heureux -> erex
paul -> pol
roue -> r3e
R12
  • remplacement de "ch" par "5"
  • remplacement de "sch" par "5"
  • remplacement de "sh" par "5"
  • remplacement de "ss" par "s"
  • remplacement de "sc" par "s" si suivi d'un "i" ou d'un "e"
chat -> 5at
scaralatine -> scarlatine
scie -> sie
R13 remplacement du "c" par "s" s'il est suivi dun "e" ou d'un "i" car -> car
innocence -> inosense
R14
  • remplacement de "c" par "k"
  • remplacement de "q" par "k"
  • remplacement de "qu" par "k"
  • remplacement de "gu" par "k"
  • remplacement de "ga" par "ka"
  • remplacement de "go" par "ko"
car -> kar
gateau -> kato
R15
  • remplacement de "a" par "o"
  • remplacement de "d" et "p" par "t"
  • remplacement de "j" par "g"
  • remplacement de "b" et "v" par "f"
  • remplacement de "m" par "n"
depart -> tetord
homme -> one
R16 (optionnelle) remplacement des "y" (les sons "é") par "e" nez -> nyz -> nez
R17
  • suppression des finales "t","x","s","z"
  • (optionnelle) suppression du "e" final après une consonne (fait en deux fois pour eliminer les finales "ez" par exemple)
heureux -> ere
tetard -> tetor
R18 suppression des lettres doubles (pour la 2ème fois) arrivee -> arive
R19 retourne une chaine d'une taille maximale de 16 caractères et ne contenant que les caractères autorisés.
Au vu des traductions décrites, les caractères obtenus font partie de l'alphabet réduit:
12345efghiklnorstuwxyz
Les caractères qui n'appartiennent pas à cet ensemble sont supprimés

4.Altération de l'algorithme

La fonction phonex2() accepte, outre la chaine à traiter, un 2ème paramètre qui modifie légèrement l'algorithme de traduction phonétique précédent. La valeur du paramètre est la somme de plusieurs drapeaux dont les significations sont :

  • 0x1 : ne supprime pas les "e" finals (par exemple, la chaine "arrivée devient "orife" et non pas "orif")
  • 0x2 : ne convertit pas les "é" en "e" (par exemple, la chaine "arrivez" devient "orify" et non pas "orif")

Libre à vous d'ajouter de nouvelles valeurs et de modifier le comportement de l'algorithme initial !

5.Codage de notre fonction

Nous codons alors la fonction phonex2() ainsi (extrait):

/* liste des caractères autorisés dans la conversion en phonex: */
static unsigned char *finals = "12345efghiklnorstuwxyz";

static void phonex2(unsigned char *copy, unsigned int flag)
{
  unsigned char *p,achar;
  unsigned char *voyelles1 = "aeiouy";
  unsigned char *voyelles2 = "aeiouy1234";

  /* Cas trivial de la chaine vide: */
  if (!*copy) return;

  /* R1:
   * - remplace les accents et autres caracteres "bizarres".
   * - le Y/y devient i
   * - la cédille devient 'ss'
   * - les autres cars. sont mis en minuscules
   */
  p = copy;
  while (*p) {
    if ((*p >= 0xE0 && *p <= 0xE6) || (*p >= 0xC0 && *p <= 0xC6)) { *p++ = 'a'; continue; }
    if ((*p >= 0xE8 && *p <= 0xEB) || (*p >= 0xC8 && *p <= 0xCB)) { *p++ = 'e'; continue; }
    if ((*p >= 0xD2 && *p <= 0xD6) || (*p >= 0xF2 && *p <= 0xF6)) { *p++ = 'o'; continue; }
    if ((*p >= 0xCC && *p <= 0xCF) || (*p >= 0xEC && *p <= 0xEF)) { *p++ = 'i'; continue; }
    if ((*p >= 0xF9 && *p <= 0xFC) || (*p >= 0xD9 && *p <= 0xDC)) { *p++ = 'u'; continue; }
    if (*p == 'Y' || *p == 'y') { *p++ = 'i'; continue; }
    if (*p == 0xC7 || *p == 0xE7) {
      *p++ = 's';
      memmove(p,p+1,strlen(p));
      *p++ = 's';
      continue;
    }
    *p++ = tolower(*p);
  }

  /* R2: Remplace 'ph' par 'f': */
  p = copy;
  while (*p) {
    if (*p == 'p' && *(p+1) == 'h') {
      *p = 'f';
      memmove(p+1,p+2,strlen(p+1));
    }
    *p++;
  }
  
  /* .... code manquant ...
   * code complet disponible sur le Net */

  /* FIN: ne retourne que les caractères autorisés avec un
  * maximum de 16 car. dans la chaine:
  */
  p = copy;
  while (*p && (p-copy) < PHONEX_MAXSZ) {
    if (!strchr(finals,*p)) {
      memmove(p,p+1,strlen(p));
      continue;
    }
    p++;
  }
  *p = '\0';
}

Le code complet de la fonction est disponible à l'adresse indiquée en bas de page...

6.Conversion du résultat en nombre réel

Le mode de conversion est inspiré de [BROUARD] :
comme l'alphabet final comporte 22 symboles, nous allons utiliser les puissances de 22. Pour chaque caractère du résultat final nous obtenons le rang de ce caractère dans l'ensemble des symboles définis par la variable "finals" (voir ci-dessus, l'extrait du code de la fonction phonex2(). Puis nous multiplierons ce rang à par la puissance "i ** 22", où "i" est le rang du caractère dans la chaine.
En fait, le résultat est un "grand nombre", non décimal, qui est obtenu par le code suivant :

/* chiffrement numerique en ignorant les car. non autorises: */
float phonex = 0; /* contient la valeur finale */
p = copy;
indice = 0;
while (*p) {
  unsigned char *rank = strchr(finals,*p);
  /* normalement tous les car. sont corrects */
  phonex += (rank-finals) * powf(indice,base);
  indice++; p++;
}

7.Intégration dans MySQL

Maintenant que nous disposons de notre fonction de calcul phonex2(), nous devons l'intégrer à MySQL.
Pour cela, nous allons ajouter trois fonctions à notre code:

  • phonex_init() : cette fonction optionnelle est appelée par MySQL avant l'appel à phonex() décrite ci-dessous. Son prototype est :

    my_bool phonex_init(UDF_INIT *initid, UDF_ARGS *args, char *message);

    Le paramètre initid est utilisé par les fonctions pour se passer une structure "opaque" pour MySQL.
    Nos besoins sont simples, nous n'avons pas besoin de passer ni valeurs ni paramètres.
    Nous nous contenterons d'indiquer à MySQL que notre fonction phonex() ne retourne jamais NULL. Ce que nous écrirons ainsi :

    initid->maybe_null = 0;

    Le paramètre args est plus utile : il permet de vérifier le nombre et le type des paramètres spécifiés par l'utilisateur lors de l'appel à phonex().

    La structure UDF_ARGS permet de connaitre le nombre de paramètres via le champ argc_count, puis chacun des paramètre est défini par les champs suivants :

    • arg_type[i] : donne le type du paramètre. Les valeurs possibles sont STRING_RESULT, INT_RESULT ou REAL_RESULT
    • arg->args[i] : donne la valeur du paramètre. Ce pointeur doit ensuite être interprété suivant son type.
      • Si le type est INT_RESULT, on obtient la valeur du paramètre ainsi :

        long long int_val;
        int_val = *((long long *)args->arg[i]);

      • Si le type est REAL_RESULT, on obtient de manière similaire la valeur du paramètre ainsi :

        double real_val;
        real_val = *((double *)args->arg[i]);

      • Enfin, si le type est STRING_RESULT, on ne doit pas considérer que l'argument pointe vers une chaine terminée par un caractère nul ('\0'). La longueur de la chaine est donnée par le champ lengths[i].

    Notre fonction phonex_init() doit donc s'assurer des points suivants :

    • phonex() est appelée avec deux paramètres. Le premier doit être une chaine, le deuxième doit être un entier. En cas d'erreur, la fonction d'initialisation a la possibilité de retourner un message d'erreur à MySQL, par l'intermédiaire du paramètre message. Le message d'erreur ne doit pas dépasser MYSQL_ERRMSG_SIZE, soit 80 caractères (la largeur de l'écran). Le code de phonex_init() est alors trivial et devient:


      my_bool phonex_init(UDF_INIT *initid, UDF_ARGS *args, char *message)
      {
        /* ne retourne jamais NULL !*/
        initid->maybe_null = 0;

        /* on améliore en rendant le 2ème paramètre optionnel ! */
        if (args->arg_count < 1 || args->arg_count > 2) {
          strcpy(message,"PHONEX syntax is PHONEX(string[,flag])");
          return 1;
        }

        /* le 1er parm doit être une chaine ! */
        if (args->arg_type[0] != STRING_RESULT) {
          strcpy(message,"PHONEX needs a STRING Parameter");
          return 1;
        }

        /* ...et le 2ème un entier ! */
        if (args->arg_count >= 2 &&args->arg_type[1] != INT_RESULT) {
          strcpy(message,"Second Parameter of PHONEX must be an INT (the flag)");
          return 1;
        }

        /* pas d'erreur */
        return 0;
      }

  • phonex_deinit() : cette fonction optionnelle est appelée par MySQL après l'appel à phonex(). Son prototype est :

    void phonex_deinit(UDF_INIT *initid);

    Cette fonction peut désallouer la mémoire que phonex_init() aurait allouée. Dans notre cas, comme il n'y pas eu d'appel aux fonctions de la famille malloc/calloc(), la fonction phonex_deinit() a un corps vide.

  • Nous devons maintenant réaliser l'interface entre MySQL et notre vraie fonction phonex2(). Pour cela, nous devons écrire une fonction phonex() qui doit se conformer à la spécification suivante :

    double phonex(
      UDF_INIT *initid,
      UDF_ARGS *args,
      char *is_null,
      char *error)

    En effet, suivant le type de la valeur retournée par notre fonction, MySQL impose un prototype particulier. Ici, notre fonction doit retourner une valeur réelle (d'où le type double), et elle reçoit en paramètre initid et args décrits précédemment, ainsi que deux paramètres supplé,mentaires :

    • is_null : doit recevoir la valeur 1 si la valeur retournée par le fonction est le NULL de SQL
    • error : doit recevoir la valeur 1 si la fonction retourne une erreur

    Notre fonction phonex() doit donc appeler la fonction phonex2() codée dans le paragraphe précédent; mais elle doit au préalable recopier le mot à examiner, passé sous forme de chaine, dans un buffer temporaire, car rappelez-vous que MySQL n'assure pas que ce paramètre soit terminé par un '\0'.

    Notez que le fait de dissocier phonex() de phonex2() permet d'invoquer notre fonction phonex2() sans passer par MySQL !

    Le code de phonex() est alors :

    double phonex(
      UDF_INIT *initid,
      UDF_ARGS *args,
      char *is_null,
      char *error)
    {
      unsigned int flag = 0;
      float phonex = 0; /* résultat final */
      int indice = 0;
      int base = strlen(finals);

      /* copie la chaine: */
      unsigned int len = args->lengths[0];
      unsigned char *p,*copy = (unsigned char *)malloc(len+1);
      memcpy(copy,args->args[0],len);
      copy[len] = '\0';

      /* le 2ème parm est optionnel ! */
      if (args->arg_count > 1) {
        flag = *((long long *)args->args[1]);
      }

      /* appel de notre "fameuse fonction": */
      phonex2(copy,flag);

      /* pas de NULL, pas d'erreur */
      *is_null = *error = 0;

      /* chiffrement numerique: */
      p = copy;
      indice = 0;
      while (*p) {
      unsigned char *rank = strchr(finals,*p);
        /* normalement tous les car. sont corrects */
        phonex += (rank-finals) * powf(indice,base);
        indice++; p++;
      }

      free(copy);

      return phonex;
    }

8.Finalisation de l'intégration:

Rien de plus simple :

  • compilons enfin notre programme avec la commande :

    gcc -shared -I/usr/include/mysql -o phonex.so phonex.c

    Vous constatez que vous avez besoin des entêtes pour le développement MySQL. Suivant votre système, ces fichiers peuvent se trouver ailleurs que sous le répertoire /usr/include/mysql.

    L'option -shared indique au compilateur de créer une librairie dynamique. Le nom de cette librairie peut être quelconque - on pourrait même y placer plusieurs fonctions UDF pour MySQL.

  • il faut rendre la librairie accessible pour MySQL :

    le fichier phonex.so doit normalement être placé dans un des répertoires listés dans le fichier /etc/ld.so.conf. En pratique, nous avons constaté que MySQL, suivant ses versions, n'utilisait pas ces répertoires pour rechercher notre librairie. Pour éviter les problèmes lors d'un premier test, je vous suggère de copier la librairie sous /lib ou sous /usr/lib :

    cp phonex.so /lib (il faut être 'root' pour effectuer cette copie !)

  • pour que MySQL s'enrichisse de notre nouvelle fonction, lancez la commande mysql et déclarer la fonction ainsi :

    mysql> CREATE FUNCTION phonex RETURNS REAL SONAME "phonex.so";
    Query OK, 0 rows affected (0.00 sec)

    mysql>

    Attention, respectez bien la casse des caractères pour le nom de la fonction et le nom de la librairie !
    Mais vous pourrez ensuite invoquer cette nouvelle fonction en utilisant son nom en minuscules ou majuscules.

  • Nous pouvons alors tester notre fonction :

    mysql> SELECT PHONEX("seau"),PHONEX("sot");
    +----------------+---------------+
    | PHONEX("seau") | PHONEX("sot") |
    +----------------+---------------+
    |             13 |            13 |
    +----------------+---------------+
    1 row in set (0.00 sec)

    Victoire ! ça marche !

  • Si vous voulez modifier le code de la fonction, il faudra soit arrêter MySQL pour remplacer la librairie phonex.so, soit supprimer l'extension par la commande suivante :

    mysql> DROP FUNCTION phonex;

9.Conclusion

J'espère que cet aperçu sur les possibilités d'extension de MySQL vous a convaincu de l'intérêt et de la simplicité de cet énorme potentiel.

Toutefois, nous n'avons évoqué, ici, que les fonctions "simples", par opposition aux fonctions d'agrégation (comme SUM(), MAX(), AVG()...) qui travaillent sur des lignes multiples. L'écriture de telles fonctions utilise une interface légèrement différente dont vous trouverez les spécifications dans [MYSQL2].

Sachez aussi que MySQL intègre, à partir de sa version 5.1, une nouvelle interface, appelée "plug-ins" qui est amenée à améliorer puis remplacer les fonctions UDF actuelles. Pour cela, une nouvelle API est proposée mais qui ne permet que la création de plug-ins de recherches FULL-TEXT. La manipulation des plug-ins fait aussi intervenir de nouvelles commandes (INSTALL PLUGIN, UNINSTALL PLUGIN et SHOW PLUGINS).

L'adaptation de notre fonction phonex() au futur standard ne devrait toutefois pas poser de problème !

Vous n'avez plus quà implémenter votre extension de rêve pour MySQL...et à la faire partager à la communauté !

Téléchargement

Code source de phonex2.c

Bibliographie

[MYSQL1]
String Comparison Functions
http://dev.mysql.com/doc/refman/5.0/en/string-comparison-functions.html

[BROUARD]
L'art des "Soundex"
http://sql.developpez.com/soundex/

[MYSQL2]
Adding New Functions to MySQL
http://dev.mysql.com/doc/refman/5.0/en/adding-functions.html