الحشيش الملفوف

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

تسمح بعض وظائف التجزئة بحساب التجزئة المتداولة بسرعة كبيرة - يتم حساب قيمة التجزئة الجديدة بسرعة بالنظر فقط إلى قيمة التجزئة القديمة، والقيمة القديمة التي تمت إزالتها من النافذة، والقيمة الجديدة التي تمت إضافتها إلى النافذة - على غرار الطريقة التي يمكن بها حساب دالة المتوسط ​​المتحرك بسرعة أكبر بكثير من مرشحات التمرير المنخفض الأخرى؛ وعلى غرار الطريقة التي يمكن بها تحديث تجزئة Zobrist بسرعة من قيمة التجزئة القديمة.

من أبرز تطبيقاتها خوارزمية البحث عن السلاسل النصية رابين-كارب ، التي تستخدم التجزئة المتغيرة الموضحة أدناه. ومن التطبيقات الشائعة الأخرى برنامج rsync ، الذي يستخدم مجموعًا اختباريًا مبنيًا على خوارزمية adler-32 لمارك أدلر كتجزئة متغيرة. يستخدم نظام ملفات الشبكة منخفض النطاق الترددي (LBFS) بصمة رابين كتجزئة متغيرة. أما FastCDC (التجزئة السريعة المحددة المحتوى) فيستخدم بصمة Gear ذات الكفاءة الحسابية العالية كتجزئة متغيرة.

في أفضل الأحوال، تكون قيم التجزئة المتغيرة مستقلة ثنائياً ^{[ 1 ]} أو عالمية بقوة . لا يمكن أن تكون مستقلة ثلاثياً ، على سبيل المثال.

غالباً ما يتم شرح خوارزمية البحث عن السلاسل النصية لرابين -كارب باستخدام دالة تجزئة متدحرجة لا تستخدم سوى عمليات الضرب والجمع:

${\displaystyle H=c_{1}a^{k-1}+c_{2}a^{k-2}+c_{3}a^{k-3}+...+c_{k}a^{0}}$،

أين${\displaystyle a}$ثابت، و${\displaystyle c_{1},...,c_{k}}$هي الأحرف المدخلة (لكن هذه الوظيفة ليست بصمة رابين ، انظر أدناه).

لتجنب التلاعب بالبيانات الضخمة${\displaystyle H}$القيم، جميع العمليات الحسابية تتم باستخدام باقي القسمة${\displaystyle n}$اختيار${\displaystyle a}$و${\displaystyle n}$يُعدّ الحصول على تجزئة جيدة أمرًا بالغ الأهمية؛ وخاصةً المعامل.${\displaystyle n}$عادةً ما يكون عددًا أوليًا . انظر مولد التوافق الخطي لمزيد من التفاصيل.

تتضمن عملية إزالة الأحرف وإضافتها ببساطة جمع أو طرح الحد الأول أو الأخير. أما إزاحة جميع الأحرف بمقدار خانة واحدة إلى اليسار فتتطلب ضرب المجموع بأكمله.${\displaystyle H}$بواسطة${\displaystyle a}$يتطلب تحريك جميع الأحرف بمقدار موضع واحد إلى اليمين قسمة المجموع الكلي${\displaystyle H}$بواسطة${\displaystyle a}$لاحظ أنه في حساب باقي القسمة،${\displaystyle a}$يمكن اختيارها بحيث يكون لها معكوس ضربي${\displaystyle a^{-1}}$والتي من خلالها${\displaystyle H}$يمكن ضربها للحصول على نتيجة القسمة دون إجراء عملية قسمة فعلية.

بصمة رابين هي دالة تجزئة أخرى، تُفسر المدخلات أيضًا على أنها متعددة حدود، ولكن على حقل غالوا GF(2) . فبدلًا من اعتبار المدخلات متعددة حدود من البايتات، تُعتبر متعددة حدود من البتات، وتُجرى جميع العمليات الحسابية في GF(2) (على غرار CRC-32 ). وتُمثل دالة التجزئة باقي قسمة متعددة الحدود هذه على متعددة حدود غير قابلة للاختزال على GF(2). ويمكن تحديث بصمة رابين باستخدام بايت الدخول وبايت الخروج فقط، مما يجعلها فعليًا دالة تجزئة متغيرة. ^{[ 2 ]}

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

