README.ar-AR.md

التجزئة الدوارة متعددة الحدود

دالة التجزئة

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

التطبيق الأساسي للتجزئة هو الاختبار الفعال لتساوي المفاتيح من خلال مقارنة بصماتها.

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

التجزئة الدوارة

التجزئة الدوارة (تُعرف أيضًا باسم التجزئة التكرارية أو المجموع الاختباري الدوار) هي دالة تجزئة حيث يتم تجزئة المدخلات في نافذة تتحرك عبر المدخلات.

تسمح بعض دوال التجزئة بحساب التجزئة الدوارة بسرعة كبيرة - يتم حساب قيمة التجزئة الجديدة بسرعة بناءً على البيانات التالية فقط:

• قيمة التجزئة القديمة،
• القيمة القديمة المزالة من النافذة،
• والقيمة الجديدة المضافة إلى النافذة.

تجزئة السلاسل متعددة الحدود

يجب أن تعتمد دالة التجزئة المثالية للسلاسل بشكل واضح على كل من مجموعة الرموز الموجودة في المفتاح وعلى ترتيب الرموز. العائلة الأكثر شيوعًا لمثل هذه الدوال التجزئة تعامل رموز السلسلة كمعاملات متعددة حدود مع متغير صحيح p وتحسب قيمته بالنسبة لثابت صحيح M:

غالبًا ما يتم شرح خوارزمية البحث عن السلاسل Rabin-Karp باستخدام دالة تجزئة دوارة بسيطة جدًا تستخدم فقط عمليات الضرب والإضافة - التجزئة الدوارة متعددة الحدود:

H(s₀, s₁, ..., s_k) = s₀ _ p^k-1 + s₁ _ p^k-2 + ... + s_k * p⁰

حيث p هو ثابت، و (s₁، ... ، s_k) هي أحرف الإدخال.

على سبيل المثال، يمكننا تحويل السلاسل القصيرة إلى أرقام مفاتيح عن طريق ضرب رموز الأرقام في قوى ثابتة. يمكن تحويل الكلمة المكونة من ثلاثة أحرف ace إلى رقم عن طريق حساب:

key = 1 _ 26² + 3 _ 26¹ + 5 * 26⁰

لتجنب التعامل مع قيم H ضخمة، يتم إجراء جميع العمليات الحسابية بالنسبة لـ M.

H(s₀, s₁, ..., s_k) = (s₀ _ p^k-1 + s₁ _ p^k-2 + ... + s_k * p⁰) mod M

الاختيار الدقيق للمعلمات M، p مهم للحصول على خصائص "جيدة" لدالة التجزئة، أي معدل تصادم منخفض.

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

function hash(key, arraySize) {
  const base = 13

  let hash = 0
  for (let charIndex = 0; charIndex < key.length; charIndex += 1) {
    const charCode = key.charCodeAt(charIndex)
    hash += charCode * base ** (key.length - charIndex - 1)
  }

  return hash % arraySize
}

طريقة hash() ليست فعالة كما يمكن أن تكون. بخلاف تحويل الأحرف، هناك عمليتا ضرب وإضافة داخل الحلقة. يمكننا إزالة عملية ضرب واحدة باستخدام طريقة هورنر:

a₄ _ x⁴ + a₃ _ x³ + a₂ _ x² + a₁ _ x¹ + a₀ = (((a₄ _ x + a₃) _ x + a₂) _ x + a₁) _ x + a₀

بعبارة أخرى:

H_i = (P * H_i-1 + S_i) mod M

لا يمكن لـ hash() التعامل مع السلاسل الطويلة لأن hashVal تتجاوز حجم int. لاحظ أن المفتاح ينتهي دائمًا بأن يكون أقل من حجم المصفوفة. في طريقة هورنر يمكننا تطبيق عامل التشغيل modulo (٪) في كل خطوة من الحساب. هذا يعطي نفس النتيجة كتطبيق عامل التشغيل modulo مرة واحدة في النهاية، ولكنه يتجنب التجاوز.

function hash(key, arraySize) {
  const base = 13

  let hash = 0
  for (let charIndex = 0; charIndex < key.length; charIndex += 1) {
    const charCode = key.charCodeAt(charIndex)
    hash = (hash * base + charCode) % arraySize
  }

  return hash
}

التجزئة متعددة الحدود لها خاصية دوارة: يمكن تحديث البصمات بكفاءة عند إضافة الرموز أو إزالتها من نهايات السلسلة (بشرط تخزين مصفوفة من قوى p بالنسبة لـ M بطول كافٍ). تعتمد خوارزمية مطابقة النمط Rabin-Karp الشائعة على هذه الخاصية

المراجع

• أين تُستخدم دالة التجزئة للسلاسل النصية متعددة الحدود
• التجزئة على موقع جامعة تكساس
• دالة التجزئة على ويكيبيديا
• التجزئة المتدحرجة على ويكيبيديا