Зеліг Гарріс та дистрибутивний аналіз

Походження обчислювального стемінгу

У 1955 році лінгвіст Зеліг Гарріс опублікував працю Від фонеми до морфеми, описуючи метод знаходження меж між значущими одиницями (морфемами) у словах.

Його прозріння було дистрибутивним: якщо подивитися на великий корпус англійських слів, межа між основою та суфіксом проявляється як статистичний сигнал.

Метод наступних варіантів

Для будь-якого префікса слова порахуй, скільки різних символів слідують за ним у корпусі. Гарріс назвав це наступним різноманіттям.

Розглянь префікс "work" у корпусі, що містить: worked, worker, working, works, workshop.

Після "work" можуть слідувати чотири різні символи: сплеск різноманіття. Цей сплеск позначає межу морфеми. Основа -- work, а все після неї -- суфікс.

У 1955 році це було радикально. Жодних лінгвістичних правил, жодного словника: лише підрахунок. Гарріс показав, що структура мови розкривається через дистрибуцію.

Розуміння наступного різноманіття

Метод Гарріса працює для будь-якої мови. Тобі не потрібно знати граматику: статистика розкриває межі морфем.

На практиці чисте наступне різноманіття вимагає великого корпусу та ретельного виявлення піків. Пізніші дослідники: Ловінс (1968), Портер (1980): спростили підхід до відсікання суфіксів на основі правил: замість обчислення наступного різноманіття з корпусу вони закодували правила суфіксів безпосередньо.

Сьогодні ти побудуєш стемер на основі правил, натхненний прозрінням Гарріса. Ти визначиш суфікси явно, потім відсічеш їх від слів. Так працює більшість виробничих стемерів.

Твій перший відсікач суфіксів

Кодуймо

Почни просто. Напиши функцію stem, яка приймає слово та відсікає ці суфікси (у такому порядку):

1. -ing (running → runn)

2. -ed (walked → walk)

3. -ly (quickly → quick)

4. -s (cats → cat)

Правила:

- Спочатку перетвори слово на нижній регістр

- Відсікай лише один суфікс (перший збіг у наведеному порядку)

- Відсікай лише якщо залишкова основа має щонайменше 3 символи

- Поверни основу

Приклад:

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

Обробка граничних випадків

Робимо стемер розумнішим

Твій базовий відсікач має проблему: running → runn та hoping → hop. Нам потрібні два уточнення:

1. Очищення подвійних приголосних: якщо відсікання -ing або -ed залишає подвійний приголосний у кінці (як runn), видали останню літеру → run

2. Відновлення безмовного «е»: якщо відсікання -ing залишає основу, що закінчується на приголосну (не голосну), і оригінал міг мати безмовне e (як hop з hoping), додай e назад → hope

Для правила безмовного «е» зроби просто: якщо після відсікання -ing основа має 3+ символи, закінчується на приголосну, і передостанній символ -- голосний (шаблон як hop, mak, tak), додай e назад.

Також додай ці нові суфікси (перевіряй їх перед -ing, -ed, -ly, -s):

5. -tion (organization → organiza)

6. -ness (happiness → happi)

7. -ment (movement → move)

8. -able (readable → read)

9. -ible (sensible → sens)

Оновлений пріоритет суфіксів: -tion, -ness, -ment, -able, -ible, -ing, -ed, -ly, -s

Зберігай правило мінімальної довжини основи: відсікай лише якщо залишкова основа має 3+ символи.

Правила -ies та -ier

Більше морфології

Англійська мова має ще один поширений шаблон: слова, що закінчуються на -y, змінюються на -ies, -ied або -ier при інфлекції.

Додай ці правила перед перевірками -s та -ed:

- -ies → відсічи та додай i (babies → babi)

- -ied → відсічи та додай i (carried → carri)

- -ier → відсічи та додай i (earlier → earli)

Те саме правило мінімальної довжини основи: трансформуй лише якщо результат має 3+ символи.

Навіщо тестувати?

Тестування не є необов'язковим

У тебе є робочий стемер. Як ти знаєш, що він насправді працює? Зараз ти запускаєш кілька прикладів вручну. Це не масштабується.

Професійне програмне забезпечення використовує три рівні тестування:

Модульні тести: тестують одну функцію ізольовано з відомими вхідними даними та очікуваними результатами. Швидкі, численні, конкретні.

