شرح خوارزمية رابين-كارب

خوارزمية رابين-كارب هي خوارزمية مطابقة / بحث تم تطويرها بواسطة مايكل أو. رابين وريتشارد إم كارب. يستخدم تقنية التجزئة والقوة الغاشمة للمقارنة ، وهو مرشح جيد لاكتشاف الانتحال.

شروط مهمة

• النمط هو السلسلة المراد البحث عنها. ضع في اعتبارك طول النمطكأحرف M.
• النص هو النص الكامل الذي سيتم البحث عن النمط منه. ضع في اعتبارك طول النصكأحرف N.

ما هي مقارنة القوة الغاشمة؟

في مقارنة القوة الغاشمة ، تتم مقارنة كل حرف من النمط مع كل حرف من أحرف النص حتى يتم العثور على الأحرف غير المتطابقة.

كيف تعمل خوارزمية رابين-كارب

1. حساب قيمة تجزئة النمط
2. احسب قيمة التجزئة لأول حرف M من النص
3. قارن بين قيمتي التجزئة
4. إذا كانت غير متساوية ، فاحسب قيمة التجزئة للأحرف M التالية من النص وقارن مرة أخرى.
5. إذا كانت متساوية ، قم بإجراء مقارنة القوة الغاشمة.

hash_p = hash value of pattern hash_t = hash value of first M letters in body of text do if (hash_p == hash_t) brute force comparison of pattern and selected section of text hash_t= hash value of next section of text, one character over while (end of text or brute force comparison == true)

ميزة على خوارزمية مطابقة السلسلة الساذجة

ينتج عن هذه التقنية مقارنة واحدة فقط لكل تسلسل فرعي للنص ، وتكون القوة الغاشمة مطلوبة فقط عندما تتطابق قيم التجزئة.