جداول التقطيع

من ويكي الهندسة المعلوماتية
اذهب إلى: تصفح، ابحث
نموذج مصغر لعملية التقطيع

يستعمل التقطيع لتخزين كمية كبيرة نسبياً من المعطيات في جدول يسمى جدول التقطيع، ويعرّف إمكانية تنفيذ العمليات الأساسية الثلاث التالية فقط على المعطيات ضمن جدول التقطيع:
الإدخال insert، والبحث search، والحذف delete.

مقدمة

تكمن الحاجة للتقطيع في أننا نحتاج إلى أن نقوم بالعمليات السابقة في زمن من رتبة O(1)، وبالحقيقة ذلك ممكن عن طريق العنونة المباشرة direct addressing، عند استخدام جدول عبارة عن بنية معطيات توفر الوصول العشوائي كالمصفوفة. ووجود رقم مميز key لكل عنصر يراد تخزينه، عندها يستخدم هذا الرقم في تحديد مكان حفظ العنصر في المصفوفة،ويكون هذا الحل ممتازاً عندما يكون عدد المعطيات التي يراد تخزينها صغيراً ولكن يمكن أن يكون مجال اختيار الأرقام كبيراً جداً (نسميه universe رمزه U) مما سيدفعنا لاختيار حجم كبير جداً للمصفوفة وهدر مساحة كبيرة، ولتفادي ذلك نلجأ إلى التقطيع ونستخدم ما يسمى بتابع التقطيع.

مثال: تخزين ذاتيات 200 طالب تتوزع أرقامهم التسلسلية (ID) بين 0 و 2000،(إذا فرضنا أننا نريد تسجيل الأرقام التسلسلية للطلاب الذين اختاروا قسماً معيناً في كلية معينة) في هذه الحالة لدينا مجال اختيار الأرقام [0,2000] لكن عددها 200 فإذا أردنا استخدام العنونة المباشرة في هذه الحالة (أي استخدام رقم الطالب كدليل للمصفوفة index) فسنحتاج إلى مصفوفة مكونة من 2000 خانة، ولكن سيكون هناك 1800 خانة فارغة ضمنها، ولذلك نلجأ إلى عملية التقطيع hashing فنقوم بإيجاد دليل المصفوفة بتطبيق تابع التقطيع على رقم الطالب وعندها يمكن أن نخزن الأرقام في جدول صغير نسبياً (200 أو 300 خانة مثلاً،حيث يكون متناسباً مع عدد المفاتيح المخزنة فعلاً وليس مع عدد عناصر فضاء المفاتيح U).

نعرف عامل التحميل load factor بأنه نسبة المعطيات المخزنة في الجدول إلى طول جدول التقطيع a = n/m . في مثالنا السابق:

n=200 و m في الحالة الأولى 2000.

فيكون عامل التحميل:

a = n/m = 0.1 أي نستخدم عشر الجدول فقط.

أما في الحالة الثانية وباختيار حجم المصفوفة 300.

a = n/m = 200/300 = 2/3 أي تكون فقط ثلث مساحة الجدول مهدورة عوضاً عن تسعة أعشار.

تابع التقطيع Hash function

تابع التقطيع هو تابع رياضي h يكون دخله مفتاح العنصر المراد إضافته إلى جدول التقطيع ،key وخرجه رقم المدخل المناسب في جدول التقطيع. ويستخدم في العمليات الثلاث (البحث، والإضافة، والحذف).

ويفضل أن يتصف تابع التقطيع بالصفات التالية:

  1. أن يكون بسيطاً وسريع الحساب، مثال: باقي قسمة المفتاح على TableSize-1 (حيث TableSize هو طول المصفوفة).
  2. أن يقوم بتوزيع المفاتيح بالتساوي على مداخل جدول التقطيع، لتجنب التصادم قدر الإمكان.
  3. يفضل أن يكون لأي مفتاحين مختلفين خليتان مختلفتان في المصفوفة (هذا ليس صحيحاً بصورة عامة لأن المفاتيح تختار عشوائياً أما مساحة التخزين محدودة).

تابع القسمة

إذا كان عدد خلايا جدول التقطيع هو m، فإننا نحصل على مدخل المفتاح k، من خلال باقي قسمته على عدد مداخل جدول التقطيع m، أي:

عند استخدام هذا التابع يجب تجنب استعمال قيم معينة لـ m، مثل 2^p.

الخيار الأفضل لعدد مداخل الجدول هو عدد أولي بعيد نسبياً عن أي قوة صحيحة للعدد 2.

تابع الضرب

Hashmultiplication.PNG

