डेल्टा एन्कोडिंग

Not to be confused with Elias delta coding or delta modulation.

डेल्टा एन्कोडिंग पूर्ण फ़ाइलों के बजाय अनुक्रमिक आंकड़े के बीच डेटा अंतर (डेल्टा) के रूप में डेटा को संग्रहीत या प्रसारित करने का एक तरीका है; अधिक सामान्यतः इसे डेटा विभेदन के रूप में जाना जाता है। डेल्टा एन्कोडिंग को कभी-कभी डेल्टा संपीड़न कहा जाता है, खासकर जहां परिवर्तनों के अभिलेखीय इतिहास की आवश्यकता होती है (उदाहरण के लिए, संशोधन नियंत्रण सॉफ़्टवेयर में)।

अंतरों को अलग-अलग फाइलों में दर्ज किया जाता है जिन्हें डेल्टा या डिफ कहा जाता है। ऐसी स्थितियों में जहां अंतर छोटे होते हैं - उदाहरण के लिए, किसी बड़े दस्तावेज़ में कुछ शब्दों का परिवर्तन या बड़ी तालिका में कुछ रिकॉर्ड का परिवर्तन - डेल्टा एन्कोडिंग डेटा अतिरेक को बहुत कम कर देता है। अद्वितीय डेल्टाओं का संग्रह उनके गैर-एन्कोडेड समकक्षों की तुलना में काफी अधिक स्थान-कुशल है।

तार्किक दृष्टिकोण से दो डेटा मानों के बीच का अंतर एक मान को दूसरे से प्राप्त करने के लिए आवश्यक जानकारी है - सापेक्ष एन्ट्रापी देखें। समान मानों (कुछ तुल्यता संबंध के तहत) के बीच के अंतर को अक्सर 0 या तटस्थ तत्व कहा जाता है।

सरल उदाहरण

शायद सबसे सरल उदाहरण बाइट्स के मानों को स्वयं मानों के बजाय अनुक्रमिक मानों के बीच अंतर (डेल्टा) के रूप में संग्रहीत करना है। इसलिए, 2, 4, 6, 9, 7 के बजाय, हम 2, 2, 2, 3, −2 संग्रहित करेंगे। जब पड़ोसी नमूने सहसंबद्ध होते हैं तो यह मानों के विचरण (सीमा) को कम कर देता है, जिससे समान डेटा के लिए कम बिट उपयोग सक्षम हो जाता है। इंटरचेंज फ़ाइल प्रारूप 8एसवीएक्स ध्वनि प्रारूप इस एन्कोडिंग को कच्चे ध्वनि डेटा पर संपीड़न लागू करने से पहले लागू करता है। डेल्टा एनकोडेड होने पर सभी 8-बिट ध्वनि नमूनाकरण (सिग्नल प्रोसेसिंग) भी बेहतर ढंग से संपीड़ित नहीं होते हैं, और 16-बिट और बेहतर नमूनों के लिए डेल्टा एन्कोडिंग की उपयोगिता और भी छोटी है। इसलिए, संपीड़न एल्गोरिदम अक्सर डेल्टा एनकोड को तभी चुनते हैं जब संपीड़न बिना से बेहतर होता है। हालाँकि, वीडियो संपीड़न में, डेल्टा फ़्रेम फ़्रेम आकार को काफी कम कर सकते हैं और लगभग हर वीडियो संपीड़न कोडेक में उपयोग किए जाते हैं।

परिभाषा

डेल्टा को 2 तरीकों से परिभाषित किया जा सकता है, सममित डेल्टा और निर्देशित डेल्टा। एक सममित डेल्टा को इस प्रकार व्यक्त किया जा सकता है

$\Delta (v_{1},v_{2})=(v_{1}\setminus v_{2})\cup (v_{2}\setminus v_{1}),$

कहाँ $v_{1}$ और $v_{2}$ दो संस्करणों का प्रतिनिधित्व करें।

