Zellig Harris ve Dağılımsal Analiz

Hesaplamalı stemming'in kökeni

1955'te, dilbilimci Zellig Harris, kelimelerdeki anlamlı birimlerin (biçimbirimlerin) sınırlarını bulma yöntemini açıklayan From Phoneme to Morpheme yayınladı.

Onun anlayışı dağılımsal idi: geniş bir İngilizce sözcük derlemine bakarsanız, bir kök ile sonek arasındaki sınır istatistiksel bir sinyal olarak ortaya çıkar.

Halef çeşitliliği yöntemi

Bir kelimenin herhangi bir ön eki için, derlemde ondan sonra kaç farklı karakter geleceğini sayın. Harris buna halef çeşitliliği adını verdi.

Şunları içeren bir derlemde "work" ön ekini düşünün: worked, worker, working, works, workshop.

"work" dan sonra dört farklı karakter gelebilir: çeşitlilikte bir yükselme. Bu yükselme biçimbirim sınırını işaretler. Kök work ve ondan sonra gelen her şey sonektir.

Bu 1955'te çılgınca idi. Hiç dilbilimsel kural yok, hiç sözlük yok: sadece sayma. Harris, dil yapısının dağılım yoluyla kendini ortaya çıkardığını gösterdi.

Halef Çeşitliliğini Anlamak

Harris'in yöntemi herhangi bir dilde çalışır. Dil bilginizi bilmek gerekmez: istatistikler biçimbirim sınırlarını ortaya çıkarır.

Pratikte, saf halef çeşitliliği büyük bir derlem ve dikkatli tepe tespiti gerektirir. Daha sonraki araştırmacılar: Lovins (1968), Porter (1980): yaklaşımı kural tabanlı sonek çıkarmaya basitleştirdi: derlemden halef çeşitliliğini hesaplamak yerine, sonek kurallarını doğrudan kodladılar.

Bugün, Harris'in anlayışından ilham alan kural tabanlı bir sonek sökücü inşa edeceksiniz. Sonekleri açıkça tanımlayacak ve sonra kelimelerden çıkaracaksınız. Çoğu ürün stemmer'ı bu şekilde çalışır.

İlk Sonek Sökücünüz

Kod yazalım

Basit başlayın. stem adında bir fonksiyon yazın ve bu sonekleri çıkartsın (bu sırayla):

1. -ing (running → runn)

2. -ed (walked → walk)

3. -ly (quickly → quick)

4. -s (cats → cat)

Kurallar:

- Kelimeyi önce küçük harfe dönüştürün

- Sadece bir soneki çıkarın (yukarıdaki sıradaki ilk eşleşme)

- Sadece kalan kök en az 3 karakter uzunluğundaysa çıkarın

- Kökü döndürün

Örnek:

def stem(word):
    word = word.lower()
    # sonek çıkarma mantığınız burada
    return word

Kenar Durumlarını Ele Almak

Stemmer'ı daha akıllı yapma

Temel sökücünüzün bir sorunu vardır: running → runn & hoping → hop. İki iyileştirmeye ihtiyacımız var:

1. Çift ünsüz temizliği: -ing veya -ed çıkarmak sonunda çift ünsüzü bırakırsa (runn gibi), son harfi çıkarın → run

2. Sessiz-e restorasyonu: -ing çıkarmak sonra sessiz harfle biten bir kök bırakırsa (ünlü değil), orijinal sessiz e olabilir (hop from hoping gibi), e geri ekleyin → hope

Sessiz-e kuralı için, basit tutun: -ing çıkardıktan sonra, kök 3+ kar, ünsüzle biterse & ikinci karakter ünlüyse (bir desen hop, mak, tak gibi), e geri ekleyin.

