Zellig Harris och Distributionsanalys

Ursprunget till beräkningsmässig stemming

År 1955 publicerade lingvisten Zellig Harris From Phoneme to Morpheme, som beskrev en metod för att hitta gränserna mellan meningsfulla enheter (morfem) i ord.

Hans insikt var distributionell: om du tittar på ett stort korpus med engelska ord, kommer gränsen mellan en stam & ett suffix att visa sig som en statistisk signal.

Metoden för efterföljande variation

För varje prefix i ett ord, räkna hur många distinkta tecken som följer det i korpusen. Harris kallade detta för successor variety.

Betrakta prefixet "work" i ett korpus innehållande: worked, worker, working, works, workshop.

Efter "work" kan fyra olika tecken följa: en ökning i variation. Den ökningen markerar en morfemgräns. Stamen är work och allt efter det är ett suffix.

Det var radikalt år 1955. Inga språkliga regler, ingen ordbok: bara räkning. Harris visade att språkets struktur avslöjar sig genom distribution.

Förstå Successor Variety

Harris metod fungerar på alla språk. Du behöver inte veta grammatiken: statistiken avslöjar morfemgränserna.

I praktiken kräver ren successor variety ett stort korpus och försiktig toppdetektering. Senare forskare: Lovins (1968), Porter (1980): förenklade tillvagagången till regelbaserad suffixborttagning: istället för att beräkna successor variety från ett korpus, kodade de suffixreglerna direkt.

Idag kommer du att bygga en regelbaserad suffixborttagare inspirerad av Harris insikt. Du kommer att definiera suffixen uttryckligen, sedan ta bort dem från ord. Det här är hur de flesta produktionsstemmers fungerar.

Din Första Suffixborttagare

Låt oss koda

Börja enkelt. Skriv en funktion som heter stem som tar ett ord & tar bort dessa suffix (i denna ordning):

1. -ing (running → runn)

2. -ed (walked → walk)

3. -ly (quickly → quick)

4. -s (cats → cat)

Regler:

- Konvertera ordet till små bokstäver först

- Ta bara bort ett suffix (den första träffen i ordningen ovan)

- Ta bara bort om den återstående stamen är minst 3 tecken lång

- Returnera stamen

Exempel:

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

Hantera Kantfall

Göra stemmern smartare

Din grundläggande borttagare har ett problem: running → runn & hoping → hop. Vi behöver två förbättringar:

1. Dubbel konsonantborttagning: om borttagning av -ing eller -ed lämnar en dubbel konsonant i slutet (som runn), ta bort den sista bokstaven → run

2. Återställning av tyst e: om borttagning av -ing lämnar en stam som slutar med en konsonant (inte en vokal), & originalet kan ha haft ett tyst e (som hop från hoping), lägg till e igen → hope

För den tysta e-regeln, håll det enkelt: efter borttagning av -ing, om stamen är 3+ tecken, slutar med en konsonant, & den näst sista tecknet är en vokal (ett mönster som hop, mak, tak), lägg till e igen.

Lägg också till dessa nya suffix (kontrollera dem innan -ing, -ed, -ly, -s):

5. -tion (organization → organiza)

6. -ness (happiness → happi)

7. -ment (movement → move)

8. -able (readable → read)

9. -ible (sensible → sens)

Uppdaterad suffixprioritet: -tion, -ness, -ment, -able, -ible, -ing, -ed, -ly, -s

Behåll regeln för minsta stamlängd: ta bara bort om den återstående stamen är 3+ tecken.

-ies & -ier Regler

Mer morfologi

Engelska har ett annat vanligt mönster: ord som slutar på -y ändras till -ies, -ied, eller -ier vid böjning.

Lägg till dessa regler innan kontrollerna av -s & -ed:

- -ies → ta bort & lägg till i (babies → babi)

- -ied → ta bort & lägg till i (carried → carri)

- -ier → ta bort & lägg till i (earlier → earli)

Samma regel för minsta stamlängd: ta bara bort om resultatet är 3+ tecken.

Varför Testa?

Testning är inte valfritt

Du har en fungerande stemmer. Hur vet du att det faktiskt fungerar? Just nu kör du några exempel för hand. Det skalas inte.

Professionell programvara använder tre nivåer av testning:

Enhetstester: testa en funktion isolerad med kända ingångar och förväntade utmatningar. Snabb, många, specifik.

