خوازمية رابين وكارب
دالة التجزئة المستخدمة في الخوارزمية

السر في علو أداء خوارزمية رابين – كارب هو الحساب السريع لقيم التجزئة لأجزاء متتالية من النص المراد البحث فيه. ومن الخوارزميات الشائعة وذات الكفاءة العالية والتي تُستخدم كدوال تجزئة متدرجة هي بصمة رابين (Rabin Fingerprint). ومع أن دالة التجزئة المتدرجة التي سيتم شرحها في هذا القسم هي ليست نفسها بصمة رابين، إلا أنها تحقق الكفاءة نفسها تقريبًا. فهي تقوم على فكرة معالجة كل نص جزئي كرقم بأساس معين، وهذا الأساس بالعادة يكون الرقم المساوي لحجم عدد الرموز في مجموعة الرموز المستخدمة لكتابة النص. ففي المثال التالي، تم استخدام العدد 256 كأساس وهو حجم المجموعة التي تحوي كل رموز الآسكي (ASCII).
في المثال التالي، المطلوب حساب قيمة التجزئة للسلسلة "hi"، مع اعتبار أن الأساس هو 256، وأن العدد الأوّلي المراد استخدامه لإيجاد باقي القسمة هو 101، في هذه الحالة، يتم حساب قيمة التجزئة كالتالي:
مع الأخذ بعين الاعتبار أن قيمة الآسكي لحرف 'h' هي 104، ولحرف 'i' هي 105، فتتم حساب قيمة التجزئة في المعادلة التالية، لتُنتج الرقم 65.
[(104 × 256 ) % 101  + 105] % 101  =  65
الرمز % المستخدم في المعادلة، هي عملية حسابية تعني باقي القسمة الصحيحة (mod).
وهنا تكمُن الفائدة في استخدام دالة تجزئة متدرجة مثل بصمة رابين في تسريع الخوارزمية، والتي تعمل على حساب قيمة التجزئة لجزء من النص بالاعتماد على الجزء السابق منه بعدد ثابت من العمليات، وبغض النظر عن طول هذا الجزء من النص.
في المثال التالي، لنفرض أن النص لدينا هو "abracadabra"، وأن السلسلة المراد البحث عنها في النص طولها 3 رموز. فسنعمل على حساب قيمة التجزئة لكل جزء من النص بطول 3. فتكون البداية بحساب قيمة التجزئة للسلسلة "abr"، باستخدام الأساس 256 والعدد الأولي 101 المستخدم لحساب باقي القسمة الصحيحة، فيكون حساب قيمة التجزئة كالتالي:
// قيم الآسكي للأحرف في السلسلة a = 97, b = 98, r = 114.
// hash: هي دالة التجزئة المستخدمة

hash("abr") =  [ ( [ ( [  (97 × 256) % 101 + 98 ] % 101 ) × 256 ] %  101 ) + 114 ]   % 101   =  4
ثم ستقوم الخوارزمية بحساب قيمة التجزئة للجزء التالي من النص، "bra"، والذي سيعتمد على قيمة التجزئة للجزء السابق "abr"، والذي تم حسابه في المعادلة السابقة. ستقوم الخوارزمية بطرح قيمة الحرف الأول من الجزء السابق "a"، ومن ثم إضافة قيمة الحرف الأخير من الجزء التالي وهو أيضًا حرف "a"، ولكن هنا ستختلف قيمة التجزئة للحرفين حسب موقعهما في السلسلة.
hash("bra") =     [ ( 4   + 101         -  97 * [(256%101)*256] % 101 ) * 256         +    97 ] % 101              =  30
نلاحظ في المعادلة السابقة، أنه لحساب القيمة الجديدة، نطرح الحرف الأول من القيمة السابقة، ونضيف الحرف الأخير إلى القيمة الجديدة، بدون المرور على الأحرف الأخرى في هذا الجزء من النص، وبالتالي ستزيد سرعة الخوارزمية بتقليل الزمن الذي تحتاجه لحساب قيم التجزئة لجميع المواقع في النص. وسيظهر هذا الفرق بالسرعة مع زيادة طول السلسلة المراد البحث عنها.
من الناحية النظرية، هناك خوارزميات أخرى تستطيع أن تعيد حساب قيمة التجزئة بسرعة مقبولة ومُقنعة. فمثلًا، من الممكن ضرب قيم الآسكي لجميع الرموز في السلسلة لحساب قيمة التجزئة، ثم عند حساب الجزء التالي، تقوم الخوارزمية بالقسمة على قيمة التجزئة للرمز الأول من الجزء السابق، وضرب قيمة التجزئة للرمز الأخير من الجزء التالي. المشكلة بهذه الطرق التي تستخدم باقي القسمة الصحيحة، هو ضرورة استخدام القيم الصحيحة فقط، والتي تقبل إجراء هذه العملية (mod)، وهذا يُحدد الخوارزمية بمدى معين من الأعداد التي يسمح بها هذا النوع من البيانات (Integer). ومن المشاكل الأخرى التي يُمكن أن تواجهها الخوارزمية، أن قيمة التجزئة قد لا تتم حسابها بطريقة سريعة لحدوث تصادم (تشابه – hash collisions) بقيم التجزئة لأكثر من سلسلة مختلفة في الواقع، وبالتالي تقل سرعة الخوارزمية عن السرعة المُحبذة.