Zellig Harris e l'Analisi Distribuzionale

L'origine dello stemming computazionale

Nel 1955, il linguista Zellig Harris ha pubblicato From Phoneme to Morpheme, descrivendo un metodo per trovare i confini tra unità significative (morfemi) nelle parole.

La sua intuizione era distribuzionale: se guardi un grande corpus di parole inglesi, il confine tra uno stem e un suffisso si presenta come un segnale statistico.

Il metodo della varietà di successore

Per qualsiasi prefisso di una parola, conta quanti caratteri distinti lo seguono nel corpus. Harris ha chiamato questo la varietà di successore.

Considera il prefisso "work" in un corpus contenente: worked, worker, working, works, workshop.

Dopo "work", quattro caratteri diversi possono seguire: un'impennata nella varietà. Quella picco contrassegna un confine di morfema. Lo stem è work e tutto quello che segue è un suffisso.

Questo era radicale nel 1955. Nessuna regola linguistica, nessun dizionario: solo conteggio. Harris ha dimostrato che la struttura del linguaggio si rivela attraverso la distribuzione.

Comprendere la Varietà di Successore

Il metodo di Harris funziona in qualsiasi lingua. Non devi conoscere la grammatica: le statistiche rivelano i confini dei morfemi.

In pratica, la pura varietà di successore richiede un corpus ampio e un'attenta rilevazione dei picchi. Ricercatori successivi: Lovins (1968), Porter (1980): hanno semplificato l'approccio nello stripping dei suffissi basato su regole: invece di calcolare la varietà di successore da un corpus, hanno codificato direttamente le regole dei suffissi.

Oggi costruirai uno strumento di stripping dei suffissi basato su regole ispirato dall'intuizione di Harris. Definirai i suffissi esplicitamente, quindi li stripperai dalle parole. È così che funzionano la maggior parte degli stemmer di produzione.

Il Tuo Primo Strumento di Stripping dei Suffissi

Iniziamo a programmare

Inizia in modo semplice. Scrivi una funzione chiamata stem che accetta una parola & rimuove questi suffissi (in questo ordine):

1. -ing (running → runn)

2. -ed (walked → walk)

3. -ly (quickly → quick)

4. -s (cats → cat)

Regole:

- Converti la parola in minuscole per primo

