Zellig Harris und Distributional Analysis

Der Ursprung des computergestützten Stemmings

1955 veröffentlichte der Linguist Zellig Harris From Phoneme to Morpheme und beschrieb eine Methode zum Finden der Grenzen zwischen bedeutungsvollen Einheiten (Morphemen) in Wörtern.

Seine Einsicht war distributiv: Wenn Sie ein großes Corpus englischer Wörter betrachten, zeigt sich die Grenze zwischen einem Stamm und einem Suffix als statistisches Signal.

Die Successor-Variety-Methode

Für jedes Präfix eines Wortes zählen Sie, wie viele verschiedene Zeichen in dem Corpus darauf folgen. Harris nannte dies die Successor Variety.

Betrachten Sie das Präfix "work" in einem Corpus mit: worked, worker, working, works, workshop.

Nach "work" können vier verschiedene Zeichen folgen: ein Anstieg der Vielfalt. Dieser Anstieg markiert eine Morphemgrenze. Der Stamm ist work und alles danach ist ein Suffix.

Dies war 1955 revolutionär. Keine linguistischen Regeln, kein Wörterbuch: nur Zählen. Harris zeigte, dass sich die Struktur der Sprache durch Distribution offenbart.

Successor Variety verstehen

Harris's Methode funktioniert in jeder Sprache. Sie müssen die Grammatik nicht kennen: Die Statistiken offenbaren die Morphemgrenzen.

In der Praxis erfordert reine Successor Variety ein großes Corpus und sorgfältige Peak-Erkennung. Spätere Forscher wie Lovins (1968) und Porter (1980) vereinfachten den Ansatz zu regelbasiertem Suffix-Stripping: Anstatt Successor Variety aus einem Corpus zu berechnen, codierten sie die Suffix-Regeln direkt.

Heute werden Sie einen regelbasierten Suffix-Stripper bauen, der von Harris's Einsicht inspiriert ist. Sie werden die Suffixe explizit definieren und dann von Wörtern abziehen. So funktionieren die meisten produktiven Stemmer.

Ihr erster Suffix-Stripper

Lassen Sie uns Code schreiben

Fangen Sie einfach an. Schreiben Sie eine Funktion namens stem, die ein Wort nimmt und diese Suffixe abzieht (in dieser Reihenfolge):

1. -ing (running → runn)

2. -ed (walked → walk)

3. -ly (quickly → quick)

4. -s (cats → cat)

Regeln:

- Konvertieren Sie das Wort zuerst in Kleinbuchstaben

- Ziehen Sie nur ein Suffix ab (der erste Match in der obigen Reihenfolge)

- Ziehen Sie nur ab, wenn der verbleibende Stamm mindestens 3 Zeichen lang ist

- Geben Sie den Stamm zurück

Beispiel:

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

Umgang mit Sonderfällen

Den Stemmer intelligenter machen

Ihr grundlegender Stripper hat ein Problem: running → runn und hoping → hop. Wir brauchen zwei Verbesserungen:

1. Bereinigung von Doppelkonsonanten: Wenn das Abziehen von -ing oder -ed einen Doppelkonsonanten am Ende hinterlässt (wie runn), entfernen Sie den letzten Buchstaben → run

2. Stilles-e-Wiederherstellung: Wenn das Abziehen von -ing einen Stamm mit Konsonant am Ende hinterlässt (kein Vokal), und der ursprüngliche möglicherweise ein stilles e hatte (wie hop von hoping), fügen Sie e zurück → hope

Halten Sie es für die stille-e-Regel einfach: Wenn nach dem Abziehen von -ing der Stamm 3+ Zeichen ist, mit Konsonant endet, und das zweite-letzte Zeichen ein Vokal ist (ein Muster wie hop, mak, tak), fügen Sie e zurück.

Fügen Sie auch diese neuen Suffixe hinzu (überprüfen Sie sie vor -ing, -ed, -ly, -s):

5. -tion (organization → organiza)

6. -ness (happiness → happi)

7. -ment (movement → move)

8. -able (readable → read)

9. -ible (sensible → sens)

Aktualisierte Suffix-Priorität: -tion, -ness, -ment, -able, -ible, -ing, -ed, -ly, -s

Behalten Sie die Regel für minimale Stammlänge: Ziehen Sie nur ab, wenn der verbleibende Stamm 3+ Zeichen hat.

-ies & -ier Regeln

Mehr Morphologie

Englisch hat ein anderes häufiges Muster: Wörter, die auf -y enden, ändern sich zu -ies, -ied oder -ier, wenn sie flektiert werden.

Fügen Sie diese Regeln vor den -s & -ed Überprüfungen hinzu:

- -ies → abziehen & hinzufügen i (babies → babi)

- -ied → abziehen & hinzufügen i (carried → carri)

- -ier → abziehen & hinzufügen i (earlier → earli)

Gleiche Regel für minimale Stammlänge: transformieren Sie nur, wenn das Ergebnis 3+ Zeichen hat.

Warum Testen?

Testen ist nicht optional

Sie haben einen funktionsfähigen Stemmer. Woher wissen Sie, dass er wirklich funktioniert? Im Moment führen Sie ein paar Beispiele von Hand aus. Das skaliert nicht.

Professionelle Software verwendet drei Ebenen des Testens:

Unit Tests: testen Sie eine Funktion isoliert mit bekannten Ein- und Ausgaben. Schnell, zahlreich, spezifisch.

