Zellig Harris dan Analisis Distribusional

Asal mula stemming komputasional

Pada tahun 1955, ahli bahasa Zellig Harris menerbitkan From Phoneme to Morpheme, menggambarkan metode untuk menemukan batas-batas antara unit-unit bermakna (morfem) dalam kata-kata.

Wawasannya adalah distribusional: jika Anda melihat corpus bahasa Inggris yang besar, batas antara stem & akhiran muncul sebagai sinyal statistik.

Metode successor variety

Untuk setiap awalan kata, hitunglah berapa banyak karakter berbeda yang mengikutinya dalam corpus. Harris menyebut ini successor variety.

Pertimbangkan awalan "work" dalam corpus yang berisi: worked, worker, working, works, workshop.

Setelah "work", empat karakter berbeda dapat mengikuti: lonjakan dalam varietas. Lonjakan itu menandai batas morfem. Stem adalah work dan segalanya setelahnya adalah akhiran.

Ini radikal pada tahun 1955. Tidak ada aturan linguistik, tidak ada kamus: hanya menghitung. Harris menunjukkan bahwa struktur bahasa mengungkapkan dirinya melalui distribusi.

Memahami Successor Variety

Metode Harris bekerja pada bahasa apa pun. Anda tidak perlu tahu tata bahasanya: statistik mengungkapkan batas-batas morfem.

Dalam praktiknya, successor variety murni memerlukan corpus besar dan deteksi puncak yang hati-hati. Peneliti kemudian: Lovins (1968), Porter (1980): menyederhanakan pendekatan menjadi penghilangan akhiran berbasis aturan: bukan menghitung successor variety dari corpus, mereka mengkodekan aturan akhiran secara langsung.

Hari ini Anda akan membangun penghilang akhiran berbasis aturan yang terinspirasi oleh wawasan Harris. Anda akan mendefinisikan akhiran secara eksplisit, kemudian menghilangkannya dari kata-kata. Ini adalah cara kebanyakan stemmer produksi bekerja.

Penghilang Akhiran Pertama Anda

Mari kita buat kode

Mulai sederhana. Tulis fungsi yang disebut stem yang mengambil kata & menghilangkan akhiran-akhiran ini (dalam urutan ini):

1. -ing (running → runn)

2. -ed (walked → walk)

3. -ly (quickly → quick)

4. -s (cats → cat)

Aturan:

- Konversi kata menjadi huruf kecil terlebih dahulu

- Hanya hapus satu akhiran (kecocokan pertama dalam urutan di atas)

- Hanya hapus jika stem yang tersisa setidaknya 3 karakter panjang

- Kembalikan stem

Contoh:

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

Menangani Kasus Tepi

Membuat stemmer lebih pintar

Penghilang dasar Anda memiliki masalah: running → runn & hoping → hop. Kami memerlukan dua penyempurnaan:

1. Pembersihan konsonan ganda: jika menghilangkan -ing atau -ed meninggalkan konsonan ganda di akhir (seperti runn), hapus huruf terakhir → run

2. Pemulihan e diam: jika menghilangkan -ing meninggalkan stem berakhir dengan konsonan (bukan vokal), & aslinya mungkin memiliki e diam (seperti hop dari hoping), tambahkan kembali e → hope

Untuk aturan e diam, sederhanakan: jika setelah menghilangkan -ing, stem adalah 3+ karakter, berakhir dengan konsonan, & karakter kedua-terakhir adalah vokal (pola seperti hop, mak, tak), tambahkan e kembali.

Juga tambahkan akhiran baru ini (periksa sebelum -ing, -ed, -ly, -s):

5. -tion (organization → organiza)

6. -ness (happiness → happi)

7. -ment (movement → move)

8. -able (readable → read)

9. -ible (sensible → sens)

Prioritas akhiran yang diperbarui: -tion, -ness, -ment, -able, -ible, -ing, -ed, -ly, -s

Pertahankan aturan panjang stem minimum: hanya hapus jika stem yang tersisa adalah 3+ karakter.

Aturan -ies & -ier

Lebih banyak morfologi

Bahasa Inggris memiliki pola umum lainnya: kata-kata yang diakhiri dengan -y berubah menjadi -ies, -ied, atau -ier ketika fleksi.

Tambahkan aturan-aturan ini sebelum pemeriksaan -s & -ed:

- -ies → hapus & tambahkan i (babies → babi)

- -ied → hapus & tambahkan i (carried → carri)

- -ier → hapus & tambahkan i (earlier → earli)

Aturan panjang stem minimum yang sama: hanya ubah jika hasilnya adalah 3+ karakter.

Mengapa Menguji?

Pengujian bukan opsional

Anda memiliki stemmer yang berfungsi. Bagaimana Anda tahu bahwa itu benar-benar berfungsi? Sekarang, Anda menjalankan beberapa contoh dengan tangan. Itu tidak berskala.

Perangkat lunak profesional menggunakan tiga tingkat pengujian:

Unit test: uji satu fungsi secara terisolasi dengan input yang diketahui dan output yang diharapkan. Cepat, banyak, spesifik.

