ترميز دلتا

يُعرَّف الفرق بين القيم العددية ببساطة عن طريق الطرح، كما هو موضح في المثال أعلاه. وبسبب خاصية العمليات الحسابية، فإن الفرق العددي متناظر : إذا كانت القيمة الأخيرة${\displaystyle b}$إذا كان معروفًا، فمن الممكن تطبيق دلتا${\displaystyle ba}$بالعكس للحصول على القيمة السابقة${\displaystyle a}$.

من الممكن أيضًا إنتاج "فرق عددي بين الفروق". قد يكون هذا مفيدًا إذا تم توليد البيانات الأساسية بواسطة عملية تشبه${\displaystyle f(x)=ax+b}$لأن دالة دلتا من الدرجة الثانية تُسطّح البيانات إلى سلسلة من الأصفار. وغالبًا ما تتصرف الطوابع الزمنية بهذه الطريقة. ^{[ 1 ]} بل إن دوال دلتا من الرتب الأعلى قد تكون مفيدة لبيانات الحياة الواقعية: على سبيل المثال، تُضغط المسافة المقاسة ( المدى الزائف ) إلى قمر صناعي للملاحة بمرور الوقت بشكل أفضل باستخدام دالة دلتا من الدرجة الثالثة، وهي "دالة دلتا من دلتا من دلتا". ^{[ 2 ]}

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

ثمة طريقة أخرى تتمثل في تغيير المسافة بين العناصر المستخدمة في عملية دلتا: بدلاً من حساب${\displaystyle ba}$في التسلسل${\displaystyle (a,b,c,d)}$، سيتم حساب دلتا "المسافة-2"${\displaystyle ca}$يظهر هذا في مرشح "دلتا" الخاص بـ xz . ^{[ 3 ]}

void encode ( uint8_t buffer [], size_t length ) { uint8_t last = 0 ; for ( size_t i = 0 ; i < length ; ++ i ) { uint8_t current = buffer [ i ]; buffer [ i ] = current - last ; last = current ; } }void decode ( uint8_t buffer [], size_t length ) { uint8_t last = 0 ; for ( size_t i = 0 ; i < length ; ++ i ) { uint8_t delta = buffer [ i ]; buffer [ i ] = delta + last ; last = buffer [ i ]; } }

بالنسبة للفرق بين سلاسل أو مجموعات من القيم (مثل سلاسل الأحرف والصور)، يمكن تعريف دلتا بطريقتين: دلتا متناظرة ودلتا موجهة . تتضمن دلتا المتناظرة بين مجموعتين معلومات كافية لجعلها قابلة للعكس.

${\displaystyle \Delta ({\mathit {version}}_{1},{\mathit {version}}_{2})=({\mathit {version}}_{1}\setminus {\mathit {version}}_{2})\cup ({\mathit {version}}_{2}\setminus {\mathit {version}}_{1}).}$

يُعرَّف الفرق بين سلسلتين بشكل مماثل، باستثناء إضافة معلومات لتحديد مواقع الإضافات والحذوفات. في تطبيقات الحاسوب، يُوضَّح ذلك من خلال مخرجات الأمر diff (في الوضع الافتراضي والموحد والسياقي): تعليمات على شكل "في الموضع".${\displaystyle x}$استبدل (المحتوى القديم) بـ (المحتوى الجديد).

دلتا الموجهة ، وتسمى أيضًا التغيير، هي سلسلة من عمليات التغيير (الأولية) التي عند تطبيقها على${\displaystyle {\mathit {version}}_{1}}$، مما ينتج عنه آخر،${\displaystyle {\mathit {version}}_{2}}$(لاحظ التطابق مع سجلات المعاملات في قواعد البيانات). في تطبيقات الحاسوب، عادةً ما تأخذ هذه السجلات شكل لغة برمجة تتضمن أمرين: نسخ البيانات من${\displaystyle {\mathit {version}}_{1}}$وكتابة البيانات الحرفية . مثال على ذلك هو ناتج الأمر diff في وضع تحرير النص البرمجي .

ومن الأمثلة الأخرى على استخدام ترميز دلتا RFC 3229 ، "ترميز دلتا في HTTP"، والذي يقترح أن تكون خوادم HTTP قادرة على إرسال صفحات الويب المحدثة في شكل اختلافات بين الإصدارات (دلتا)، مما يقلل من حركة مرور الإنترنت، حيث أن معظم الصفحات تتغير ببطء بمرور الوقت، بدلاً من إعادة كتابتها بالكامل بشكل متكرر:

توضح هذه الوثيقة كيفية دعم ترميز دلتا كامتداد متوافق مع HTTP/1.1.

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

[...] نعتقد أنه قد يكون من الممكن دعم rsync باستخدام إطار عمل "معالجة المثيل" الموضح لاحقًا في هذه الوثيقة، ولكن لم يتم العمل على ذلك بالتفصيل.

تم تطبيق إطار العمل المقترح القائم على rsync في نظام rproxy كزوج من وكلاء HTTP. ^{[ 5 ]} ومثل التطبيق الأساسي القائم على vcdiff، نادرًا ما يُستخدم كلا النظامين.

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

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

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

تم توثيق هذا التنسيق في صفحة تنسيق الحزمة في وثائق Git. وهو يطبق دلتا موجهة. ^{[ 10 ]}

أحد التنسيقات العامة لترميز دلتا الموجه هو VCDIFF، الموصوف في RFC 3284. وتشمل تطبيقات البرامج المجانية Xdelta و open-vcdiff.

يُعد تنسيق الفرق العام (GDIFF) تنسيقًا آخر لترميز دلتا الموجه. وقد تم تقديمه إلى اتحاد شبكة الويب العالمية (W3C) في عام 1997. ^{[ 11 ]} في كثير من الحالات، يتمتع تنسيق VCDIFF بمعدل ضغط أفضل من تنسيق GDIFF.

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

يُعدّ Bsdiff مفيدًا لتحديثات دلتا. تستخدمه جوجل في كلٍّ من كروميوم وأندرويد. تعتمد ميزة deltarpm في مدير حزم RPM على نسخة معدّلة من Bsdiff تستخدم جدول تجزئة للمطابقة. ^{[ 13 ]} كما يستخدم نظام FreeBSD أيضًا Bsdiff للتحديثات. ^{[ 14 ]}

منذ إصدار النسخة 4.3 من برنامج bsdiff عام 2005، أُجريت عليه تحسينات وإصلاحات عديدة. تحتفظ جوجل بنسخ متعددة من الكود لكل منتج من منتجاتها. ^{[ 15 ]} يتبنى نظام FreeBSD العديد من التغييرات المتوافقة التي أدخلتها جوجل، وأهمها إصلاح ثغرة أمنية والتحول إلى divsufsortروتين فرز اللواحق الأسرع. ^{[ 16 ]} أما نظام Debian، فقد أدخل سلسلة من التحسينات على أداء البرنامج. ^{[ 17 ]}

ddelta هي نسخة مُعاد كتابتها من bsdiff، مُقترحة للاستخدام في تحديثات دلتا لنظام دبيان. ومن بين تحسينات الكفاءة الأخرى، تستخدم نافذة منزلقة لتقليل استهلاك الذاكرة ووحدة المعالجة المركزية. ^{[ 18 ]}