Zellig Harris và Phân tích Phân bố

Nguồn gốc của stemming tính toán

Năm 1955, nhà ngôn ngữ học Zellig Harris xuất bản From Phoneme to Morpheme, mô tả một phương pháp để tìm các ranh giới giữa các đơn vị có ý nghĩa (morpheme) trong các từ.

Cái nhìn sâu sắc của ông là phân bố: nếu bạn xem xét một kho ngữ liệu tiếng Anh lớn, ranh giới giữa một stem & một tiền tố xuất hiện như một tín hiệu thống kê.

Phương pháp successor variety

Với bất kỳ tiền tố nào của một từ, đếm bao nhiêu ký tự riêng biệt theo sau nó trong kho ngữ liệu. Harris gọi điều này là successor variety.

Hãy xem xét tiền tố "work" trong một kho ngữ liệu chứa: worked, worker, working, works, workshop.

Sau "work", bốn ký tự khác nhau có thể theo sau: một sự tăng đột ngột trong variety. Sự tăng đột ngột này đánh dấu một ranh giới morpheme. Stem là work và mọi thứ sau đó là một tiền tố.

Điều này là cách mạng vào năm 1955. Không có quy tắc ngôn ngữ, không có từ điển: chỉ đếm. Harris đã chỉ ra rằng cấu trúc của ngôn ngữ tiết lộ chính nó thông qua phân bố.

Hiểu Successor Variety

Phương pháp của Harris hoạt động trên bất kỳ ngôn ngữ nào. Bạn không cần phải biết ngữ pháp: thống kê tiết lộ các ranh giới morpheme.

Trên thực tế, successor variety thuần túy yêu cầu một kho ngữ liệu lớn & phát hiện peak cẩn thận. Các nhà nghiên cứu sau này: Lovins (1968), Porter (1980): đơn giản hóa cách tiếp cận thành tách tiền tố dựa trên quy tắc: thay vì tính successor variety từ một kho ngữ liệu, họ mã hóa các quy tắc tiền tố trực tiếp.

Hôm nay bạn sẽ xây dựng một bộ tách tiền tố dựa trên quy tắc được lấy cảm hứng từ cái nhìn sâu sắc của Harris. Bạn sẽ định nghĩa các tiền tố một cách rõ ràng, sau đó tách chúng khỏi các từ. Đây là cách hầu hết các bộ stemming production hoạt động.

Bộ tách Tiền tố Đầu tiên của Bạn

Bắt đầu code

Bắt đầu đơn giản. Viết một hàm gọi là stem nhận một từ & tách các tiền tố này (theo thứ tự này):

1. -ing (running → runn)

2. -ed (walked → walk)

3. -ly (quickly → quick)

4. -s (cats → cat)

Quy tắc:

- Chuyển đổi từ thành chữ thường trước tiên

- Chỉ tách một tiền tố (khớp đầu tiên theo thứ tự trên)

- Chỉ tách nếu stem còn lại có ít nhất 3 ký tự

- Trả về stem

Ví dụ:

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

Xử lý Trường hợp Edge

Làm cho stemmer thông minh hơn

Bộ tách cơ bản của bạn có một vấn đề: running → runn & hoping → hop. Chúng ta cần hai cải tiến:

1. Làm sạch phụ âm kép: nếu tách -ing hoặc -ed để lại một phụ âm kép ở cuối (như runn), hãy xóa chữ cái cuối cùng → run

2. Khôi phục e câm: nếu tách -ing để lại một stem kết thúc bằng một phụ âm (không phải nguyên âm), & ban đầu có thể có một e câm (như hop từ hoping), hãy thêm e trở lại → hope

Đối với quy tắc e câm, hãy giữ nó đơn giản: nếu sau tách -ing, stem là 3+ ký tự, kết thúc bằng phụ âm, & ký tự thứ hai-đến-cuối cùng là nguyên âm (một mẫu như hop, mak, tak), hãy thêm e trở lại.

Cũng thêm các tiền tố mới này (kiểm tra chúng trước -ing, -ed, -ly, -s):

5. -tion (organization → organiza)

6. -ness (happiness → happi)

7. -ment (movement → move)

8. -able (readable → read)

9. -ible (sensible → sens)

Ưu tiên tiền tố được cập nhật: -tion, -ness, -ment, -able, -ible, -ing, -ed, -ly, -s

Giữ quy tắc độ dài stem tối thiểu: chỉ tách nếu stem còn lại là 3+ ký tự.

Quy tắc -ies & -ier

Hơn nữa morphology

Tiếng Anh có một mẫu phổ biến khác: các từ kết thúc bằng -y thay đổi thành -ies, -ied, hoặc -ier khi được biến hóa.

Thêm các quy tắc này trước kiểm tra -s & -ed:

- -ies → tách & thêm i (babies → babi)

- -ied → tách & thêm i (carried → carri)

- -ier → tách & thêm i (earlier → earli)

Cùng quy tắc độ dài stem tối thiểu: chỉ biến đổi nếu kết quả là 3+ ký tự.

Tại sao Kiểm thử?

Kiểm thử không phải là tùy chọn

Bạn có một stemmer hoạt động. Làm thế nào để bạn biết nó thực sự hoạt động? Ngay bây giờ, bạn đang chạy một vài ví dụ bằng tay. Điều đó không mở rộng được.

Phần mềm chuyên nghiệp sử dụng ba cấp độ kiểm thử:

Unit test: kiểm thử một hàm một cách cô lập với đầu vào & kết quả đầu ra đã biết. Nhanh, nhiều, cụ thể.

