La recherche Full Text avec Solr

Configurer un moteur de recherche performant à l'aide d'Apache Lucene/Solr et Apache Tomcat
Solr


précédentsommairesuivant

I. Introduction

I-A. La recherche intuitive

Dans mon expérience, la plupart des sites Internet utilisent une base de données relationnelle (type MySQL, PostgreSQL, Microsoft SQL Server ou autre) pour conserver leurs données. Ces données sont donc enregistrées de manière très structurée, mais elles ne sont accessibles que par le langage SQL.

L'avantage de cette solution est que l'on peut aisément retrouver un enregistrement lié à partir d'un autre : quel est le dernier article écrit dans chaque catégorie, quel est l'âge de la personne dont je suis en train de consulter le profil, etc. Retrouver une donnée élémentaire (un champ) à partir d'une autre donnée élémentaire (un identifiant) est une tâche que SQL accomplit à merveille.

Cependant, le comportement naturel d'un visiteur sur un site Web n'est pas toujours de passer par les menus très hiérarchiques et successifs mis à sa disposition. Prenons l'exemple de Google : combien connaissez-vous d'internautes qui ne prennent plus la peine de configurer des marques pages dans leur navigateur, préférant chercher leurs sites favoris sur Google chaque fois qu'ils en ont besoin ? Eh oui, une très grande proportion des internautes préfère utiliser un moteur de recherche efficace et rapide à une navigation plus efficace mais segmentée. C'est le concept de recherche en langage naturel qui séduit ces internautes.

Il convient de rappeler l'une des grandes faiblesses de SQL : sa pauvreté en matière de permutations de texte (instructions LIKE et REGEXP). Que se passe-t-il lorsqu'un visiteur fait une faute de frappe dans votre moteur de recherche à base de SQL, sans doute n'obtient-il pas de résultats ou pas les résultats attendus ? Ou lorsqu'il recherche un nom propre, a-t-il correctement placé chaque accent, trait d'union ou apostrophe ? Ou bien avez-vous calculé vous-même toutes les permutations possibles et les avez-vous gardées dans votre base de données ? Pensez-vous que vote visiteur, frustré par la faiblesse de votre moteur de recherche, ne va pas très rapidement s'en lasser ? Après avoir effectué la même recherche sur Google, ce même visiteur ne va-t-il pas rapidement se retrouver sur un site concurrent ?

Pire, que se passe-t-il si le contenu lui-même de votre site n'est pas écrit et corrigé à la perfection ? Une proportion de vos documents est vraisemblablement exclue de vos résultats de recherche.

Certes, les moteurs de recherche tel Google fonctionnent bien, mais ce sont aussi des visites qui ne sont pas effectuées sur notre site et, par conséquent, nous ne pouvons pas les inclure dans des études des habitudes de comportement. Ainsi, il serait utile de proposer à nos visiteurs un système de recherche qui se rapproche de celui proposé par les grands moteurs de recherche.

Dans cet article, nous verrons qu'un tel système n'est pas réservé à quelques multinationales. En effet, il existe des solutions open source et gratuites qui répondent à notre besoin : nous présenterons ici Lucene au travers de son extension, Solr.

I-B. La recherche Full-Text

I-B-1. Le concept

Nous partons de l'observation suivante : il est parfaitement illusoire de croire qu'il est possible d'obliger les utilisateurs d'un moteur de recherche à saisir leurs termes sous une forme déterminée (au masculin singulier, en minuscules etc.) car ce n'est pas intuitif. Ainsi, notre moteur de recherche doit être capable d'analyser les termes saisis par l'utilisateur et de trouver des correspondances dans le texte indexé.

La recherche full text est le principe d'opérer des traitements (l'indexation) sur du texte afin d'y retrouver plus facilement des mots. Ce procédé consiste à effectuer une suite de manipulations sur chacun des mots du texte afin d'augmenter la pertinence des recherches.

