Racinisation

La racinisation (ou désuffixation, ou stemming en anglais) est le nom donné au procédé qui vise à transformer les flexions en leur radical ou stemme. Il cherche à rassembler les différentes variantes flexionnelle et dérivationnelle d’un mot autour d’un stemme.

La racine d’un mot correspond à la partie du mot restante une fois que l’on a supprimé son préfixe et son suffixe, à savoir son radical. Elle est aussi parfois connu sous le nom de stemme d’un mot. Contrairement au lemme qui correspond à un mot réel de la langue, la racine ou stemme ne correspond généralement pas à un mot réel. Par exemple, le mot « chercher » a pour radical ou stemme « cherch » qui ne correspond pas à un mot réel. Par contre dans l’exemple de « frontal » , le radical ou stemme 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 son stemme. Algorithmes pour racinisation ont été étudiés en informatique depuis 1968. Les meilleurs algorithmes connus de racinisation ont été développés par Julie Beth Lovins (1968)^[1] et Martin Porter (1980)^[2] Et les réalisation d'algorithmes de racilisation sont applés « stemmer » ou « racinisateur ».

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 tel quel, il serait impossible lors d'une recherche de faire référence aux documents comportants 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

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 ensembles 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

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]

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	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 fourni sa propre implémentation^[6]de son algorithme dans plusieurs langages car les autre 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 en suite 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 les quelles 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é pour l'étude de la morphologie de français, et ils sont téléchargeable gratuitement sur le site du projet GALILEI^[8] (Generic Analyser and Listener for Indexed and Linguistics Entities of Information).

Algorithme de Paice/Husk^[9]

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 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:

Les méthodes utilisées pour la lemmatisation et la désuffixation ne sont pas les mêmes
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 stemmers fait aussi baisser la précision.

Références

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

Pour en savoir plus

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.

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

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

Catégories :

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Racinisation de Wikipédia en français (auteurs)

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

Radical (linguistique) — Pour les articles homonymes, voir Racine. En linguistique, un radical (ou racine ou encore morphème lexical, lexème, bien que ces notions ne soient pas, dans le détail, identiques) est la plus petite et plus ancienne unité lexicale qui permette… … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

Racinisation

Sommaire

Exemples