डिफ्लेट: 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 की डुप्लिकेट बनाई जा सकती है।

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

=== बिट कमी ===

{{main article|Huffman coding}}

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

एक ट्री बनाया गया है, जिसमें 288 प्रतीकों के लिए जगह है:

* 0-255: शाब्दिक बाइट्स/प्रतीकों 0-255 का प्रतिनिधित्व करें।

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

=== डिफ्लेट64/उन्नत डिफ्लेट ===

PKWARE द्वारा निर्दिष्ट Deflate64, Deflate का एक मालिकाना संस्करण है। यह मूल रूप से वही एल्गोरिदम है। जो परिवर्तन हुआ है वह है शब्दकोश का आकार 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> इसके कारण Deflate64 का कम्प्रेशन समय लंबा हो जाता है, और संभावित रूप से Deflate की तुलना में थोड़ा अधिक कम्प्रेशन अनुपात होता है।<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> कई मुफ़्त और/या ओपन सोर्स प्रोजेक्ट्स Deflate64 का समर्थन करते हैं, जैसे [[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] का उपयोग कर सकते हैं।

 

 

* एएचए 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_deflate_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-Deflate] जीपीएल एफपीजीए कार्यान्वयन।

*[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])।