زيليج هاريس والتحليل التوزيعي

أصل التجذير الحسابي

في عام 1955، نشر اللغوي زيليج هاريس كتاب From Phoneme to Morpheme، يصف فيه طريقة للعثور على الحدود بين الوحدات ذات المعنى (المورفيمات) في الكلمات.

رؤيته كانت توزيعية: إذا نظرت إلى مجموعة كبيرة من الكلمات الإنجليزية، يظهر الحد بين الجذر واللاحقة كإشارة إحصائية.

طريقة تنوع الخليفة

لأي بادئة من كلمة، عد كم عدد الأحرف المختلفة التي تتبعها في المجموعة. أطلق هاريس على هذا تنوع الخليفة.

فكر في البادئة "work" في مجموعة تحتوي على: worked, worker, working, works, workshop.

بعد "work"، يمكن لأربعة أحرف مختلفة أن تتبع: قفزة في التنوع. هذه القفزة تحدد حد مورفيم. الجذر هو work وكل شيء بعده لاحقة.

هذا كان ثوريا في عام 1955. لا قوانين لغوية، لا قاموس: فقط عد. أظهر هاريس أن بنية اللغة تكشف نفسها من خلال التوزيع.

فهم تنوع الخليفة

تعمل طريقة هاريس على أي لغة. لا تحتاج أن تعرف القواعد: الإحصائيات تكشف حدود المورفيمات.

في الممارسة العملية، يتطلب تنوع الخليفة النقي مجموعة بيانات كبيرة والكشف الدقيق عن القمم. لاحقا، الباحثون: لوفينز (1968)، بورتر (1980): بسطوا النهج إلى حذف لواحق قائم على القواعد: بدلا من حساب تنوع الخليفة من مجموعة بيانات، قاموا بترميز قواعد اللواحق مباشرة.

اليوم ستقوم ببناء جهاز حذف لواحق قائم على القواعد مستوحى من رؤية هاريس. ستحدد اللواحق بشكل صريح، ثم تحذفها من الكلمات. هكذا تعمل معظم خوارزميات التجذير في الإنتاج.

جهاز حذف اللواحق الأول

دعنا نكود

ابدأ بسيط. اكتب دالة تسمى stem التي تأخذ كلمة و تحذف هذه اللواحق (بهذا الترتيب):

1. -ing (running → runn)

2. -ed (walked → walk)

3. -ly (quickly → quick)

4. -s (cats → cat)

القواعد:

- حول الكلمة إلى حروف صغيرة أولا

- احذف لاحقة واحدة فقط (أول تطابق بالترتيب أعلاه)

- احذف فقط إذا كان الجذر المتبقي 3 أحرف على الأقل

- أعد الجذر

مثال:

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

التعامل مع الحالات الخاصة

جعل جهاز التجذير أذكى

جهاز التجذير الأساسي لديه مشكلة: running → runn و hoping → hop. نحتاج إلى تحسينين:

1. تنظيف الحروف المزدوجة: إذا أدى حذف -ing أو -ed إلى ترك حرف متكرر في النهاية (مثل runn)، احذف الحرف الأخير → run

2. استعادة e الصامتة: إذا أدى حذف -ing إلى ترك جذر ينتهي بحرف ساكن (وليس حرف متحرك)، و قد يكون الأصلي قد احتوى على e صامتة (مثل hop من 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'),
        # ... 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

اكتب اختبارات التكامل

اختبارات التكامل

اختبارات الوحدة تتحقق من مدخلات فردية. اختبارات التكامل تتحقق من أن المكونات تعمل معا بشكل صحيح.

لجهاز تجذير، خاصية تكامل أساسية هي الاتساق: إذا قمت بتجذير نفس الكلمة مرتين، تحصل على نفس النتيجة. و الكلمات التي يجب أن تتجمع معا يجب أن تنتج نفس الجذر.

اكتب دالة تسمى run_integration_tests التي تختبر:

1. الحياد: تجذير كلمة تم اختزالها بالفعل يجب أن تعيد نفس الجذر. stem(stem(word)) == stem(word) لجميع الكلمات.

2. التجميع: الكلمات التي يجب أن تشترك في جذر تفعل فعلا. اختبر 3 عائلات كلمات على الأقل (مثلا run/runs/running/runner يجب أن تشترك جميعها في جذر).

3. معالجة الدفعات: معالجة قائمة بـ 20+ كلمات والتحقق من عدم تعطل، لا سلاسل فارغة، لا قيم None.

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

اكتب اختبارات وظيفية

اختبارات وظيفية

اختبارات وظيفية تتحقق من أن النظام يعمل لحالة الاستخدام المقصودة. جهاز التجذير موجود لتحسين البحث: لذا اختبر ذلك.

اكتب دالة تسمى run_functional_tests التي:

1. محاكاة البحث: بناء على قائمة سلاسل مستندات و كلمة استعلام، قم بتجذير المستندات و الاستعلام، ثم تحقق مما إذا كانت شروط الاستعلام المجذرة تظهر في المستندات المجذرة. اختبر أن البحث عن 'running' يجد مستند يحتوي على 'run' و 'runner'.

2. فحص الدقة: تحقق من أن التجذير لا يجمع بشكل غير صحيح الكلمات غير ذات الصلة. 'university' و 'universe' قد تشترك في جذر: تحقق مما إذا كان جهاز التجذير يتعامل مع هذا (لا بأس إذا قام بتجميعهما؛ وثّق السلوك).

3. معالجة النص الحقيقي: جذّر كل كلمة في فقرة من النص الإنجليزي الحقيقي. تحقق من أن الإخراج معقول: لا سلاسل فارغة، لا تعطل، الإخراج له نفس عدد الكلمات كما هو الحال في الإدخال.

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

ما الذي بنيته

ما الذي بنيته

قمت بتنفيذ جهاز تجذير للعمل مع:

- 12 قاعدة لاحقة (-tion, -ness, -ment, -able, -ible, -ies, -ied, -ier, -ing, -ed, -ly, -s)

- تنظيف الحروف المزدوجة

- استعادة e الصامتة

- اختبارات الوحدة و اختبارات التكامل و اختبارات وظيفية

السلالة

ينحدر جهاز التجذير الخاص بك من سلسلة عمل بدأت مع زيليج هاريس في عام 1955:

- هاريس (1955): اكتشف أن حدود المورفيمات تظهر كإشارات إحصائية (تنوع الخليفة)

- لوفينز (1968): أول خوارزمية تجذير منشورة، 294 قاعدة لاحقة

- بورتر (1980): مبسطة إلى ~60 قاعدة في 5 خطوات، أصبحت المعيار لعقود

- Snowball (2001): إطار عمل بورتر معممة لعدة لغات

- جهاز التجذير الخاص بك (اليوم): 12 قاعدة، نفس المبدأ الأساسي

ما يمكنك أن تفعله بعد ذلك

- تطبيق خوارزمية بورتر الكاملة (يتم توثيقها بشكل جيد و تمرين رائع)

- نقل جهاز التجذير الخاص بك إلى C لتحسين السرعة بـ 100 مرة

- بناء محرك بحث بسيط يستخدم جهاز التجذير الخاص بك للفهرسة و الاستعلام عن ملفات النصوص

- مقارنة إخراج جهاز التجذير الخاص بك مع PorterStemmer الخاص بـ NLTK لقياس الدقة

الكود الذي كتبته اليوم هو نفس العملية الأساسية التي تعمل داخل كل محرك بحث على الكوكب. ليس سيئا لعمل يوم واحد.