Zellig Harris e Análise Distribucional

A origem do stemming computacional

Em 1955, o linguista Zellig Harris publicou From Phoneme to Morpheme, descrevendo um método para encontrar as fronteiras entre unidades significativas (morfemas) em palavras.

Sua visão foi distribucional: se você olhar para um grande corpus de palavras em inglês, a fronteira entre um stem & um sufixo aparece como um sinal estatístico.

O método da variedade sucessora

Para qualquer prefixo de uma palavra, conte quantos caracteres distintos o seguem no corpus. Harris chamou isso de variedade sucessora.

Considere o prefixo "work" em um corpus contendo: worked, worker, working, works, workshop.

Depois de "work", quatro caracteres diferentes podem seguir: um pico na variedade. Esse pico marca uma fronteira de morfema. O stem é work e tudo depois dele é um sufixo.

Isso era radical em 1955. Nenhuma regra linguística, nenhum dicionário: apenas contagem. Harris mostrou que a estrutura da linguagem se revela através da distribuição.

Entendendo Variedade Sucessora

O método de Harris funciona em qualquer idioma. Você não precisa saber a gramática: a estatística revela as fronteiras dos morfemas.

Na prática, a variedade sucessora pura requer um grande corpus e detecção cuidadosa de picos. Pesquisadores posteriores: Lovins (1968), Porter (1980): simplificaram a abordagem em remoção de sufixos baseada em regras: em vez de computar a variedade sucessora a partir de um corpus, eles codificaram as regras de sufixo diretamente.

Hoje você construirá um removedor de sufixos baseado em regras inspirado pela visão de Harris. Você definirá os sufixos explicitamente, depois os removerá das palavras. É assim que a maioria dos stemmers de produção funcionam.

Seu Primeiro Removedor de Sufixos

Vamos programar

Comece simples. Escreva uma função chamada stem que pega uma palavra & remove esses sufixos (nessa ordem):

1. -ing (running → runn)

2. -ed (walked → walk)

3. -ly (quickly → quick)

4. -s (cats → cat)

Regras:

- Converta a palavra para minúsculas primeiro

- Remova apenas um sufixo (a primeira correspondência na ordem acima)

- Remova apenas se o stem restante tem pelo menos 3 caracteres de comprimento

- Retorne o stem

Exemplo:

def stem(word):
    word = word.lower()
    # sua lógica de remoção de sufixo aqui
    return word

Tratando Casos Extremos

Tornando o stemmer mais inteligente

Seu stripper básico tem um problema: running → runn & hoping → hop. Precisamos de dois refinamentos:

1. Limpeza de consoante dupla: se remover -ing ou -ed deixa uma consoante dupla no final (como runn), remova a última letra → run

2. Restauração de e silencioso: se remover -ing deixa um stem terminando em uma consoante (não uma vogal), & o original poderia ter tido um e silencioso (como hop de hoping), adicione e de volta → hope

Para a regra de e silencioso, mantenha simples: se depois de remover -ing, o stem tem 3+ caracteres, termina com uma consoante, & o penúltimo caractere é uma vogal (um padrão como hop, mak, tak), adicione e de volta.

Também adicione esses novos sufixos (verifique-os antes de -ing, -ed, -ly, -s):

5. -tion (organization → organiza)

6. -ness (happiness → happi)

7. -ment (movement → move)

8. -able (readable → read)

9. -ible (sensible → sens)

Prioridade de sufixo atualizada: -tion, -ness, -ment, -able, -ible, -ing, -ed, -ly, -s

Mantenha a regra de comprimento mínimo do stem: remova apenas se o stem restante tem 3+ caracteres.

Regras -ies & -ier

Mais morfologia

O inglês tem outro padrão comum: palavras terminando em -y mudam para -ies, -ied, ou -ier quando flexionadas.

Adicione essas regras antes das verificações -s & -ed:

- -ies → remova & adicione i (babies → babi)

- -ied → remova & adicione i (carried → carri)

- -ier → remova & adicione i (earlier → earli)

Mesma regra de comprimento mínimo do stem: transforme apenas se o resultado tem 3+ caracteres.

Por que Testar?

Testes não são opcionais

Você tem um stemmer funcional. Como você sabe que ele realmente funciona? Agora você está executando alguns exemplos à mão. Isso não escala.

O software profissional usa três níveis de testes:

Testes unitários: testam uma função isoladamente com entradas conhecidas e saídas esperadas. Rápidos, numerosos, específicos.

Testes de integração: testam que múltiplos componentes funcionam juntos. Para um stemmer, isso significa testar contra um lote de palavras e verificar se os resultados são consistentes.

Testes funcionais: testam o sistema de fora, como um usuário faria. Para um stemmer, isso significa alimentá-lo com texto real e verificar se a saída faz sentido para um caso de uso real como busca.