Integration test: kiểm thử rằng nhiều thành phần hoạt động cùng nhau. Đối với một stemmer, điều này có nghĩa là kiểm thử nó trên một loạt từ và xác minh các kết quả nhất quán.

Functional test: kiểm thử hệ thống từ bên ngoài, như một người dùng sẽ làm. Đối với một stemmer, điều này có nghĩa là đưa nó vào văn bản thực tế và xác minh kết quả đầu ra có ý nghĩa cho một trường hợp sử dụng thực như tìm kiếm.

Bạn sẽ viết cả ba.

Viết Unit Test

Unit test

Viết một hàm gọi là run_unit_tests kiểm thử hàm stem của bạn với ít nhất 15 trường hợp kiểm thử bao gồm:

1. Tách tiền tố cơ bản: các từ kết thúc bằng -ing, -ed, -ly, -s

2. Tiền tố phức tạp: -tion, -ness, -ment, -able, -ible

3. Biến đổi Y: -ies, -ied, -ier

4. Trường hợp edge: các từ ngắn không nên bị tách, các từ không có tiền tố, các từ đã được cắt gốc

5. Làm sạch phụ âm kép: running → run, sitting → sit

6. Khôi phục e câm: hoping → hope

7. Không phân biệt chữ hoa chữ thường: đầu vào chữ hoa nên được chuyển thành chữ thường

Cấu trúc các test của bạn như sau:

def run_unit_tests():
    tests = [
        ('running', 'run'),
        ('cats', 'cat'),
        # ... ít nhất 15 test case
    ]
    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

Viết Integration Test

Integration test

Unit test xác minh các đầu vào riêng lẻ. Integration test xác minh rằng các thành phần hoạt động cùng nhau một cách chính xác.

Đối với một stemmer, một thuộc tính tích hợp chính là tính nhất quán: nếu bạn cắt gốc từ tương tự hai lần, bạn sẽ nhận được cùng một kết quả. & các từ sẽ được nhóm với nhau có thể tạo ra cùng một stem.

Viết một hàm gọi là run_integration_tests kiểm thử:

1. Idempotency: cắt gốc một từ đã được cắt gốc nên trả về cùng một stem. stem(stem(word)) == stem(word) cho tất cả các từ.

2. Nhóm: các từ sẽ chia sẻ một stem thực sự làm như vậy. Kiểm thử ít nhất 3 gia đình từ (e.g., run/runs/running/runner nên chia sẻ một stem).

3. Xử lý hàng loạt: xử lý một danh sách 20+ từ và xác minh không có sự cố, không có chuỗi rỗng, không có giá trị None.

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

Viết Functional Test

Functional test

Functional test xác minh hệ thống hoạt động cho trường hợp sử dụng dự kiến của nó. Stemmer của bạn tồn tại để cải thiện tìm kiếm: vì vậy hãy kiểm thử điều đó.

Viết một hàm gọi là run_functional_tests mà:

1. Mô phỏng tìm kiếm: được đưa ra một danh sách các chuỗi tài liệu và một từ truy vấn, cắt gốc cả tài liệu và truy vấn, sau đó kiểm tra nếu các điều khoản truy vấn được cắt gốc xuất hiện trong tài liệu được cắt gốc. Kiểm thử rằng tìm kiếm cho 'running' tìm thấy một tài liệu chứa 'run' & 'runner'.

2. Kiểm tra độ chính xác: xác minh rằng cắt gốc KHÔNG sai lầm nhóm các từ không liên quan. 'university' & 'universe' có thể chia sẻ một stem: kiểm tra nếu stemmer của bạn xử lý điều này (OK nếu nó nhóm chúng; tài liệu hành vi).

3. Xử lý văn bản thực: cắt gốc mọi từ trong một đoạn văn tiếng Anh thực sự. Xác minh đầu ra là hợp lý: không có chuỗi rỗng, không có sự cố, đầu ra có cùng số từ như đầu vào.

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

Những gì Bạn Đã Xây dựng

Những gì bạn đã xây dựng

Bạn đã triển khai một stemmer tiếng Anh hoạt động với:

- 12 quy tắc tiền tố (-tion, -ness, -ment, -able, -ible, -ies, -ied, -ier, -ing, -ed, -ly, -s)

- Làm sạch phụ âm kép

- Khôi phục e câm

- Unit test, integration test, & functional test

Dòng nối kế thừa

Stemmer của bạn bắt nguồn từ một dòng công việc bắt đầu từ Zellig Harris vào năm 1955:

- Harris (1955): Phát hiện rằng các ranh giới morpheme xuất hiện như các tín hiệu thống kê (successor variety)

- Lovins (1968): Thuật toán cắt gốc được xuất bản đầu tiên, 294 quy tắc tiền tố

- Porter (1980): Đơn giản hóa thành ~60 quy tắc trong 5 bước, trở thành tiêu chuẩn trong nhiều thập kỷ

- Snowball (2001): Khung của Porter được khái quát hóa thành nhiều ngôn ngữ

- Stemmer của bạn (hôm nay): 12 quy tắc, cùng nguyên tắc cơ bản

Những gì bạn có thể làm tiếp theo

- Triển khai thuật toán Porter đầy đủ (nó được tài liệu tốt & là một bài tập tuyệt vời)

- Chuyển stemmer của bạn sang C để cải thiện tốc độ 100x

- Xây dựng một search engine đơn giản sử dụng stemmer của bạn để lập chỉ mục & truy vấn các tập tin văn bản

- So sánh đầu ra stemmer của bạn với PorterStemmer của NLTK để đo lường độ chính xác

Mã bạn viết hôm nay là cùng hoạt động cơ bản chạy bên trong mọi search engine trên hành tinh. Không tồi tệ cho một ngày làm việc.