Ayrıca bu yeni sonekleri ekleyin (-ing, -ed, -ly, -s'den önce kontrol edin):

5. -tion (organization → organiza)

6. -ness (happiness → happi)

7. -ment (movement → move)

8. -able (readable → read)

9. -ible (sensible → sens)

Güncellenmiş sonek önceliği: -tion, -ness, -ment, -able, -ible, -ing, -ed, -ly, -s

Minimum kök uzunluğu kuralını tutun: sadece kalan kök 3+ karakterse çıkarın.

-ies & -ier Kuralları

Daha fazla biçimbilim

İngilizce, infleksiyon yapıldığında -y ile biten başka bir yaygın desen vardır: -ies, -ied veya -ier'a değişirler.

-s & -ed kontrolleri öncesinde bu kuralları ekleyin:

- -ies → çıkarın & i ekleyin (babies → babi)

- -ied → çıkarın & i ekleyin (carried → carri)

- -ier → çıkarın & i ekleyin (earlier → earli)

Aynı minimum kök uzunluğu kuralı: sadece sonuç 3+ karakterse dönüştürün.

Neden Test?

Test isteğe bağlı değildir

Çalışan bir stemmer'ınız var. Gerçekten çalıştığını nereden biliyorsunuz? Şu anda birkaç örneği el ile çalıştırıyorsunuz. Bu ölçeklenmiyor.

Profesyonel yazılım üç düzey test kullanır:

Birim testleri: bilinen girdiler ve beklenen çıktılar ile izolasyonda bir fonksiyonu test edin. Hızlı, çok sayıda, spesifik.

Entegrasyon testleri: birden çok bileşenin birlikte çalıştığını test edin. Bir stemmer için, bu kelime gruplarını test etmek ve sonuçların tutarlı olduğunu doğrulamak anlamına gelir.

Fonksiyonel testler: sistemi dışarıdan, bir kullanıcının yapacağı şekilde test edin. Bir stemmer için, bu gerçek metni beslemek ve çıktının arama gibi gerçek bir kullanım durumu için mantıklı olduğunu doğrulamak anlamına gelir.

Üçünü de yazacaksınız.

Birim Testleri Yazın

Birim testleri

En az 15 test durumu ile run_unit_tests adında bir fonksiyon yazın:

1. Temel sonek çıkarma: -ing, -ed, -ly, -s ile biten kelimeler

2. Karmaşık sonekler: -tion, -ness, -ment, -able, -ible

3. Y-çekim: -ies, -ied, -ier

4. Kenar durumları: çıkarılmaması gereken kısa kelimeler, soneksiz kelimeler, zaten köklenmiş kelimeler

5. Çift ünsüz temizliği: running → run, sitting → sit

6. Sessiz-e restorasyonu: hoping → hope

7. Büyük/küçük harf duyarsızlığı: büyük harf girişi küçük harfe dönüştürülmelidir

Testlerinizi şöyle yapılandırın:

def run_unit_tests():
    tests = [
        ('running', 'run'),
        ('cats', 'cat'),
        # ... en az 15 test durumu
    ]
    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

Entegrasyon Testleri Yazın

Entegrasyon testleri

Birim testleri bireysel girdileri doğrular. Entegrasyon testleri bileşenlerin birlikte doğru çalıştığını doğrular.

Bir stemmer için, temel entegrasyon özelliği tutarlılıktır: aynı kelimeyi iki kez kökleştirirseniz, aynı kökü alırsınız. Ve birlikte gruplandırılması gereken kelimeler aynı kökü üretmelidir.

run_integration_tests adında bir fonksiyon yazın:

1. İdemliylik: zaten köklenmiş bir kelimeyi kökleştirmek aynı kökü döndürmelidir. stem(stem(word)) == stem(word) tüm kelimeler için.

2. Gruplandırma: kök paylaşması gereken kelimeler gerçekten de paylaşıyor. En az 3 kelime ailesini test edin (örneğin, run/runs/running/runner hepsi bir kökü paylaşmalı).

3. Toplu işleme: 20+ kelime listesini işleyin ve çökmeme, boş dize yok, None değeri yok olduğunu doğrulayın.

def run_integration_tests():
    # Test 1: İdemliylik
    # Test 2: kelime ailesi gruplandırma
    # Test 3: toplu durum istikrarı
    ...

Fonksiyonel Testler Yazın

Fonksiyonel testler

Fonksiyonel testler, sistem amaçlanan kullanım durumları için çalıştığını doğrular. Stemmer'ınız aramayı iyileştirmek için var: bu yüzden test edin.

run_functional_tests adında bir fonksiyon yazın:

1. Arama simülasyonu: belge dizeleri listesi ve bir sorgu kelimesi verildiğinde, hem belgeleri hem de sorguyu kökleştirin, ardından köklenmiş sorgu terimlerinin köklenmiş belgelerde göründüğünü kontrol edin. 'running' araması 'run' ve 'runner' içeren bir belgeyi bulacağını test edin.

2. Kesinlik kontrolü: stemming, alakasız kelimeleri yanlışlıkla gruplandırmadığını doğrulayın. 'university' ve 'universe' bir kökü paylaşabilir: stemmer'ınız bunu ele alırsa kontrol edin (bunları gruplandırması tamam; davranışı belgeyin).

3. Gerçek metni işleme: bir paragrafın her kelimesini kökleştirin. Çıktı makul olduğunu doğrulayın: boş dize yok, çökme yok, çıktı girişle aynı kelime sayısına sahip.

def run_functional_tests():
    # Test 1: arama ilgili belgeleri bulur
    # Test 2: kesinlik: aşırı-stemming kontrol edin
    # Test 3: gerçek paragraf işleme
    ...

İnşa Ettikleri

İnşa ettikleri

Şunlarla çalışan bir İngilizce stemmer uyguladınız:

- 12 sonek kuralı (-tion, -ness, -ment, -able, -ible, -ies, -ied, -ier, -ing, -ed, -ly, -s)

- Çift ünsüz temizliği

- Sessiz-e restorasyonu

- Birim testleri, entegrasyon testleri & fonksiyonel testler

Soy ağacı

Stemmer'ınız, 1955'te Zellig Harris ile başlayan bir çalışma hattından doğmaktadır:

- Harris (1955): Biçimbirim sınırlarının istatistiksel sinyaller olarak göründüğünü keşfetti (halef çeşitliliği)

- Lovins (1968): İlk yayınlanan stemming algoritması, 294 sonek kuralı

- Porter (1980): 5 adımda ~60 kurala sadeleştirildi, onlarca yıl için standart haline geldi

- Snowball (2001): Porter'ın çerçevesi birden çok dile genelleştirildi

- Senin stemmer'ın (bugün): 12 kural, aynı temel ilke

Sonra ne yapabilirsiniz

- Tam Porter algoritmasını uygulayın (iyi belgelenmiş & harika bir alıştırma)

- Stemmer'ınızı C'ye aktarın 100x hız iyileştirmesi için

- Stemmer'ınızı metin dosyalarını indekslemek & sorgulamak için kullanan basit bir arama motoru inşa edin

- Doğruluğu ölçmek için stemmer'ınızın çıktısını NLTK'nin PorterStemmer'ıyla karşılaştırın

Bugün yazdığınız kod, bu gezegende her arama motorunun içinde çalışan aynı temel işlemdir. Bir günün çalışması için fena değil.