Dans le cadre de divers développements à Octopuce, nous avons dû mettre en oeuvre un moteur de recherche pour plusieurs de nos clients, sur une application initialement écrite en PHP5.
Nous avons tout d’abord pensé utiliser Lucene, le système d’indexation et de recherche de la fondation Apache, écrit en Java. Or, il advient que pour pouvoir l’utiliser depuis une application PHP, nous devons passer par php-java-bridge, qui semble se comporter très bizarrement quand l’index est gros, les requêtes compliquées, ou leur nombre important…
Nous avons aussi essayé la version PHP du système Lucene, mis en oeuvre par les développeurs du fabuleux Zend Framework, mais autant leur framework est fabuleux, autant leur version de Lucene n’est visiblement qu’un proof of concept difficilement utilisable sur des bases ou des charges importantes.
Nous avons donc fini par revenir au bon vieil index MySQL Full-Text, qui d’une part s’est nettement amélioré depuis ses premières versions, mais auquel nous avons ajouté des améliorations « à notre sauce » afin qu’il puisse chercher plus efficacement dans du texte en français.
Pour cela, nous lui avons ajouté 2 concepts :
- L’indexation non pas des mots, mais des racines de mots, en utilisant un algorithme dit de « stemming » de Martin Porter. ainsi, « moteurs » devient « moteur » et « partirons » devient « partir », ce qui nous permet d’indexer et rechercher en ne dépendant pas des pluriels ou conjugaisons. Pour cet index, nous utilisons un module PECL de PHP (ajout de fonctions natives à PHP, généralement écrites en langage C), nommé stem, qui permet de déterminer le stemming (la racine d’un mot) de mots de nombreuses langues (dont le français).
- Un second index contient non pas les mots, mais les phonèmes de ces mots, ce qui nous permet de trouver quand même un mot lorsqu’il est mal orthographié. Pour cela, MySQL contient nativement l’algorithme soundex, mais ce dernier n’étant pas adapté à la langue française (par exemple casque et kasque sont différents, merci Serge pour cet exemple…), nous avons dû trouver autre chose…
Soundex 2 FR
J’ai retrouvé dans mes vieux livres un certain SQL avancé, de Joe Celko (ISBN 978-2711786503) dans lequel un algrithme soundex en français est décrit. De là, je suis ensuite tombé sur un article de Florent Carlier, de l’Université du Mans
Cet article détaille le fonctionnement des algorithmes soundex et de ses variantes en français. Une mise en oeuvre en python est par ailleurs fournie. N’ayant pas trop envie de me baser sur cette version, et ayant bien l’intention d’en faire une fonction native de PHP5, j’ai donc réimplémenté l’algorithme soundex2_fr en langage C, afin non seulement de bénéficier de la rapidité du C, mais de pouvoir facilement en faire une fonction de PHP5 à travers un module PECL …
L’avantage de cet algorithme est son adaptation à la langue française, à travers des phonèmes tel PH qui se transforme en F, ou les spécifiques GU Ç, etc. Ainsi, notre fameux kasque se traduit KSK, et casque aussi !
Vous trouverez donc ci-joint le programme en C soundex2.c, qui prend en entrée standard un mot par ligne, et retourne à chaque fois son équivalent en code soundex2_fr (4 caractères). Il quitte quand on lui retourne une chaîne vide.
Ce programme est distribué sous licence BSD, l’auteur étant Benjamin Sonntag. Cela signifie en gros que vous pouvez l’utiliser pour tout usage y compris dans des logiciels propriétaires, y compris sans fournir les sources. La seule condition est de ne pas altérer sa paternité (cela dit, on parle de 150 lignes de C là, hein…). Il est par ailleurs fourni sans aucune garantie (enfin, je suis conscient qu’il utilise la fonction strcopy d’une manière non documentée(…)).
- Source du demon Soundex2 en français