Zellig Harris en Distributionele Analyse

De oorsprong van computationeel stemming

In 1955 publiceerde de linguïst Zellig Harris From Phoneme to Morpheme, waarin hij een methode beschreef voor het vinden van grenzen tussen betekenisvolle eenheden (morfemen) in woorden.

Zijn inzicht was distributioneel: als je naar een groot corpus van Engelse woorden kijkt, verschijnt de grens tussen een stam & een suffix als een statistisch signaal.

De successor variety methode

Voor elk voorvoegsel van een woord, tel hoeveel verschillende karakters het volgen in het corpus. Harris noemde dit de successor variety.

Beschouw het voorvoegsel "work" in een corpus met: worked, worker, working, works, workshop.

Na "work" kunnen vier verschillende karakters volgen: een piek in variëteit. Die piek markeer een morfeem grens. De stam is work en alles erna is een suffix.

Dit was radicaal in 1955. Geen taalkundige regels, geen woordenboek: gewoon tellen. Harris toonde aan dat de structuur van taal zich openbaart door distributie.

Successor Variety Begrijpen

Harris's methode werkt in elke taal. Je hoeft de grammatica niet te kennen: de statistieken onthullen de morfeem grenzen.

In de praktijk vereist pure successor variety een groot corpus en voorzichtige piek detectie. Latere onderzoekers: Lovins (1968), Porter (1980): vereenvoudigden de aanpak tot rule-based suffix stripping: in plaats van successor variety uit een corpus te berekenen, codeerden ze de suffixregels rechtstreeks.

Vandaag zul je een rule-based suffix stripper bouwen geïnspireerd door Harris's inzicht. Je definieert de suffixen expliciet, dan strip je ze uit woorden. Dit is hoe de meeste productie stemmers werken.

Je Eerste Suffix Stripper

Laten we coderen

Maak het eenvoudig. Schrijf een functie genaamd stem die een woord neemt & deze suffixen strip (in deze volgorde):

1. -ing (running → runn)

2. -ed (walked → walk)

3. -ly (quickly → quick)

4. -s (cats → cat)

Regels:

- Zet het woord eerst om naar kleine letters

- Strip slechts één suffix (de eerste match in de bovenstaande volgorde)

- Strip alleen als de resterende stam minstens 3 karakters lang is

- Geef de stam terug

Voorbeeld:

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

Edge Cases Afhandelen

De stemmer intelligenter maken

Je basis stripper heeft een probleem: running → runn & hoping → hop. We hebben twee verfijningen nodig:

1. Double consonant cleanup: als strippen van -ing of -ed een dubbele medeklinker aan het einde achterlaat (zoals runn), verwijder de laatste letter → run

2. Silent-e restoration: als strippen van -ing een stam achterlaat die eindigt met een medeklinker (geen klinker), & het origineel mogelijk een stille e had (zoals hop van hoping), voeg e terug toe → hope

Houd de silent-e regel eenvoudig: als na strippen van -ing, de stam 3+ karakters is, eindigt met een medeklinker, & het tweede-naar-laatste karakter is een klinker (een patroon zoals hop, mak, tak), voeg e terug toe.

Voeg ook deze nieuwe suffixen toe (controleer ze vóór -ing, -ed, -ly, -s):

5. -tion (organization → organiza)

6. -ness (happiness → happi)

7. -ment (movement → move)

8. -able (readable → read)

9. -ible (sensible → sens)

Bijgewerkte suffixprioriteit: -tion, -ness, -ment, -able, -ible, -ing, -ed, -ly, -s

Houd de minimale stamlengte regel: strip alleen als de resterende stam 3+ karakters is.

-ies & -ier Regels

Meer morphologie

Engels heeft nog een ander veelvoorkomend patroon: woorden eindigend op -y veranderen naar -ies, -ied, of -ier als ze vervoegd worden.

Voeg deze regels vóór de -s & -ed checks toe:

- -ies → strip & voeg i toe (babies → babi)

- -ied → strip & voeg i toe (carried → carri)

- -ier → strip & voeg i toe (earlier → earli)

Dezelfde minimale stamlengte regel: transformeer alleen als het resultaat 3+ karakters is.

Waarom Testen?

Testen is niet optioneel

Je hebt een werkende stemmer. Hoe weet je dat het daadwerkelijk werkt? Op dit moment voer je een paar voorbeelden met de hand uit. Dat schaalt niet.

Professionele software gebruikt drie niveaus van testen:

Unit tests: test één functie in isolatie met bekende inputs en verwachte outputs. Snel, talrijk, specifiek.

