डिफ्लेट: Difference between revisions

{{About|the data compression algorithm||Deflation (disambiguation)}}

{{More citations needed|date=January 2009}}

काट्ज़ ने डिफ्लेट स्ट्रीम के निर्माण के लिए उपयोग किए जाने वाले मूल एल्गोरिदम को भी डिज़ाइन किया। यह एल्गोरिदम [[सॉफ्टवेयर पेटेंट]] के रूप में था {{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" />इससे इसका व्यापक उपयोग हुआ - उदाहरण के लिए, जिप (फ़ाइल प्रारूप) फ़ाइल प्रारूप के अलावा, जी[[ gzip ]] संपीड़ित फ़ाइलों और [[ पोर्टेबल नेटवर्क ग्राफ़िक्स ]] छवि फ़ाइलों में, जिसके लिए कैटज़ ने मूल रूप से इसे डिज़ाइन किया था। पेटेंट अब समाप्त हो चुका है।

== स्ट्रीम प्रारूप ==

डिफ्लेट स्ट्रीम में ब्लॉकों की एक श्रृंखला होती है। प्रत्येक ब्लॉक के पहले 3-[[ अंश ]] हेडर होता है:

** <code>1</code>: यह धारा का अंतिम ब्लॉक है।

** <code>00</code>: एक संग्रहीत (उर्फ कच्चा या शाब्दिक) अनुभाग, लंबाई में 0 और 65,535 बाइट्स के बीच

** <code>01</code>: आरएफसी में परिभाषित पूर्व-सहमत हफमैन पेड़ का उपयोग करके एक स्थिर हफमैन संपीड़ित ब्लॉक

** <code>10</code>: एक गतिशील हफ़मैन संपीड़ित ब्लॉक, आपूर्ति की गई हफ़मैन तालिका के साथ पूर्ण

** <code>11</code>: आरक्षित—उपयोग न करें।

संग्रहीत ब्लॉक विकल्प न्यूनतम ओवरहेड जोड़ता है और उस डेटा के लिए उपयोग किया जाता है जो असम्पीडित है।

अधिकांश संपीड़ित डेटा अंततः विधि का उपयोग करके एन्कोड किया जाएगा <code>10</code>, गतिशील हफ़मैन एन्कोडिंग, जो व्यक्तिगत रूप से डेटा के प्रत्येक ब्लॉक के लिए अनुकूलित एक अनुकूलित हफ़मैन ट्री तैयार करता है। आवश्यक हफ़मैन ट्री उत्पन्न करने के निर्देश तुरंत ब्लॉक हेडर का पालन करें। स्थैतिक हफ़मैन विकल्प का उपयोग छोटे संदेशों के लिए किया जाता है, जहां पेड़ को हटाकर प्राप्त की गई निश्चित बचत गैर-इष्टतम (इस प्रकार, तकनीकी रूप से हफ़मैन नहीं) कोड का उपयोग करने के कारण प्रतिशत संपीड़न हानि से अधिक होती है।

संपीड़न दो चरणों के माध्यम से प्राप्त किया जाता है:

* उपयोग की आवृत्ति के आधार पर प्रतीकों को नए, भारित प्रतीकों से बदलना।

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

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

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

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

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

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

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

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

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

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>

 

 

* 7-ज़िप: सी++ में इगोर पावलोव द्वारा लिखित, यह संस्करण स्वतंत्र रूप से लाइसेंस प्राप्त है और सीपीयू उपयोग की कीमत पर zlib की तुलना में उच्च संपीड़न प्राप्त करता है। DEFLATE64 संग्रहण प्रारूप का उपयोग करने का विकल्प है।

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

* रेड गेट सॉफ्टवेयर#हाइपरबैक: DEFLATE64 स्टोरेज फॉर्मेट को लागू करने के विकल्प के साथ अपनी स्वयं की मालिकाना संपीड़न लाइब्रेरी (C++ और असेंबली में) का उपयोग करता है

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

* igzip: [[x86 असेंबली भाषा]] में लिखा गया एक एनकोडर, जो MIT लाइसेंस के तहत [[इंटेल]] द्वारा जारी किया गया है। 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>

AdvanceCOMP 7-ज़िप, लिबडेफ्लेट और ज़ोपफ्ली में डिफ्लेट के उच्च संपीड़न अनुपात संस्करणों का उपयोग करता है ताकि जीज़िप की तुलना में छोटे फ़ाइल आकार की संभावना के साथ जीज़िप, पोर्टेबल नेटवर्क ग्राफिक्स, [[ मल्टीपल-इमेज नेटवर्क ग्राफ़िक्स ]] और ज़िप फ़ाइल प्रारूप फ़ाइलों के पुनर्संपीड़न को सक्षम किया जा सके। अधिकतम सेटिंग्स पर प्राप्त करें।<ref>{{cite web |last1=Mazzoleni |first1=Andrea |title=amadvance/advancecomp |website=[[GitHub]] |url=https://github.com/amadvance/advancecomp/blob/fcf71a89265c78fc26243574dda3a872574a5c02/doc/advzip.txt |date=21 February 2023}}</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_deflate_aha</code>[[अपाचे HTTP सर्वर]] से हार्डवेयर संपीड़न का उपयोग करने में सक्षम। हार्डवेयर [[Xilinx]] Virtex ([[FPGA]]) FPGA और चार कस्टम AHA3601 एप्लिकेशन-विशिष्ट एकीकृत सर्किट पर आधारित है। AHA361/AHA362 बोर्ड केवल स्थिर हफ़मैन ब्लॉकों को संभालने तक ही सीमित हैं और समर्थन जोड़ने के लिए सॉफ़्टवेयर को संशोधित करने की आवश्यकता होती है - कार्ड पूर्ण डिफ्लेट विनिर्देश का समर्थन करने में सक्षम नहीं थे, जिसका अर्थ है कि वे केवल अपने स्वयं के आउटपुट को विश्वसनीय रूप से डीकोड कर सकते हैं (एक स्ट्रीम जिसमें कोई गतिशील हफ़मैन प्रकार 2 ब्लॉक शामिल नहीं थे)।

* [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://web.archive.org/web/20101203144755/http://www.cavium.com/processor_security_nitrox-III.html Nitrox] और [https://github.com/zerix/Cavium-SDK-2.0 /पेड़/मास्टर/उदाहरण/ज़िप ऑक्टियन]{{Dead link|date=November 2019 |bot=InternetArchiveBot |fix-attempted=yes }} [http://cavium.com कैवियम, इंक.] के प्रोसेसर में ZLIB और GZIP दोनों के साथ संगत हाई-स्पीड हार्डवेयर डिफ्लेट और इनफ्लेट इंजन होते हैं, साथ ही कुछ डिवाइस एक साथ कई डेटा स्ट्रीम को संभालने में सक्षम होते हैं।

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