Zellig Harris et l'Analyse Distributionnelle

L'origine de l'élagage informatique

En 1955, le linguiste Zellig Harris a publié From Phoneme to Morpheme, décrivant une méthode pour trouver les frontières entre les unités significatives (morphèmes) dans les mots.

Son intuition était distributionnelle : si vous regardez un grand corpus de mots anglais, la frontière entre une racine & un suffixe se manifeste comme un signal statistique.

La méthode de la variété successive

Pour tout préfixe d'un mot, comptez combien de caractères distincts le suivent dans le corpus. Harris a appelé cela la variété successive.

Considérez le préfixe « work » dans un corpus contenant : worked, worker, working, works, workshop.

Après « work », quatre caractères différents peuvent suivre : un pic de variété. Ce pic marque une frontière de morphème. La racine est work et tout après est un suffixe.

C'était révolutionnaire en 1955. Pas de règles linguistiques, pas de dictionnaire : juste du comptage. Harris a montré que la structure du langage se révèle par la distribution.

Comprendre la Variété Successive

La méthode de Harris fonctionne sur n'importe quelle langue. Vous n'avez pas besoin de connaître la grammaire : les statistiques révèlent les frontières des morphèmes.

En pratique, la variété successive pure nécessite un grand corpus et une détection de pic minutieuse. Des chercheurs ultérieurs : Lovins (1968), Porter (1980) : ont simplifié l'approche en suppression de suffixes basée sur des règles : au lieu de calculer la variété successive à partir d'un corpus, ils ont codé les règles de suffixe directement.

Aujourd'hui vous allez construire un stripper de suffixes basé sur des règles inspiré par l'intuition de Harris. Vous allez définir les suffixes explicitement, puis les retirer des mots. C'est ainsi que fonctionnent la plupart des stemmers de production.

Votre Premier Stripper de Suffixes

Commençons à coder

Commencez simplement. Écrivez une fonction appelée stem qui prend un mot & supprime ces suffixes (dans cet ordre) :

1. -ing (running → runn)

2. -ed (walked → walk)

3. -ly (quickly → quick)

4. -s (cats → cat)

Règles :

- Convertissez d'abord le mot en minuscules

- Ne supprimez qu'un seul suffixe (la première correspondance dans l'ordre ci-dessus)

- Ne supprimez que si la racine restante a au moins 3 caractères

- Renvoyez la racine

Exemple :

def stem(word):
    word = word.lower()
    # your suffix stripping logic here
    return word

Gérer les Cas Limite

Rendre le stemmer plus intelligent

Votre stripper de base a un problème : running → runn & hoping → hop. Nous avons besoin de deux améliorations :

1. Nettoyage de double consonne : si retirer -ing ou -ed laisse une double consonne à la fin (comme runn), retirez la dernière lettre → run

2. Restauration du e muet : si retirer -ing laisse une racine finissant par une consonne (pas une voyelle), & l'original aurait pu avoir un e muet (comme hop de hoping), rajoutez e → hope

Pour la règle du e muet, gardez-la simple : si après suppression de -ing, la racine a 3+ caractères, se termine par une consonne, & l'avant-dernier caractère est une voyelle (un motif comme hop, mak, tak), rajoutez e.

Ajoutez aussi ces nouveaux suffixes (vérifiez-les avant -ing, -ed, -ly, -s) :

5. -tion (organization → organiza)

6. -ness (happiness → happi)

7. -ment (movement → move)

8. -able (readable → read)

9. -ible (sensible → sens)

Priorité de suffixe mise à jour : -tion, -ness, -ment, -able, -ible, -ing, -ed, -ly, -s

Gardez la règle de longueur minimale de racine : ne retirer que si la racine restante a 3+ caractères.

Règles -ies & -ier

Plus de morphologie

L'anglais a un autre motif courant : les mots se terminant par -y changent en -ies, -ied, ou -ier lors de l'inflexion.

Ajoutez ces règles avant les vérifications -s & -ed :

- -ies → retirer & ajouter i (babies → babi)

- -ied → retirer & ajouter i (carried → carri)

- -ier → retirer & ajouter i (earlier → earli)

Même règle de longueur minimale de racine : ne transformer que si le résultat a 3+ caractères.

Pourquoi Tester ?

Les tests ne sont pas optionnels

Vous avez un stemmer qui fonctionne. Comment savez-vous qu'il fonctionne vraiment ? En ce moment, vous exécutez quelques exemples à la main. Cela ne s'ajuste pas.

Les logiciels professionnels utilisent trois niveaux de test :

Tests unitaires : testent une fonction isolément avec des entrées connues et des sorties attendues. Rapide, nombreux, spécifiques.

Tests d'intégration : testent que plusieurs composants fonctionnent ensemble. Pour un stemmer, cela signifie tester un lot de mots et vérifier que les résultats sont cohérents.

Tests fonctionnels : testent le système de l'extérieur, comme un utilisateur le ferait. Pour un stemmer, cela signifie l'alimenter avec un vrai texte et vérifier que la sortie a du sens pour un vrai cas d'usage comme la recherche.