Integration test: uji bahwa beberapa komponen bekerja bersama. Untuk stemmer, ini berarti menguji terhadap sekelompok kata dan memverifikasi hasilnya konsisten.

Functional test: uji sistem dari luar, seperti yang dilakukan pengguna. Untuk stemmer, ini berarti memberinya teks nyata dan memverifikasi output masuk akal untuk kasus penggunaan nyata seperti pencarian.

Anda akan menulis ketiganya.

Tulis Unit Test

Unit test

Tulis fungsi yang disebut run_unit_tests yang menguji fungsi stem Anda dengan setidaknya 15 kasus pengujian yang mencakup:

1. Penghilangan akhiran dasar: kata yang diakhiri -ing, -ed, -ly, -s

2. Akhiran kompleks: -tion, -ness, -ment, -able, -ible

3. Infleksi Y: -ies, -ied, -ier

4. Kasus tepi: kata pendek yang tidak boleh dihilangkan, kata tanpa akhiran, kata-kata yang sudah di-stem

5. Pembersihan konsonan ganda: running → run, sitting → sit

6. Pemulihan e diam: hoping → hope

7. Ketidakpekaan kasus: input huruf besar harus diubah menjadi huruf kecil

Strukturkan tes Anda seperti ini:

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

Tulis Integration Test

Integration test

Unit test memverifikasi input individual. Integration test memverifikasi bahwa komponen bekerja dengan benar bersama-sama.

Untuk stemmer, properti integrasi utama adalah konsistensi: jika Anda stem kata yang sama dua kali, Anda mendapatkan hasil yang sama. Dan kata-kata yang harus dikelompokkan bersama harus menghasilkan stem yang sama.

Tulis fungsi yang disebut run_integration_tests yang menguji:

1. Idempotency: stemming kata yang sudah di-stem harus mengembalikan stem yang sama. stem(stem(word)) == stem(word) untuk semua kata.

2. Pengelompokan: kata-kata yang harus berbagi stem benar-benar melakukannya. Uji setidaknya 3 keluarga kata (misalnya, run/runs/running/runner harus semuanya berbagi stem).

3. Pemrosesan batch: memproses daftar 20+ kata dan verifikasi tidak ada crash, tidak ada string kosong, tidak ada nilai None.

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

Tulis Functional Test

Functional test

Functional test memverifikasi sistem bekerja untuk kasus penggunaan yang ditujukan. Stemmer Anda ada untuk meningkatkan pencarian: jadi uji itu.

Tulis fungsi yang disebut run_functional_tests yang:

1. Simulasi pencarian: diberikan daftar string dokumen dan kata pertanyaan, stem baik dokumen maupun pertanyaan, kemudian periksa apakah istilah pertanyaan yang di-stem muncul dalam dokumen yang di-stem. Uji bahwa mencari 'running' menemukan dokumen yang berisi 'run' dan 'runner'.

2. Periksa presisi: verifikasi bahwa stemming TIDAK secara tidak benar mengelompokkan kata-kata yang tidak terkait. 'university' dan 'universe' mungkin berbagi stem: periksa apakah stemmer Anda menangani ini (tidak apa-apa jika itu mengelompokkannya; dokumentasikan perilakunya).

3. Pemrosesan teks nyata: stem setiap kata dalam paragraf teks bahasa Inggris nyata. Verifikasi output masuk akal: tidak ada string kosong, tidak ada crash, output memiliki jumlah kata yang sama dengan input.

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

Apa Yang Anda Bangun

Apa yang Anda bangun

Anda mengimplementasikan stemmer bahasa Inggris yang berfungsi dengan:

- 12 aturan akhiran (-tion, -ness, -ment, -able, -ible, -ies, -ied, -ier, -ing, -ed, -ly, -s)

- Pembersihan konsonan ganda

- Pemulihan e diam

- Unit test, integration test, & functional test

Keturunannya

Stemmer Anda mewarisi dari garis kerja yang dimulai dengan Zellig Harris pada tahun 1955:

- Harris (1955): Menemukan bahwa batas-batas morfem muncul sebagai sinyal statistik (successor variety)

- Lovins (1968): Algoritma stemming pertama yang dipublikasikan, 294 aturan akhiran

- Porter (1980): Disederhanakan menjadi ~60 aturan dalam 5 langkah, menjadi standar selama beberapa dekade

- Snowball (2001): Kerangka Porter digeneralisir ke berbagai bahasa

- Stemmer Anda (hari ini): 12 aturan, prinsip inti yang sama

Apa yang bisa Anda lakukan selanjutnya

- Implementasikan algoritma Porter lengkap (itu didokumentasikan dengan baik & latihan yang bagus)

- Portkan stemmer Anda ke C untuk peningkatan kecepatan 100x

- Bangun mesin pencari sederhana yang menggunakan stemmer Anda untuk mengindeks & menanyakan file teks

- Bandingkan output stemmer Anda dengan PorterStemmer NLTK untuk mengukur akurasi

Kode yang Anda tulis hari ini adalah operasi fundamental yang sama yang berjalan di dalam setiap mesin pencari di planet ini. Tidak buruk untuk pekerjaan sehari.