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

خوارزمية رابين وكارب بيانات عامّة الصنف خوارزمية للبحث في النصوص (string) الأداء أسوء حالة $O(mn)$ plus $O(m)$ بالإضافة إلى وقت المعالجة الأداء الوسطي $O(n)$ أسوأ حالة تعقيد مكاني $O(1)$

في عام 1987 قام الباحثان ريتشارد م. كارب ومايكل أ. رابين بإنشاء خوارزمية بحث في النصوص سُميت باسم خوارزمية رابين – كارب أو خوارزمية كارب – رابين. وهي تُعد من الخوارزميات المشهورة في علم الحاسوب. تستخدم هذه الخوارزمية مبدءًا من مبادئ التجزئة (hashing) لإيجاد تطابق تام لسلسلة من الرموز (string) في نص وهو التجزئة المتدرجة (rolling hash). باستخدام التجزئة المتدرجة تقوم الخوارزمية بشكل سريع باستثناء مواقع من النص لا يُمكن مطابقتها للسلسلة المراد البحث عنها، وتكتفي بالبحث ضمن المواقع المتبقية عن التطابق المطلوب. من الممكن تعميم فكرة الخوارزمية للبحث عن أكثر من تطابق واحد للسلسلة في نفس النص، أو البحث عن تطابق لعدة سلاسل مختلفة فيه.

يتم حساب معدل الوقت المتوقع (expected time) الذي تحتاجه الخوارزمية لإيجاد تطابق واحد لسلسة من الرموز في نص عن طريق إيجاد مجموع أطوال السلسلة والنص معًا، مما يُعد وقتًا خطيًّا (linear). أما بالنسبة للتعقيد الزمني الأسوأ (worst-case time complexity)  فيُحسب كحاصل ضرب هذين الطولين. أما في حالة إيجاد عدة تطابقات للسلسلة، فتحتاج الخوارزمية، بالمعدل، وقتًا خطيًّا بالاعتماد على طول المدخلات، ويضاف إليه أطوال كل التطابقات مما يجعل معدل الوقت المتوقع يتعدّى الوقت الخطي. وفي المقابل، نجد خوارزمية أخرى، وهي خوارزمية أهو – كوراسيك (Aho-Corasick algorithm)، تستطيع بدورها إيجاد جميع حالات التطابق لأكثر من سلسلة في النص بتعقيد خطّي للزمن والمساحة الأسوأ بالاعتماد على طول المدخلات وعدد التطابقات التي تم إيجادها، وليس مجموع أطوال التطابقات.

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

نظرة عامة

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

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

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

من المشاكل المعروفة لدوال التجزئة، التطابق الخاطئ أو الإيجابية الكاذبة (false positive). تحدث هذه المشكلة عندما تُنتج الدالة نفس قيمة التجزئة لسلسلتين مختلفتين فعليًّا. ومن هنا جاءت أهمية اختيار دالة تجزئة بشكل عشوائي من مجموعة من الدوال ذوات الاحتمالية الأقل لحدوث هذه الحالة.

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

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

الخوارزمية

الخوارزمية كما هو موضح:

// خوارزمية رابين - كارب
function RabinKarp(string s[1..n], string pattern[1..m])
// s: النص المراد البحث فيه
// pattern: السلسلة المراد البحث عنها في النص
    hpattern := hash(pattern[1..m]);
    for i from 1 to n-m+1
        hs := hash(s[i..i+m-1])
        if hs = hpattern
            if s[i..i+m-1] = pattern[1..m]
                return i
    return not found

لتحليل الخوارزمية، لنبدأ بالأسطر 5، 7 و9، حيث أن كلًّا منها تحتاج إلى O(m) من الوقت. بالنسبة لسطر 5، فيتم تنفيذه مرة واحدة فقط. أما السطر 7، فلا يتم تنفيذه إلا في حال تطابق قيمة التجزئة للسلسلة مع قيمة التجزئة في النص ابتداءًا من الموقع i. أما بالنسبة للسطر 8، صحيح أنه يُنفذ n من المرات، ولكن كل مقارنة تحتاج إلى وقت ثابت (constant)، فيحتاج إلى وقت لا يزيد عن O(n). يتبقى لدينا السطر 7، وهو الذي يحتاج الوقت الأكبر في الخوارزمية، وبالتالي يعتمد عليه تحليل سرعتها.

في حال استخدام دالة تجزئة بسيطة لحساب قيمة التجزئة للنص الجزئي s[i+1..i+m]، تحتاج الخوارزمية إلى O(m) من الزمن وذلك لضرورة فحص كل رمز من النص الجزئي. وبما أن هذا الحساب يتم داخل دوران يمر بكل مواقع النص حتى i+m-1، فسيصبح الزمن كاملًا O(mn) ، وهو التعقيد الزمني لأي خوارزمية مباشرة للبحث في نصوص.

لضمان سرعة الخوارزمية، يجب حساب قيمة التجزئة في زمن ثابت. عند التركيز على المتغير hs  سنلاحظ أنه في كل لفة من الدوران يحتوي على القيمة السابقة للتجزئة (في الموقع السابق من النص) وهي قيمة التجزئة ل s[i..i+m-1]. فالفكرة هنا، هي الاستفادة من هذه القيمة لحساب قيمة التجزئة التالية للموقع التالي بزمن ثابت. إن تحقق هذا، ستنفذ الخوارزمية حسابات متتالية لقيم التجزئة بشكل سريع.

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

