डिफ्लेट: Difference between revisions

काट्ज़ ने डिफ्लेट स्ट्रीम के निर्माण के लिए उपयोग किए जाने वाले मूल एल्गोरिदम को भी डिज़ाइन किया। इस एल्गोरिदम को {{US patent|5051745}} के रूप में [[सॉफ्टवेयर पेटेंट]] कराया गया था, और PKWARE, Inc. को सौंपा गया था।<ref name="patent">{{cite patent |country=US |number=5051745 |publication-date=1991-09-24 |issue-date=1991-09-24 |title=स्ट्रिंग खोजकर्ता, और कंप्रेसर समान का उपयोग कर रहे हैं|inventor-last=Katz|inventor-first=Phillip W.|inventorlink=Phil Katz |assign1= PKWare Inc. | status=patent}}</ref><ref>{{cite book|title=Data Compression: The Complete Reference | last=David | first=Salomon|year=2007|edition=4|page=241|publisher=Springer|isbn=978-1-84628-602-5|url=https://books.google.com/books?id=ujnQogzx_2EC&pg=PA241}}</ref> जैसा कि आरएफसी डॉक्यूमेंट में कहा गया है, डिफ्लेट फ़ाइलों का उत्पादन करने वाले एल्गोरिदम को व्यापक रूप से पेटेंट द्वारा कवर नहीं किए जाने वाले तरीके से कार्यान्वयन योग्य माना जाता था।<ref name="IETF" />इससे इसका व्यापक उपयोग हुआ - उदाहरण के लिए, जीज़िप कंप्रेस्ड फ़ाइलों और पीएनजी इमेज फ़ाइलों में, ज़िप फ़ाइल फॉर्मेट के अलावा जिसके लिए कैटज़ ने मूल रूप से इसे डिज़ाइन किया था। पेटेंट अब समाप्त हो चुका है।

* पॉइंटर्स के साथ डुप्लिकेट स्ट्रिंग्स का मिलान और प्रतिस्थापन।

=== डुप्लिकेट स्ट्रिंग उन्मूलन ===

कंप्रेस्ड ब्लॉकों के भीतर, यदि बाइट्स की एक डुप्लिकेट श्रृंखला (एक दोहराई गई स्ट्रिंग) देखी जाती है,तो उसके बजाय उस समान स्ट्रिंग के पिछले स्थान से लिंक करते हुए एक बैक-रेफरेंस (कंप्यूटर विज्ञान) डाला जाता है। पिछली स्ट्रिंग के एन्कोडेड मिलान में डुप्लिकेट की शुरुआत में 8-बिट लंबाई (3-258 बाइट्स) और 15-बिट दूरी (1-32,768 बाइट्स) होती है। सापेक्ष बैक-रेफरेंस किसी भी संख्या में ब्लॉक में किए जा सकते हैं, जब तक कि दूरी डिकोड किए गए इनकंप्रेसिब्ल डेटा के अंतिम 32 [[किबिबाइट]] (स्लाइडिंग विंडो कहा जाता है) के भीतर दिखाई देती है ।

यदि दूरी लंबाई से कम है, तो डुप्लिकेट स्वयं ओवरलैप हो जाता है, जो पुनरावृत्ति का संकेत देता है। उदाहरण के लिए, 10 समान बाइट्स के एक रन को एक बाइट के रूप में एन्कोड किया जा सकता है, इसके बाद पिछले बाइट से शुरू करके लंबाई 9 की डुप्लिकेट बनाई जा सकती है।

डुप्लिकेट सबस्ट्रिंग के लिए पूर्ववर्ती पाठ की खोज करना डिफ्लेट एल्गोरिदम का सबसे कम्प्यूटेशनल रूप से महंगा हिस्सा है, और वह ऑपरेशन जो कम्प्रेशन स्तर सेटिंग्स को प्रभावित करता है।

{{main article|Huffman coding}}

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

* 256: ब्लॉक का अंत - अंतिम ब्लॉक होने पर प्रोसेसिंग बंद हो जाता है, अन्यथा अगले ब्लॉक पर प्रोसेसिंग शुरू बंद हो जाता है।

* 257-285: अतिरिक्त बिट्स के साथ संयुक्त, 3-258 बाइट्स की एक मिलान लंबाई है।

* 286, 287: उपयोग नहीं किया गया, रिजर्व्ड और अवैध लेकिन फिर भी ट्री का हिस्सा है।

मैच लंबाई कोड के बाद हमेशा दूरी कोड आएगा। पढ़े गए दूरी कोड के आधार पर, अंतिम दूरी उत्पन्न करने के लिए अतिरिक्त अतिरिक्त बिट्स पढ़े जा सकते हैं। दूरी ट्री में 32 सिम्बल्स के लिए स्थान होता है:

* 0-3: 1-4 दूरियाँ

* 4-5: 1 अतिरिक्त बिट, दूरियाँ 5-8

* 6-7:  2 अतिरिक्त बिट्स, दूरियाँ 9-16

* 8-9: 3 अतिरिक्त बिट्स, दूरियाँ 17-32

* 26-27: 12 अतिरिक्त बिट्स, दूरियाँ 8,193-16,384

* 28-29: 13 अतिरिक्त बिट्स, दूरियाँ 16,385-32,768

*30-31: उपयोग नहीं किया गया, रिजर्व्ड और अवैध लेकिन फिर भी ट्री का हिस्सा।

ध्यान दें कि मिलान दूरी सिम्बल्स 2-29 के लिए, अतिरिक्त बिट्स की संख्या की गणना <math>\left\lfloor\frac{n}{2}\right\rfloor-1</math> प्रकार की जा सकती है .

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

कम्प्रेशन चरण के दौरान, यह एनकोडर है जो मिलान स्ट्रिंग की तलाश में बिताए गए समय की मात्रा को चुनता है। Zlib/gzip [[संदर्भ कार्यान्वयन]] उपयोगकर्ता को संभावित परिणामी कम्प्रेशन-स्तर बनाम एन्कोडिंग की गति के स्लाइडिंग पैमाने से चयन करने की अनुमति देता है। विकल्प <code>0</code> से लेकर होते हैं  (कम्प्रेशन का प्रयास न करें, केवल अकंप्रेस्ड आर्चिविंग करें)। <code>9</code> 9 तक होते हैं जो zlib/gzip में संदर्भ कार्यान्वयन की अधिकतम क्षमता का प्रतिनिधित्व करते हैं।

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

PKWARE द्वारा निर्दिष्ट डिफ्लेट64, डिफ्लेट का एक मालिकाना संस्करण है। यह मूल रूप से वही एल्गोरिदम है। जो परिवर्तन हुआ है वह है शब्दकोश का आकार 32 केबी से बढ़ाकर 64 केबी, दूरी कोड को 16 बिट तक विस्तारित करना ताकि वे 64 केबी की सीमा को संबोधित कर सकें, और लंबाई कोड, जिसे 16 बिट तक बढ़ाया गया है ताकि यह तीन से 65,538 बाइट्स की लंबाई को परिभाषित कर सके।<ref>{{Cite web |url=http://www.binaryessence.com/dct/imp/en000225.htm |title=Binary Essence – Deflate64 |access-date=22 May 2011 |archive-url=https://web.archive.org/web/20170621195505/http://www.binaryessence.com/dct/imp/en000225.htm |archive-date=21 June 2017 |url-status=bot: unknown }}</ref> इसके कारण डिफ्लेट64 का कम्प्रेशन समय लंबा हो जाता है, और संभावित रूप से डिफ्लेट की तुलना में थोड़ा अधिक कम्प्रेशन अनुपात होता है।<ref>{{Cite web |url=http://www.binaryessence.com/dct/apc/en000263.htm |title=Binary Essence – "Calgary Corpus" compression comparisons |access-date=22 May 2011 |archive-url=https://web.archive.org/web/20171227131819/http://www.binaryessence.com/dct/apc/en000263.htm |archive-date=27 December 2017 |url-status=bot: unknown }}</ref> कई मुफ़्त और/या ओपन सोर्स प्रोजेक्ट्स डिफ्लेट64 का समर्थन करते हैं, जैसे [[7-ज़िप]],<ref>{{Cite web|url=https://sevenzip.osdn.jp/chm/cmdline/switches/method.htm|title=-एम (संपीड़न विधि सेट करें) स्विच|website=sevenzip.osdn.jp}}</ref> जबकि अन्य, जैसे [[zlib]], प्रक्रिया की स्वामित्व प्रकृति के परिणामस्वरूप ऐसा नहीं करते हैं<ref>History of Lossless Data Compression Algorithms – [http://ieeeghn.org/wiki/index.php/History_of_Lossless_Data_Compression_Algorithms#DEFLATE64 Deflate64]</ref> और डिफ्लेट की तुलना में प्रदर्शन में बहुत मामूली वृद्धि हुई।<ref>zlib FAQ – [https://www.zlib.net/zlib_faq.html#faq40 Does zlib support the new "Deflate64" format introduced by PKWare?]</ref>

डिफ्लेट का कार्यान्वयन कई भाषाओं में निःशुल्क उपलब्ध है। C (प्रोग्रामिंग भाषा) में लिखे गए ऐप्स आमतौर पर zlib लाइब्रेरी (अनुमेय zlib लाइसेंस के तहत) का उपयोग करते हैं। [[बोर्लैंड पास्कल]] (और संगत भाषाओं) में ऐप्स paszlib का उपयोग कर सकते हैं। [[C++]] में ऐप्स 7-ज़िप में बेहतर डिफ्लेट लाइब्रेरी का लाभ उठा सकते हैं। [[जावा (सॉफ़्टवेयर प्लेटफ़ॉर्म)]] और .NET फ़्रेमवर्क दोनों अपने पुस्तकालयों में डिफ्लेट के लिए आउट-ऑफ़-द-बॉक्स समर्थन प्रदान करते हैं (क्रमशः, <code>java.util.zip</code> और [https://docs.microsoft.com/en-us/dotnet/api/system.io.compression.deflatestream System.IO.Compression])। Ada (प्रोग्रामिंग भाषा) में ऐप्स [http://unzip-ada.sourceforge.net/ Zip-Ada] (शुद्ध) या [http://zlib-ada.sourceforge.net/ ZLib-Ada] का उपयोग कर सकते हैं।

=== एनकोडर कार्यान्वयन ===

* PKZIP: पहला कार्यान्वयन, मूल रूप से PKZip के हिस्से के रूप में फिल काट्ज़ द्वारा किया गया

* zlib: इसके ओपन-सोर्स, अनुमेय लाइसेंस के कारण कई ऐप्स में मानक संदर्भ कार्यान्वयन अपनाया गया है। उच्च-प्रदर्शन वाले फ़ोर्क्स के लिए {{section link|Zlib#Forks}} देखें।

* [[क्रिप्टो++]]: संभावित [[भेद्यता (कंप्यूटिंग)]] को कम करने के उद्देश्य से C++ में एक सार्वजनिक-डोमेन कार्यान्वयन सम्मिलित है। लेखक, वेई दाई कहते हैं "यह कोड कम चतुर है, लेकिन उम्मीद है कि [zlib की तुलना में] अधिक समझने योग्य और रखरखाव योग्य है"।

* पुटी 'sshzlib.c': साइमन टैथम द्वारा [[मेरा लाइसेंस|एमआईटी  लाइसेंस]] के तहत एक स्टैंडअलोन कार्यान्वयन, इसमें पूर्ण डिकोडिंग क्षमता है, लेकिन केवल स्टेटिक ट्री निर्माण का समर्थन करता है

* लिबफ़्लेट:<ref>{{Cite web |url=http://plan9.bell-labs.com/sources/plan9/sys/src/libflate/ |title=Plan 9 from Bell Labs's /n/sources/plan9/sys/src/libflate |website=plan9.bell-labs.com |publisher=Lucent Technologies |archive-date=2006-03-15 |archive-url=https://web.archive.org/web/20060315063934/http://plan9.bell-labs.com/sources/plan9/sys/src/libflate/ |url-status=dead }}</ref> बेल लैब्स की योजना 9 का हिस्सा, डिफ्लेट कम्प्रेशन को लागू करता है

* [[Zopfli]]: [[Google]] द्वारा [[अपाचे लाइसेंस]] के तहत C कार्यान्वयन; सीपीयू उपयोग की कीमत पर उच्चतम कम्प्रेशन प्राप्त करता है। ZopfliPNG पोर्टेबल नेटवर्क ग्राफ़िक्स फ़ाइलों के साथ उपयोग के लिए Zopfli का एक रूप है।

* igzip:एमआईटी लाइसेंस के तहत [[इंटेल]] द्वारा जारी [[x86 असेंबली भाषा]] में लिखा गया एक एनकोडर। zlib -1 से 3 गुना तेज। जीनोमिक डेटा को कंप्रेस्ड करने के लिए उपयोगी।<ref>{{cite web |title=जीनोमिक डेटा सेट के लिए अनुकूलन के साथ उच्च प्रदर्शन DEFLATE संपीड़न|url=https://software.intel.com/en-us/articles/igzip-a-high-performance-deflate-compressor-with-optimizations-for-genomic-data |website=Intel Software |access-date=18 January 2020 |date=1 October 2019}}</ref>

* एएचए 361-पीसीआई/एएचए362-पीसीआई एक्स [http://www.aha.com/ कॉमटेक एएचए] से {{Webarchive|url=https://web.archive.org/web/20061208005415/http://www.aha.com/ |date=2006-12-08 }}. कॉमटेक ने एक [[पीसीआई-एक्स]] कार्ड (पीसीआई-आईडी) तैयार किया: <code>193f:0001</code>) आने वाले इनकंप्रेसिब्ल डेटा के लिए 3.0 जीबी/एस (375 एमबी/एस) तक की दर पर डिफ्लेट का उपयोग करके स्ट्रीम को कंप्रेस्ड करने में सक्षम है। AHA361-PCIX के लिए [[लिनक्स (कर्नेल)]] [[डिवाइस ड्राइवर]] के साथ एक है<code>ahagzip</code>उपयोगिता और अनुकूलित<code>mod_डिफ्लेट_aha</code>[[अपाचे HTTP सर्वर]] से हार्डवेयर कम्प्रेशन का उपयोग करने में सक्षम। हार्डवेयर [[Xilinx]] Virtex ([[FPGA]]) FPGA और चार कस्टम AHA3601 एप्लिकेशन-विशिष्ट एकीकृत सर्किट पर आधारित है। AHA361/AHA362 बोर्ड केवल स्टेटिक हफ़मैन ब्लॉकों को संभालने तक ही सीमित हैं और समर्थन जोड़ने के लिए सॉफ़्टवेयर को संशोधित करने की आवश्यकता होती है - कार्ड पूर्ण डिफ्लेट विनिर्देश का समर्थन करने में सक्षम नहीं थे, जिसका अर्थ है कि वे केवल अपने स्वयं के आउटपुट को विश्वसनीय रूप से डीकोड कर सकते हैं (एक स्ट्रीम जिसमें कोई डायनामिक हफ़मैन प्रकार 2 ब्लॉक सम्मिलित नहीं थे)।

* [http://www.dranetworks.com/SC300.html StorCompress 300]/[http://www.dranetworks.com/SCMX3.html MX3] [http://www.dranetworks.com/ इंद्रा नेटवर्क्स] से। यह [[पीसीआई लोकल बस]] की एक श्रृंखला है (पीसीआई-आईडी: <code>17b4:0011</code>) या PCI-X कार्ड जिसमें एक से छह कम्प्रेशन इंजन होते हैं जिनकी प्रोसेसिंग गति 3.6 Gbit/s (450 MB/s) तक होने का दावा किया जाता है। कार्ड का एक संस्करण अलग ब्रांड WebEnhance के साथ उपलब्ध है जो विशेष रूप से [[संरक्षण क्षेत्र नियंत्रण कार्य]] या बैकअप उपयोग के बजाय वेब-सर्विंग उपयोग के लिए डिज़ाइन किया गया है; एक [[PCIe]] संशोधन, [http://www.indanetworks.com/SCMX4E.html MX4E] भी तैयार किया गया है।

* [https://web.archive.org/web/20080912222617/http://www.aha.com/show_prod.php?id=36 AHA363-PCIe]/[https://web.archive.org/web/20090212202014/http://www.aha.com/show_prod.php?id=37 AHA364-PCI e]/[https://web.archive.org/web/20090820184941/http://www.aha.com/show_prod.php?id=38 AHA367-PCIe]। 2008 में, कॉमटेक ने दो PCIe कार्ड का उत्पादन शुरू किया (<code>PCI-ID: 193f:0363</code>/<code>193f:0364</code>) एक नए हार्डवेयर AHA3610 एनकोडर चिप के साथ। नई चिप को निरंतर 2.5 Gbit/s में सक्षम होने के लिए डिज़ाइन किया गया था। इनमें से दो चिप्स का उपयोग करके, AHA363-PCIe बोर्ड दो चैनलों (दो कम्प्रेशन और दो डीकंप्रेसन) का उपयोग करके 5.0 Gbit/s (625 MB/s) तक की दर पर डिफ्लेट को संसाधित कर सकता है। AHA364-PCIe वैरिएंट आउट-गोइंग [[ भार संतुलन ]]्स के लिए डिज़ाइन किए गए कार्ड का एक एन्कोड-केवल संस्करण है और इसके बजाय दो भौतिक कम्प्रेशन इंजनों को खिलाने वाले 32 स्वतंत्र वर्चुअल कम्प्रेशन चैनलों की अनुमति देने के लिए कई रजिस्टर सेट हैं। लिनक्स, [[ माइक्रोसॉफ़्ट विंडोज़ ]] और [[ ओपनसोलर ]] कर्नेल डिवाइस ड्राइवर संशोधित zlib सिस्टम लाइब्रेरी के साथ दोनों नए कार्डों के लिए उपलब्ध हैं ताकि डायनामिक रूप से लिंक किए गए एप्लिकेशन आंतरिक संशोधन के बिना स्वचालित रूप से हार्डवेयर समर्थन का उपयोग कर सकें। AHA367-PCIe बोर्ड (<code>PCI-ID: 193f:0367</code>) AHA363-PCIe के समान है लेकिन 10 Gbit/s (1250 MB/s) की निरंतर कम्प्रेशन दर के लिए चार AHA3610 चिप्स का उपयोग करता है। AHA362-PCIX के विपरीत, AHA363-PCIe और AHA367-PCIe बोर्ड पर डीकंप्रेसन इंजन पूरी तरह से डिफ्लेट के अनुरूप हैं।

* [https://github.com/tomtor/HDL-deflate HDL-डिफ्लेट] जीपीएल एफपीजीए कार्यान्वयन।

*[https://www.cast-inc.com/compression/gzip-losless-data-compression/zipaccel-c/ ZipAccel-C] से [https://www.cast-inc.com/ CAST Inc]। यह एक सिलिकॉन आईपी कोर है जो डिफ्लेट, ज़लिब और जीज़िप कम्प्रेशन का समर्थन करता है। ZipAccel-C को एप्लिकेशन-विशिष्ट एकीकृत सर्किट या [[क्षेत्र में प्रोग्राम की जा सकने वाली द्वार श्रंखला]] में कार्यान्वित किया जा सकता है, जो डायनेमिक और स्टेटिक हफ़मैन टेबल दोनों का समर्थन करता है, और 100Gbps से अधिक थ्रूपुट प्रदान कर सकता है। कंपनी Intel FPGA ([https://www.cast-inc.com/compression/gzip-losless-data-compression/gzip-rd-int/ ZipAccel-RD-INT]) के लिए कंप्रेशन/डीकंप्रेसन एक्सेलेरेटर बोर्ड संदर्भ डिज़ाइन प्रदान करती है। और Xilinx FPGAs ([https://www.cast-inc.com/compression/gzip-losless-data-compression/gzip-rd-xil/ ZipAccel-RD-XIL])।

* Intel [[Xeon]] E5-2600 और E5-2400 प्रोसेसर सीरीज (सैंडी ब्रिज-EP/EN) के लिए Intel Xeon चिपसेट (केव क्रीक) QuickAssist Technology का उपयोग करके हार्डवेयर कम्प्रेशन और डीकंप्रेसन का समर्थन करता है। चिपसेट के आधार पर, 5Gbit/s, 10Gbit/s, या 20Gbit/s की कम्प्रेशन और डीकंप्रेसन दरें उपलब्ध हैं।<ref name="quickassist">{{cite web

* IBM z15 (माइक्रोप्रोसेसर) CPU में RFC1951 द्वारा निर्दिष्ट हार्डवेयर डिफ्लेट कम्प्रेशन और डीकंप्रेसन के लिए z14 सिस्टम में उपयोग किए जाने वाले zEDC एक्सप्रेस I/O विस्तार कार्ड से नेस्ट एक्सेलेरेटर यूनिट (NXU) हार्डवेयर त्वरण का एक उन्नत संस्करण सम्मिलित है।&