Racinisation

Racinisation

Type	Canonique (informatique)

En linguistique, la racinisation ou désuffixation est un procédé de transformation des flexions en leur radical ou racine. 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 terme issu de l’usage ordinaire des locuteurs de la langue, la racine ne correspond généralement qu’à un terme résultant de ce type d’analyse. Par exemple, le mot chercher a pour radical cherch qui ne correspond pas à un terme employé en dehors d’une référence à ce radical même. Dans des cas particuliers, le radical peut coïncider avec un terme de vocabulaire ordinaire. C’est par exemple le cas de frontal qui donne la racine front.

Les techniques utilisées pour ce faire reposent généralement sur une liste d’affixes (suffixes, préfixes, infixes, circonfixes) 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. Les algorithmes les plus connus ont été développés par Julie Beth Lovins (en) (1968) et Martin Porter (en) (1980). 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

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.

À l'inverse, la racinisation est aussi source d'erreur. Par exemple en anglais, les mots « university » et « universe » ont la même racine («univers») quand bien même les documents utilisant ces deux mots peuvent avoir un rapport très ténu.

Les différents algorithmes

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 racinisateurs sont présentes dans la littérature : les racinisateurs algorithmiques et ceux utilisant un dictionnaire.

Un racinisateur 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é, regroupant des mots qui ne devraient pas l'être (sur-racinisation).

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

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

Soit $\scriptstyle v$ représentant une voyelle ('y' est considéré comme une voyelle s'il est précédé par une consonne), $\scriptstyle c$ représentant une consonne ; et soit $\scriptstyle V$ représentant une suite de voyelles, $\scriptstyle C$ représentant 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)^{m}V?$, 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

Étape 1	a	SSES → SS IES → I SS → SS S →	caresses → caress ponies → poni caress → caress cats → cat
	b	(m>0) EED → EE (*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) ATIONAL → ATE (m>0) TIONAL → TION (m>0) ENCI → ENCE (m>0) ANCI → ANCE …	relational → relate conditional → condition, rational → rational valenci → valence hesitansi → hesitance …
Étape 3		(m>0) ICATE → IC (m>0) ATIVE → (m>0) ALIZE → AL (m>0) ICITI → IC …	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 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

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.

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 (Generic Analyser and Listener for Indexed and Linguistics Entities of Information).

Algorithme de Paice/Husk

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 1980. 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

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, marmite ⇒ marm

• 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

(cheval ≡ chevaux) ≠ chevalerie ≠ chevauche

Application

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 l'usage des stemmers fait aussi baisser la précision.

Références

(en) Cet article contient des extraits de la Free On-line Dictionary of Computing qui autorise l'utilisation de son contenu sous licence GFDL.

Voir aussi

Bibliographie

• Lovins, J. (1971) Error Evaluation for Stemming Algorithms as Clustering Algorithms, JASIS, 22: 28–40
• Lovins, J. B. "Development of a Stemming Algorithm." Mechanical Translation and Computational Linguistics 11, 1968, 22—31.

Article connexe

• Lemmatisation

Liens externes

• Snowball - free stemming algorithms for many languages, includes source code, including stemmers for five romance languages
• Ruby-Stemmer - Ruby extension to Snowball API
• PECL - PHP extension to the Snowball API
• Oleander Porter's algorithm - stemming library in C++ released under BSD
• Unofficial home page of the Lovins stemming algorithm - with source code in a couple of languages
• Official home page of the Porter stemming algorithm - including source code in several languages
• Official home page of the Lancaster stemming algorithm - Lancaster University, UK
• Modifications to the Lancaster Stemming Algorithm - Extensions to improve the handling of errors in the rules, allow interactive testing, provide more precise stems, and add some flexibility for implementing finite state automata.
• Official home page of the UEA-Lite Stemmer - University of East Anglia, UK
• Overview of stemming algorithms
• PTStemmer - A Java/Python/.Net stemming toolkit for the Portuguese language
• jsSnowball - open source JavaScript implementation of Snowball stemming algorithms for many languages