(ملاحظة مهمة: الجزء التالي من النص، هو عبارة عن الجزء السابق، محذوفًا منه الرمز الأول، ومضافًا إليه الرمز التالي في النص).

s[i+1..i+m] = s[i..i+m-1] - s[i] + s[i+m]

هذه الدالة البسيطة جيدة، وتُسرع من عملية حساب قيمة التجزئة لأجزاء متتالية من النص، ولكن هذا لن يمنع أن يتم تنفيذ السطر 8 بشكل متكرر أكثر من لو تم استخدام إحدى الدوال الخاصة بالتجزئة المتدرجة والأكثر تطوّرًا من هذه. سيتم مناقشة إحدى هذه الدوال في القسم الآتي من المقال.

النقطة المهمة هنا، أن اختيار دالة تجزئة جيدة تعني أداءً جيدًا بسرعة جيدة للخوارزمية. فإن كانت دالة التجزئة سيئة، بمعنى إنتاجها لقيم تجزئة متشابهة لكل مدخلاتها، فإن السطر 9 سيحتاج لتنفيذه O(n)  من الزمن (أي لكل لفة في الدوران). وبما أن مقارنة كل رمز بسلسلة طولها m يحتاج إلى زمن O(m) ، فإن الزمن الأسوأ للخوارزمية كاملة سيكون O(mn).

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

السر في علو أداء خوارزمية رابين – كارب هو الحساب السريع لقيم التجزئة لأجزاء متتالية من النص المراد البحث فيه. ومن الخوارزميات الشائعة وذات الكفاءة العالية والتي تُستخدم كدوال تجزئة متدرجة هي بصمة رابين (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) بقيم التجزئة لأكثر من سلسلة مختلفة في الواقع، وبالتالي تقل سرعة الخوارزمية عن السرعة المُحبذة.

البحث عن سلاسل متعددة في النص

على الرغم من اعتبار خوارزمية رابين – كارب للبحث عن سلسلة واحدة في نص، أسوأ من الخوارزميات الأخرى من أمثال خوارزمية كنوث – موريس – برات، وخوارزمية بوير – مور، وغيرها من الخوارزميات السريعة للبحث في النصوص (single searching algorithms)، وذلك بسبب التعقيد الزمني الأسوأ لأداء خوارزمية رابين – كارب في هذه الحالة، والذي يُعتبر أبطأ من الخوارزميات الأخرى. ولكنها في المقابل، تُتعبر من الخوارزميات المرغوبة والمفيدة للبحث عن عدة سلاسل مختلفة في النص (multiple pattern search).

للبحث وإيجاد عدد من السلاسل المختلفة (k strings)، ذات الأطوال المتشابهة،  نستطيع استخدام نسخة مُطورة من خوارزمية رابين – كارب والتي تستخدم مرشح بلوم (Bloom Filter)، أو المجموعة (set) كنوع من أنواع تراكيب البيانات. وتقوم هذه الخوارزمية بمقارنة قيمة التجزئة لكل جزء من النص بجميع قيم التجزئة للسلاسل المراد البحث عنها.

//خوارزمية رابين - كارب للبحث عن عدة سلاسل في نص
function RabinKarpSet(string s[1..n], set of string subs, m):
//s: النص المراد البحث فيه
// m: طول كل سلسلة في مجموعة السلاسل المراد الحث عنها
// على افتراض أن أطوال هذه السلاسل متشابهة
    set hsubs := emptySet
    foreach sub in subs
        insert hash(sub[1..m]) into hsubs
    hs := hash(s[1..m])
    for i from 1 to n-m+1
        if hs ∈ hsubs and s[i..i+m-1] ∈ subs
            return i
        hs := hash(s[i+1..i+m])
    return not found

إن اعتمدنا إحدى خوارزميات البحث عن سلسلة واحدة في نص، والتي تحتاج إلى تعقيد زمني O(m+n) ، ممكن بطريقة مباشرة حساب التعقيد الزمني لنفس الخوارزمية إن تم استخدامها للبحث عن عدد k  من السلاسل في نص، وسيكون بهذه الحالة O((m+n)k). ولكن فعليًا، ممكن حساب معدل التعقيد الزمني المتوقع للخوارزمية أعلاه لإيجاد كل k  من السلاسل في النص ب O(n+km)، وذلك على افتراض أن التعقيد الزمني للبحث في جدول قيم التجزئة هو O(1)  بالمعدل.

مراجع

• Karp، Richard M.؛ Rabin، Michael O. (مارس 1987). "Efficient randomized pattern-matching algorithms". IBM Journal of Research and Development. ج. 31 ع. 2: 249–260. DOI:10.1147/rd.312.0249.
• Cormen، Thomas H.؛ Leiserson، Charles E.؛ Rivest، Ronald L.؛ Stein، Clifford (1 سبتمبر 2001) [1990]. "The Rabin–Karp algorithm". مقدمة في الخوارزميات (كتاب) (ط. 2nd). كامبريدج (ماساتشوستس): MIT Press. ص. 911–916. ISBN:978-0-262-03293-3.
• Candan، K. Selçuk؛ Sapino، Maria Luisa (2010). Data Management for Multimedia Retrieval. Cambridge University Press. ص. 205–206. ISBN:978-0-521-88739-7. مؤرشف من الأصل في 2022-11-10. (for the Bloom filter extension)
• Yet another explanation

روابط خارجية

• "Rabin–Karp Algorithm/Rolling Hash" (PDF). MIT 6.006: Introduction to Algorithms 2011- Lecture Notes. MIT. مؤرشف من الأصل (PDF) في 2022-11-10.