एक निर्देशित डेल्टा, जिसे परिवर्तन भी कहा जाता है, (प्राथमिक) परिवर्तन संचालन का एक क्रम है, जो एक संस्करण पर लागू होने पर $v_{1}$, एक और संस्करण उत्पन्न करता है $v_{2}$ (डेटाबेस में लेनदेन लॉग के पत्राचार पर ध्यान दें)। कंप्यूटर कार्यान्वयन में, वे आम तौर पर दो कमांड वाली भाषा का रूप लेते हैं: v1 से डेटा कॉपी करें और शाब्दिक डेटा लिखें।

वेरिएंट

डेल्टा एन्कोडिंग की एक भिन्नता जो स्ट्रिंग (कंप्यूटर विज्ञान) के उपसर्ग (कंप्यूटर विज्ञान) या प्रत्यय (कंप्यूटर विज्ञान) के बीच अंतर को एन्कोड करती है, वृद्धिशील एन्कोडिंग कहलाती है। यह स्ट्रिंग के बीच छोटे अंतर वाली क्रमबद्ध सूचियों के लिए विशेष रूप से प्रभावी है, जैसे शब्दकोश से शब्दों की सूची।

कार्यान्वयन मुद्दे

एन्कोड किए जाने वाले डेटा की प्रकृति एक विशेष संपीड़न एल्गोरिदम की प्रभावशीलता को प्रभावित करती है।

डेल्टा एन्कोडिंग सबसे अच्छा प्रदर्शन करती है जब डेटा में छोटी या निरंतर भिन्नता होती है; किसी अवर्गीकृत डेटा सेट के लिए, इस पद्धति से बहुत कम या कोई संपीड़न संभव नहीं हो सकता है।

एक नेटवर्क पर डेल्टा एन्कोडेड ट्रांसमिशन में जहां संचार चैनल के प्रत्येक छोर पर फ़ाइल की केवल एक प्रति उपलब्ध होती है, विशेष त्रुटि-सुधार का उपयोग यह पता लगाने के लिए किया जाता है कि फ़ाइल के कौन से हिस्से इसके पिछले संस्करण के बाद से बदल गए हैं। उदाहरण के लिए, rsync मार्क एडलर के एडलर-32 अंततः, पर आधारित एक रोलिंग चेकसम एल्गोरिदम का उपयोग करता है।

नमूना सी कोड

निम्नलिखित सी (प्रोग्रामिंग भाषा) कोड वर्णों के अनुक्रम पर डेल्टा एन्कोडिंग और डिकोडिंग का एक सरल रूप निष्पादित करता है:

void delta_encode(unsigned char *buffer, int length)
{
    unsigned char last = 0;
    for (int i = 0; i < length; i++)
    {
        unsigned char current = buffer[i];
        buffer[i] = current - last;
        last = current;
    }
}

void delta_decode(unsigned char *buffer, int length)
{
    unsigned char last = 0;
    for (int i = 0; i < length; i++)
    {
        unsigned char delta = buffer[i];
        buffer[i] = delta + last;
        last = buffer[i];
    }
}

उदाहरण

HTTP में डेल्टा एन्कोडिंग

डेल्टा एन्कोडिंग के उपयोग का एक अन्य उदाहरण है RFC 3229, HTTP में डेल्टा एन्कोडिंग, जो प्रस्तावित करता है कि HTTP सर्वर अद्यतन वेब पेजों को इस रूप में भेजने में सक्षम होना चाहिए संस्करणों (डेल्टा) के बीच अंतर, जिससे इंटरनेट ट्रैफ़िक में कमी आनी चाहिए, क्योंकि अधिकांश पृष्ठ बार-बार पूरी तरह से लिखे जाने के बजाय समय के साथ धीरे-धीरे बदलते हैं:

This document describes how delta encoding can be supported as a compatible extension to HTTP/1.1.

Many HTTP (Hypertext Transport Protocol) requests cause the retrieval of slightly modified instances of resources for which the client already has a cache entry. Research has shown that such modifying updates are frequent, and that the modifications are typically much smaller than the actual entity. In such cases, HTTP would make more efficient use of network bandwidth if it could transfer a minimal description of the changes, rather than the entire new instance of the resource.

[...] We believe that it might be possible to support rsync using the "instance manipulation" framework described later in this document, but this has not been worked out in any detail.