Você vai escrever todos os três.

Escreva Testes Unitários

Testes unitários

Escreva uma função chamada run_unit_tests que testa sua função stem com pelo menos 15 casos de teste cobrindo:

1. Remoção básica de sufixo: palavras terminando em -ing, -ed, -ly, -s

2. Sufixos complexos: -tion, -ness, -ment, -able, -ible

3. Flexão de y: -ies, -ied, -ier

4. Casos extremos: palavras curtas que não devem ser removidas, palavras sem sufixo, palavras já stemmadas

5. Limpeza de consoante dupla: running → run, sitting → sit

6. Restauração de e silencioso: hoping → hope

7. Insensibilidade a maiúsculas: entrada em maiúsculas deve ser convertida para minúsculas

Estruture seus testes assim:

def run_unit_tests():
    tests = [
        ('running', 'run'),
        ('cats', 'cat'),
        # ... pelo menos 15 casos de teste
    ]
    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

Escreva Testes de Integração

Testes de integração

Testes unitários verificam entradas individuais. Testes de integração verificam que componentes funcionam juntos corretamente.

Para um stemmer, uma propriedade de integração chave é consistência: se você stemma a mesma palavra duas vezes, obtém o mesmo resultado. E palavras que devem agrupar-se devem produzir o mesmo stem.

Escreva uma função chamada run_integration_tests que testa:

1. Idempotência: stemmando uma palavra já stemmada deve retornar o mesmo stem. stem(stem(word)) == stem(word) para todas as palavras.

2. Agrupamento: palavras que devem compartilhar um stem realmente compartilham. Teste pelo menos 3 famílias de palavras (p.ex., run/runs/running/runner devem todos compartilhar um stem).

3. Processamento em lote: processe uma lista de 20+ palavras e verifique sem crashes, sem strings vazias, sem valores None.

def run_integration_tests():
    # Teste 1: idempotência
    # Teste 2: agrupamento de família de palavras
    # Teste 3: estabilidade em lote
    ...

Escreva Testes Funcionais

Testes funcionais

Testes funcionais verificam que o sistema funciona para seu caso de uso pretendido. Seu stemmer existe para melhorar a busca: então teste isso.

Escreva uma função chamada run_functional_tests que:

1. Simulação de busca: dada uma lista de strings de documentos e uma palavra de consulta, stemma tanto os documentos quanto a consulta, depois verifique se os termos de consulta stemmados aparecem em documentos stemmados. Teste que buscar por 'running' encontra um documento contendo 'run' e 'runner'.

2. Verificação de precisão: verifique que stemming NÃO agrupa incorretamente palavras não relacionadas. 'university' e 'universe' poderiam compartilhar um stem: verifique se seu stemmer trata isso (é OK se ele as agrupar; documente o comportamento).

3. Processamento de texto real: stemma cada palavra em um parágrafo de texto inglês real. Verifique se a saída é razoável: sem strings vazias, sem crashes, a saída tem o mesmo número de palavras que a entrada.

def run_functional_tests():
    # Teste 1: busca encontra documentos relacionados
    # Teste 2: precisão: verificar sobre-stemming
    # Teste 3: processamento de parágrafo real
    ...

O que Você Construiu

O que você construiu

Você implementou um stemmer de inglês funcional com:

- 12 regras de sufixo (-tion, -ness, -ment, -able, -ible, -ies, -ied, -ier, -ing, -ed, -ly, -s)

- Limpeza de consoante dupla

- Restauração de e silencioso

- Testes unitários, testes de integração, & testes funcionais

A linhagem

Seu stemmer descende de uma linha de trabalho que começou com Zellig Harris em 1955:

- Harris (1955): Descobriu que fronteiras de morfemas aparecem como sinais estatísticos (variedade sucessora)

- Lovins (1968): Primeiro algoritmo de stemming publicado, 294 regras de sufixo

- Porter (1980): Simplificou para ~60 regras em 5 passos, tornou-se o padrão por décadas

- Snowball (2001): Framework de Porter generalizado para múltiplos idiomas

- Seu stemmer (hoje): 12 regras, mesmo princípio central

O que você poderia fazer a seguir

- Implementar o algoritmo Porter completo (é bem documentado & um ótimo exercício)

- Portar seu stemmer para C para uma melhoria de 100x em velocidade

- Construir um mecanismo de busca simples que usa seu stemmer para indexar & consultar arquivos de texto

- Comparar a saída do seu stemmer contra PorterStemmer do NLTK para medir precisão

O código que você escreveu hoje é a mesma operação fundamental que roda dentro de todo mecanismo de busca no planeta. Não é mau para um dia de trabalho.