البحث عن الكلمات المتشابهة

 

البحث عن الكلمات المتشابهة باستخدام

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

Levenshtein Distance Algorithm

 

افترض أن لديك نصا عربيا، وتريد أن تبحث فيه عن الكلمة "لعب" أو أي كلمات شبيهة بها.

أول طريقة ستفكر فيها، هي البحث عن أي كلمة تحتوي الحروف "لعب".. يمكن فحص هذا باستخدام الوسيلة String.Contains، كما أن الوسيلة String.IndexOf تبحث عن الحروف المطلوبة دون الاهتمام ببداية أو نهاية الكلمة.

هذه الطريقة ستتيح لك العثور على كلمات مثل ملعب ـ لعبة ـ لعبنا ـ اللعب.. إلخ.. لكنها لن تستطيع العثور على كلمات مثل لاعب، ملاعب، ألعاب.

هنا قد تفكر في استخدام التعبيرات النمطية Regular Expressions بتكوين صيغة تبحث عن أي كلمة داخل فيها الحروف "ل، ع، ب" سواء كانت متلاصقة أو يوجد بينها حروف أخرى (ما عدا الأرقام والمسافات وعلامات الترقيم).. هذه الصيغة ستكون هكذا:

\w*?ل\w*?ع\w*?ب\w*?

(التعبيرات النمطية مشروحة بالتفصيل في مرجع: من الصفر إلى الاحتراف: برمجة إطار العمل)

هذه الطريقة ستحل جزءا كبيرا من المشكلة، لكنها ستفشل حينما تبحث في النص عن الكلمة "لاعب"، فلن تستطيع حينها أن تعثر على كلمات مثل: لعب، لعبة، ملعب، لأنها لا تحتوي على حرف الألف.. وهذا يعني أنك تحتاج إلى برنامج تحليل صرفي لتحصل على مادة الكلمة "لاعب" أولا (وهي لعب)، ثم تستخدم الصيغة النمطية السابقة في البحث.. وهو أمر يعقد مسألة بسيطة في جوهرها، ويتطلب أداة لا تستطيع بناءها بنفسك وقد تضطر إلى شرائها، إضافة إلى أنها ستبطئ عملية البحث، كما أن المحلل الصرفي قد يعيد أكثر من جذر محتمل لنفس الكلمة (مثلا: الكلمة نمت، قد تكون من نام ينام نِمْت، أو نما تَنمو نَمَت، أو متّ يمتّ نَمُتُّ، أو مات يموت لم نَمُتْ)!

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

من هنا، تظهر أهمية حساب "مسافة ليفنيشتاين"، التي سبق أن شرحتها في هذا الموضوع.

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

وقد لاحظت بالتجربة أن هذه الخوارزمية تعطي نتائج بحث أفضل مع اللغة العربية إذا جعلت تكلفة تغير حرف = 2 بدلا من 1، وأبقيت على تكلفة حذف أو إضافة حرف = 1 كما في الخوارزمية الأصلية.. لهذا السبب عرّفت الثوابت الثلاثة التالية في بداية الدالة LevenshteinDistance:

Const SubstitutionFactor = 2

Const AdditionFactor = 1

Const DeletionFactor = 1

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

وقد كتبت مشروعا ليريكم التطبيق العملي لهذه الفكرة، وهو يبدو كما في الصورة، حيث نسخت مادة وفي من لسان العرب في مربع النص العلوي، ليمكنكم تجربة البحث عن أي كلمة مشتقة من هذه المادة ورؤية النتائج (يمكن البحث أيضا عن أي كلمة أخرى، سواء كانت موجودة بالنص أم لا).. ويمكنك وضع أي نص آخر في مربع النص والتجربة.

المهم هنا هو خوارزمية دالة البحث Find، فهي تفعل ما يلي:

- تستخدم فئة التعبيرات النمطية Regex للبحث في النص عن كل كلمة كاملة بواسطة التعبير النمطي البسيط: "\w+"

- تمر عبر كل كلمة، وتزيل التشكيل منها (يمكنك ترك التشكيل لو أردت، لكن حساب كل تشكيل كحرف مختلف قد يعطي نتائج غير متوقة، لأن بعض الكلمات المختلفة في الحروف قد تكون أقرب لكلمة البحث بسبب تشابه التشكيل!!)

- سنتجاهل الكلمة إذا كانت المسافة بينها وبين كلمة البحث، أطول من طول كلمة البحث (اختلافات كثيرة جدا)

- إذا كانت الكلمة الحالية تحتوي على كلمة البحث أو العكس، فسنعطي أولوية لهذه الكلمة أكبر من أولوية مسافات ليفنيشتاين.. سنفعل هذا بوضع True في الخاصية IsPartial في الكائن الذي نحفظ فيه بيانات البحث، وعند الترتيب سنرتب على أساس قيمة الخاصية IsPartial أولا، ثم نرتب على أساس المسافة، ثم نرتب على أساس الترتيب الأبجدي للكلمات بدون تشكيل، ثم أخيرا نرتب على أساس أسبقية مواضع الكلمات في النص، وبهذا تظهر نتائج البحث بأفضل ترتيب منطقي يتوقعه المستخدم.. كل هذا ينفذه استعلام LinQ التالي:

From Sel In WordSelections

Order By Sel.IsPartial Descending, Sel.Distance,

                Sel.GetAbsWord(Txt), Sel.StartPos               

ويمكنكم تحميل المشروع (نسخة فيجوال بيزيك ونسخة سي شارب) من ميديا فاير من هذا الرابط.

 

ملحوظة:

يمكنك الحصول على نتائج أفضل، باستخدام التحليل الصرفي للحصول على الجذر المحتملة لكلمة البحث أولا، وتحليل جذور كل كلمات النص الذي ستبحث فيه، لأخذ الكلمات المشتركة في الجذور مع كلمة البحث، ثم حساب مسافة ليفنشتاين لها.. هذا إن كان تحت تصرفك محلل صرفي.. هذه الطريقة تستخدم لإنشاء محركات البحث والفهرسة Indexing (مثل محركات البحث في الويب) .