सुझाए गए rsync-आधारित ढांचे को HTTP प्रॉक्सी की एक जोड़ी के रूप में rproxy सिस्टम में लागू किया गया था। बुनियादी vcdiff-आधारित कार्यान्वयन की तरह, दोनों प्रणालियों का उपयोग शायद ही कभी किया जाता है।

डेल्टा प्रतिलिपि

डेल्टा प्रतिलिपि किसी फ़ाइल की प्रतिलिपि बनाने का एक तेज़ तरीका है जिसे आंशिक रूप से बदल दिया जाता है, जब पिछला संस्करण गंतव्य स्थान पर मौजूद होता है। डेल्टा कॉपीिंग के साथ, फ़ाइल का केवल बदला हुआ भाग ही कॉपी किया जाता है। इसका उपयोग आमतौर पर बैकअप या फ़ाइल प्रतिलिपि करने वाले सॉफ़्टवेयर में किया जाता है, अक्सर निजी नेटवर्क या इंटरनेट पर कंप्यूटर के बीच कॉपी करते समय बैंडविड्थ (कंप्यूटिंग) को बचाने के लिए। एक उल्लेखनीय ओपन-सोर्स उदाहरण rsync है।

ऑनलाइन बैकअप

Main article: Online backup services

कई ऑनलाइन बैकअप सेवाएँ अपने उपयोगकर्ताओं को पिछले बैकअप से उसी फ़ाइल के पिछले संस्करण देने के लिए इस पद्धति को अपनाती हैं, जिसे अक्सर डेल्टा के रूप में जाना जाता है। इससे संबंधित लागत कम हो जाती है, न केवल डेटा की मात्रा में जिसे अलग-अलग संस्करणों के रूप में संग्रहीत किया जाना है (क्योंकि फ़ाइल के प्रत्येक परिवर्तित संस्करण को उपयोगकर्ताओं तक पहुंचने के लिए पेश किया जाना है), बल्कि अपलोडिंग (और) में लागत भी कम हो जाती है कभी-कभी अद्यतन की गई प्रत्येक फ़ाइल की डाउनलोडिंग (पूरी फ़ाइल के बजाय केवल छोटे डेल्टा का उपयोग करके)।

डेल्टा अपडेट

Main article: delta update

बड़े सॉफ़्टवेयर पैकेजों के लिए, आमतौर पर संस्करणों के बीच बहुत कम डेटा बदला जाता है। कई विक्रेता समय और बैंडविड्थ बचाने के लिए डेल्टा ट्रांसफ़र का उपयोग करना चुनते हैं।

अंतर

Main article: Diff

डिफ एक फ़ाइल तुलना प्रोग्राम है, जिसका उपयोग मुख्य रूप से टेक्स्ट फ़ाइलों के लिए किया जाता है। डिफ़ॉल्ट रूप से, यह सममित डेल्टा उत्पन्न करता है जो प्रतिवर्ती होता है। सॉफ़्टवेयर पैच (यूनिक्स) के लिए उपयोग किए जाने वाले दो प्रारूप, संदर्भ और एकीकृत, अतिरिक्त संदर्भ लाइनें प्रदान करते हैं जो लाइन संख्या में बदलाव को सहन करने की अनुमति देते हैं।

गिट

Main article: Git (software)

Git स्रोत कोड नियंत्रण प्रणाली एक सहायक git repack ऑपरेशन में डेल्टा संपीड़न का उपयोग करती है। रिपॉजिटरी में मौजूद वस्तुएं जो अभी तक डेल्टा-संपीड़ित नहीं हुई हैं (ढीली वस्तुएं) की तुलना अन्य सभी वस्तुओं के अनुमानी रूप से चुने गए सबसेट से की जाती है, और सामान्य डेटा और अंतर को एक पैक फ़ाइल में संयोजित किया जाता है जिसे पारंपरिक तरीकों का उपयोग करके संपीड़ित किया जाता है। सामान्य उपयोग के मामलों में, जहां स्रोत या डेटा फ़ाइलों को कमिट के बीच क्रमिक रूप से बदला जाता है, इसके परिणामस्वरूप महत्वपूर्ण स्थान की बचत हो सकती है। रीपैक ऑपरेशन आम तौर पर git gc प्रक्रिया के भाग के रूप में किया जाता है, जो स्वचालित रूप से तब चालू हो जाता है जब ढीली वस्तुओं या पैक फ़ाइलों की संख्या कॉन्फ़िगर सीमा से अधिक हो जाती है।