التجزئة باستخدام كثير الحدود الدوري ^{[ 4 ]} - والتي تُسمى أحيانًا Buzhash ^{[ 5 ]} - بسيطة أيضًا، وتتميز بتجنب عمليات الضرب، حيث تستخدم الإزاحة الدائرية بدلاً منها. وهي شكل من أشكال تجزئة الجدولة : إذ تفترض وجود دالة استبدال.${\displaystyle s}$من الأحرف إلى الأعداد الصحيحة في الفترة${\displaystyle [0,2^{L})}$، وهو في الأساس جدول بحث (يجب أن تكون كل خانة من خانات البت الـ 32 لقيم s متوازنة، أي أن تحتوي على عدد من الآحاد يساوي عدد الأصفار). لنفترض أن الدالة${\displaystyle \operatorname {rol} }$يكون دورانًا ثنائيًا . على سبيل المثال،${\displaystyle \operatorname {rol} (101)=011}$. يترك${\displaystyle \oplus }$ليكن .​${\displaystyle c_{i}}$ليكن البايت رقم i في دفق البيانات، و${\displaystyle w}$يكون حجم النافذة المستخدم.

نقوم بالحساب المسبق${\displaystyle s'}$لإزالة مساهمة بايت خارج النافذة: ^{[ 4 ] : ​​الجدول الثالث}

${\displaystyle s'[i]=\operatorname {rol} (s[i],w)}$

تُعرَّف قيم التجزئة وفقًا لعلاقة التكرار التالية: ^{[ 4 ] : ​​الجدول الثالث}

${\displaystyle H_{i}={\begin{cases}0&{\text{إذا كان }}i=0\\\operatorname {rol} (H_{i-1},1)\oplus s[c_{i}]&{\text{إذا كان }}i\leq w\\\operatorname {rol} (H_{i-1},1)\oplus s[c_{i}]\oplus s'[c_{iw}]&{\text{إذا كان }}i>w\end{cases}}}$

جميع قيم H تقع ضمن الفترة${\displaystyle [0,2^{L})}$تصف هذه العلاقة التكرارية طريقة حساب التجزئة بطريقة متجددة: ^{[ 4 ] : ​​الجدول الثالث}

• تم تهيئة التجزئة عند القيمة 0.
• عند ملء النافذة، تتضمن إضافة حرف تدوير التجزئة القديمة إلى اليسار بمقدار موضع واحد وإجراء عملية XOR على التجزئة الجديدة.${\displaystyle s[c_{i}]}$.
• عندما تمتلئ النافذة، يتم استخدام نفس الإجراء لإضافة حرف، متبوعًا بإزالة مساهمة الحرف الموجود خارج النافذة عن طريق عملية XOR.${\displaystyle s'[c_{iw}]}$.

إن قيمة H ليست منتظمة رسميًا ولا عالمية من الدرجة الثانية، على الرغم من انتظامها التجريبي. ومع ذلك، يمكن جعلها منتظمة رسميًا ومستقلة ثنائيًا إذا كان هناك عدد متتالٍ فقط${\displaystyle L-w+1}$تُؤخذ البتات من التجزئة. عمليًا، يمكن أن تكون هذه عملية AND منطقية (عملية إخفاء):${\displaystyle H'_{i}=H_{i}\mathbin {\&} (1\ll (w-1)-1)}$، أين${\displaystyle \mathbin {\&} }$هي عملية AND ثنائية و${\displaystyle \ll }$هو إزاحة إلى اليسار. ^{[ 1 ]}

بالإضافة إلى ذلك، يشير مؤلفو borg إلى أنه لا ينبغي أن يكون w من مضاعفات 2L إذا تم استخدام بذرة لتعديل s[] عن طريق إجراء عملية XOR بين كل قيمة والبذرة. ^{[ 6 ]}

يُعدّ تجزئة البيانات باستخدام Gear نوعًا آخر من أنواع التجزئة الجدولية. لنفترض أن s عبارة عن جدول ثابت يحتوي على 256 عددًا صحيحًا عشوائيًا غير مُوقّع من 32 بت، وأن H هو مُجمِّع التجزئة (عدد صحيح غير مُوقّع، 32 بت على الأقل)، وأن f هو الملف المُمثَّل كمصفوفة من البايتات (أعداد صحيحة من 8 بت، فهرس يبدأ من 1).${\displaystyle \ll }$ليكن عامل الإزاحة إلى اليسار. العلاقة التكرارية هي: ^{[ 7 ]}

${\displaystyle H_{0}=0}$

${\displaystyle H_{i}=(H_{i-1}\ll 1)+s[f[i]]}$

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

^{يُعد استخدام البتات السفلية مقبولاً أيضاً ،} ولكنه يُقلل من حجم النافذة المنزلقة الفعال. ويظهر أكبر حجم فعال عندما تأخذ القناع عينة من عدد من البتات غير المتتالية من "نطاق" واسع نسبياً من H. [ ^{8 ]}

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

تتمثل إحدى الطرق البسيطة لإنشاء أجزاء ديناميكية في حساب قيمة تجزئة متغيرة، وإذا تطابقت قيمة التجزئة مع نمط عشوائي (مثل جميع الأصفار) في البتات N السفلى (باحتمالية 0.00)${\textstyle {1 \over 2^{n}}}$إذا كان للتجزئة توزيع احتمالي منتظم، فسيتم اختيارها لتكون حدودًا للجزء. وبالتالي، سيكون لكل جزء حجم متوسط ​​قدره${\textstyle 2^{n}}$بايتات. يضمن هذا الأسلوب أن البيانات غير المعدلة (التي تبعد أكثر من حجم نافذة عن التغييرات) ستحتفظ بنفس الحدود. بمجرد معرفة الحدود، يجب مقارنة الأجزاء باستخدام قيمة التجزئة المشفرة للكشف عن التغييرات. ^{[ 10 ]}

يُستخدم تجزئة البيانات المُحددة بالمحتوى (CDC) أو التجزئة القائمة على المحتوى (CBC) غالبًا لإزالة البيانات المُكررة . ^{[ 9 ] [ 11 ]} يمكن أن تكون دالة التجزئة المُستخدمة أي خوارزمية تجزئة مُتغيرة. ومن الأمثلة على ذلك:

• تقسيم البيانات إلى أجزاء أقل أهمية
  • مجموع غير مرجح (rsyncrypto) ^{[ 12 ]}
  • التجزئة المتدحرجة متعددة الحدود لرابين-كارب ^{[ 10 ]}
• بصمة رابين، كما هو مستخدم في برنامج النسخ الاحتياطي restic (مع حجم بيانات يتراوح بين 512 كيلوبايت و 8 ميجابايت ونافذة 64 بايت). ^{[ 9 ]}
• تقسيم البيانات إلى أجزاء بناءً على أي بتات متتالية
  • تُستخدم خوارزمية التجزئة الدورية (buzhash) في برنامج النسخ الاحتياطي Borg . يوفر Borg نطاقًا قابلًا للتخصيص لحجم أجزاء الملفات، وذلك بتغيير قيمة N (افتراضيًا بين 512 كيلوبايت و 8 ميجابايت ). ^{[ 11 ]} ويستخدم نافذة بحجم 4095 بايت ^{[ 11 ]} ودالة استبدال غير متوازنة. ^{[ 13 ]}
• تقسيم أي مجموعة من البتات
  • تجزئة التروس. ^{[ 7 ]} تم تحسين CDC القائم على التروس بشكل متتابع، مما أدى إلى ظهور FastCDC وRapidCDC وQuickCDC. ^{[ 14 ]}

تتميز تقنية تجزئة الملفات بناءً على المحتوى بميزة أن التغييرات المحلية التي تُجرى على ملف ما، في معظم الحالات، لا تؤثر إلا على الجزء الذي يوجد فيه، وربما على الجزء التالي، دون التأثير على أي جزء آخر. وتوفر الخوارزميات وأنواع التجزئة المختلفة مستويات متفاوتة من قوة هذا الضمان.

مدخلات خوارزمية FastCDC : مصدر مخزن البيانات ، طول البيانات n ، الناتج: نقطة القطع iMinSize ← 2 كيلوبايت // الحد الأدنى لحجم الجزء المُقسّم هو 2 كيلوبايت MaxSize ← 64 كيلوبايت // الحد الأقصى لحجم الجزء المُقسّم هو 64 كيلوبايت Mask ← 0x0000d93003530000 // تم ضبط 13 بت -> الحجم المتوسط ​​المطلوب هو 2^13 بايت = 8 كيلوبايت fp ← 0 // uint64 i ← 0 // حجم المخزن المؤقت أقل من الحد الأدنى لحجم القطعة إذا كان n ≤ MinSize، فأرجع n . إذا كان n ≥ MaxSize، فأرجع n ← MaxSize. // تخطَّ أول 16 بايت من MinSize ، وابدأ عملية التجزئة     بينما i < MinSize do fp ← ( fp << 1 ) + Gear [ src [ i ]] i ← i + 1     بينما i < n، نفّذ ما يلي: fp ← ( fp << 1) + Gear [ src [ i ]] ، إذا لم يكن fp & Mask موجودًا ، فأرجع i ، i ← i + 1     أعد i

يمكن حساب جميع دوال التجزئة المتدحرجة في وقت خطي لعدد الأحرف، وتحديثها في وقت ثابت عند إزاحة الأحرف بمقدار موضع واحد. على وجه الخصوص، حساب تجزئة رابين-كارب المتدحرجة لسلسلة طولها${\displaystyle k}$يتطلب${\displaystyle O(k)}$تتطلب عمليات الحساب النمطي والتجزئة باستخدام كثيرات الحدود الدورية${\displaystyle O(k)}$عمليات XOR الثنائية وعمليات الإزاحة الدائرية . ^{[ 1 ]}

• MinHash – تقنية استخراج البيانات 
• w - القرميد

• معهد ماساتشوستس للتكنولوجيا 6.006: مقدمة في الخوارزميات 2011 - جلسة مراجعة 9 - التجزئة المتداولة