Інтеграційні тести: перевіряють, що кілька компонентів працюють разом. Для стемера це означає тестування на пакеті слів і перевірку узгодженості результатів.

Функціональні тести: тестують систему ззовні, як це робить користувач. Для стемера це означає подачу реального тексту та перевірку, що вихід має сенс для реального випадку використання, наприклад пошуку.

Ти напишеш усі три.

Пишемо модульні тести

Модульні тести

Напиши функцію run_unit_tests, яка тестує функцію stem з щонайменше 15 тестовими випадками, що охоплюють:

1. Базове відсікання суфіксів: слова, що закінчуються на -ing, -ed, -ly, -s

2. Складні суфікси: -tion, -ness, -ment, -able, -ible

3. Відмінювання через -y: -ies, -ied, -ier

4. Граничні випадки: короткі слова без відсікання, слова без суфікса, вже зведені слова

5. Очищення подвійних приголосних: running → run, sitting → sit

6. Відновлення безмовного «е»: hoping → hope

7. Нечутливість до регістру: введення у верхньому регістрі має бути переведено в нижній

Структуруй свої тести ось так:

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

Пишемо інтеграційні тести

Інтеграційні тести

Модульні тести перевіряють окремі вхідні дані. Інтеграційні тести перевіряють, що компоненти правильно працюють разом.

Для стемера ключова інтеграційна властивість -- узгодженість: якщо ти зведеш одне й те ж слово двічі, отримаєш той самий результат. А слова, що мають групуватися разом, повинні давати однакову основу.

Напиши функцію run_integration_tests, яка тестує:

1. Ідемпотентність: зведення вже зведеного слова має повертати ту саму основу. stem(stem(word)) == stem(word) для всіх слів.

2. Групування: слова, що мають спільну основу, дійсно її мають. Перевір щонайменше 3 родини слів (наприклад, run/runs/running/runner мають мати спільну основу).

3. Пакетна обробка: обробити список з 20+ слів і перевірити відсутність збоїв, порожніх рядків, значень None.

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

Пишемо функціональні тести

Функціональні тести

Функціональні тести перевіряють, що система працює для свого призначеного використання. Твій стемер існує для покращення пошуку: то й тестуй це.

Напиши функцію run_functional_tests, яка:

1. Симуляція пошуку: дано список рядків документів та слово-запит, зведи як документи, так і запит, потім перевір, чи з'являються зведені терміни запиту в зведених документах. Перевір, що пошук 'running' знаходить документ, що містить 'run' і 'runner'.

2. Перевірка точності: переконайся, що стемінг НЕ помилково групує непов'язані слова. 'university' та 'universe' можуть мати спільну основу: перевір, як твій стемер з цим справляється (нормально, якщо він їх групує; задокументуй таку поведінку).

3. Обробка реального тексту: зведи кожне слово в абзаці реального англійського тексту. Переконайся, що вихідні дані розумні: немає порожніх рядків, немає збоїв, вихід містить стільки ж слів, скільки й вхід.

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

Що ти побудував

Що ти побудував

Ти реалізував робочий англійський стемер з:

- 12 правилами суфіксів (-tion, -ness, -ment, -able, -ible, -ies, -ied, -ier, -ing, -ed, -ly, -s)

- Очищенням подвійних приголосних

- Відновленням безмовного «е»

- Модульними тестами, інтеграційними тестами та функціональними тестами

Лінія наступності

Твій стемер походить від лінії робіт, що почалася із Зеліга Харріса у 1955 році:

- Харріс (1955): Виявив, що межі морфем проявляються як статистичні сигнали (метод наступних варіантів)

- Ловінс (1968): Перший опублікований алгоритм стемінгу, 294 правила суфіксів

- Портер (1980): Спрощено до ~60 правил у 5 кроках, став стандартом на десятиліття

- Snowball (2001): Фреймворк Портера узагальнено для кількох мов

- Твій стемер (сьогодні): 12 правил, той самий основний принцип

Що ти міг би зробити далі

- Реалізувати повний алгоритм Портера (він добре задокументований та є чудовою вправою)

- Портувати стемер на C для покращення швидкості в 100 разів

- Побудувати просту пошукову систему, яка використовує твій стемер для індексування та пошуку текстових файлів

- Порівняти вихід свого стемера з PorterStemmer від NLTK для вимірювання точності

Код, який ти написав сьогодні, -- це та сама фундаментальна операція, що виконується всередині кожної пошукової системи на планеті. Непогано для одного дня роботи.