Zellig Harris와 분포 분석

계산 스테밍의 기원

1955년, 언어학자 Zellig Harris는 From Phoneme to Morpheme을 발표하여 단어의 의미 있는 단위(형태소) 사이의 경계를 찾는 방법을 설명했습니다.

그의 통찰은 분포적이었습니다: 대규모 영어 단어 말뭉치를 살펴보면, 줄기와 접미사 사이의 경계가 통계적 신호로 나타납니다.

후속자 다양성 방법

단어의 모든 접두사에 대해, 말뭉치에서 그것을 따르는 서로 다른 문자의 개수를 세세요. Harris는 이것을 후속자 다양성이라고 불렀습니다.

worked, worker, working, works, workshop을 포함하는 말뭉치에서 접두사 "work"를 생각해보세요.

"work" 다음에 네 개의 서로 다른 문자가 올 수 있습니다: 다양성이 증가합니다. 이 증가는 형태소 경계를 표시합니다. 줄기는 work이고 그 뒤의 모든 것은 접미사입니다.

이것은 1955년에 혁명적이었습니다. 언어 규칙도 없고, 사전도 없습니다: 그냥 세세요. Harris는 언어의 구조가 분포를 통해 스스로를 드러낸다는 것을 보여주었습니다.

후속자 다양성 이해하기

Harris의 방법은 모든 언어에서 작동합니다. 문법을 알 필요가 없습니다: 통계가 형태소 경계를 드러냅니다.

실제로, 순수 후속자 다양성은 큰 말뭉치와 신중한 피크 감지가 필요합니다. 나중의 연구자들: Lovins (1968), Porter (1980): 규칙 기반 접미사 제거로 접근을 단순화했습니다: 말뭉치에서 후속자 다양성을 계산하는 대신, 접미사 규칙을 직접 인코딩했습니다.

오늘 당신은 Harris의 통찰에서 영감을 받은 규칙 기반 접미사 제거기를 구축할 것입니다. 접미사를 명시적으로 정의한 다음 단어에서 제거할 것입니다. 이것이 대부분의 프로덕션 스테머가 작동하는 방식입니다.

첫 번째 접미사 제거기

코딩을 시작해 봅시다

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 from 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():
    # Test 1: 멱등성
    # Test 2: 단어 가족 그룹화
    # Test 3: 배치 안정성
    ...

기능 테스트 작성하기

기능 테스트

기능 테스트는 시스템이 의도된 사용 사례에 대해 작동하는지 확인합니다. 스테머는 검색을 개선하기 위해 존재합니다: 그것을 테스트하세요.

run_functional_tests라는 함수를 작성하여:

1. 검색 시뮬레이션: 문서 문자열 목록과 쿼리 단어가 주어지면, 문서와 쿼리를 모두 줄기하고, 줄기된 쿼리 용어가 줄기된 문서에 나타나는지 확인합니다. 'running'을 검색하면 'run' & 'runner'를 포함하는 문서를 찾는지 테스트하세요.

2. 정확성 확인: 줄기가 관련 없는 단어를 부정확하게 그룹화하지 않도록 확인합니다. 'university' & 'universe'가 같은 줄기를 공유할 수 있습니다: 스테머가 이를 처리하는지 확인하세요 (그룹화해도 괜찮습니다: 행동을 문서화하세요).

3. 실제 텍스트 처리: 실제 영어 텍스트 단락의 모든 단어를 줄기하세요. 출력이 합리적인지 확인하세요: 빈 문자열이 없고, 충돌이 없으며, 출력이 입력과 같은 수의 단어를 가지고 있습니다.

def run_functional_tests():
    # Test 1: 검색이 관련 문서를 찾음
    # Test 2: 정확성: 과도한 줄기 확인
    # Test 3: 실제 단락 처리
    ...

당신이 구축한 것

당신이 구축한 것

다음을 갖춘 작동하는 영어 스테머를 구현했습니다:

- 12개의 접미사 규칙 (-tion, -ness, -ment, -able, -ible, -ies, -ied, -ier, -ing, -ed, -ly, -s)

- 쌍자음 정리

- 무음 e 복원

- 단위 테스트, 통합 테스트, & 기능 테스트

계보

스테머는 1955년 Zellig Harris부터 시작되는 작업 선을 계승합니다:

- Harris (1955): 형태소 경계가 통계적 신호로 나타난다는 것을 발견함 (후속자 다양성)

- Lovins (1968): 첫 번째 공개된 줄기 알고리즘, 294개의 접미사 규칙

- Porter (1980): 5개 단계로 약 60개의 규칙으로 단순화, 수십 년 동안 표준이 됨

- Snowball (2001): Porter의 프레임워크를 여러 언어로 일반화

- 당신의 스테머 (오늘): 12개의 규칙, 같은 핵심 원칙

다음에 할 수 있는 것

- 전체 Porter 알고리즘 구현 (좋은 문서화되어 있고 좋은 운동)

- 스테머를 C로 포팅하여 100배 속도 향상

- 스테머를 사용하여 텍스트 파일을 색인화하고 쿼리하는 간단한 검색 엔진 구축

- 스테머의 출력을 NLTK의 PorterStemmer와 비교하여 정확성 측정

오늘 작성한 코드는 행성의 모든 검색 엔진 내부에서 실행되는 것과 동일한 기본 작업입니다. 하루 일치고는 나쁘지 않습니다.