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

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

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

بسبب درجة استقلالها العالية، يمكن استخدام التجزئة الجدولية مع طرق التجزئة التي تتطلب دالة تجزئة عالية الجودة، بما في ذلك تجزئة الحجلة ، وتجزئة الوقواق ، وتقنية MinHash لتقدير حجم تقاطعات المجموعات.

الفكرة الأساسية هي كالتالي:

أولًا، قسّم المفتاح المراد تشفيره إلى "كتل" أصغر ذات طول محدد. ثم، أنشئ مجموعة من جداول البحث ، جدول لكل كتلة، واملأها بقيم عشوائية. أخيرًا، استخدم الجداول لحساب قيمة تجزئة لكل كتلة، واجمع كل هذه التجزئات في قيمة تجزئة نهائية باستخدام عملية "أو" الحصرية الثنائية . ^{[ 1 ]}

بصورة أكثر رسمية:

لنفترض أن p هو عدد البتات في المفتاح المراد تجزئته، و q هو عدد البتات المطلوبة في دالة التجزئة الناتجة. اختر حجم كتلة r ≤ p ؛ يتحكم اختيار حجم الكتلة في المفاضلة بين الوقت واستهلاك الذاكرة، لذا يجب أن يكون حجم الجداول مناسبًا بحيث لا تكون كبيرة جدًا، على سبيل المثال، بحيث تتناسب مع ذاكرة التخزين المؤقت للحاسوب . ^{[ 2 ]} تستخدم الكتل الأصغر ذاكرة أقل ولكنها تبطئ دالة التجزئة. احسب t = ceil( p / r )، وهو عدد الكتل المكونة من r بت اللازمة لتمثيل مفتاح.

أنشئ مصفوفة ثنائية الأبعاد بحجم 2r ^× t ، ولنسمها T ، واملأها بأرقام عشوائية مكونة من q بت. الآن، يمكن استخدام T لحساب قيمة التجزئة h ( x ) لأي مفتاح x مُعطى . وللقيام بذلك، قسّم x إلى قيم مكونة من r بت، حيث x₀ تتكون من أقل r بت من x ، _و x₁ تتكون من r بت التالية ، وهكذا. على سبيل المثال، إذا كان r = 8، فإن _xᵢ هو البايت رقم i _من x . ثم، استخدم قيم r بت والموقع هذه كمؤشرات في T ، واجمع النتائج باستخدام عملية XOR: ^{[ 1 ]}   

h ( x ) = T [0][ x ₀ ] ⊕ T [1][ x ₁ ] ⊕ T [2][ x ₂ ] ⊕ ... ⊕ T [t-1][ x _t-1 ].

لاحظ أنه ليس من الصحيح استخدام نفس الجدول (على سبيل المثال T[0] ) لكل x _i ، لأنه بعد ذلك لن تتمكن دالة التجزئة من التمييز بين السلاسل التي لها نفس x _i ، ولكن تم تبديلها بشكل مختلف.

يُعطى أدناه رمز لمثال نموذجي مع r  = t = 8 و q = p = 64.       

// جدول سري للأرقام العشوائية uint64_t T [ 8 ][ 256 ]; for ( int i = 0 ; i < 8 ; i ++ ) for ( int j = 0 ; j < 256 ; j ++ ) T [ i ][ j ] = getRandomUInt64 ();// دالة التجزئة الجدولية البسيطة uint64_t hash ( uint64_t x ) { uint64_t res = 0 ; for ( int i = 0 ; i < 8 ; i ++ ) res ^= T [ i ][( char )( x >> 8 * i )]; return res ; }

أول مثال على التجزئة الجدولية هو تجزئة زوبريست ، وهي طريقة لتجزئة المواضع في ألعاب لوحية مجردة مثل الشطرنج، سُميت نسبةً إلى ألبرت ليندسي زوبريست الذي نشرها عام 1970. ^{[ 3 ]} في هذه الطريقة، يتم توليد سلسلة بتات عشوائية لكل ميزة من ميزات اللعبة، مثل مزيج قطعة شطرنج ومربع من رقعة الشطرنج. بعد ذلك، لتجزئة أي موضع في اللعبة، تُدمج سلاسل البتات الخاصة بميزات ذلك الموضع باستخدام عملية "أو" الحصرية الثنائية. يمكن استخدام قيمة التجزئة الناتجة كمؤشر في جدول التبديل . ولأن كل حركة عادةً ما تُغير عددًا قليلًا فقط من ميزات اللعبة، يمكن تحديث قيمة زوبريست للموضع بعد الحركة بسرعة من قيمة الموضع قبل الحركة، دون الحاجة إلى المرور على جميع ميزات الموضع. ^{[ 4 ]}

