Racinisation

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

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

• ${\displaystyle \scriptstyle CVCV\ldots C}$
• ${\displaystyle \scriptstyle CVCV\ldots V}$
• ${\displaystyle \scriptstyle VCVC\ldots C}$
• ${\displaystyle \scriptstyle VCVC\ldots V}$

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

• ${\displaystyle m=0}$ : tree, by
• ${\displaystyle m=1}$ : trouble, oats, trees, ivy
• ${\displaystyle m=2}$ : troubles, private, oaten, orrery

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

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

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

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.

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

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.

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

• 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