خوازمية رابين وكارب
نظرة عامة

في الخوارزميات البسيطة للبحث في النصوص، تقوم الخوارزمية بمقارنة السلسلة المراد البحث عنها بكل موقع (حرف) في النص المراد البحث فيه. فعند حساب التعقيد الأسوأ لهذا النوع من الخوارزميات، نجد أن الوقت الذي تحتاجه الخوارزمية لمقارنة كل حرف بالسلسلة يتناسب تناسبًا طرديًا مع طول هذه السلسلة، وكذلك الحال بالنسبة للوقت الذي تحتاجه للمرور على جميع المواقع في النص المراد البحث فيه، فهو يتناسب تناسبًا طرديًا مع طول النص. وبالتالي يتناسب الوقت الأسوأ لأداء هذه الخوارزمية تناسبًا طرديًا مع حاصل ضرب الطولين (طول السلسلة m وطول النص n).  عند التطبيق العملي، من الممكن زيادة سرعة الخوارزمية بتقليل الوقت اللازم للمقارنات بشكل كبير، عن طريق إيقاف المقارنة مباشرة عند موقع معيّن في النص، بمجرد حصول عدم تطابق. لكن هذه الطريقة، لا تضمن زيادة السرعة بكل الحالات.
تعمل بعض خوارزميات البحث في نص، مثل خوارزمية كنوث – موريس – برات، وخوارزمية بوير- مور، على تقليل الوقت الأسوأ لمطابقة سلسلة معينة في النص، وذلك عن طريق استغلال عدم المطابقة في مواقع من النص واستخلاص معلومات منها تفيد في تخطي بعض المواقع التالية فيه والتي تضمن الخوارزمية عدم مطابقتها للسلسلة المراد البحث عنها. أما بالنسبة لخوارزمية رابين – كارب، فهي تعمل على زيادة سرعة الخوارزمية باستخدام دالة تجزئة (hash function). تُساعد الدالة على إعطاء احتمالية وجود تطابق في موقع معين من النص مع السلسلة، وبالتالي في حال وجود هذه الاحتمالية، يتبقى فقط عمل مقارنة واحدة للسلسة ابتداءً من هذا الموقع لإيجاد التطابق بشكل مباشر. بهذه الطريقة، لا تتم مقارنة السلسلة مع كل موقع من النص، وبهذا لا تحتاج الخوارزمية إلى مسح كافة مواقع النص، مما يزيد من سرعة أدائها.
دالة التجزئة، هي عبارة عن دالة (function) تقوم بتحويل سلسلة من الرموز (string) إلى قيمة رقمية واحدة، تُسمى قيمة التجزئة (hash value). فإذا تساوت سلسلتان من الرموز، فالمُفترض أن ينتج من دالة التجزئة نفس القيمة الرقمية بالحالتين. والعكس صحيح في حال تم بناء الدالة بشكل جيد، فإن تم إدخال سلسلتين غير متشابهتين إلى الدالة، فمن غير المحتمل، بشكل تقريبي، أن ينتج عن كليهما نفس قيمة التجزئة. وهذا هو المبدأ القائم عليه عملية البحث في رابين – كارب. فتقوم الخوارزمية بحساب قيمة التجزئة لكل جزء من النص ابتداءً من كل موقع فيه، وبنفس طول السلسلة المراد البحث عنها. ففي اللحظة التي تشابه قيمة التجزئة لهذا الجزء من النص مع قيمة التجزئة للسلسلة، يتم عمل مقارنة كاملة لكل أحرف السلسلة ابتداءً من هذا الموقع، للتأكد من المطابقة.
من المشاكل المعروفة لدوال التجزئة، التطابق الخاطئ أو الإيجابية الكاذبة (false positive). تحدث هذه المشكلة عندما تُنتج الدالة نفس قيمة التجزئة لسلسلتين مختلفتين فعليًّا. ومن هنا جاءت أهمية اختيار دالة تجزئة بشكل عشوائي من مجموعة من الدوال ذوات الاحتمالية الأقل لحدوث هذه الحالة.
عند حدوث التطابق الخاطئ في خوارزمية رابين – كارب عند موقع معين من النص المراد البحث فيه، أي أن قيمة التجزئة التي نتجت من هذا الموقع، مشابهة لقيمة التجزئة للسلسلة المراد البحث عنها. هذه النتيجة ستستدعي ضرورة التأكد من مطابقة السلسلة للنص ابتداءً من هذا الموقع، وبالتالي سيزيد من الوقت الفعلي الذي تحتاجه الخوارزمية بدون داعي، وذلك لأن الخوارزمية ستكتشف عدم وجود تطابق عند هذا الموقع.
إذا افترضنا أن عملية حساب قيم التجزئة في النص تتم على كل موقع فيه بطول السلسلة المراد البحث عنها وذلك بتطبيق دالة التجزئة عند كل موقع، فستكون العملية بطيئة جدًا، وتحتاج إلى وقت يتناسب مع عدد المواقع (الرموز) الموجودة في النص الكامل. لذلك، فإن عملية التجزئة التي تستخدمها خوارزمية رابين – كارب، تعتمد على مبدأ التجزئة المتدرجة (rolling hash). وهي عبارة عن دالة للتجزئة تقوم بحساب قيمة التجزئة لكل موقع بالاعتماد على قيمة الموقع السابق، مما يؤدي إلى سرعة أكبر في إنتاج قيم التجزئة للنص كاملًا.