Zellig Harris i Analiza Dystrybucyjna

Pochodzenie obliczeniowego stemmingu

W 1955 roku lingwista Zellig Harris opublikował From Phoneme to Morpheme, opisując metodę znajdowania granic między znaczącymi jednostkami (morfemami) w słowach.

Jego wgląd był dystrybucyjny: jeśli przejrzysz duży korpus angielskich słów, granica między tematem & sufiksem pojawia się jako sygnał statystyczny.

Metoda następnika

Dla dowolnego prefiksu słowa policz, ile odrębnych znaków może go następować w korpusie. Harris nazwał to następnikiem.

Rozważ prefiks "work" w korpusie zawierającym: worked, worker, working, works, workshop.

Po "work" mogą następować cztery różne znaki: skok w różnorodności. Ten skok oznacza granicę morfemu. Temat to work a wszystko po nim to sufiks.

To było radykalne w 1955 roku. Brak reguł lingwistycznych, brak słownika: tylko liczenie. Harris wykazał, że struktura języka objawia się poprzez dystrybucję.

Zrozumienie Następnika Harrisą

Metoda Harrisą działa w każdym języku. Nie musisz znać gramatyki: statystyka ujawnia granice morfemów.

W praktyce czysty następnik wymaga dużego korpusu i ostrożnego wykrywania pików. Później badacze: Lovins (1968), Porter (1980): uprościli podejście do usuwania sufiksów opartego na regułach: zamiast obliczać następnika z korpusu, kodowali reguły sufiksów bezpośrednio.

Dzisiaj zbudujesz usuwacz sufiksów oparty na regułach inspirowany wglądem Harrisą. Zdefiniujesz sufiksy jawnie, a następnie usuniesz je ze słów. Tak funkcjonują większość produkcyjnych stemmerów.

Twój Pierwszy Usuwacz Sufiksów

Zacznijmy kodować

Zacznij prosto. Napisz funkcję o nazwie stem, która bierze słowo & usuwa te sufiksy (w tej kolejności):

1. -ing (running → runn)

2. -ed (walked → walk)

3. -ly (quickly → quick)

4. -s (cats → cat)

Reguły:

- Najpierw konwertuj słowo na małe litery

- Usuwaj tylko jeden sufiks (pierwsza dopasowana reguła w powyższej kolejności)

- Usuwaj tylko, jeśli pozostały temat ma co najmniej 3 znaki

- Zwróć temat

Przykład:

def stem(word):
    word = word.lower()
    # twoja logika usuwania sufiksów tutaj
    return word

Obsługa Przypadków Brzegowych

Robienie stemmera inteligentniejszym

Twój podstawowy usuwacz ma problem: running → runn & hoping → hop. Potrzebujemy dwóch ulepszeń:

1. Czyszczenie spółgłosek podwójnych: jeśli usunięcie -ing lub -ed zostawia spółgłoskę podwójną na końcu (jak runn), usuń ostatnią literę → run

2. Przywrócenie cichy e: jeśli usunięcie -ing zostawia temat kończący się spółgłoską (nie samogłoską), & oryginał mógł mieć ciche e (jak hop z hoping), dodaj e z powrotem → hope

Dla reguły cichego e, zachowaj ją prosto: jeśli po usunięciu -ing, temat to 3+ znaki, kończy się spółgłoską, & drugi do ostatniego znaku to samogłoska (wzór jak hop, mak, tak), dodaj e z powrotem.

Dodaj także te nowe sufiksy (sprawdzaj je przed -ing, -ed, -ly, -s):

5. -tion (organization → organiza)

6. -ness (happiness → happi)

7. -ment (movement → move)

8. -able (readable → read)

9. -ible (sensible → sens)

Zaktualizowana kolejność sufixów: -tion, -ness, -ment, -able, -ible, -ing, -ed, -ly, -s

Zachowaj regułę minimalnej długości tematu: usuwaj tylko jeśli pozostały temat to 3+ znaki.

Reguły -ies & -ier

Więcej morfologii

Angielski ma inny wspólny wzór: słowa kończące się na -y zmieniają się na -ies, -ied, lub -ier gdy są odmieniające się.

Dodaj te reguły przed kontrolami -s & -ed:

- -ies → usuń & dodaj i (babies → babi)

- -ied → usuń & dodaj i (carried → carri)

- -ier → usuń & dodaj i (earlier → earli)

Ta sama reguła minimalnej długości tematu: transformuj tylko jeśli wynik to 3+ znaki.

Dlaczego Testować?

Testowanie nie jest opcjonalne

Masz pracujący stemmer. Skąd wiesz, że faktycznie działa? Teraz uruchamiasz kilka przykładów ręcznie. To nie skaluje się.

Profesjonalne oprogramowanie używa trzech poziomów testowania:

Testy jednostkowe: testuj jedną funkcję w izolacji ze znanymi wejściami i oczekiwanymi wyjściami. Szybkie, liczne, konkretne.

Testy integracyjne: testuj, że wiele komponentów współpracuje razem. Dla stemmera, oznacza to testowanie go na partii słów i weryfikację, że wyniki są spójne.

