Зеллиг Харрис и распределительный анализ

Истоки вычислительного стемминга

В 1955 году лингвист Зеллиг Харрис опубликовал От фонемы к морфеме, описывая метод поиска границ между значимыми единицами (морфемами) в словах.

Его идея была распределительной: если вы посмотрите на большой корпус английских слов, граница между основой & суффиксом проявляется как статистический сигнал.

Метод разнообразия преемников

Для любого префикса слова подсчитайте, сколько разных символов за ним следуют в корпусе. Харрис назвал это разнообразием преемников.

Рассмотрим префикс "work" в корпусе, содержащем: worked, worker, working, works, workshop.

После "work" могут следовать четыре разных символа: скачок в разнообразии. Этот скачок отмечает границу морфемы. Основа — work, а все остальное — суффикс.

Это было радикально в 1955 году. Никаких лингвистических правил, никакого словаря: просто подсчет. Харрис показал, что структура языка раскрывает себя через распределение.

Понимание разнообразия преемников

Метод Харриса работает для любого языка. Вам не нужно знать грамматику: статистика раскрывает границы морфем.

На практике чистое разнообразие преемников требует большого корпуса и тщательного определения пика. Более поздние исследователи: Lovins (1968), Porter (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()
    # ваша логика удаления суффиксов здесь
    return word

Обработка граничных случаев

Делаем стеммер умнее

Ваш базовый удалитель имеет проблему: running → runn & hoping → hop. Нам нужны два улучшения:

1. Очистка двойных согласных: если удаление -ing или -ed оставляет двойной согласный в конце (как runn), удалите последний символ → run

2. Восстановление немого e: если удаление -ing оставляет основу, заканчивающуюся согласной (не гласной), & исходное слово могло иметь немое e (как hop из hoping), добавьте e назад → hope

Для правила немого e, держите его просто: если после удаления -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. Восстановление немого e: hoping → hope

7. Нечувствительность к регистру: прописной ввод должен быть переведен в нижний регистр

Структурируйте ваши тесты так:

def run_unit_tests():
    tests = [
        ('running', 'run'),
        ('cats', 'cat'),
        # ... не менее 15 тестовых случаев
    ]
    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():
    # Тест 1: идемпотентность
    # Тест 2: группировка семейств слов
    # Тест 3: стабильность партии
    ...

Напишите функциональные тесты

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

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

Напишите функцию под названием run_functional_tests, которая:

1. Моделирование поиска: дан список строк документа и слово запроса, стеммируйте как документы, так и запрос, затем проверьте, появляются ли стеммированные условия запроса в стеммированных документах. Протестируйте, что поиск 'running' находит документ, содержащий 'run' и 'runner'.

2. Проверка точности: убедитесь, что стемминг НЕ группирует неправильно несвязанные слова. 'university' и 'universe' могут делить стем: проверьте, как ваш стеммер это обрабатывает (это нормально, если он их группирует; задокументируйте поведение).

3. Обработка реального текста: стеммируйте каждое слово в абзаце реального английского текста. Убедитесь, что вывод разумен: нет пустых строк, нет сбоев, вывод имеет такое же количество слов, как вход.

def run_functional_tests():
    # Тест 1: поиск находит связанные документы
    # Тест 2: точность: проверка избыточного стемминга
    # Тест 3: обработка реального абзаца
    ...

Что вы создали

Что вы создали

Вы реализовали работающий английский стеммер с:

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

- Очисткой двойных согласных

- Восстановлением немого e

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

Родословная

Ваш стеммер происходит из линии работ, которая началась с Зеллига Харриса в 1955 году:

- Харрис (1955): Открыл, что границы морфем проявляются как статистические сигналы (разнообразие преемников)

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

- Porter (1980): Упрощено до ~60 правил в 5 шагов, стал стандартом на десятилетия

- Snowball (2001): Фреймворк Porter обобщен для нескольких языков

- Ваш стеммер (сегодня): 12 правил, тот же основной принцип

Что вы можете делать дальше

- Реализуйте полный алгоритм Porter (это хорошо задокументировано & отличное упражнение)

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

- Создайте простую поисковую систему, которая использует ваш стеммер для индексирования & запроса текстовых файлов

- Сравните выход вашего стеммера с PorterStemmer NLTK для измерения точности

Код, который вы написали сегодня, — это та же фундаментальная операция, которая работает внутри каждой поисковой системы на планете. Неплохо для дневной работы.