प्रारूप को Git दस्तावेज़ के पैक-प्रारूप पृष्ठ में प्रलेखित किया गया है। यह एक निर्देशित डेल्टा लागू करता है।

वीसीडीआईएफएफ

Main article: VCDIFF

निर्देशित डेल्टा एन्कोडिंग के लिए एक सामान्य प्रारूप VCDIFF है, जिसका वर्णन RFC 3284 में किया गया है। मुफ्त सॉफ्टवेयर कार्यान्वयन में Xdelta और open-vcdiff शामिल हैं।

जीडीआईएफएफ

जेनेरिक डिफ फॉर्मेट (जीडीआईएफएफ) एक अन्य निर्देशित डेल्टा एन्कोडिंग प्रारूप है। इसे 1997 में W3C को प्रस्तुत किया गया था। कई मामलों में, VCDIFF की संपीड़न दर GDIFF से बेहतर है।

bsdiff

Bsdiff प्रत्यय सरणी का उपयोग करने वाला एक बाइनरी डिफ प्रोग्राम है। उन निष्पादनयोग्यों के लिए जिनमें सूचक पते में कई परिवर्तन होते हैं, यह वीसीडीआईएफएफ-प्रकार की प्रतिलिपि और शाब्दिक एन्कोडिंग से बेहतर प्रदर्शन करता है। इरादा असेंबली कोड को पार्स करने की आवश्यकता के बिना एक छोटा सा अंतर उत्पन्न करने का एक तरीका ढूंढना है (जैसा कि Google के कौरगेट में है)। Bsdiff त्रुटियों के साथ प्रतिलिपि मिलान की अनुमति देकर इसे प्राप्त करता है, जिसे बाद में बाइटवाइज अंतरों की एक अतिरिक्त ऐड सरणी का उपयोग करके ठीक किया जाता है। चूँकि यह सरणी अधिकतर या तो शून्य है या ऑफ़सेट परिवर्तनों के लिए दोहराई गई मान है, यह संपीड़न के बाद बहुत कम जगह लेती है। डेल्टा अपडेट के लिए Bsdiff उपयोगी है। Google क्रोमियम और Android में bsdiff का उपयोग करता है। आरपीएम पैकेज मैनेजर की deltarpm सुविधा एक भारी-संशोधित bsdiff पर आधारित है जो मिलान के लिए हैश तालिका का उपयोग कर सकती है। FreeBSD अपडेट के लिए bsdiff का भी उपयोग करता है। 2005 में bsdiff के 4.3 रिलीज़ के बाद से, इसके लिए विभिन्न सुधार या सुधार किए गए हैं। Google अपने प्रत्येक उत्पाद के लिए कोड के कई संस्करण रखता है। फ्रीबीएसडी Google के कई संगत परिवर्तनों को अपनाता है, मुख्य रूप से भेद्यता को ठीक करना और तेजी से स्विच करना divsufsort प्रत्यय-सॉर्टिंग रूटीन। डेबियन के पास कार्यक्रम में प्रदर्शन बदलावों की एक श्रृंखला है। डेल्टा डेबियन डेल्टा अपडेट में उपयोग के लिए प्रस्तावित bsdiff का पुनर्लेखन है। अन्य दक्षता सुधारों के अलावा, यह मेमोरी और सीपीयू लागत को कम करने के लिए एक स्लाइडिंग विंडो का उपयोग करता है।

यह भी देखें

• डेटा अंतर
• इंटरलीव्ड डेल्टा
• स्रोत कोड नियंत्रण प्रणाली
• स्ट्रिंग-टू-स्ट्रिंग सुधार समस्या
• एक्सडेल्टा: ओपन-सोर्स डेल्टा एनकोडर

बाहरी संबंध

• RFC 3229 – Delta Encoding in HTTP