تحويل النص غير المتباعد إلى كلمات باستخدام خوارزميات فعالة

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

بيان التحدي

تتضمن المهمة المطروحة تقسيم سلسلة إدخال مثل "tableapplechairtablecupboard..." في قائمة الكلمات، مع الأخذ في الاعتبار إمكانية وجود سلاسل فرعية غامضة حيث يمكن أن يشكل التسلسل كلمات متعددة (على سبيل المثال، "cupboard" يمكن أن تكون "cup" أو "board").

الخوارزمية: استغلال تردد الكلماتإن النهج الساذج المتمثل في تحديد أطول كلمة ممكنة بشكل متكرر في كل موضع يؤدي إلى نتائج غير مرضية في سيناريوهات العالم الحقيقي . للتغلب على هذا القيد، نستخدم خوارزمية تتضمن توزيع تكرار الكلمات.

نمذجة تردد الكلمات

نفترض أن ترددات الكلمات تتبع قانون Zipf، الذي ينص على أن الاحتمالية إن مواجهة الكلمة المتكررة n هي تقريبًا 1/(n * log(N))، حيث N هو إجمالي عدد الكلمات في اللغة. باستخدام قاموس التكلفة المحسوب مسبقًا والذي يشفر هذه العلاقة، يمكننا تعيين تكلفة لكل كلمة محتملة.

نهج البرمجة الديناميكية

لتحديد تجزئة الكلمات الأمثل، نحن استخدام البرمجة الديناميكية. نحن نكرر من خلال سلسلة الإدخال، مع الحفاظ على قيمة تكلفة التشغيل لكل نقطة تقسيم محتملة. في كل موضع، نقوم بتقييم الكلمات المرشحة بدءًا من نهاية السلسلة واختيار التقسيم بأقل تكلفة.

تنفيذ الخوارزمية

يقدم كود بايثون المقدم تنفيذ موجز لهذه الخوارزمية:

من سجل استيراد الرياضيات # قاموس تكلفة الكلمات المحسوبة مسبقًا باستخدام قانون Zipf تكلفة الكلمة =... # وظيفة مساعدة للعثور على أفضل مطابقة للكلمات بناءً على التكلفة بالتأكيد best_match(i): ... # وظيفة لاستنتاج المسافات في سلسلة الإدخال باستخدام البرمجة الديناميكية تعريف infer_spaces(s): ...

from math import log

# Precomputed word cost dictionary using Zipf's law
wordcost = ...

# Helper function to find the best word match based on cost
def best_match(i):
    ...

# Function to infer spaces in the input string using dynamic programming
def infer_spaces(s):
    ...

لاستخدام هذا الرمز، ما عليك سوى إدخال السلسلة النصية المستمرة كما يلي:

s = 'thumbgreenappleactivesignmentweeklymetaphor ' print(infer_spaces(s))

s = 'thumbgreenappleactiveassignmentweeklymetaphor'
print(infer_spaces(s))

توضح هذه الخوارزمية أداءً استثنائيًا حتى مع وجود قاموس محدود للكلمات. لقد نجح في ترميز النص المعقد بدقة عالية.