Integratietests: test dat meerdere componenten goed samenwerken. Voor een stemmer betekent dit het testen tegen een batch woorden en het verifiëren dat de resultaten consistent zijn.

Functionele tests: test het systeem van buitenaf, zoals een gebruiker zou doen. Voor een stemmer betekent dit het invoeren van echte tekst en het verifiëren dat de output logisch is voor een echt gebruiksgeval zoals zoeken.

Je zult alle drie schrijven.

Unit Tests Schrijven

Unit tests

Schrijf een functie genaamd run_unit_tests die je stem functie test met minstens 15 testgevallen ter dekking van:

1. Basis suffixstripping: woorden eindigend op -ing, -ed, -ly, -s

2. Complexe suffixen: -tion, -ness, -ment, -able, -ible

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

4. Edge cases: korte woorden die niet gestrip moeten worden, woorden zonder suffix, al gestamde woorden

5. Double consonant cleanup: running → run, sitting → sit

6. Silent-e restoration: hoping → hope

7. Casogevoeligheid: hoofdletterinvoer moet in kleine letters worden omgezet

Structureer je tests als volgt:

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

Integratietests Schrijven

Integratietests

Unit tests verifiëren afzonderlijke inputs. Integratietests verifiëren dat componenten goed samenwerken.

Voor een stemmer is een sleutelintegratieigenschaap consistentie: als je hetzelfde woord twee keer stamt, krijg je hetzelfde resultaat. En woorden die samen moeten groeperen, moeten dezelfde stam produceren.

Schrijf een functie genaamd run_integration_tests die test:

1. Idempotentie: stammen van een al-gestamde woord moet hetzelfde stam retourneren. stem(stem(word)) == stem(word) voor alle woorden.

2. Groepering: woorden die een stam moeten delen doen dat ook daadwerkelijk. Test minstens 3 woordfamilies (bijv. run/runs/running/runner zouden allemaal een stam moeten delen).

3. Batch verwerking: verwerk een lijst van 20+ woorden en verifieer geen crashes, geen lege strings, geen None waarden.

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

Functionele Tests Schrijven

Functionele tests

Functionele tests verifiëren dat het systeem voor zijn beoogde gebruiksgeval werkt. Je stemmer bestaat om zoeken te verbeteren: dus test dat.

Schrijf een functie genaamd run_functional_tests die:

1. Zoeksimulatie: gegeven een lijst van documentstrings en een zoekoord, stem zowel de documenten als de query, controleer of gestamde querytermen in gestamde documenten voorkomen. Test dat zoeken naar 'running' een document vindt met 'run' en 'runner'.

2. Nauwkeurigheidscontrole: verifieer dat stemming NIET onjuist gerelateerde woorden groepeert. 'university' en 'universe' kunnen een stam delen: controleer hoe je stemmer dit behandelt (het OK als hij ze groepeert; document het gedrag).

3. Echte tekstverwerking: stem elk woord in een alinea van echte Engelse tekst. Verifieer dat de output redelijk is: geen lege strings, geen crashes, output heeft hetzelfde aantal woorden als invoer.

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

Wat Je Bouwde

Wat je bouwde

Je implementeerde een werkende Engelse stemmer met:

- 12 suffixregels (-tion, -ness, -ment, -able, -ible, -ies, -ied, -ier, -ing, -ed, -ly, -s)

- Double consonant cleanup

- Silent-e restoration

- Unit tests, integratietests, & functionele tests

De afkomst

Je stemmer daalt af van een lijn van werk die in 1955 begon met Zellig Harris:

- Harris (1955): Ontdekt dat morfeem grenzen als statistische signalen verschijnen (successor variety)

- Lovins (1968): Eerste gepubliceerd stemmingalgoritme, 294 suffixregels

- Porter (1980): Vereenvoudigd tot ~60 regels in 5 stappen, werd de standaard voor decennia

- Snowball (2001): Porters framework veralgemeend naar meerdere talen

- Je stemmer (vandaag): 12 regels, hetzelfde kernprincipe

Wat je volgende zou kunnen doen

- Implementeer het volledige Porter-algoritme (het is goed gedocumenteerd & een geweldige oefening)

- Port je stemmer naar C voor een 100x snelheidsverbetering

- Bouw een eenvoudige zoekmachine die je stemmer gebruikt om tekstbestanden te indexeren & op te vragen

- Vergelijk je stemmers output met NLTK's PorterStemmer om nauwkeurigheid te meten

De code die je vandaag schreef is dezelfde fundamentele bewerking die in elke zoekmachine op de planeet draait. Niet slecht voor een dag werk.