Algorithms/Rabin Karp

تحرّك خوارزمية رابين-كارب Rabin-Karp النمط الذي تبحث عنه عبر السلسلة النصية موقعًا تلو الآخر كما هو الحال مع خوارزمية البحث البسيطة Naive algorithm، ولكن تختلف خوارزمية رابين-كارب في أنّها تطابق قيمة التقطيع Hash value للنمط المعطى مع قيمة التقطيع لجزء السلسلة الذي تجري معه المقارنة، ولا تطابق الخوارزمية الحروف المفردة إلا بعد أن تتساوى قيمتا التقطيع.

تحتاج خوارزمية رابين-كارب إلى حساب قيمة التقطيع لكلّ من:

1. النمط الذي تبحث عنه.
2. جميع السلاسل النصية ذات الطول m والمتفرعة من النصّ الأصلي.

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

يوضح المثال التالي طريقة عمل الخوارزمية:

لنفترض أنّ لدينا النصّ "yeminsajid" وأنّنا نرغب في معرفة هل أنّ النمط "nsa" موجود فيه أم لا.

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

تستخدم الصيغة الرياضية التالية لحساب قيمة التقطيع:

(الحرف الأول) × (العدد الأولي)^0 + (الحرف الثاني) × (العدد الأولي)^1 + (الحرف الثالث) × (العدد الأولي)^2 + .....

(1st letter) X (prime) + (2nd letter) X (prime)¹ + (3rd letter) X (prime)² X + ......

وسنعطي كل حرف في الأبجدية رقمًا كما يلي:

a -> 1    g -> 7    m -> 13   s -> 19   y -> 25
b -> 2    h -> 8    n -> 14   t -> 20   z -> 26
c -> 3    i -> 9    o -> 15   u -> 21
d -> 4    j -> 10   p -> 16   v -> 22
e -> 5    k -> 11   q -> 17   w -> 23
f -> 6    l -> 12   r -> 18   x -> 24

تصبح قيمة التقطيع للنمط "nsa" بالاعتماد على المعطيات السابقة:

14 X 11⁰ + 19 X 11¹ + 1 X 11² = 344

سنحسب الآن قيمة التقطيع للجزء المقابل من النص، وإن تطابقت هذه القيمة مع قيمة التقطيع الخاصة بالنمط، فسنتحقق من تطابق السلسلتين النصيتين حينها.

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

25 X 11⁰ + 5 X 11¹ + 13 X 11² = 1653

لا تتطابق هذه القيمة مع قيمة التقطيع الخاصة بالنمط، وهذا يعني أنّ السلسلة النصية المطلوبة غير موجودة في هذا المقطع؛ لذا سننتقل خطوة واحدة إلى الأمام، وسنحسب قيمة التقطيع للسلسلة "emi". يمكن حساب قيمة التقطيع باستخدام الصيغة الواردة في أعلاه، ولكنّ تكرار تلك الطريقة سيستهلك المزيد من الوقت والمصادر.

يمكن استخدام الطريقة التالية لحساب قيمة التقطيع للسلسلة النصية الثانية:

نطرق قيمة الحرف الأول في السلسلة النصية السابقة من قيمة التقطيع الحالية، وفي هذه الحالة الحرف الأول هو "y" لنحصل على: ‎1653 - 25 = 1628‎. ثم نقسّم حاصل الطرح على العدد الأوّلي الذي اخترناه (11 في هذا المثال): ‎1628 / 11 = 148‎، ثم نضيف القيمة الناتجة من العملية (الحرف الجديد) × (العدد الأولي)^‎m-1‎، وتمثّل m عدد الأحرف في النمط (قيمة الحرف الجديد i هي 9): ‎148 + 9 X 11^2 = 1237‎.

لاحظ أنّ قيمة التقطيع الجديدة لا تساوي قيمة التقطيع الخاصة بالنمط؛ لذا سننتقل خطوة واحدة إلى الأمام:

السلسلة النصية السابقة: emi
الحرف الأول في السلسلة النصية السابقة: e(5)‎
الحرف الجديد: n(14)‎
السلسلة النصية الجديدة: "min"
‎1237 - 5 = 1232‎
‎1232 / 11 = 112‎
‎112 + 14 X 11² = 1806‎