Integrationstests: testen Sie, dass mehrere Komponenten zusammenarbeiten. Für einen Stemmer bedeutet dies, ihn gegen einen Batch von Wörtern zu testen und zu überprüfen, ob die Ergebnisse konsistent sind.

Funktionstests: testen Sie das System von außen, wie ein Benutzer es würde. Für einen Stemmer bedeutet dies, echten Text einzuführen und zu überprüfen, ob die Ausgabe für einen realen Anwendungsfall wie Suche sinnvoll ist.

Sie werden alle drei schreiben.

Schreiben Sie Unit Tests

Unit Tests

Schreiben Sie eine Funktion namens run_unit_tests, die Ihre stem-Funktion mit mindestens 15 Testfällen testet, die folgende abdecken:

1. Grundlegendes Suffix-Stripping: Wörter, die auf -ing, -ed, -ly, -s enden

2. Komplexe Suffixe: -tion, -ness, -ment, -able, -ible

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

4. Sonderfälle: kurze Wörter, die nicht entfernt werden sollten, Wörter ohne Suffix, bereits stammende Wörter

5. Bereinigung von Doppelkonsonanten: running → run, sitting → sit

6. Wiederherstellung des stillen e: hoping → hope

7. Schreibweise-Unempfindlichkeit: Großbuchstaben-Eingabe sollte zu Kleinbuchstaben konvertiert werden

Strukturieren Sie Ihre Tests wie folgt:

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

Schreiben Sie Integrationstests

Integrationstests

Unit Tests überprüfen einzelne Eingaben. Integrationstests überprüfen, dass Komponenten korrekt zusammenarbeiten.

Für einen Stemmer ist eine Schlüssel-Integrationseigenschaft Konsistenz: Wenn Sie das gleiche Wort zweimal stemmen, erhalten Sie das gleiche Ergebnis. Und Wörter, die zusammen gruppiert werden sollten, sollten den gleichen Stamm produzieren.

Schreiben Sie eine Funktion namens run_integration_tests, die testet:

1. Idempotenz: Das Stemmen eines bereits gestemmten Wortes sollte den gleichen Stamm zurückgeben. stem(stem(word)) == stem(word) für alle Wörter.

2. Gruppierung: Wörter, die einen Stamm teilen sollten, tun dies tatsächlich. Testen Sie mindestens 3 Wortfamilien (z. B. run/runs/running/runner sollten alle einen Stamm teilen).

3. Batch-Verarbeitung: verarbeiten Sie eine Liste von 20+ Wörtern und überprüfen Sie keine Absturze, keine leeren Strings, keine None-Werte.

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

Schreiben Sie Funktionstests

Funktionstests

Funktionstests überprüfen, dass das System für seinen beabsichtigten Anwendungsfall funktioniert. Ihr Stemmer soll die Suche verbessern: also testen Sie das.

Schreiben Sie eine Funktion namens run_functional_tests, die:

1. Such-Simulation: Bei einer Liste von Dokument-Strings und einem Abfrage-Wort stemmen Sie beide Dokumente und die Abfrage, überprüfen dann, ob Begriffe aus der gestemmten Abfrage in gestemmten Dokumenten erscheinen. Testen Sie, dass die Suche nach 'running' ein Dokument mit 'run' und 'runner' findet.

2. Genauigkeitsprüfung: Überprüfen Sie, dass Stemming verwandte Wörter NICHT fälschlicherweise gruppiert. 'university' und 'universe' könnten einen Stamm teilen: Überprüfen Sie, ob Ihr Stemmer dies behandelt (es ist OK, wenn er sie gruppiert; dokumentieren Sie das Verhalten).

3. Verarbeitung echter Texte: stemmen Sie jedes Wort in einem Absatz von echtem englischen Text. Überprüfen Sie, dass die Ausgabe sinnvoll ist: keine leeren Strings, keine Abstürze, die Ausgabe hat die gleiche Anzahl von Wörtern wie die Eingabe.

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

Was Sie gebaut haben

Was Sie gebaut haben

Sie implementierten einen funktionsfähigen englischen Stemmer mit:

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

- Bereinigung von Doppelkonsonanten

- Wiederherstellung des stillen e

- Unit-Tests, Integrationstests & Funktionstests

Die Abstammung

Ihr Stemmer stammt ab von einer Reihe von Arbeiten, die 1955 mit Zellig Harris begannen:

- Harris (1955): Entdeckte, dass sich Morphemgrenzen als statistische Signale zeigen (Successor Variety)

- Lovins (1968): Veröffentlichte den ersten Stemming-Algorithmus mit 294 Suffix-Regeln

- Porter (1980): Vereinfacht auf ~60 Regeln in 5 Schritten, wurde zum Standard für Jahrzehnte

- Snowball (2001): Porters Framework verallgemeinert auf mehrere Sprachen

- Ihr Stemmer (heute): 12 Regeln, gleiches Kernprinzip

Was Sie als nächstes tun könnten

- Implementieren Sie den vollständigen Porter-Algorithmus (er ist gut dokumentiert und eine großartige Übung)

- Portieren Sie Ihren Stemmer auf C für eine 100x Geschwindigkeitsverbesserung

- Bauen Sie eine einfache Suchmaschine, die Ihren Stemmer zum Indexieren und Abfragen von Textdateien verwendet

- Vergleichen Sie die Ausgabe Ihres Stemmers mit NLTKs PorterStemmer, um die Genauigkeit zu messen

Der Code, den Sie heute geschrieben haben, ist die gleiche grundlegende Operation, die in jeder Suchmaschine auf dem Planeten ausgeführt wird. Nicht schlecht für einen Tag's Arbeit.