تجزئة رابين-كارب المتداولة

خطوات الاستخدام

أدخل النص الذي تريد حساب قيمة التجزئة المتداولة له. على سبيل المثال، النص "abc".</br>ملاحظة: يتم تحويل كل حرف إلى قيمته الرقمية (مثل ASCII أو يونيكود) لتطبيق العمليات الحسابية.

حدد الأساس (Base) المستخدم في الحساب. الأساس هو رقم أولي أو عدد صحيح كبير مثل 256 أو 131. يفضل استخدام عدد أولي لتقليل احتمالية التصادمات (Collisions) في التجزئة. الأساس يُستخدم لتمثيل قيم الأحرف في نظام عددي.</br>مثال: إذا كان الأساس = 256، فهذا يعني أننا نتعامل مع البايتات (0-255).

حدد المعامل (Modulus) وهو عدد أولي كبير (مثل 10^9+7 أو 2^64) يستخدم للتقليل من حجم القيم ومنع الفيضان (Overflow). المعامل يضمن أن قيمة التجزئة تبقى ضمن نطاق محدد.</br>مثال: modulus = 1000000007 (وهو عدد أولي معروف).

الأسئلة الشائعة

خوارزمية رابين-كارب (Rabin-Karp) هي خوارزمية بحث عن أنماط في النصوص (String Matching) طورها مايكل رابين وريتشارد كارب عام 1987. تستخدم فكرة التجزئة (Hashing) للمقارنة بين النمط (Pattern) وجميع النوافذ الفرعية للنص (Substrings) بنفس الطول. بدلاً من مقارنة كل نافذة حرفاً بحرف (وهو ما يكلف O(m) لكل نافذة)، تحسب الخوارزمية قيمة تجزئة للنمط وجميع النوافذ باستخدام التجزئة المتداولة (Rolling Hash)، مما يسمح بتحديث قيمة التجزئة من نافذة إلى التالية في وقت ثابت O(1). هذا يجعل التعقيد الزمني المتوقع للخوارزمية O(n+m) في أفضل الحالات، حيث n طول النص و m طول النمط. التجزئة المتداولة تعمل كالتالي: لكل نافذة من الأحرف، يتم حساب قيمة عددية باستخدام دالة تجزئة مثل H = (c1 * b^(m-1) + c2 * b^(m-2) + ... + cm * b^0) mod M، حيث b هو الأساس (عادة عدد أولي) وM معامل كبير. عند الانتقال إلى النافذة التالية، يتم طرح مساهمة الحرف الأول (c1 * b^(m-1))، ضرب النتيجة في b، وإضافة الحرف الجديد. العملية تتم باستخدام حسابيات معيارية. لاحظ أن التجزئة قد تؤدي إلى تصادمات (Collisions) حيث نافذتان مختلفتان لهما نفس قيمة التجزئة. للتعامل مع ذلك، عند تطابق التجزئات، يتم إجراء مقارنة حرفية (Character by Character) للتأكد من التطابق الفعلي. مع اختيار مناسب للأساس والمعامل (أعداد أولية كبيرة)، تكون احتمالية التصادم منخفضة جداً، مما يجعل الخوارزمية فعالة عملياً خاصة في التطبيقات مثل كشف السرقة الأدبية (Plagiarism Detection) أو البحث في ملفات كبيرة.

اختيار الأساس (Base) والمعامل (Modulus) أمر حاسم لأداء وموثوقية خوارزمية رابين-كارب. الهدف هو تقليل احتمال التصادمات (أي أن نافذتين مختلفتين تعطيان نفس قيمة التجزئة). إليك مبادئ التوجيه: - الأساس (Base): يجب أن يكون عدداً أولياً (Prime) أو عدداً صحيحاً أكبر من حجم الأبجدية (Alphabet Size). مثلاً، إذا كانت الأحرف من 0 إلى 255 (بايتات)، يمكن استخدام base=257 أو 263. استخدام عدد أولي يساعد في توزيع القيم بشكل أفضل ويقلل من أنماط معينة تؤدي لتصادمات. أيضاً، يمكن استخدام base=131 أو 137 لأنها أعداد أولية مشهورة. لا ينصح باستخدام base زوجي أو قوى 2، لأن ذلك قد يسبب فقدان معلومات. - المعامل (Modulus): يجب أن يكون عدداً أولياً كبيراً (Large Prime) لتقليل احتمالية أن يكون الفرق بين نافذتين مضاعفاً للمعامل. أيضاً، اختيار معامل داخل نطاق الأعداد الصحيحة (مثل 10^9+7 أو 10^9+9) يمنع الفيضان في اللغات التي تستخدم أعداداً صحيحة 32 بت (حيث أن القيم قبل المعامل قد تتجاوز 2^31). في لغات مثل C++ مع 64 بت، يمكن استخدام معامل 2^64 (أي ترك الفيضان يحدث بشكل طبيعي) أو استخدام أعداد أولية أكبر مثل 2^61-1. - قاعدة عامة: استخدام base=91138233 و mod=97266353 (أعداد أولية عشوائية) أو استخدام زوج من الأعداد الأولية لتجزئة مزدوجة (Double Hashing) للتقليل من التصادمات إلى حد صفر تقريباً. - مثال عملي: إذا كنت تتعامل مع نصوص صغيرة (مثل أسماء)، يمكن استخدام base=256 (أساس البايتات) و mod=1000003. لكن للأحرف الأكبر (يونيكود)، استخدم base=65536 (BMP). - أيضاً، من المهم مراعاة أن المعامل لا يجب أن يكون أصغر من حجم الأبجدية أو الأساس، وإلا سيكون هناك فقدان للمعلومات. باختيار مناسب، تكون احتمالية التصادم صغيرة جداً (أقل من 1/M) لكل زوج من النوافذ، ومع ملايين النوافذ لا يزال الاحتمال مقبولاً.