تم إعادة اكتشاف التجزئة الجدولية بشكل عام، للقيم الثنائية التعسفية، لاحقًا بواسطة كارتر وويغمان (1979) ودُرست بمزيد من التفصيل بواسطة باتراسكو وثورب (2012) .

عرّف كارتر وويغمان (1979) مخططًا عشوائيًا لتوليد دوال التجزئة بأنه شامل إذا كان احتمال تصادم أي مفتاحين (أي تعيينهما إلى نفس القيمة) يساوي 1/ m ، حيث m هو عدد القيم التي يمكن أن يأخذها المفتاحان. وفي ورقة بحثية لاحقة ( ويغمان وكارتر ، 1981) ، عرّفا خاصية أقوى : المخطط العشوائي لتوليد دوال التجزئة هو مستقل من الدرجة k إذا كان احتمال تعيين كل زوج من المفاتيح (k - tuple ) وكل زوج ممكن من القيم (k -tuple) يساوي 1/ mk . مخططات التجزئة المستقلة من ^الدرجة 2 شاملة تلقائيًا، ويمكن تحويل أي مخطط تجزئة شامل إلى مخطط مستقل من الدرجة 2 عن طريق تخزين عدد عشوائي x كجزء من مرحلة تهيئة الخوارزمية وإضافة x إلى كل قيمة تجزئة. وبالتالي، فإن الشمولية هي في جوهرها نفس الاستقلال من الدرجة 2. ومع ذلك، فإن استقلال k بالنسبة للقيم الأكبر من k هو خاصية أقوى، ويتم الاحتفاظ بها بواسطة عدد أقل من خوارزميات التجزئة.

كما لاحظ باتراشكو وثورب (2012) ، فإن التجزئة الجدولية مستقلة من الدرجة الثالثة ولكنها ليست مستقلة من الدرجة الرابعة. بالنسبة لأي مفتاح مفرد _x ، فإن احتمالية أن تأخذ T [ x0,0 ] أي قيمة تجزئة _{متساوية ، ولا يؤثر تطبيق عملية "أو الحصرية" على} T [ x0,0 ] مع قيم الجدول المتبقية على هذه الخاصية. بالنسبة لأي مفتاحين x و y ، فإن احتمالية أن يُربط x بأي قيمة تجزئة متساوية كما في السابق ، ويوجد على الأقل موضع واحد i حيث xᵢ ≠ yᵢ ؛ تُستخدم قيمة الجدول _{T [} yᵢ,ᵢ] في حساب h ( y ) _ولكن ليس في حساب h ( x ) ، لذا حتى بعد تحديد قيمة h ( x )، فإن احتمالية أن تكون h ( y ) أي قيمة تجزئة صالحة متساوية. وبالمثل، بالنسبة لأي ثلاثة مفاتيح x و y و z ، _فإن أحد المفاتيح الثلاثة على الأقل له موضع i حيث تختلف قيمته zi عن المفتاحين الآخرين، بحيث حتى بعد تحديد قيم h ( x ) و h ( y )، فإن احتمال أن تكون h ( z ) أي قيمة تجزئة صالحة متساوٍ. ^{[ 5 ]}  

مع ذلك، ينهار هذا المنطق في حالة أربعة مفاتيح، لوجود مجموعات من المفاتيح w و x و y و z حيث لا يمتلك أي منها قيمة بايت لا يشترك فيها مع مفتاح واحد على الأقل من المفاتيح الأخرى. على سبيل المثال، إذا كان لكل مفتاح بايتان، وكانت w و x و y و z هي المفاتيح الأربعة التي تكون قيم بايتاتها إما صفرًا أو واحدًا، فإن كل قيمة بايت في كل موضع تشترك فيها مفاتيحان فقط من المفاتيح الأربعة. بالنسبة لهذه المفاتيح الأربعة، فإن قيم التجزئة المحسوبة بواسطة تجزئة الجدولة ستُحقق دائمًا المعادلة h ( w ) ⊕ h ( x ) ⊕ h ( y ) ⊕ h ( z ) = 0 ، بينما في نظام تجزئة مستقل رباعيًا، لن تتحقق المعادلة نفسها إلا باحتمالية 1/ m . لذلك، فإن تجزئة الجدولة ليست مستقلة رباعيًا. ^{[ 5 ]}

نظرًا لأن التجزئة الجدولية هي خوارزمية تجزئة شاملة، يمكن استخدامها في أي خوارزمية تجزئة تتطلب الشمولية. على سبيل المثال، في تسلسل التجزئة ، يتناسب الوقت المتوقع لكل عملية طرديًا مع مجموع احتمالات التصادم، وهو نفس ما ينطبق على أي خوارزمية شاملة كما هو الحال مع دوال التجزئة العشوائية تمامًا، ويكون ثابتًا عندما يكون عامل تحميل جدول التجزئة ثابتًا. لذلك، يمكن استخدام التجزئة الجدولية لحساب دوال التجزئة لتسلسل التجزئة مع ضمان نظري لثبات الوقت المتوقع لكل عملية. ^{[ 6 ]}

مع ذلك، لا يُعدّ التجزئة الشاملة كافيًا لضمان أداء بعض خوارزميات التجزئة الأخرى. فعلى سبيل المثال، في حالة الاستكشاف الخطي ، تُعدّ دوال التجزئة المستقلة من الدرجة 5 كافية لضمان التشغيل في زمن ثابت، بينما تفشل دوال التجزئة المستقلة من الدرجة 4 في ذلك. ^{[ 7 ]} ومع ذلك، وعلى الرغم من أن تجزئة الجدولة مستقلة من الدرجة 3 فقط، إلا أنها توفر نفس ضمان التشغيل في زمن ثابت للاستكشاف الخطي. ^{[ 8 ]}

تضمن تجزئة الوقواق ، وهي تقنية أخرى لتنفيذ جداول التجزئة ، زمنًا ثابتًا لكل عملية بحث (بغض النظر عن دالة التجزئة). قد تفشل عمليات الإدخال في جدول تجزئة الوقواق، مما يستدعي إعادة بناء الجدول بالكامل، ولكن احتمالية حدوث مثل هذه الإخفاقات ضئيلة بما يكفي لضمان ثبات الزمن المتوقع لكل عملية إدخال (باستخدام دالة تجزئة عشوائية تمامًا أو دالة تجزئة ذات استقلال لوغاريتمي). من ناحية أخرى، في تجزئة الجدولة، يكون أفضل حد معروف لاحتمالية الفشل أعلى، لدرجة أنه لا يمكن ضمان ثبات الزمن المتوقع لعمليات الإدخال. ومع ذلك، تُعد تجزئة الجدولة كافية لضمان بناء جدول تجزئة الوقواق بزمن متوقع خطي لمجموعة ثابتة من المفاتيح لا تتغير أثناء استخدام الجدول. ^{[ 8 ]}

على الرغم من أن التجزئة الجدولية الموصوفة أعلاه ("التجزئة الجدولية البسيطة") مستقلة من الدرجة الثالثة فقط، إلا أنه يمكن استخدام تنويعات لهذه الطريقة للحصول على دوال تجزئة بدرجات استقلال أعلى بكثير. يستخدم سيجل (2004) الفكرة نفسها المتمثلة في استخدام عمليات "أو" الحصرية لدمج قيم عشوائية من جدول، مع خوارزمية أكثر تعقيدًا تعتمد على رسوم بيانية موسّعة لتحويل بتات المفتاح إلى مؤشرات جدول، وذلك لتعريف مخططات تجزئة مستقلة من الدرجة k لأي قيمة ثابتة أو حتى لوغاريتمية لـ k . مع ذلك، فإن عدد عمليات البحث في الجدول اللازمة لحساب كل قيمة تجزئة باستخدام تنويع سيجل للتجزئة الجدولية، على الرغم من ثباته، لا يزال كبيرًا جدًا ليكون عمليًا، كما أن استخدام الموسّعات في تقنية سيجل يجعلها غير فعّالة تمامًا. يقدم ثورب (2013) مخططًا يعتمد على التجزئة الجدولية يصل إلى درجات استقلال عالية بسرعة أكبر، وبطريقة أكثر فعالية. ويلاحظ أن استخدام جولة واحدة من التجزئة الجدولية البسيطة لتوسيع مفاتيح الإدخال إلى ستة أضعاف طولها الأصلي، ثم جولة ثانية من التجزئة الجدولية البسيطة على المفاتيح الموسعة، ينتج عنه مخطط تجزئة يكون عدد استقلاله أسيًا في المعلمة r ، وهو عدد البتات لكل كتلة في تقسيم المفاتيح إلى كتل.

يقتصر التجزئة الجدولية البسيطة على المفاتيح ذات الطول الثابت، نظرًا للحاجة إلى تهيئة جدول مختلف من القيم العشوائية لكل موضع من مواضع الكتل في المفاتيح. درس ليمير (2012) تنويعات التجزئة الجدولية المناسبة للمفاتيح ذات الأطوال المتغيرة، مثل سلاسل الأحرف. يستخدم النوع العام من مخطط التجزئة الذي درسه ليمير جدولًا واحدًا T مُفهرسًا بقيمة الكتلة، بغض النظر عن موضعها داخل المفتاح. مع ذلك، يمكن دمج القيم من هذا الجدول باستخدام دالة أكثر تعقيدًا من عملية XOR الثنائية. يُبين ليمير أنه لا يمكن لأي مخطط من هذا النوع أن يكون مستقلًا من الدرجة 3. ومع ذلك، يُبين أنه لا يزال من الممكن تحقيق الاستقلال من الدرجة 2. على وجه الخصوص، يُعطي مخطط التجزئة الجدولية الذي يُفسر القيم T [ xi ] (حيث _xi هي ، كما _في السابق، الكتلة رقم i من المدخلات) كمعاملات لكثير حدود على حقل منتهٍ ، ثم يأخذ باقي كثير الحدود الناتج بتردد كثير حدود آخر، دالة تجزئة مستقلة من الدرجة 2.

int D = 2 ; uint128_t T1 [ 8 ][ 256 ]; uint64_t T2 [ D ][ 256 ];// املأ الجداول بقيم عشوائية for ( int j = 0 ; j < 256 ; j ++ ) { for ( int i = 0 ; i < 8 ; i ++ ) T1 [ i ][ j ] = getRandomUInt128 (); for ( int i = 0 ; i < D ; i ++ ) T2 [ i ][ j ] = getRandomUInt64 (); }// حساب جدولة مختلطة لـ x مع D من الأحرف المشتقة uint64_t hash ( uint64_t x ) { uint128_t v1v2 = 0 ; for ( int i = 0 ; i < 8 ; i ++ ) v1v2 ^= T1 [ i ][( char )( x >> 8 * i )]; uint64_t v1 = v1v2 >> 64 ; // أخذ v1 من البتات المنخفضة uint64_t h = ( uint64_t ) v1v2 ; // أخذ v2 من البتات العالية for ( int i = 0 ; i < D ; i ++ ) h ^= T2 [ i ][( char )( v1 >> 8 * i )]; return h ; }

مصادر ثانوية

• مورين، بات (22 فبراير 2014)، "القسم 5.2.3: تجزئة الجدولة"، هياكل البيانات المفتوحة (بالشفرة الزائفة) (إصدار 0.1 جيجابايت بيتا  )، الصفحات 115-116 ، تاريخ الاسترجاع 2016-01-08 .
• ميتزنماخر، مايكل ؛ أوبفال، إيلي (2014)، "بعض الخوارزميات العشوائية العملية وهياكل البيانات"، في تاكر، ألين؛ غونزاليس، تيوفيلو ؛ دياز-هيريرا، خورخي (محررون)، دليل الحوسبة: علوم الحاسوب وهندسة البرمجيات (الطبعة الثالثة  )، مطبعة سي آر سي، الصفحات 11-1 – 11-23، رقم ISBN 9781439898529انظر على وجه الخصوص القسم 11.1.1: تجزئة الجدولة، الصفحات 11-3 – 11-4 .

المصادر الأولية