En règle générale, les interfaces de recherche full text permettent de segmenter le texte en mots (tokens) selon diverses règles (espaces, ponctuation, changement de casse etc.). Les manipulations possibles sur ces mots sont diverses : modifier la casse, remplacer les lettres accentuées, etc. Outre ces traitements simples (et qui ne sont pas toujours judicieux), il existe deux procédés plus complexes mais qui donnent de meilleurs résultats : la recherche par radicaux (lexèmes) et la recherche par consonances (phonétique).

I-B-2. La recherche par lexèmes

I-B-2-a. Introduction

Je ne suis linguiste qu'à mes heures perdues et je ne maîtrise pas à la perfection le vocabulaire que je vais utiliser dans ce chapitre. Je prie le lecteur de bien vouloir faire preuve d'indulgence à mon égard. Je corrigerai cet article si des imperfections sont relevées.

Le wiki de SolrAnalyzers, Tokenizers, and Token Filters décrit trois méthodes principales de recherche par lexèmes. La racinisation (Porter ou KStem) permet de retrouver la forme élémentaire du mot (son lexème). À l'inverse, la flexion détermine toutes les variantes du mot (déclinaisons, conjugaisons, ajout d'affixes ou modifications du radical). Enfin, le projet Hunspell permet d'effectuer divers traitements sur les mots : correction orthographique, racinisation, flexion, etc. en tenant compte des règles grammaticales de la langue spécifiée.

En contexte linguistique, il me semble que cette comparaison est inexacte dans la mesure où la flexion ne donne pas des lexèmes mais des mots. Cependant, cette simplification sera suffisante pour la mise en application qui nous intéresse ici.

Ce mode de recherche est très efficace pour trouver les correspondances des mots faisant partie du vocabulaire d'une langue, mais sa pertinence est bien plus faible pour les noms propres, les néologismes et les autres mots n'en faisant pas partie.

I-B-2-b. Racinisation

Un lexème est la forme élémentaire de chaque mot, c'est en quelque sorte sa racine linguistique. C'est sa forme, réduite au point de ne pas avoir d'existence dans la langue écrite ou orale, mais qui sert de point de départ pour toutes les formes dérivées de ce mot. Le procédé permettant d'obtenir le lexème d'un mot s'appelle la racinisation, ou stemming en anglais.

Le lexème est le point de départ pour constituer les lemmes, qui sont eux-mêmes le point de départ pour constituer les mots. La racinisation est un procédé complexe et il est différent dans chaque langue, c'est pourquoi il n'existe pas d'algorithme informatique pour toutes les langues. De même, les algorithmes existants ne sont pas implémentés dans tous les langages informatiques. Ainsi, le langage informatique convenant le mieux à vos choix techniques (Java, .NET, PHP, etc.) n'a peut-être pas d'implémentation d'un algorithme de racinisation pour les langues qui vous intéressent. Un projet, cependant, facilite leur implémentation : SnowballSnowball is a language in which stemming algorithms can be easily represented. Il présente une liste d'exemples pour chaque algorithme, notamment en françaisHere is a sample of French vocabulary, with the stemmed forms that will be generated with this algorithm.