Vous allez écrire tous les trois.

Écrire des Tests Unitaires

Tests unitaires

Écrivez une fonction appelée run_unit_tests qui teste votre fonction stem avec au moins 15 cas de test couvrant :

1. Suppression de suffixe de base : mots se terminant par -ing, -ed, -ly, -s

2. Suffixes complexes : -tion, -ness, -ment, -able, -ible

3. Inflexion Y : -ies, -ied, -ier

4. Cas limite : mots courts qui ne doivent pas être élagués, mots sans suffixe, mots déjà élagués

5. Nettoyage de double consonne : running → run, sitting → sit

6. Restauration du e muet : hoping → hope

7. Insensibilité à la casse : l'entrée en majuscules doit être minusculée

Structurez vos tests comme ceci :

def run_unit_tests():
    tests = [
        ('running', 'run'),
        ('cats', 'cat'),
        # ... at least 15 test cases
    ]
    passed = 0
    failed = 0
    for word, expected in tests:
        result = stem(word)
        if result == expected:
            passed += 1
        else:
            failed += 1
            print(f'FAIL: stem({word}) = {result}, expected {expected}')
    print(f'{passed}/{passed + failed} unit tests passed')
    return failed == 0

Écrire des Tests d'Intégration

Tests d'intégration

Les tests unitaires vérifient les entrées individuelles. Les tests d'intégration vérifient que les composants fonctionnent correctement ensemble.

Pour un stemmer, une propriété d'intégration clé est la cohérence : si vous élagez le même mot deux fois, vous obtenez le même résultat. Et les mots qui devraient se regrouper devraient produire la même racine.

Écrivez une fonction appelée run_integration_tests qui teste :

1. Idempotence : élaguer un mot déjà élagué devrait retourner la même racine. stem(stem(word)) == stem(word) pour tous les mots.

2. Regroupement : les mots qui devraient partager une racine le font vraiment. Testez au moins 3 familles de mots (par ex., run/runs/running/runner devraient tous partager une racine).

3. Traitement en lot : traitez une liste de 20+ mots et vérifiez l'absence de crash, pas de chaînes vides, pas de valeurs None.

def run_integration_tests():
    # Test 1: idempotency
    # Test 2: word family grouping
    # Test 3: batch stability
    ...

Écrire des Tests Fonctionnels

Tests fonctionnels

Les tests fonctionnels vérifient que le système fonctionne pour son cas d'usage prévu. Votre stemmer existe pour améliorer la recherche : alors testez cela.

Écrivez une fonction appelée run_functional_tests qui :

1. Simulation de recherche : données une liste de chaînes de document et un mot requête, élagez à la fois les documents et la requête, puis vérifiez si les termes de requête élagués apparaissent dans les documents élagués. Testez que chercher « running » trouve un document contenant « run » et « runner ».

2. Vérification de précision : vérifiez que l'élagage ne groupe PAS incorrectement les mots non liés. « university » et « universe » pourraient partager une racine : vérifiez si votre stemmer gère cela (c'est OK s'il les groupe ; documentez le comportement).

3. Traitement de texte réel : élagez chaque mot dans un paragraphe de vrai texte anglais. Vérifiez que la sortie est raisonnable : pas de chaînes vides, pas de crash, la sortie a le même nombre de mots que l'entrée.

def run_functional_tests():
    # Test 1: search finds related documents
    # Test 2: precision: check over-stemming
    # Test 3: real paragraph processing
    ...

Ce Que Vous Avez Construit

Ce que vous avez construit

Vous avez implémenté un stemmer d'anglais fonctionnel avec :

- 12 règles de suffixe (-tion, -ness, -ment, -able, -ible, -ies, -ied, -ier, -ing, -ed, -ly, -s)

- Nettoyage de double consonne

- Restauration du e muet

- Tests unitaires, tests d'intégration, & tests fonctionnels

La généalogie

Votre stemmer descend d'une lignée de travail qui a commencé avec Zellig Harris en 1955 :

- Harris (1955) : Découvert que les frontières de morphème se manifestent comme des signaux statistiques (variété successive)

- Lovins (1968) : Premier algorithme de stemming publié, 294 règles de suffixe

- Porter (1980) : Simplifié à ~60 règles en 5 étapes, devenu le standard pendant des décennies

- Snowball (2001) : Cadre de Porter généralisé à plusieurs langues

- Votre stemmer (aujourd'hui) : 12 règles, même principe fondamental

Ce que vous pourriez faire ensuite

- Implémentez l'algorithme Porter complet (il est bien documenté & un excellent exercice)

- Portez votre stemmer en C pour une amélioration de vitesse de 100x

- Construisez un moteur de recherche simple qui utilise votre stemmer pour indexer & interroger des fichiers texte

- Comparez la sortie de votre stemmer avec PorterStemmer de NLTK pour mesurer la précision

Le code que vous avez écrit aujourd'hui est la même opération fondamentale qui s'exécute à l'intérieur de chaque moteur de recherche sur la planète. Pas mal pour une journée de travail.