توجد خطوتان، الخطوة الأولى هي ضرب المفتاح نص مائلk بعدد ثابت A ينتمي إلى المجال [0,1]، واستخراج الجزء الكسري من العدد kA. وبعبارة أخرى فإن تابع التقطيع هو:

حيث kA mod 1 تعني الجزء الكسري من kA.

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

ظاهرة التصادم collision

ينتج التصادم عن سببين:

  1. أن عدد العناصر التي نريد وضع مفاتيحها في الجدول غالباً ما يكون أكبر من عدد خلايا الجدول.
  2. عند تطبيق تابع التقطيع على مجموعة من المفاتيح يمكن أن ينتج خرجين متساويين (أي يشيران إلى نفس الخانة في الجدول).

مثال: إذا كان طول المصفوفة لدينا هو 10 واستخدمنا تابع التقطيع: key mod 10 وكان لدينا الفتاحين 16 و 36 فسينج لدينا الخلية 6 أي الخلية السادسة للمفتاحين :وهذا ما يسمى بالتصادم، وسنرى طريقتين لحل هذه المشكلة.


حل التصادم

السلاسل المنفصلة separate chaining

Separatechaining.PNG

عند استخدام هذه الطريقة يتم حل مشكلة التصادم عن طريق حفظ القيم المتصادمة في سلسلة مترابطة، أي تكون خانة المصفوفة (التي هي جدول التقطيع) تحوي على مؤشر يأشر إلى سلسلة مترابطة، وإذا كانت الخانة خالية يكون المؤشر يشير إلى nil.

عند استخدام هذه الطريقة يجب اختيار تابع تقطيع منتظم قدر الإمكان فكلما قل انتظام تابع التقطيع زاد طول السلاسل المترابطة، وفي أسوأ الأحوال يمكن أن يقوم تابع التقطيع بفرز جميع المفاتيح إلى خانة واحدة فيتحول البحث في جدول التقطيع إلى البحث في سلسلة مترابطة بزمن قدره O(n).

يعبر عامل التحميل عن القيمة الوسطية لطول السلسلة.

من السهل تطبيق عمليات القاموس على جدول التقطيع عند استخدام السلاسل لحل التصادم:
الإدراج:
عدد منتهي من التعليمات:أدرج العنصر x في رأس السلسة المترابطة T[h(k)].
البحث:
ابحث عن العنصر ذي المفتاح k في السلسلة المترابطةT[h(k)].
الحذف:
احذف العنصر x من السلسلة المترابطةT[h(x.key)].<rb /> تتم عملية الإدراج في زمن O(1) وذلك لأنها تتطلب عدداً ثابتاً من العمليات حيث يتم إدارج العنصر في رأس السلسلة المترابطة.
ويتم حذف العنصر x أيضاً في زمن O(1) وذلك في حالة استخدام سلسلة مترابطة من الجهتين doubly linked list حيث في الحالة الأولى (عند الإدارج) نعطي تابع الإدراج مفتاح العنصر فيقوم بتطبيق تابع التقطيع عليه وإضافته في الجدول بمكانه المناسب في رأس السلسلة المترابطة سواء كانت أحادية الترابطة أو مزدوجة الترابط أما في حالة الحذف إذا كانت السلسلة أحادية الترابط فسنحتاج إلى البحث عن العنصر لذلك نستخدم سلسلة مزدوجة الترابط ونعطي تابع الحذف العنصر كاملاً (يمكن أن نعطيه مرجع reference للعنصر مثلاً) فيقوم التابع بحذف العنصر دون معرفة مكانه في الجدول وذلك عن طريق ربط العنصر السابق له في السلسلة بالعنصر اللاحق.

طريقة العنونة المفتوحة open addressing

في العنونة المفتوحة توجد جميع العناصر داخل جدول التقطيع.

ميزة العنونة المفتوحة أنها تتجنب استخدام المؤشرات على الإطلاق ولا تحتاج إلى مساحة تخزين إضافية بل تستخدم الفراغات الموجودة في جدول التقيطع. فبدلاً من تتبع المؤشرات، نقوم بحساب سلسلة من المداخل التي يجب أن نفحصها.

للقيام بعملية الإدخال، نقوم بعملية فحص متتابع، أو سبر probing، خلال جدول التقطيع حتى العثور على مدخل فارغ.

استراتيجيات إيجاد المدخل فارغ:

السبر الخطي

يستخدم تابع تقطيع من الشكل:

السبر التربيعي

يستخدم تابع تقطيع من الشكل:

تابع التقطيع المزدوج

يستخدم تابع تقطيع من الشكل: