التجزئة الشاملة

يتناول هذا القسم حالة تجزئة الأعداد الصحيحة التي تتناسب مع عدد الكلمات في الآلة؛ وبالتالي، فإن عمليات مثل الضرب والجمع والقسمة، وما إلى ذلك، هي تعليمات رخيصة على مستوى الآلة. لنفترض أن الكون المراد تجزئته هو${\displaystyle \{0,\dots ,|U|-1\}}$وليكن مدى دوال التجزئة هو${\displaystyle {0,\ldots ,n-1}}$.

كان الاقتراح الأصلي لكارتر وويغمان ^{[ 1 ]} هو اختيار عدد أولي${\displaystyle p\geq |U|}$وحدد

${\displaystyle h_{a,b}(x)=((ax+b)~{\bmod {~}}p)~{\bmod {~}}n}$

أين${\displaystyle a,b}$هي أعداد صحيحة مختارة عشوائياً بتردد${\displaystyle p}$مع${\displaystyle a\neq 0}$(هذه دورة واحدة من مولد التوافق الخطي .)

لرؤية ذلك${\displaystyle H=\{h_{a,b}\}}$هي عائلة عالمية، لاحظ أن${\displaystyle h(x)=h(y)}$لا ينطبق إلا عندما

${\displaystyle ax+b\equiv ay+b+i\cdot m{\pmod {p}}}$

لبعض الأعداد الصحيحة${\displaystyle i}$بين${\displaystyle 0}$و${\displaystyle (p-1)/m}$. منذ${\displaystyle p\geq |U|}$، لو${\displaystyle x\neq y}$اختلافهم${\displaystyle x-y}$هو عدد غير صفري وله مقلوب باقي القسمة${\displaystyle p}$حل المعادلة لـ${\displaystyle a}$العائد

${\displaystyle a\equiv i\cdot m\cdot (x-y)^{-1}{\pmod {p}}}$.

هناك${\displaystyle p-1}$الخيارات الممكنة لـ${\displaystyle a}$(منذ${\displaystyle a=0}$(باستثناء) و، متفاوتة${\displaystyle i}$ضمن النطاق المسموح به،${\displaystyle \lfloor (p-1)/m\rfloor }$القيم غير الصفرية المحتملة للجانب الأيمن. وبالتالي، فإن احتمال التصادم هو

${\displaystyle \lfloor (p-1)/m\rfloor /(p-1)\leq ((p-1)/m)/(p-1)=1/m}$.

طريقة أخرى للنظر${\displaystyle H}$تُعرَّف العائلة العالمية من خلال مفهوم المسافة الإحصائية . اكتب الفرق${\displaystyle h(x)-h(y)}$مثل

${\displaystyle h(x)-h(y)\equiv (a(x-y)~{\bmod {~}}p){\pmod {m}}}$.

منذ${\displaystyle x-y}$غير صفري و${\displaystyle a}$موزعة بشكل منتظم في${\displaystyle \{1,\dots ,p-1\}}$وبناءً على ذلك${\displaystyle a(x-y)}$modulo${\displaystyle p}$كما أنه موزع بشكل منتظم في${\displaystyle \{1,\dots ,p-1\}}$توزيع${\displaystyle (h(x)-h(y))~{\bmod {~}}m}$وبالتالي، يكون الأمر شبه منتظم، حتى مع وجود اختلاف في احتمالية${\displaystyle \pm 1/p}$بين العينات. ونتيجة لذلك، فإن المسافة الإحصائية إلى عائلة متجانسة هي${\displaystyle O(m/p)}$، وهو ما يصبح ضئيلاً عندما${\displaystyle p\gg m}$.

عائلة دوال التجزئة الأبسط

${\displaystyle h_{a}(x)=(ax~{\bmod {~}}p)~{\bmod {~}}m}$

هو عالمي تقريبًا فقط:${\displaystyle \Pr\{h_{a}(x)=h_{a}(y)\}\leq 2/m}$للجميع${\displaystyle x\neq y}$^{[ 1 ]} علاوة على ذلك ، فإن هذا التحليل دقيق للغاية؛ فقد أظهر كارتر وويغمان ^{[ 1 ]} أن${\displaystyle \Pr\{h_{a}(1)=h_{a}(m+1)\}\geq 2/(m+1)}$حينما${\displaystyle (p-1)~{\bmod {~}}m=1}$.

يتناول هذا القسم تجزئة متجه ثابت الطول من كلمات الآلة. فسر المدخلات كمتجه.${\displaystyle {\bar {x}}=(x_{0},\dots ,x_{k-1})}$ل${\displaystyle k}$كلمات الآلة (أعداد صحيحة من${\displaystyle w}$(بضعة أجزاء لكل منها). إذا${\displaystyle H}$هي عائلة شاملة ذات خاصية الفرق المنتظم، والعائلة التالية (التي يعود تاريخها إلى كارتر وويغمان ^{[ 1 ]} ) لديها أيضًا خاصية الفرق المنتظم (وبالتالي فهي شاملة):

${\displaystyle h({\bar {x}})=\left(\sum _{i=0}^{k-1}h_{i}(x_{i})\right)\,{\bmod {~}}m}$حيث كل${\displaystyle h_{i}\in H}$يتم اختيارها بشكل مستقل وعشوائي.

لو${\displaystyle m}$إذا كان أحد قوى العدد اثنين، فيمكن استبدال الجمع بعملية "أو الحصرية". ^{[ 11 ]}

عمليًا، إذا كانت العمليات الحسابية ذات الدقة المزدوجة متاحة، يتم استخدام عائلة دوال التجزئة ذات الإزاحة المضاعفة. ^{[ 12 ]} تهيئة دالة التجزئة بمتجه${\displaystyle {\bar {a}}=(a_{0},\dots ,a_{k-1})}$من الأعداد الفردية العشوائية على${\displaystyle 2w}$بتات لكل منها. ثم إذا كان عدد الخانات${\displaystyle m=2^{M}}$ل${\displaystyle M\leq w}$:

${\displaystyle h_{\bar {a}}({\bar {x}})=\left({\big (}\sum _{i=0}^{k-1}x_{i}\cdot a_{i}{\big )}~{\bmod {~}}2^{2w}\right)\,\,\mathrm {div} \,\,2^{2w-M}}$.

من الممكن تقليل عدد عمليات الضرب إلى النصف، وهو ما يُترجم عمليًا إلى زيادة السرعة بمقدار الضعف تقريبًا. ^{[ 11 ]} قم بتهيئة دالة التجزئة باستخدام متجه.${\displaystyle {\bar {a}}=(a_{0},\dots ,a_{k-1})}$من الأعداد الفردية العشوائية على${\displaystyle 2w}$كل بت. عائلة التجزئة التالية عالمية: ^{[ 13 ]}

${\displaystyle h_{\bar {a}}({\bar {x}})=\left({\Big (}\sum _{i=0}^{\lceil k/2\rceil }(x_{2i}+a_{2i})\cdot (x_{2i+1}+a_{2i+1}){\Big )}{\bmod {~}}2^{2w}\right)\,\,\mathrm {div} \,\,2^{2w-M}}$.

إذا لم تكن عمليات الدقة المزدوجة متاحة، فيمكن تفسير المدخلات على أنها متجه من أنصاف الكلمات (${\displaystyle w/2}$الأعداد الصحيحة ذات البتات). ثم ستستخدم الخوارزمية${\displaystyle \lceil k/2\rceil }$عمليات الضرب، حيث${\displaystyle k}$كان عدد أنصاف الكلمات في المتجه. وبالتالي، تعمل الخوارزمية بمعدل عملية ضرب واحدة لكل كلمة من المدخلات.

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

من الممكن أيضًا تحقيق شمولية قوية بسرعة عالية. ^{[ 15 ]} قم بتهيئة دالة التجزئة باستخدام متجه.${\displaystyle {\bar {a}}=(a_{0},\dots ,a_{k})}$من الأعداد الصحيحة العشوائية على${\displaystyle 2w}$بتات. حساب

${\displaystyle h_{\bar {a}}({\bar {x}})^{\mathrm {strong} }=(a_{0}+\sum _{i=0}^{k-1}a_{i+1}x_{i}{\bmod {~}}2^{2w})\,\,\mathrm {div} \,\,2^{w}}$.

والنتيجة عالمية بشكل كبير${\displaystyle w}$بتات. وقد وُجد تجريبياً أنه يعمل بمعدل 0.2 دورة معالجة مركزية لكل بايت على معالجات إنتل الحديثة لـ${\displaystyle w=32}$.

يشير هذا إلى تجزئة متجه متغير الحجم من كلمات الآلة. إذا أمكن تحديد طول السلسلة برقم صغير، فمن الأفضل استخدام حل المتجه المذكور أعلاه (أي إضافة أصفار إلى المتجه حتى الوصول إلى الحد الأعلى). المساحة المطلوبة هي أقصى طول للسلسلة، ولكن وقت التقييم هو${\displaystyle h(s)}$هو مجرد طول${\displaystyle s}$طالما أن الأصفار ممنوعة في السلسلة النصية، يمكن تجاهل إضافة الأصفار عند تقييم دالة التجزئة دون التأثير على شموليتها. ^{[ 11 ]} تجدر الإشارة إلى أنه إذا سُمح بالأصفار في السلسلة النصية، فقد يكون من الأفضل إضافة حرف وهمي غير صفري (مثل 1) إلى جميع السلاسل النصية قبل إضافة الأصفار: سيضمن ذلك عدم تأثر الشمولية. ^{[ 15 ]}

لنفترض الآن أننا نريد استخدام التجزئة${\displaystyle {\bar {x}}=(x_{0},\dots ,x_{\ell })}$، حيث يكون هناك حد جيد على${\displaystyle \ell }$غير معروف مسبقًا. تعالج عائلة عالمية مقترحة في ^{[ 12 ]} السلسلة${\displaystyle x}$كمعاملات متعددة الحدود بتردد عدد أولي كبير. إذا${\displaystyle x_{i}\in [u]}$، يترك${\displaystyle p\geq \max\{u,m\}}$ليكن عددًا أوليًا، وعرّفه:

${\displaystyle h_{a}({\bar {x}})=h_{\mathrm {int} }\left({\big (}\sum _{i=0}^{\ell }x_{i}\cdot a^{\ell -i}{\big )}{\bmod {~}}p\right)}$، أين${\displaystyle a\in [p]}$عشوائي بشكل منتظم و${\displaystyle h_{\mathrm {int} }}$يتم اختيارها عشوائياً من عائلة عالمية تمثل مجال الأعداد الصحيحة${\displaystyle [p]\mapsto [m]}$.

باستخدام خصائص الحساب النمطي، يمكن حساب ما سبق دون إنتاج أعداد كبيرة للسلاسل الكبيرة على النحو التالي: ^{[ 16 ]}

دالة التجزئة uint hash ( سلسلة نصية x ، عدد صحيح a ، عدد صحيح p ) uint h = القيمة الابتدائية (INITIAL_VALUE) for ( uint i = 0 ; i < طول x ; ++ i ) h = (( h * a ) + x [ i ]) mod p return h

تعتمد دالة التجزئة المتدحرجة لرابين-كارب على مولد توافقي خطي . ^{[ 17 ]} تُعرف الخوارزمية المذكورة أعلاه أيضًا باسم دالة التجزئة الضربية . ^{[ 18 ]} عمليًا، يمكن تجنب عامل باقي القسمة (mod ) والمعامل p تمامًا بالسماح للأعداد الصحيحة بالفيضان، لأنه يُكافئ باقي القسمة على ( أقصى قيمة عددية صحيحة + 1) في العديد من لغات البرمجة. ومع ذلك، فإن استخدام الأعداد غير الأولية${\displaystyle 2^{n}}$يكون المعامل عرضةً للتداخل مع بعض المدخلات ، بغض النظر عن قيمة a . يوضح الجدول أدناه القيم المختارة لتهيئة h و a لبعض التطبيقات الشائعة.

لنفترض وجود سلسلتين${\displaystyle {\bar {x}},{\bar {y}}}$ودع${\displaystyle \ell }$ليكن طول السلسلة الأطول؛ ولأغراض التحليل، يتم افتراضياً إضافة أصفار إلى السلسلة الأقصر حتى يصل طولها إلى الطول المطلوب.${\displaystyle \ell }$. حدوث تصادم قبل التطبيق${\displaystyle h_{\mathrm {int} }}$يشير ذلك إلى أن${\displaystyle a}$هو جذر لكثير الحدود ذي المعاملات${\displaystyle {\bar {x}}-{\bar {y}}}$تحتوي هذه المعادلة متعددة الحدود على أكثر من${\displaystyle \ell }$جذور modulo${\displaystyle p}$لذا فإن احتمال التصادم هو على الأكثر${\displaystyle \ell /p}$احتمالية التصادم من خلال العشوائية${\displaystyle h_{\mathrm {int} }}$يؤدي ذلك إلى زيادة احتمالية التصادم الكلية إلى${\displaystyle {\frac {1}{m}}+{\frac {\ell }{p}}}$وبالتالي، إذا كان العدد الأولي${\displaystyle p}$إذا كانت كبيرة بما يكفي مقارنة بطول السلاسل التي تم تجزئتها، فإن العائلة قريبة جدًا من العالمية (في المسافة الإحصائية ).

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