- Rimuovi solo un suffisso (il primo match nell'ordine sopra)

- Rimuovi solo se lo stem rimanente è lungo almeno 3 caratteri

- Restituisci lo stem

Esempio:

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

Gestione dei Casi Limite

Rendere lo stemmer più intelligente

Il tuo strumento di base ha un problema: running → runn & hoping → hop. Abbiamo bisogno di due raffinamenti:

1. Pulizia consonante doppia: se la rimozione di -ing o -ed lascia una consonante doppia alla fine (come runn), rimuovi l'ultima lettera → run

2. Ripristino di e silenziosa: se la rimozione di -ing lascia uno stem che termina con una consonante (non una vocale), & l'originale potrebbe aver avuto una e silenziosa (come hop da hoping), aggiungi e indietro → hope

Per la regola di e silenziosa, mantienila semplice: se dopo la rimozione di -ing, lo stem è 3+ caratteri, termina con una consonante, & il penultimo carattere è una vocale (un pattern come hop, mak, tak), aggiungi e indietro.

Aggiungi anche questi nuovi suffissi (controllali prima di -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à dei suffissi aggiornata: -tion, -ness, -ment, -able, -ible, -ing, -ed, -ly, -s

Mantieni la regola della lunghezza minima dello stem: rimuovi solo se lo stem rimanente è 3+ caratteri.

Regole -ies & -ier

Più morfologia

L'inglese ha un altro pattern comune: le parole che terminano in -y cambiano in -ies, -ied, o -ier quando sono flesse.

Aggiungi queste regole prima dei controlli -s & -ed:

- -ies → rimuovi & aggiungi i (babies → babi)

- -ied → rimuovi & aggiungi i (carried → carri)

- -ier → rimuovi & aggiungi i (earlier → earli)

Stessa regola della lunghezza minima dello stem: trasforma solo se il risultato è 3+ caratteri.

Perché Testare?

I test non sono opzionali

Hai uno stemmer che funziona. Come sai che in realtà funziona? Proprio ora, stai eseguendo alcuni esempi a mano. Questo non scala.

Il software professionale utilizza tre livelli di test:

Test unitari: testano una funzione in isolamento con input noti e output attesi. Veloci, numerosi, specifici.

Test di integrazione: testano che più componenti funzionino insieme. Per uno stemmer, questo significa testarlo su un lotto di parole e verificare che i risultati siano coerenti.

Test funzionali: testano il sistema dall'esterno, come farebbe un utente. Per uno stemmer, questo significa alimentarlo con testo reale e verificare che l'output abbia senso per un caso d'uso reale come la ricerca.

Scriverai tutti e tre.

Scrivi i Test Unitari

Test unitari

Scrivi una funzione chiamata run_unit_tests che testa la tua funzione stem con almeno 15 casi di test coprendo:

1. Stripping dei suffissi di base: parole che terminano in -ing, -ed, -ly, -s

2. Suffissi complessi: -tion, -ness, -ment, -able, -ible

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

4. Casi limite: parole corte che non dovrebbero essere rimosse, parole senza suffisso, parole già stemmate

5. Pulizia consonante doppia: running → run, sitting → sit

6. Ripristino di e silenziosa: hoping → hope

7. Insensibilità alle maiuscole: l'input maiuscolo dovrebbe essere minuscolo

Struttura i tuoi test così:

def run_unit_tests():
    tests = [
        ('running', 'run'),
        ('cats', 'cat'),
        # ... almeno 15 casi di test
    ]
    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

Scrivi i Test di Integrazione

Test di integrazione

I test unitari verificano input individuali. I test di integrazione verificano che i componenti funzionino insieme correttamente.

Per uno stemmer, una proprietà di integrazione chiave è coerenza: se stemmi la stessa parola due volte, ottieni lo stesso risultato. E le parole che dovrebbero raggrupparsi dovrebbero produrre lo stesso stem.

Scrivi una funzione chiamata run_integration_tests che testa:

1. Idempotenza: fare uno stemming di una parola già stemmate dovrebbe restituire lo stesso stem. stem(stem(word)) == stem(word) per tutte le parole.

2. Raggruppamento: le parole che dovrebbero condividere uno stem effettivamente lo fanno. Testa almeno 3 famiglie di parole (ad es., run/runs/running/runner dovrebbero tutti condividere uno stem).

3. Elaborazione batch: elabora un elenco di 20+ parole e verifica nessun arresto anomalo, nessuna stringa vuota, nessun valore None.

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

Scrivi i Test Funzionali

Test funzionali

I test funzionali verificano che il sistema funzioni per il suo caso d'uso previsto. Il tuo stemmer esiste per migliorare la ricerca: quindi testalo.

Scrivi una funzione chiamata run_functional_tests che:

1. Simulazione di ricerca: dato un elenco di stringhe di documenti e una parola di query, stemma sia i documenti che la query, quindi controlla se i termini della query stemmate appaiono nei documenti stemmate. Testa che cercare 'running' trovi un documento contenente 'run' e 'runner'.

2. Controllo della precisione: verifica che lo stemming NON raggruppi erroneamente le parole non correlate. 'university' e 'universe' potrebbero condividere uno stem: controlla come il tuo stemmer gestisce questo (va bene se li raggruppa; documenta il comportamento).

3. Elaborazione di testo reale: stemma ogni parola in un paragrafo di testo inglese reale. Verifica che l'output sia ragionevole: nessuna stringa vuota, nessun arresto anomalo, l'output ha lo stesso numero di parole dell'input.

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

Quello che Hai Costruito

Quello che hai costruito

Hai implementato uno stemmer inglese funzionante con:

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

- Pulizia consonante doppia

- Ripristino di e silenziosa

- Test unitari, test di integrazione, & test funzionali

La discendenza

Il tuo stemmer discende da una linea di lavoro iniziata con Zellig Harris nel 1955:

- Harris (1955): Ha scoperto che i confini dei morfemi mostrano come segnali statistici (varietà di successore)

- Lovins (1968): Primo algoritmo di stemming pubblicato, 294 regole di suffisso

- Porter (1980): Semplificato a ~60 regole in 5 passaggi, divenne lo standard per decenni

- Snowball (2001): Quadro di Porter generalizzato a più lingue

- Il tuo stemmer (oggi): 12 regole, lo stesso principio fondamentale

Cosa potresti fare dopo

- Implementare l'algoritmo Porter completo (è ben documentato & un grande esercizio)

- Portare il tuo stemmer in C per un miglioramento della velocità di 100x

- Costruire un semplice motore di ricerca che utilizza il tuo stemmer per indicizzare & interrogare i file di testo

- Confrontare l'output del tuo stemmer con PorterStemmer di NLTK per misurare l'accuratezza

Il codice che hai scritto oggi è la stessa operazione fondamentale che viene eseguita all'interno di ogni motore di ricerca del pianeta. Non male per un giorno di lavoro.