Racinisation

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En linguistique, la racinisation ou désuffixation (anglais : stemming) est un procédé de transformation des flexions en leur radical ou racine (anglais : stem).

La racine d’un mot correspond à la partie du mot restante une fois que l’on a supprimé son (ses) préfixe(s) et suffixe(s), à savoir son radical. Contrairement au lemme qui correspond à un mot réel de la langue, la racine ne correspond généralement pas à un mot réel. Par exemple, le mot « chercher » a pour radical « cherch » qui ne correspond pas à un mot réel. Par contre dans l’exemple de « frontal » , le radical est « front » qui lui l’est.

Les techniques utilisées pour ce faire reposent généralement sur une liste d’affixes (suffixes, préfixes, postfixe, antéfixes) de la langue considérée et sur un ensemble de règles de racinisation/désuffixation construites a priori qui permettent, étant donné un mot de trouver sa racine.

Un programme informatique de racinisation est appelé un racinisateur (anglais : stemmer). Les algorithmes les plus connus ont été développés par Julie Beth Lovins (1968)[1] et Martin Porter (1980)[2]. La racinisation est un procédé fréquent dans les applications de traitement automatique du langage naturel, par exemple dans la traduction automatique, la recherche d'information (reconnaissance d'entités) et l'indexation des moteurs de recherche.

Exemples[modifier | modifier le code]

Par exemple, en anglais, la racinisation de "fishing", "fished", "fish" et "fisher" donne "fish". Si on ne conservait dans l'index que les mots tels quels, il serait impossible lors d'une recherche de faire référence aux documents comportant uniquement le mot "fishing" en cherchant "fisher". Grâce à la racinisation on sait qu'ils partagent la même racine et qu'à priori ils font partie du même lexique.

Les différents algorithmes[modifier | modifier le code]

Ces divers algorithmes de racinisation procèdent en deux étapes : un pas de désuffixation qui consiste à ôter aux mots des terminaisons prédéfinies les plus longues possibles, et un pas de recodage qui ajoute aux racines obtenues des terminaisons prédéfinies. L'algorithme de Lovins fait les deux étapes séparés, mais celui de Porter fait les deux étapes en simultané.

Il est important de noter que les racines fournies par l’algorithme de Porter ne sont pas forcément de véritables morphèmes.

Deux principales familles de stemmers sont présentes dans la littérature : les stemmers algorithmiques et ceux utilisant un dictionnaire[3].

Un stemmer algorithmique va être souvent plus rapide et va permettre d'extraire des racines de mots inconnus (en un sens, tous les mots qu'il rencontre lui sont inconnus). Il va cependant avoir un taux d'erreur plus élevé, groupant ensemble des mots qui ne devraient pas l'être (sur-racinisation, ou over-stemming).
L'approche par dictionnaire quant à elle ne fait pas d'erreur sur les mots connus, mais en produit sur ceux qu'elle ne liste pas. Elle est aussi plus lente, et nécessite malgré tout la suppression de suffixes avant d'aller chercher la racine correspondante dans le dictionnaire.

Algorithme de Porter[modifier | modifier le code]

L'algorithme développé par Porter se compose d'une cinquantaine de règles de racinisation/désuffixation classées en sept phases successives (traitement des pluriels et verbes à la troisième personne du singulier, traitement du passé et du progressif,...). Les mots à analyser passent par tous les stades et, dans le cas où plusieurs règles pourraient leur être appliquées, c'est toujours celle comprenant le suffixe le plus long qui est choisie. La racinisation/désuffixation est accompagnée, dans la même étape, de règles de recodage. Ainsi, par exemple, "troubling" deviendra "troubl" par enlèvement du suffixe marqueur du progressif -ing et sera ensuite transformé en "trouble" par application de la règle "bl" devient "ble". Cet algorithme comprend aussi cinq règles de contexte, qui indiquent les conditions dans lesquelles un suffixe devra être supprimé. La terminaison en -ing, par exemple, ne sera enlevée que si le radical comporte au moins une voyelle. De cette manière, "troubling" deviendra "troubl", nous l'avons vu, alors que "sing" restera "sing".

Détail de l'algorithme de Porter[4][modifier | modifier le code]