Testy funkcjonalne: testuj system z zewnątrz, tak jak robiłby to użytkownik. Dla stemmera, oznacza to karmienie go prawdziwym tekstem i weryfikację, że wynik ma sens dla rzeczywistego przypadku użycia, takiego jak wyszukiwanie.

Będziesz pisać wszystkie trzy.

Napisz Testy Jednostkowe

Testy jednostkowe

Napisz funkcję o nazwie run_unit_tests, która testuje twoją funkcję stem z co najmniej 15 przypadkami testowymi obejmującymi:

1. Podstawowe usuwanie suffiksów: słowa kończące się na -ing, -ed, -ly, -s

2. Złożone sufiksy: -tion, -ness, -ment, -able, -ible

3. Odmiany y: -ies, -ied, -ier

4. Przypadki brzegowe: krótkie słowa, które nie powinny być usunięte, słowa bez suffiksu, już stemmowe słowa

5. Czyszczenie spółgłosek podwójnych: running → run, sitting → sit

6. Przywrócenie cichego e: hoping → hope

7. Niezależność od wielkości liter: wejście w dużych literach powinno być zmieniane na małe litery

Strukturyzuj testy w ten sposób:

def run_unit_tests():
    tests = [
        ('running', 'run'),
        ('cats', 'cat'),
        # ... co najmniej 15 przypadków testowych
    ]
    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

Napisz Testy Integracyjne

Testy integracyjne

Testy jednostkowe weryfikują poszczególne wejścia. Testy integracyjne weryfikują, że komponenty razem działają poprawnie.

Dla stemmera, kluczową właściwością integracyjną jest spójność: jeśli stemmisz to samo słowo dwa razy, otrzymujesz ten sam wynik. & słowa, które powinny się grupować, powinny dać ten sam temat.

Napisz funkcję o nazwie run_integration_tests, która testuje:

1. Idempotentność: stemowanie już stemmowanego słowa powinno zwrócić ten sam temat. stem(stem(word)) == stem(word) dla wszystkich słów.

2. Grupowanie: słowa, które powinny dzielić temat rzeczywiście to robią. Przetestuj co najmniej 3 rodziny słów (np. run/runs/running/runner powinny wszystkie dzielić temat).

3. Przetwarzanie batch: przetworzaj listę 20+ słów i weryfikuj brak crashów, brak pustych ciągów, brak wartości None.

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

Napisz Testy Funkcjonalne

Testy funkcjonalne

Testy funkcjonalne weryfikują, że system działa dla zamierzonego przypadku użycia. Twój stemmer istnieje, aby poprawić wyszukiwanie: więc przetestuj to.

Napisz funkcję o nazwie run_functional_tests, która:

1. Symulacja wyszukiwania: biorąc listę ciągów dokumentów i słowo kwerendy, stemuj zarówno dokumenty, jak i kwerendę, a następnie sprawdzić, czy warunki stemowanej kwerendy pojawiają się w stemmowanych dokumentach. Przetestuj, że wyszukiwanie "running" znajduje dokument zawierający "run" i "runner".

2. Sprawdzenie dokładności: zweryfikuj, że stemming NIEE nieprawidłowo grupy niepowiązane słowa. "university" i "universe" mogą dzielić temat: sprawdzić, czy twój stemmer to obsługuje (jest OK, jeśli je grupuje; udokumentuj zachowanie).

3. Przetwarzanie rzeczywistego tekstu: stemmuj każde słowo w akapicie prawdziwego angielskiego tekstu. Zweryfikuj, że wynik jest rozsądny: brak pustych ciągów, brak crashów, wynik ma tę samą liczbę słów co wejście.

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

Co Zbudowałeś

Co zbudowałeś

Zaimplementowałeś pracujący angielski stemmer z:

- 12 reguł suffiksów (-tion, -ness, -ment, -able, -ible, -ies, -ied, -ier, -ing, -ed, -ly, -s)

- Czyszczenie spółgłosek podwójnych

- Przywrócenie cichego e

- Testy jednostkowe, testy integracyjne, & testy funkcjonalne

Linia dziedziczenia

Twój stemmer pochodzi z linii pracy, która zaczęła się od Zelliga Harrisą w 1955 roku:

- Harris (1955): Odkrył, że granice morfemów pojawiają się jako sygnały statystyczne (następnik)

- Lovins (1968): Pierwszy opublikowany algorytm stemmingu, 294 reguł suffiksów

- Porter (1980): Uproszczył do ~60 reguł w 5 krokach, stał się standardem przez dziesięciolecia

- Snowball (2001): Framework Portera uogólniony do wielu języków

- Twój stemmer (dzisiaj): 12 reguł, ta sama zasada rdzenia

Co możesz zrobić dalej

- Zaimplementuj pełny algorytm Portera (jest dobrze udokumentowany & świetne ćwiczenie)

- Portuj swój stemmer do C dla 100x przyspieszenia

- Zbuduj prostą wyszukiwarkę, która używa twojego stemmera do indeksowania & zapytań plików tekstowych

- Porównaj wynik twojego stemmera z PorterStemmer NLTK, aby zmierzyć dokładność

Kod, który napisałeś dzisiaj, jest tą samą fundamentalną operacją, która działa wewnątrz każdej wyszukiwarki na planecie. Nieźle na dzień pracy.