 |
Principe
Qu'est-ce qu'un stemmer ? À quoi sert-il ?
Un stemmer (ou racinisateur) est un algorithme qui supprime les suffixes flexionnels et dérivationnels pour réduire les différentes formes d'un mot à leur racine. Cette racine doit être comprise dans un sens morphologique : deux mots peuvent ici avoir la même racine morphologique, mais des sens différents.
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.
Familles de stemmers, présentation de l'algorithme de Paice/Husk
Deux principales familles de stemmers sont présentes dans la littérature : les stemmers algorithmiques et ceux utilisant un dictionnaire. 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.
L'algorithme de Paice/Husk appartient donc à 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.
Haut de page
Utilisation
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 (PaiceHuskStemmer.php), ainsi que l'ensemble de règles de réécriture (PaiceHuskStemRules_en.php pour l'anglais - adaptées des règles du site The Lancaster (Paice/Husk) Stemming Algorithm -, et PaiceHuskStemRules_fr.php pour le français).
La fonction principale prend en paramètres le mot dont on souhaite extraire la racine et le code de la langue ('en' pour l'anglais, et 'fr' pour le français).
Ainsi, PaiceHuskStemmer('abusively','en') retournera la racine 'abusive', tandis que PaiceHuskStemmer('constitutionnellement','fr') retournera la racine 'constitu'.
Haut de page
Performances
En premier lieu, cette implémentation en PHP n'a pas été conçue pour être la plus rapide possible. Elle peut très certainement être accélérée de beaucoup, et le choix du langage PHP est déjà une question à se poser lorsqu'il s'agit d'extraire des racines d'un texte de taille raisonnable.
Néanmoins, il peut être utile de pouvoir comparer ce stemmer doté d'un ensemble donné de règles à un autre, ou au même doté d'un autre ensemble de règles. Les métriques suivantes sont listées dans la page Performance de racinisation et implémentées dans la fonction getStatistics de StemmingToolKit.php.
* Nombre de mots par classe de conflation
Il s'agit de la taille moyenne des groupes de mots correspondant à une racine particulière (qu'elle soit correcte ou non). Ainsi, si seuls les mots « rougeâtre », « rouges » et « rougeur » sont liés à la racine « roug », alors la taille de cette classe de conflation est de 3. Si de la conflation de 1.000 mots différents résultent 250 racines distinctes, alors on compte en moyenne 4 mots par classe de conflation.
Cette métrique dépend du nombre de mots traités, mais pour une collection de mots d'une taille donnée, une plus grande valeur indique un stemmer plus fort. Cette valeur est facilement calculable ainsi :
NMC = Nombre moyen de mots par classe de conflation
M = nombre de mots uniques avant racinisation
R = nombre de racines uniques après racinisation
NMC = M / R
* Indice de compression
L'indice de compression représente jusqu'à quel point une collection de mots uniques est réduite (compressée) par la racinisation. L'idée sous-jacente est que plus le stemmer est fort, plus l'indice de compression est élevé. Il peut être calculé par :
IC = indice de compression
M = nombre de mots uniques avant racinisation
R = nombre de racines uniques après racinisation
IC = (M - R) / M
* Le facteur de changement de mot
C'est simplement la proportion des mots d'un échantillon qui ont été modifiés par le processus de racinisation. L'idée est ici que plus le nombre de mots modifiés est important, plus le stemmer est fort.
* Nombre de caractères supprimés
De nombreuses métriques utilisent le principe que les stemmers les plus forts suppriment plus de caractères que les stemmers plus faibles. L'une d'elle consiste à compter le nombre moyen de lettres supprimées quand un stemmer est appliqué à une collection de textes. Ainsi, si les trois mots « rougeâtre », « rouges » et « rougeur » sont tous réduits à la racine « roug », le nombre de caractères supprimés est donc respectivement de 5, 2 et 3, ce qui donne un taux moyen de suppression de 10/3 = 3,33.
L'échantillon provient d'extraits du roman « Pêcheur d'Islande » (1886) de Pierre Loti, soit un texte du même type (roman) et de la même période (fin 19ème) que les textes du corpus utilisés pour extraire les règles de réécriture des racines.
Fichier échantillon : sample_fr.inc.php (voir la source)
Fichier stop list : stoplist_fr.inc.php (voir la source)
Taille de l'échantillon : 23.135 mots (répartis en 427 unités textuelles)
Nombre de mots uniques : 4.278
| Stemmer Paice/Husk |
| Nombre de racines : |
3.265 |
| Nombre de racines uniques : |
3.265 |
| Longueur min/max des racines : |
2 / 15 |
| Longueur moyenne des racines : | 5,63 |
| Nombre de mots par classe de conflation : |
1,31 |
| Indice de compression : |
0,24 |
| Facteur de changement par mot : |
0,26 |
| Nombre de caractères supprimés : |
10.079 |
| Taux moyen de suppression : |
1,12 |
| Taux médian de suppression : |
1 |
Haut de page
Ajouter une langue
Comment créer un stemmer pour une langue donnée (par exemple le français) ?
Dans le fichier PaiceHuskStemmer.php, nous avons besoin de :
- créer une nouvelle règle de traitement pour cette langue, incluant toutes les lettres accentuées
Les lettres accentuées en français sont : à, â, è, é, ê, ë, î, ï, ô, û, ù et ç.
Nous pouvons donc ajouter la ligne suivante :
$rule_pattern_fr = "/^([a-zàâèéêëîïôûùç]*)(\*){0,1}(\d)([a-zàâèéêëîïôûùç]*)([.|>])/";
- lister toutes les voyelles de cette langue
Les voyelles en français sont : a, à, â, e, è, é, ê, ë, i, î, ï, o, ô, u, û, ù et y.
- ajouter un nouveau cas dans la fonction checkAcceptability pour définir les règles d'écriture des racines (nous avons ici besoin de la liste des voyelles de cette langue)
Le gros du travail consiste à écrire la liste ordonnée des règles de réécriture pour extraire les racines, c'est-à-dire les fichiers PaiceHuskStemRules_en.php (pour l'anglais) et PaiceHuskStemRules_fr.php (pour le français). Afin d'être en mesure d'extraire les racines d'un texte donné, il faut tout d'abord lister les suffixes les plus utilisés dans cette langue. Pour ce faire, nous devons utiliser un corpus de taille raisonnable (un million de mots est un bon départ). Le corpus utilisé pour le français est constitué de dix romans (source : Gallica) : Hernani ou L'honneur castillan (1830), Lucrèce Borgia (1833), Marie Tudor (1833), Ruy Blas (1905), Le Rhin, Lettres à un ami (1906) et Les travailleurs de la mer (1911) de Victor Hugo, et Nana (1880), Germinal (1885), La bête humaine (1890) et La débâcle (1892) de Emile Zola.
Ce corpus comprend 1.172.726 formes différentes.
La fréquence des mots dans le corpus a été calculée, puis ils ont été triés par leur fréquence et listés en inversant leurs caractères (mettant ainsi en avant le suffixe), puis par ordre alphabétique pour chaque fréquence (fonction listSuffixes de StemmingToolKit.php). Il a été ensuite possible d'identifier les suffixes les plus communs pour en extraire un ensemble de règles de réécriture. Celles-ci sont donc trouvées de manière incrémentale en fonction des suffixes les plus courants. Cette méthode permet de couvrir le vocabulaire le plus utilisé de la langue mais peut aboutir à un nombre de règles assez important.
Méthode pas à pas :
- prendre le 1er mot de la liste triée par fréquence (fichier corpus_stems_fr.txt généré par la fonction listSuffixes de StemmingToolKit.php)
- associer la forme avec sa racine dans le fichier de test words2stems_fr.inc.php (voir la source)
- faire tourner l'algorithme de Paice/Husk sur ce fichier (fonction developPaiceHusk de StemmingToolKit.php)
Si la racine trouvée ne correspond pas aux attentes, ajouter/modifier/déplacer les règles de PaiceHuskStemRules_fr.php et au besoin modifier dans une certaine mesure les racines associées à certaines formes dans le fichier de test jusqu'à ce que l'algorithme donne les « bonnes » racines pour tous les mots du fichier de test. On voit bien ici qu'il est question de choix pour définir quels mots partageront les mêmes racines ainsi que la puissance du stemmer issu de ces règles.
Haut de page
Boîte à outils
Liste des fonctions utiles de la librairie StemmingToolKit.php
| getStatistics : |
affiche les statistiques du stemmer Paice/Husk
autres fonctions utilisées : standardizePunctuation et indexText
nécessite : PaiceHuskStemmer.php, le tableau de la stop list pour la langue (stoplist_en.inc.php, stoplist_fr.inc.php (voir les sources))
|
| standardizePunctuation : |
retourne le texte donné en entrée dans lequel un espace a été inséré avant chaque ponctuation (ponctuation standardisée) |
| localizePunctuation : |
utilise des règles typographiques pour retourner un texte correctement écrit à partir d'un texte en ponctuation standardisée |
| indexText : |
indexe le texte en entrée et retourne un tableau contenant :
- 'original' : le texte sous sa forme originale
- 'modified' : le texte modifié en ponctuation standardisée
- 'index' : un tableau listant, pour chaque mot du texte modifié n'appartenant pas à la stop list, sa forme et son indice dans le texte modifié et sa racine. |
| listSuffixes : |
liste les suffixes d'un corpus qui ne sont pas listés dans le fichier words2stems_<langue>.inc.php correspondant
nécessite : corpus_fr.txt (pour le français) qui est un corpus textuel, et words2stems_fr.inc.php (pour le français) qui définit un tableau associant à chaque mot sa racine (optionnel, utile si on ne veut pas lister les mots pour lesquels les règles de réécritures renvoient déjà la racine recherchée)
retourne : sa sortie est sauvegardée dans le fichier corpus_stems_fr.txt (pour le français)
échantillon de la sortie :
frequency: 0.01474%
---------
atser (resta)
ecnirp (prince)
snolla (allons)
xuoneg (genoux)
|
| developPaiceHusk : |
affiche la forme et la racine de chaque mot du tableau words2stems après l'avoir traité par le nouvel ensemble de règles si la racine retournée est différente de celle attendue
nécessite : le fichier words2stems_fr.inc.php (pour le français) qui définit un tableau associant à chaque forme sa racine attendue |
Haut de page
Téléchargement
Cette application est domaine public : vous pouvez la télécharger et l'utiliser comme bon vous semble. Si vous y apportez des modifications que vous êtes prêt-e à partager, elles seront ajoutées sur ce site.
PaiceHuskStemmer.zip (80ko)
Version Java
Une version Java de cette application a été traduite par Tito Colonna que je tiens à remercier pour ses remarques et sa lecture critique du code. Cette version traite uniquement le français (ajouter une autre langue est assez facile), et ne dérive que les mots simples sans les comparer à une liste de stopwords. De même, la version PHP ne tient pas compte des mots composés, en considérant que deux mots séparés par un tiret n'en font qu'un (après-midi a un sens particulier que apr?s midi perdrait), et la normalisation ne s'en occupe pas du tout.
PaiceHuskStemmer.java.txt
Liens
Algorithme de racinisation de Paice/Husk (Lancaster)
Algorithme de racinisation de Porter
Snowball (fournit listes de lettres accentuées, échantillons de vocabulaire, stop lists...)
|
|
|
|