Soit \scriptstyle v représente une voyelle (y est considéré comme une voyelle s'il est précédé par une consonne), \scriptstyle c représente une consonne; et soit \scriptstyle V représente une suite de voyelles, \scriptstyle C représente une suite de consonnes, alors, un mot en anglais peut être de l'une des 4 formes suivantes:

  • \scriptstyle CVCV\ldots C
  • \scriptstyle CVCV\ldots V
  • \scriptstyle VCVC\ldots C
  • \scriptstyle VCVC\ldots V

ce qui peut se représenter par \scriptstyle C?VCVC\ldots V? ou \scriptstyle C?(VC)^mV?, où m est appelée la mesure d'un mot. Les valeurs différents présent les mots différents:

  • m=0: tree, by
  • m=1: trouble, oats, trees, ivy
  • m=2: troubles, private, oaten, orrery

Les règles de désuffixation/racinisation sont exprimées sous la forme \scriptstyle (condition) S_1 \mapsto S_2 ce qui signifie que si un mot se termine par \scriptstyle S_1 et que le préfixe satisfait la condition alors le suffixe \scriptstyle S_1 est remplacé par \scriptstyle S_2

  • \scriptstyle ^*e : le préfixe se termine par la lettre \scriptstyle e
  • \scriptstyle ^*v^* : le préfixe contient une voyelle
  • \scriptstyle ^*d : le préfixe se termine par une consonne doublée
  • \scriptstyle ^*o : le préfixe se termine par \scriptstyle cvc où le second \scriptstyle c n'est ni \scriptstyle w, ni \scriptstyle x, ni \scriptstyle y.

Il est possible d'utiliser des opérateurs booléens: et, ou, non

Racines obtenues par le raciniseur de Porter[5]

Étape 1

a

  • SSESSS
  • IESI
  • SSSS
  • S

caresses → caress
ponies → poni
caress → caress
cats → cat

b

  • (m>0) EEDEE
  • (*v*) ED →
  • (*v*) ING

feed → feed, agreed → agree
plastered → plaster, bled → bled
motoring → motor, sing → sing

c

  • (*v*) Y → I

happy → happi, sky → sky

Étape 2

  • (m>0) ATIONALATE
  • (m>0) TIONALTION
  • (m>0) ENCIENCE
  • (m>0) ANCIANCE

relational → relate
conditional → condition, rational → rational
valenci → valence
hesitansi → hesitance

Étape 3

  • (m>0) ICATEIC
  • (m>0) ATIVE
  • (m>0) ALIZEAL
  • (m>0) ICITIIC

triplicate → triplic
formative → form
formalize → formal
electriciti → electric

Étape 4

  • (m>1) AL
  • (m>1) ANCE
  • (m>1) ENCE
  • (m>1) ER

revival → reviv
allowance → allow
inference → infer
airliner → airlin

Étape 5

  • (m>1) E
  • (m=1 and not *o) E
  • (m>1 and *d and *L) → lettre non doublée

probate → probat, rate → rate
cease → ceas
controll → control, roll → roll

Tester cet algorithme avec 2 mots: Generalizations et Oscillators

Generalizations
étape 1: Generalization
étape 2: Generalize
étape 3: General
étape 4: Gener
Oscillators
étape 1: Oscillator
étape 2: Oscillate
étape 4: Oscill
étape 5: Oscil

L'algorithme de Porter est distribué librement et a été implanté dans de nombreux langages. En 2000 Martin Porter fournit sa propre implémentation[6]de son algorithme dans plusieurs langages car les autres contenant de légères failles. L'algorithme de Porter est efficace pour l'anglais mais pas très adapté au français. Un autre algorithme est donc ensuite développé pour le français.

Carry, un algorithme de racinisation pour le français[modifier | modifier le code]

Tout comme celui de Porter, l'algorithme de Carry se déroule en diverse étapes par lesquelles les mots à traiter passent successivement. Selon les règles, quand l'analyseur reconnaît un suffixe de la liste, soit il le supprime, soit il le transforme. C'est ici aussi le suffixe le plus long qui détermine la règle à appliquer[7].

Les règles de Carry ont été proposées pour l'étude de la morphologie de français, et ils sont téléchargeables gratuitement sur le site du projet GALILEI[8] (Generic Analyser and Listener for Indexed and Linguistics Entities of Information).

Algorithme de Paice/Husk[9][modifier | modifier le code]

L'algorithme de Paice/Husk appartient à la famille des stemmers algorithmiques. Il se base sur un ensemble de règles pour extraire les racines, et qui plus est stocke ces règles en dehors du code. Ainsi, il est possible de traiter de la même façon une nouvelle langue à partir d'un autre ensemble de règles sans réécrire le code, moyennant quelques ajustements (pour chaque langue, la liste des voyelles acceptées et les règles de validité des racines doivent être fournies). Ainsi l'algorithme est plus facilement portable à la gestion d'une nouvelle langue.

Cet algorithme a été développé par Chris Paice à l’Université Lancaster dans les années 80. Il a ensuite été codé en Pascal, C, PERL et Java.

L'implémentation de l'algorithme de Paice/Husk est composée d'un ensemble de fonctions qui vont utiliser les règles d'extraction de racines applicables au mot fourni en entrée et vérifier l'acceptabilité de la racine proposée.

Racinisation vs. lemmatisation[modifier | modifier le code]

Racinisation et lemmatisation sont deux notions très proches, mais il y a des différences fondamentales:

  1. Les méthodes utilisées pour la lemmatisation et la désuffixation ne sont pas les mêmes
  2. La lemmatisation a pour objectif de retrouver le lemme d'un mot, par exemple l'infinitif pour les verbes. La racinisation consiste à supprimer la fin des mots, ce qui peut résulter en un mot qui n'existe pas dans la langue. Par exemple, le résultat de la désuffixation pour le mot "dividing" en anglais est "divid", qui n'existe pas en anglais.
Racinisation (stemming
obtention d'une forme tronquée du mot, commune à toutes les variantes morphologiques
  • Suppression des flexions
  • Suppression des suffixes
Ex : cheval, chevaux, chevalier, chevalerie, chevaucher⇒« cheva » (mais pas « cavalier »)
But: faire augmenter le rappel en RI
Risque: faire baisser la précision
  • La racinisation conduit à des formes qui ne sont pas des mots. C'est donc un traitement final, qui n'autorise rien de plus fin derrière.
  • La racinisation agrège aussi des formes très différentes
marmaille, marmitemarm
  • La racinisation est très rapide, la lemmatisation s'inscrit dans le processus d'étiquetage morphosyntaxique
Lemmatisation 
obtention de la forme canonique (le lemme) à partir du mot
  • Pour un verbe: sa forme à l'infinitif
  • Pour un nom, adjectif, article, ... : sa forme au masculin singulier
  • La lemmatisation n'agrège que les variantes flexionnelles
(chevalchevaux) ≠ chevaleriechevauche

Application[modifier | modifier le code]

Les moteurs de recherche utilisent des stemmers pour améliorer la recherche d'information. Les mots-clés d'une requête ou d'un document sont représentés par leurs racines plutôt que par les mots d'origine. Plusieurs variantes d'un terme peuvent ainsi être groupées dans une seule forme représentative, ce qui réduit la taille du dictionnaire, c'est-à-dire le nombre de termes distincts nécessaires pour représenter un ensemble de documents. Un dictionnaire de taille réduite permet de gagner à la fois de l'espace et du temps d'exécution. Mais stemmers fait aussi baisser la précision.

Références[modifier | modifier le code]

Cet article est fondé sur une traduction de la Free On-line Dictionary of Computing et est utilisé avec permission selon la GFDL.

  1. Julie Beth Lovins (1968). Development of a stemming algorithm. Mechanical Translation and Computational Linguistics 11:22–31.
  2. site official d'algorithme de Porter: http://tartarus.org/~martin/PorterStemmer/
  3. Racinisateur de Paice/Husk: http://alx2002.free.fr/utilitarism/stemmer/stemmer_fr.html
  4. http://www-igm.univ-mlv.fr/~lecroq/cours/porter.pdf
  5. http://www.limsi.fr/~xtannier/fr/Enseignement/tal_eisd/M2PRO_TAL_Morphosyntaxe.pdf
  6. http://tartarus.org/~martin/PorterStemmer/
  7. M. Paternostre, P. Francq, J. Lamoral. Carry, un algorithme de désuffixation pour le français
  8. http://www.galilei.ulb.ac.be
  9. site officiel d'algorithme de Paice/Husk: http://www.comp.lancs.ac.uk/computing/research/stemming/

Voir aussi[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

Liens externes[modifier | modifier le code]