على الرغم من أن خوارزمية رابين-كارب تُعرف أساساً بالبحث عن الأنماط في النصوص، إلا أن فكرة التجزئة المتداولة لها تطبيقات واسعة في مجالات متعددة: 1. كشف السرقة الأدبية (Plagiarism Detection): حيث يتم تجزئة جمل أو فقرات النص إلى قيم تجزئة، ومقارنتها مع قواعد بيانات ضخمة. التجزئة المتداولة تسمح بالمسح السريع عبر المستندات. 2. خوارزميات ضغط البيانات (Data Compression): مثل خوارزمية LZ77 وتفرعاتها، حيث تستخدم التجزئة المتداولة للبحث عن أطول تطابق في النافذة المنزلقة. 3. مكافحة الفيروسات وتحديد الملفات المتطابقة: يتم حساب تجزئات لجزء من الملفات (مثل 4 كيلوبايت الأولى) ومقارنتها بقاعدة بيانات تواقيع الفيروسات. التجزئة المتداولة تسمح بمسح الملفات المتدفقة. 4. معالجة الصور والفيديو: يمكن تطبيق فكرة التجزئة على أجزاء من الصورة (مثل كتل بكسل) لاكتشاف المناطق المكررة أو المقارنة بين الإطارات. 5. قواعد البيانات: يستخدم في خوارزميات التقسيم (Sharding) لتحديد أي سيرفر يخزن جزءاً من البيانات، عن طريق تجزئة المفاتيح. 6. نظم الملفات: تستخدم لتحديد الأجزاء الفريدة من الملفات (Deduplication) حيث يحسب تجزئة لكل كتلة ويخزن نسخة واحدة فقط. 7. خوارزميات التشفير: بعض دوال التجزئة مثل GHash المستخدمة في GCM (Galois/Counter Mode) تعتمد على عمليات مشابهة. القوة الأساسية هي القدرة على تحديث قيمة التجزئة في وقت ثابت أثناء تحريك نافذة، مما يجعل التطبيقات التي تتطلب مسحاً مستمراً فعالة جداً.

التجزئة المتداولة (Rolling Hash) ودوال التجزئة التقليدية (مثل MD5, SHA-1, SHA-256) تختلف في التصميم والغرض: - **التجزئة المتداولة**: هي دالة تجزئة مصممة خصيصاً للتحديث السريع عند إزالة حرف من البداية وإضافة حرف في النهاية (نافذة منزلقة). تعتمد على الحسابات الحسابية (الضرب والجمع والمعامل) وليست مقاومة للتصادمات بقوة. تُستخدم أساساً في مطابقة الأنماط والبحث. يمكن عكسها نظرياً بسهولة لأنها خطية. - **دوال التجزئة التقليدية**: مثل SHA-2، صممت لتكون أحادية الاتجاه (One-way) ومقاومة للتصادمات بدرجة عالية جداً. لا يمكن تحديثها بسهولة عند تغيير جزء صغير من الإدخال (تأثير الانهيار الجليدي). تستخدم في التشفير والتوقيعات الرقمية والتحقق من سلامة البيانات. - من حيث الأداء: التجزئة المتداولة أسرع بكثير للتحديثات المتكررة (O(1) لكل خطوة) مقارنة بإعادة حساب التجزئة التقليدية من الصفر (O(n) لكل نافذة). لذلك، في خوارزميات مثل رابين-كارب، لا يمكن استخدام SHA-256 لأنها ستكون بطيئة جداً. - من حيث الأمان: التجزئة التقليدية مقاومة للتصادمات بشكل كبير (SHA-256 يتطلب حوالي 2^128 عملية لإيجاد تصادم)، بينما التجزئة المتداولة مع معامل 10^9+7 قد تصطدم مع حوالي 10^5 نافذة وفقاً لمفارقة عيد الميلاد (Birthday Paradox). لذا لا تصلح للتطبيقات الأمنية. - خلاصة: لكل نوع استخداماته: التجزئة المتداولة للسرعة في البيئات الديناميكية، والتقليدية للأمان والثبات.

تجزئة رابين-كارب المتداولة

أدخل القيم

خطوات الاستخدام

أمثلة محلولة

أمثلة محسوبة

الأسئلة الشائعة

أدخل القيم

خطوات الاستخدام

حاسبات ذات صلة

1احسب قيمة التجزئة المتداولة للنص "Hello" باستخدام base=31 و mod=1000000007.

2احسب التجزئة المتداولة للنص "ABC" (بالحروف الكبيرة) باستخدام base=256 و mod=10^9+7، ثم احسب تحديث النافذة إلى "BCD".

أمثلة محسوبة

الأسئلة الشائعة