Voici une liste de mots que nous utiliserons dans cette introduction (les traitements ont été effectués à l'aide de Solr 1.4) :

Tableau 1 : Racinisation (mots de la langue française)
Mot Lexème anglais Lexème français Lexème espagnol
développa développa développ developp
développable développ développ developp
développaient développai développ developpaient
développante développant développ developp
développement développ développ developpement
développer développ développ developp
développeur développeur développeur developpeur
développeuse développeus développ developpeus
développons développon développon developpons
enveloppe envelopp envelopp envelopp

Nous pouvons aisément voir que la plupart des mots ont un lexème français commun : "développ". Ainsi, une recherche sur l'un de ces mots pourrait permettre de sortir des résultats contenant la plupart des autres mots. D'un point de vue utilisateur, c'est effectivement souhaitable.

Il convient de rappeler que les lexèmes présentés ici sont déterminés par un programme informatique. Un être humain connaissant la langue française réduirait probablement toutes les conjugaisons de "développer" en "développ" ; de même, le mot "développeur" serait sans doute réduit au même lexème que pour "développeuse", c'est-à-dire "développ".

Afin de mieux comprendre en quoi la racinisation n'est pas adaptée aux noms propres, voici la racinisation des exemples de Frédéric Brouard (cf. la partie phonétique ci-dessous) :

Tableau 2 : Racinisation (noms propres)
Mot Lexème anglais Lexème français Lexème espagnol
MARTIN martin martin martin
BERNARD bernard bernard bernard
FAURE faur faur faur
PEREZ perez per perez
GROS gros gros gros
CHAPUIS chapui chapuis chapuis
BOYER boyer boi boy
GAUTHIER gauthier gauthi gauthi
REY rey rey rey
BARTHELEMY barthelemi barthelemy barthelemy
HENRY henri henry henry
MOULIN moulin moulin moulin
ROUSSEAU rousseau rousseau rousseau

Nous pouvons voir ici le point faible de la racinisation pour les noms propres. La plupart des mots de ce dernier tableau ne sont pas réduits. Ceux qui ont été réduits ont généralement été confondus avec un verbe dont l'algorithme a cru reconnaître une forme conjuguée ou à l'infinitif et qu'il a réduit à son lexème supposé (mais incorrect).

I-B-2-c. Flexion

La flexion consiste à dériver un mot afin d'obtenir toutes ses représentations possibles : déclinaisons grammaticales (genre et nombre), conjugaisons, préfixes, suffixes et modifications du radical. C'est l'approche inverse de la racinisation, mais l'effet en est souvent proche.

En informatique, plusieurs programmes et bibliothèques permettent de fléchir un mot : ispell (d'adoption historiquement plus large), aspell/pspell (remplacement d'ispell), MySpell/Hunspell (créés par OpenOffice.org et utilisés par Mozilla), etc. Leur nombre croissant, un projet connexe a vu le jour : EnchantAbiWord: Word Processing for Everyone, qui propose une API commune et qui permet donc d'utiliser n'importe lequel de ces programmes avec les mêmes appels de fonctions.

L'inconvénient majeur de la méthode par flexion est qu'elle ne donne de bons résultats que si l'on part d'un mot équivalent au lexème (mot non fléchi). Par exemple, si dans le texte se trouve le mot "développaient" et qu'un utilisateur cherche le mot "développement", une méthode par flexion est incapable de les faire correspondre. En revanche, une méthode par racinisation permet de retrouver le lexème commun à ces deux mots : "développ".

Voici la flexion des exemples cités pour la racinisation :

Tableau 3 : Exemples de flexion avec OpenOffice.org 3.2.1 Writer
Lexème ou mot Flexions en français
développ développa, développe, développé
développaien développaient, développante, développable, développement, développable
développeme développement, développeuse, développe, développante
développon développons, développante, développée, développé, développable

À l'évidence, OpenOffice Writer ne se limite pas à de la flexion : il fait aussi une mesure de racinisation. Cela donne un exemple biaisé. Il est même possible qu'OOo effectue également des traitements supplémentaires car il me proposait également "envelopper". Néanmoins, cette liste d'exemples vous donne une idée de ce que permet d''obtenir le procédé de flexion.

I-B-3. La recherche phonétique

I-B-3-a. Introduction

La phonétique consiste à représenter la manière dont un mot se prononce. Certains dictionnaires proposent une représentation phonétique des mots, et l'enseignement des langues vivantes requiert habituellement l'accoutumance à ces mêmes signes.

En informatique, la recherche informatique ne consiste pas à représenter les mots avec des signes spéciaux comme en phonétique, mais à trouver une représentation simplifiée à base de caractères ASCII, généralement en majuscules. Des exemples de telles représentations sont présentés dans l'article L'art des SoundexMécanismes de recherche portant sur la consonance des mots par Frédéric Brouard.

Avec un ensemble de résultats naturellement large, ce mode de recherche est très pratique pour complémenter la recherche par lexèmes. Utilisé seul, en revanche, il risque de donner un trop grand nombre de "faux positifs".

I-B-3-b. Soundex

Soundex est un algorithme décrit en 1918 par Robert C. Russell and Margaret K. Odell. Il permet de décrire la prononciation des mots anglais au moyen de lettres et de chiffres.

Soundex est prévu exclusivement pour la langue anglaise et, même dans cette langue, il a des limites.

Dans les exemples présentés ici, nous supprimons tous les accents avant de calculer les codes Soundex.

I-B-3-c. Metaphone et Double Metaphone

Les algorithmes Metaphone (1990) et Double Metaphone (2000), tous deux par Lawrence Philips, permettent une meilleure représentation des mots pour la langue anglaise. Le Double Metaphone permet en principe de mieux identifier le contexte d'utilisation de chaque mot, et ce dans diverses langues (notamment le français).

Pour ma part, je ne suis pas persuadé qu'il soit possible de déterminer la prononciation d'un mot, et donc sa représentation informatique, sans savoir dans quelle langue (voire même dans quel dialecte local) il est utilisé. Toutefois, Double Metaphone semble être l'algorithme bénéficiant de la plus vaste adoption de nos jours.

I-B-3-d. Autres algorithmes

J'ai mentionné plus haut l'article de Frédéric Brouard sur L'art des Soundex : l'auteur y propose une alternative adaptée à la langue française, qu'il a baptisée Phonex et dont il propose l'implémentation dans plusieurs langages informatiques. Je laisse au lecteur le soin de déterminer s'il est judicieux de l'utiliser.

I-B-3-e. Exemples

Voici les équivalents phonétiques de nos exemples de racinisation et de flexion (les traitements ont été effectués à l'aide de Solr 1.4) :

Tableau 4 : Traitements phonétiques (mots de la langue française)
Mot Soundex Refined Soundex Metaphone Double Metaphone
développa D141 D60207010 TFLP TFLP
développable D141 D60207010170 TFLP TFLP
développaient D141 D6020701086 TFLP TFLP
développante D141 D60207010860 TFLP TFLP
développement D141 D602070108086 TFLP TFLP
développer D141 D602070109 TFLP TFLP
développeur D141 D602070109 TFLP TFLP
développeuse D141 D6020701030 TFLP TFLP
développons D141 D6020701083 TFLP TFLP
enveloppe E514 E08207010 ENFL ANFL

Pour comparaison, voici les exemples de Frédéric Brouard :

Tableau 5 : Traitements phonétiques (noms propres)
Mot Soundex Refined Soundex Metaphone Double Metaphone
MARTIN M635 M809608 MRTN MRTN
BERNARD B656 B1098096 BRNR PRNR
FAURE F600 F2090 FR FR
PEREZ P620 P10905 PRS PRS
GROS G620 G4903 KRS KRS
CHAPUIS C120 C30103 KPS XPS
BOYER B600 B109 BYR PR
GAUTHIER G360 G40609 K0R K0, KTR
REY R000 R90 R R
BARTHELEMY B634 B109607080 BR0L PR0L, PRTL
HENRY H560 H0890 HNR HNR
MOULIN M450 M80708 MLN MLN
ROUSSEAU R200 R9030 RS RS

I-B-4. Synthèse des traitements linguistiques

Voici une synthèse permettant d'identifier quel traitement linguistique est le plus efficace dans chaque situation :

Tableau 6 : Traitements linguistiques (mots de la langue française)
Mot Lexème anglais Lexème français Lexème espagnol Soundex Refined Soundex Metaphone Double Metaphone
développa développa développ developp D141 D60207010 TFLP TFLP
développable développ développ developp D141 D60207010170 TFLP TFLP
développaient développai développ developpaient D141 D6020701086 TFLP TFLP
développante développant développ developp D141 D60207010860 TFLP TFLP
développement développ développ developpement D141 D602070108086 TFLP TFLP
développer développ développ developp D141 D602070109 TFLP TFLP
développeur développeur développeur developpeur D141 D602070109 TFLP TFLP
développeuse développeus développ developpeus D141 D6020701030 TFLP TFLP
développons développon développon developpons D141 D6020701083 TFLP TFLP
enveloppe envelopp envelopp envelopp E514 E08207010 ENFL ANFL
Tableau 7 : Traitements linguistiques (collisions)
Mot Lexème anglais Lexème français Lexème espagnol Soundex Refined Soundex Metaphone Double Metaphone
accident (en, fr) accid accident accident A235 A0306086 AKST AKST
accede (en) acced acced acced A230 A03060 AKST AKST
accéder (fr) accéder acced acced A236 A030609 AKKT AKTR
acid (en) acid acid acid A230 A0306 AST AST
acide (fr) acid acid acid A230 A03060 AST AST
Tableau 8 : Traitements linguistiques (noms propres)
Mot Lexème anglais Lexème français Lexème espagnol Soundex Refined Soundex Metaphone Double Metaphone
MARTIN martin martin martin M635 M809608 MRTN MRTN
BERNARD bernard bernard bernard B656 B1098096 BRNR PRNR
FAURE faur faur faur F600 F2090 FR FR
PEREZ perez per perez P620 P10905 PRS PRS
GROS gros gros gros G620 G4903 KRS KRS
CHAPUIS chapui chapuis chapuis C120 C30103 KPS XPS
BOYER boyer boi boy B600 B109 BYR PR
GAUTHIER gauthier gauthi gauthi G360 G40609 K0R K0, KTR
REY rey rey rey R000 R90 R R
BARTHELEMY barthelemi barthelemy barthelemy B634 B109607080 BR0L PR0L, PRTL
HENRY henri henry henry H560 H0890 HNR HNR
MOULIN moulin moulin moulin M450 M80708 MLN MLN
ROUSSEAU rousseau rousseau rousseau R200 R9030 RS RS

Il apparaît que les algorithmes phonétiques sont intéressants pour les noms propres, surtout dans la mesure où ces types de mots peuvent revêtir différentes orthographes pour une même prononciation. Les mots faisant partie d'une langue, pour leur part, sont aisément retrouvés par la racinisation. En revanche, appliqués aux mots faisant partie d'une langue, les traitements phonétiques donnent beaucoup de faux positifs. Enfin, appliquée aux noms propres, la racinisation donne trop peu de résultats pour être utile.

I-B-5. Les moteurs full-text indépendants

Fondamentalement, Solr est un moteur de recherche Full Text (ou texte plein en français). Nous pourrions donc utiliser un moteur open source qui s'intègre plus facilement à notre SGBD, comme par exemple SphinxFree open-source SQL full-text search engine pour les moteurs MySQL et PostgreSQL. Malheureusement, la plupart des moteurs full text (du moins ceux sur lesquels je me suis renseigné) sont faibles pour la racinisation (ou stemming en anglais) de la langue française, c'est-à-dire retrouver la racine de chaque mot et s'en servir pour effectuer les comparaisons.

Par exemple, toutes les conjugaisons d'un verbe sont en fait des variantes du lexème de ce verbe, et une recherche sur le mot "développer" devrait également renvoyer des documents sur "développez", "développe", "développons" etc. Il en va de même pour l'accord du genre et du nombre et pour toute une série de déclinaisons possibles.

Solr implémente différents algorithmes de racinisation et pour un nombre de langues parfois supérieur aux autres moteurs. Malgré le nom du filtre utilisé par Solr (SnowballPorterFilter) suggérant l'exclusivité de l'algorithme Porter, il permet en réalité d'utiliser différents algorithmes. Il y en a notamment trois pour la langue anglaise : Porter, Porter2 et Levins. Un plugin permet également d'utiliser KStem mais des conflits de licence empêchent ce plugin d'être distribué avec Solr, il doit donc être compilé par l'utilisateur.

Nous avons vu précédemment que, si elles sont utilisées seules, les méthodes de recherche par lexèmes ou phonétique ne sont pas suffisantes. Sans l'une, il est impossible de chercher des noms propres. Sans l'autre, les résultats contiennent trop de faux positifs et ils omettent les variantes grammaticales des mots.

Voyons ci dessous quelles stratégies d'analyse linguistique sont proposées par les moteurs full-text open source énumérés par WikipédiaFull text search à l'heure de l'écriture de ces lignes :

Tableau 9 : Les moteurs full-text open source et leurs fonctionnalités d'analyse linguistique
Moteur Recherche par lexèmes Recherche phonétique Correction
DataparkSearchDataparkSearch Engine (Licence GNU GPL) Par flexion (ispell) Non Oui (aspell)
FerretHigh-performance, full-featured text search engine library written for Ruby (Licence MIT) Multilingue (cf. listeClass: Ferret :: Analysis :: StemFilter) Non Non
htdigWWW Search Engine Software (GNU GPL) Oui (ispell) Soundex, Double Metaphone Oui (ispell)
mnoGoSearchmnoGoSearch web search engine software (Licence GNU GPL ou propriétaire) Par flexion (ispell) Soundex Non
Swish-eSimple Web Indexing System for Humans - Enhanced (Licence GNU GPL) Oui Soundex, Double Metaphone Non
XapianOpen Source Search Engine Library (Licence GNU GPL) Multilingue (cf. listeNoteworthy features of Xapian include) Non Non
SphinxFree open-source SQL full-text search engine (Licence GNU GPL) Anglais et russe Via le SGBD Non
Apache (Lucene) SolrOpen source enterprise search platform (Licence Apache) Multilingue (cf. listesolr.SnowballPorterFilterFactory), par flexion ou par racinisation Soundex, Double Metaphone Oui

Partant de ces observations et en nous rappelant le constant précédent (nous avons besoin à la fois de la recherche par lexèmes et phonétique), le seul moteur adapté à nos besoins est : Apache Solr.

I-B-6. Fonctionnalité full-text dans les SGBD

Certains SGBD ont des fonctionnalités full-text suivant la norme ISO/IEC 13249-2 du langage SQL. Si vous souhaitez les essayer, voici quelques liens :

Microsoft SQL Server Express :
Oracle Express :
PostgreSQL :
MySQL Community Server

Si tous ces moteurs ont des fonctionnalités full-text, pourquoi choisir Solr ? L'une des raisons est que Solr offre bien plus de fonctionnalités que ce mode de recherche paramétrable : il permet également de renvoyer des filtres (facettes), des statistiques, un ensemble de documents similaires à un document donné, des corrections d'orthographe, etc. De plus, un index Solr peut être utilisé comme source de données pour diverses applications.

I-C. Remerciements

Comme pour la rédaction de tout article, j'ai un certain nombre de personnes à remercier pour leur soutien ou pour leurs corrections : Elsa T., Pierre R., tvibesProfil de tvibes, nils nicolasProfil de nils nicolas.


précédentsommairesuivant

Vous avez aimé ce tutoriel ? Alors partagez-le en cliquant sur les boutons suivants : Viadeo Twitter Facebook Share on Google+   

  

Les sources présentées sur cette page sont libres de droits et vous pouvez les utiliser à votre convenance. Par contre, la page de présentation constitue une œuvre intellectuelle protégée par les droits d'auteur. Copyright © 2010 Guillaume Rossolini. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.