Integrationstester: testa att flera komponenter fungerar tillsammans. För en stemmer betyder detta att testa den mot en batch av ord och verifiera att resultaten är konsekventa.

Funktionstester: testa systemet från utsidan, som en användare skulle. För en stemmer betyder detta att mata den med verklig text och verifiera att utmatningen är vettigt för ett verkligt användningsfall som sökning.

Du kommer att skriva alla tre.

Skriv Enhetstester

Enhetstester

Skriv en funktion som heter run_unit_tests som testar din stem-funktion med minst 15 testfall som täcker:

1. Grundläggande suffixborttagning: ord som slutar på -ing, -ed, -ly, -s

2. Komplexa suffix: -tion, -ness, -ment, -able, -ible

3. Y-böjning: -ies, -ied, -ier

4. Kantfall: korta ord som inte bör tas bort, ord utan suffix, redan-stemmade ord

5. Dubbel konsonantborttagning: running → run, sitting → sit

6. Tyst-e-återställning: hoping → hope

7. Skiftokänslighet: VERSAL-ingång bör konverteras till små bokstäver

Strukturera dina tester så här:

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

Skriv Integrationstester

Integrationstester

Enhetstester verifierar enskilda ingångar. Integrationstester verifierar att komponenter fungerar tillsammans korrekt.

För en stemmer är en nyckelintegreringsegenskap konsistens: om du stemmmer samma ord två gånger får du samma resultat. Och ord som bör grupperas tillsammans bör ge samma stam.

Skriv en funktion som heter run_integration_tests som testar:

1. Idempotens: att stemma ett redan-stammad ord bör returnera samma stam. stem(stem(word)) == stem(word) för alla ord.

2. Gruppering: ord som bör dela en stam gör faktiskt det. Testa minst 3 ordfamiljer (t.ex. run/runs/running/runner bör alla dela en stam).

3. Batch-bearbetning: bearbeta en lista med 20+ ord och verifiera ingen krascher, inga tomma strängar, inga None-värden.

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

Skriv Funktionstester

Funktionstester

Funktionstester verifierar att systemet fungerar för sitt avsedda användningsfall. Din stemmer finns för att förbättra sökning: så testa det.

Skriv en funktion som heter run_functional_tests som:

1. Söksimulering: givet en lista med dokumentsträngar och ett frågeord, stemma både dokumenten och frågan, kontrollera sedan om stemmade frågetermer visas i stemmade dokument. Testa att sökning efter 'running' hittar ett dokument innehållande 'run' och 'runner'.

2. Precisionskontroll: verifiera att stemming INTE felaktigt grupperar orelaterade ord. 'university' och 'universe' kan dela en stam: kontrollera om din stemmer hanterar detta (det är OK om den grupperar dem; dokumentera beteendet).

3. Bearbetning av verklig text: stemma varje ord i en paragraf med verklig engelska text. Verifiera att utmatningen är rimlig: inga tomma strängar, ingen krascher, utmatningen har samma antal ord som ingång.

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

Vad Du Byggde

Vad du byggde

Du implementerade en fungerande engelsk stemmer med:

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

- Dubbel konsonantborttagning

- Tyst-e-återställning

- Enhetstester, integrationstester, & funktionstester

Härkomsten

Din stemmer härstammar från en rad arbete som startade med Zellig Harris år 1955:

- Harris (1955): Upptäckte att morfemgränser visas som statistiska signaler (successor variety)

- Lovins (1968): Första publicerade stemmningsalgoritm, 294 suffixregler

- Porter (1980): Förenklat till ~60 regler i 5 steg, blev standarden i decennier

- Snowball (2001): Porters ramverk generaliserat till flera språk

- Din stemmer (idag): 12 regler, samma kärnprincip

Vad du kan göra härnäst

- Implementera den fullständiga Porter-algoritmen (den är väl dokumenterad & en bra övning)

- Portera din stemmer till C för en 100x hastighetsförbättring

- Bygg en enkel sökmotor som använder din stemmer för att indexera & fråga textfiler

- Jämför din stemmers utmatning mot NLTK:s PorterStemmer för att mäta noggrannhet

Koden du skrev idag är samma grundläggande operation som körs inuti varje sökmotor på planeten. Inte dåligt för en dags arbete.