لاحظ أنّ قيمة التقطيع الجديدة لا تساوي قيمة التقطيع الخاصة بالنمط؛ لذا سننتقل خطوة واحدة إلى الأمام:

السلسلة النصية السابقة: min
الحرف الأول في السلسلة النصية السابقة: m(13)‎
الحرف الجديد: s(19)‎
السلسلة النصية الجديدة: "ins"
1806 - 13 = 1793
1793 / 11 = 163
163 + 19 X 11² = 2462

لاحظ أنّ قيمة التقطيع الجديدة لا تساوي قيمة التقطيع الخاصة بالنمط؛ لذا سننتقل خطوة واحدة إلى الأمام:

السلسلة النصية السابقة: ins
الحرف الأول في السلسلة النصية السابقة: i(9)‎
الحرف الجديد: a(1)‎
السلسلة النصية الجديدة: "nsa"
2462 - 9 = 2453
2453 / 11 = 223
223 + 1 X 11² = 344

لاحظ أنّ قيمة التقطيع هذه مساوية لقيمة التقطيع الخاصة بالنمط؛ لذا يمكننا مقارنة النمط مع السلسلة النصية الحالية، ولما كانت السلسلتان متطابقتين، فإنّ السلسلة النصية الفرعية موجودة في السلسلة النصية الأصلية، وسنعيد الموقع الذي تبدأ عنده السلسلة النصية الفرعية.

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

تنفيذ الخوارزمية

تعرض الأمثلة التالية طريقة تنفيذ الخوارزمية في عدد من لغات البرمجة:

#include <bits/stdc++.h> 
using namespace std; 

// d عدد الحروف في المدخلات هو 
#define d 256 

/* pat -> النمط
	txt -> النص 
	q -> عدد أولي 
*/
void search(char pat[], char txt[], int q) 
{ 
	int M = strlen(pat); 
	int N = strlen(txt); 
	int i, j; 
	int p = 0; // قيمة التقطيع للنمط 
	int t = 0; // قيمة التقطيع للنص 
	int h = 1; 

	// The value of h would be "pow(d, M-1)%q" 
	for (i = 0; i < M - 1; i++) 
		h = (h * d) % q; 

	// Calculate the hash value of pattern and first 
	// window of text 
	for (i = 0; i < M; i++) 
	{ 
		p = (d * p + pat[i]) % q; 
		t = (d * t + txt[i]) % q; 
	} 

	// Slide the pattern over text one by one 
	for (i = 0; i <= N - M; i++) 
	{ 

		// Check the hash values of current window of text 
		// and pattern. If the hash values match then only 
		// check for characters on by one 
		if ( p == t ) 
		{ 
			/* Check for characters one by one */
			for (j = 0; j < M; j++) 
			{ 
				if (txt[i+j] != pat[j]) 
					break; 
			} 

			// if p == t and pat[0...M-1] = txt[i, i+1, ...i+M-1] 
			if (j == M) 
				cout<<"Pattern found at index "<< i<<endl; 
		} 

		// Calculate hash value for next window of text: Remove 
		// leading digit, add trailing digit 
		if ( i < N-M ) 
		{ 
			t = (d*(t - txt[i]*h) + txt[i+M])%q; 

			// We might get negative value of t, converting it 
			// to positive 
			if (t < 0) 
			t = (t + q); 
		} 
	} 
} 

/* Driver code */
int main() 
{ 
	char txt[] = "GEEKS FOR GEEKS"; 
	char pat[] = "GEEK"; 
	int q = 101; // A prime number 
	search(pat, txt, q); 
	return 0; 
} 

// This is code is contributed by rathbhupendra

التعقيد الزمني

يبلغ التعقيد الزمني لخوارزمية رابين-كارب المقدار O(n+m)‎ في أفضل الحالات وفي الحالات المتوسطة كذلك، ولكن في أسوأ الحالات يبلغ التعقيد الزمني المقدار O(nm)‎.

تمثّل n طول النص، وm مجموع أطوال الأنماط التي ستجري مطابقتها مع النص.