ما هي خوارزمية رابين كارب؟

خوارزمية Rabin-Karp عبارة عن خوارزمية مطابقة لنمط السلسلة التي تبحث بكفاءة عن تكرارات النمط داخل نص أكبر. تم تطويره بواسطة مايكل أو رابين وريتشارد إم كارب في عام 1987.

تستخدم الخوارزمية تقنية التجزئة لمقارنة قيم التجزئة للنمط والسلاسل الفرعية للنص. يعمل على النحو التالي:

• احسب قيمة التجزئة للنمط والنافذة الأولى للنص.

• حرك النمط فوق النص موضعًا واحدًا في كل مرة وقارن قيم التجزئة.

• إذا كانت قيم التجزئة متطابقة، فقم بمقارنة أحرف النمط والنافذة الحالية للنص لتأكيد المطابقة.

• إذا كان هناك تطابق، سجل موضع/فهرس التطابق.

• احسب قيمة التجزئة للنافذة التالية من النص باستخدام وظيفة التجزئة المتداول.

• كرر الخطوات من 3 إلى 5 حتى يتم التحقق من جميع مواضع النص.

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

برنامج PHP لخوارزمية رابين كارب للبحث عن الأنماط

";
      }

      // Calculate the hash value for the next window of text
      if ($i 

الإخراج

Pattern found at index 1 
Pattern found at index 4
Pattern found at index 7
Pattern found at index 10
Pattern found at index 13

شرح الكود

يطبق كود PHP خوارزمية Rabin-Karp للبحث عن الأنماط. يأخذ نمطًا ونصًا كمدخلات ويبحث عن تكرارات النمط داخل النص. تقوم الخوارزمية بحساب قيم التجزئة للنمط والنافذة الأولى للنص. ثم يقوم بعد ذلك بتمرير النمط فوق النص، ومقارنة قيم التجزئة للنافذة الحالية والنمط. إذا كانت قيم التجزئة متطابقة، فسيتم التحقق من الأحرف واحدًا تلو الآخر. إذا تم العثور على تطابق، فإنه يطبع الفهرس حيث يوجد النمط. تستخدم الخوارزمية وظيفة التجزئة المتداولة لتحديث قيمة التجزئة لكل نافذة بكفاءة. يوضح الكود استخدام الخوارزمية من خلال البحث عن النمط "BC" في النص "ABCABCABCABCABC".

خاتمة

في الختام، يقوم برنامج PHP بتنفيذ خوارزمية Rabin-Karp للبحث عن الأنماط بشكل فعال. من خلال استخدام دالة التجزئة المتداولة ومقارنة قيم التجزئة، تبحث الخوارزمية بكفاءة عن تكرارات النمط داخل نص أكبر. يحدد البرنامج بشكل صحيح المؤشرات التي يوجد بها النمط في النص ويخرج النتائج. مع بنية واضحة وحسابات التجزئة المناسبة، يوضح البرنامج وظيفة وفائدة خوارزمية Rabin-Karp للبحث عن الأنماط في PHP.