Deflate

📅 آخر تحديث: ٣ أغسطس ٢٠٢٦
✍️ نُشر في: ٣ أغسطس ٢٠٢٦
📷 يحتوي على 1 صور
الموسوعة الحرة

In computing, Deflate (stylized as DEFLATE, and also called Flate[1][2]) is a lossless data compression algorithm[a] that uses a combination of LZ77 and Huffman coding. It was designed by Phil Katz, for version 2 of his PKZIP archiving tool. Deflate was later specified in Request for Comments (RFC) 1951 (1996).[4]

Katz also designed the original algorithm used to construct Deflate streams. This algorithm received software patentU.S. patent 5,051,745, assigned to PKWare, Inc.[5][6] As stated in the RFC document, an algorithm producing Deflate files was widely thought to be implementable in a manner not covered by patents.[4] This led to its widespread use. For example, in the zlib data format, gzip file format, Portable Network Graphics (PNG) image file, ZIP file format for which Katz originally designed it. The patent has since expired.

Block structure

Deflate compression takes any sequence of bytes and outputs a sequence of blocks (commonly called Deflate stream). Deflate decompression takes a sequence of blocks and outputs the original sequence of bytes.

Endianness is little-endian. Bit 0 is the least significant bit in a byte.[7]

Each block has a 3-bit header with two fields:[8]

  • BFINAL (first bit): 1 if this is the last block in the sequence, else 0.
  • BTYPE (next two bits): Block type
    • 00: No compression (sometimes called stored). Any bits up to the next byte boundary are ignored. The rest of the block consists of 16-bit LEN, 16-bit NLEN (one's complement of LEN), and LEN bytes of uncompressed data, i.e. up to 65,535 (216 − 1) bytes. Useful for incompressible data (e.g. high-entropy, random, or already compressed), adding minimal overhead (i.e. ~5 bytes per block).
    • 01: كتلة مضغوطة ثابتة من نوع هوفمان ، باستخدام شجرة هوفمان متفق عليها مسبقًا ومحددة في RFC.
    • 10: كتلة هوفمان المضغوطة الديناميكية، كاملة مع جدول هوفمان المرفق.
    • 11: محجوز (خطأ).

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

يتم تحقيق الضغط من خلال خطوتين:

  • مطابقة واستبدال السلاسل المكررة بالمؤشرات
  • استبدال الرموز برموز جديدة موزونة بناءً على تكرار الاستخدام

إزالة السلاسل المكررة

في الكتل المضغوطة، إذا تم رصد سلسلة بايتات مكررة (سلسلة متكررة)، يتم إدراج مرجع خلفي يربط بالموقع السابق لتلك السلسلة المطابقة. تتكون المطابقة المشفرة لسلسلة سابقة من طول 8 بت (من 3 إلى 258 بايت) ومسافة 15 بت (من 1 إلى 32768 بايت) إلى بداية السلسلة المكررة. يمكن إنشاء مراجع خلفية نسبية عبر أي عدد من الكتل، طالما أن المسافة تظهر ضمن آخر 32 كيلوبايت من البيانات غير المضغوطة التي تم فك تشفيرها (وتسمى النافذة المنزلقة ). 

إذا كانت المسافة أقل من الطول، فإن النسخة المكررة تتداخل مع نفسها، مما يشير إلى التكرار. على سبيل المثال، يمكن ترميز سلسلة من 10 بايتات متطابقة كبايت واحد، متبوعًا بنسخة مكررة طولها 9، تبدأ بالبايت السابق.

يعد البحث في النص السابق عن السلاسل الفرعية المكررة الجزء الأكثر تكلفة حسابيًا في خوارزمية Deflate، وهي العملية التي تؤثر عليها إعدادات مستوى الضغط.

تقليل البت

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

يتم إنشاء شجرة تحتوي على مساحة لـ 288 رمزًا:

  • 0–255: تمثل البايتات/الرموز الحرفية 0–255.
  • 256: نهاية الكتلة - توقف عن المعالجة إذا كانت الكتلة الأخيرة، وإلا فابدأ معالجة الكتلة التالية.
  • 257–285: بالإضافة إلى البتات الإضافية، طول المطابقة من 3 إلى 258 بايت.
  • 286، 287: غير مستخدمة، محجوزة وغير قانونية ولكنها لا تزال جزءًا من الشجرة.

سيتبع رمز طول التطابق دائمًا رمز المسافة. وبناءً على رمز المسافة المقروء، قد تُقرأ بتات إضافية لحساب المسافة النهائية. تحتوي شجرة المسافة على مساحة لـ 32 رمزًا.

  • 0–3: المسافات 1–4
  • 4-5: المسافات من 5 إلى 8، بت إضافي واحد
  • 6-7: المسافات 9-16، بتّان إضافيان
  • 8-9: المسافات من 17 إلى 32، 3 بتات إضافية
  • ...
  • 26-27: المسافات من 8193 إلى 16384، 12 بت إضافي
  • 28-29: المسافات من 16385 إلى 32768، 13 بت إضافي
  • 30-31: غير مستخدم، ومحجوز وغير قانوني ولكنه لا يزال جزءًا من الشجرة

بالنسبة لرموز مسافة المطابقة من 2 إلى 29، يمكن حساب عدد البتات الإضافية على النحو التالي:⌊ن2⌋-1{\displaystyle \left\lfloor {\frac {n}{2}}\right\rfloor -1}.

يتم ترميز الرمزين (شجرة طول الرمز 288 رمزًا/الرمز الحرفي وشجرة المسافة 32 رمزًا) باستخدام رموز هوفمان القياسية ، وذلك بتحديد طول الرمز لكل رمز. ويتم ترميز أطوال الرموز بدورها باستخدام ترميز طول التشغيل لإنتاج تمثيل مضغوط قدر الإمكان. وكبديل لتضمين تمثيل الشجرة، يوفر خيار "الشجرة الثابتة" أشجار هوفمان ثابتة قياسية. ويمكن حساب حجم الملف المضغوط باستخدام الأشجار الثابتة باستخدام نفس الإحصائيات (عدد مرات ظهور كل رمز) المستخدمة لإنشاء الأشجار الديناميكية، مما يسهل على برنامج الضغط اختيار الأصغر.

جهاز التشفير والضغط

خلال مرحلة الضغط، يحدد المُشفِّر مقدار الوقت المُستغرق في البحث عن السلاسل المتطابقة. يسمح تطبيق zlib/gzip المرجعي للمستخدم بالاختيار من بين خيارات متدرجة لمستوى الضغط المُحتمل مقابل سرعة التشفير. تتراوح الخيارات من 0(عدم محاولة الضغط، وتخزين البيانات غير مضغوطة فقط) إلى 9تمثيل أقصى قدرة للتطبيق المرجعي في zlib/gzip.

تم إنتاج مُشفِّرات Deflate أخرى، جميعها تُنتج دفق بتات متوافقًا يُمكن فك ضغطه بواسطة أي مُفكِّك Deflate موجود. من المُرجَّح أن تُنتج التطبيقات المُختلفة اختلافات في دفق البتات المُشفَّر النهائي. عادةً ما يكون التركيز في إصدارات المُشفِّر غير المُعتمدة على zlib هو إنتاج دفق مُشفَّر أصغر حجمًا وأكثر كفاءة في الضغط.

Deflate64

Deflate64, specified by PKWARE, is a proprietary variant of Deflate. It's fundamentally the same algorithm. What has changed is the increase in dictionary size from 32 KB to 64 KB, an extension of the distance codes to 16 bits so that they may address a range of 64 KB, and the length code, which is extended to 16-bit, so that it may define lengths of three to 65,538 bytes.[9] This leads to Deflate64 having a longer compression time, and potentially a slightly higher compression ratio, than Deflate.[10] Several free and/or open source projects support Deflate64, such as 7-Zip,[11] while others, such as zlib, do not, because the procedure is proprietary,[12] and the performance increase over Deflate is small.[13]

Using Deflate in new software

Implementations of Deflate are freely available in many languages. Apps written in C typically use the zliblibrary (under the permissive zlib License). Apps in Borland Pascal (and compatible languages) can use paszlib. Apps in C++ can take advantage of the improved Deflate library in 7-Zip. Both Java and .NET framework offer out-of-the-box support for Deflate in their libraries (respectively, java.util.zip and System.IO.Compression). Apps in Ada can use Zip-Ada (pure) or ZLib-Ada.

Encoder implementations

  • PKZIP: the first implementation, originally done by Phil Katz as part of PKZip
  • zlib: standard reference implementation adopted in many apps because of its open-source, permissive license. See Zlib § Forks for higher-performance forks.
  • Crypto++: contains a public-domain implementation in C++ aimed at reducing potential security vulnerabilities. The author, Wei Dai states "This code is less clever, but hopefully more understandable and maintainable [than zlib]".
  • 7-Zip: written by Igor Pavlov in C++, this version is freely licensed and achieves higher compression than zlib at the expense of central processing unit (CPU) use. Has an option to use the Deflate64 storage format.
  • PuTTY 'sshzlib.c': تطبيق مستقل مرخص بموجب رخصة MIT من تطوير سيمون تاتام، يتمتع بقدرة فك تشفير كاملة، ولكنه يدعم فقط إنشاء شجرة ثابتة.
  • libflate: [ 14 ] جزء من مشروع Plan 9 من مختبرات Bell ، يُنفذ ضغط deflate
  • يستخدم برنامج Hyperbac مكتبة ضغط خاصة به (مكتوبة بلغة C++ ولغة التجميع) مع خيار لتطبيق تنسيق التخزين Deflate64
  • Zopfli : تطبيق مكتوب بلغة C مرخص من قبل جوجل بموجب رخصة أباتشي ؛ يحقق ضغطًا أعلى على حساب استهلاك وحدة المعالجة المركزية. ZopfliPNG هو نسخة معدلة من Zopfli مخصصة لملفات PNG .
  • igzip: برنامج تشفير مكتوب بلغة التجميع x86 ، أصدرته شركة إنتل بموجب ترخيص MIT . أسرع بثلاث مرات من zlib-1. مفيد لضغط البيانات الجينومية. [ 15 ]
  • libdeflate: [ 16 ] مكتبة لضغط وفك ضغط البيانات باستخدام تقنية Deflate بسرعة عالية وعلى كامل المخزن المؤقت. تم تحسين أداء libdeflate بشكل كبير، خاصةً على معالجات x86.

يستخدم برنامج AdvanceCOMP إصدارات ذات نسبة ضغط أعلى من برنامج Deflate في برامج 7-Zip و libdeflate وZopfli لتمكين إعادة ضغط ملفات gzip و PNG ورسومات الشبكة متعددة الصور (MNG) وملفات ZIP مع إمكانية الحصول على أحجام ملفات أصغر مما يمكن لبرنامج zlib تحقيقه عند أعلى الإعدادات. [ 17 ]

أجهزة التشفير

  • بطاقة AHA361-PCIX/AHA362-PCIX من شركة Comtech AHA، مؤرشفة بتاريخ 8 ديسمبر 2006 على موقع Wayback Machine . أنتجت Comtech بطاقة PCI-X (معرف PCI: 193f:0001) قادرة على ضغط البيانات باستخدام Deflate بمعدل يصل إلى 3.0  جيجابت/ثانية (375  ميجابايت/ثانية) للبيانات الواردة غير المضغوطة. يُرفق ببرنامج تشغيل نواة Linux الخاص ببطاقة AHA361-PCIX أداة مساعدة وبرنامجًا مخصصًا قادرًا على استخدام ضغط الأجهزة من Apache . يعتمد الجهاز على مصفوفة بوابات قابلة للبرمجة ميدانيًا (FPGA) من Xilinx Virtex وأربع دوائر متكاملة مخصصة للتطبيقات (ASICs) من نوع AHA3601. تقتصر بطاقات AHA361/AHA362 على معالجة كتل Huffman الثابتة فقط، وتتطلب تعديلًا برمجيًا لإضافة الدعم. لم تتمكن البطاقات من دعم مواصفات Deflate الكاملة، مما يعني أنها لم تستطع فك تشفير مخرجاتها بشكل موثوق إلا (وهو دفق لا يحتوي على أي كتل ديناميكية من نوع Huffman 2).ahagzipmod_deflate_aha
  • بطاقة StorCompress 300 / MX3 من شركة Indra Networks . وهي عبارة عن مجموعة من بطاقات PCI أو PCI-X، مزودة بمحرك ضغط واحد إلى ستة محركات، وبسرعات معالجة تصل إلى 3.6 جيجابت/ثانية (450 ميجابايت/ثانية). يتوفر إصدار من هذه البطاقات تحت العلامة التجارية WebEnhance، وهو مصمم خصيصًا للاستخدام في خوادم الويب، وليس في شبكات التخزين (SAN) أو النسخ الاحتياطي. كما يتوفر إصدار MX4E بتقنية PCI Express (PCIe) .17b4:0011  
  • AHA363-PCIe / AHA364-PCIe / AHA367-PCIe . في عام 2008، بدأت شركة Comtech بإنتاج بطاقتي PCIe مزودتين PCI-ID: 193f:0363بشريحة 193f:0364تشفير AHA3610 جديدة. صُممت هذه الشريحة الجديدة لتوفير سرعة نقل بيانات مستدامة تبلغ 2.5  جيجابت/ثانية. باستخدام شريحتين من هذه الشريحة، تستطيع بطاقة AHA363-PCIe معالجة بيانات Deflate بسرعة تصل إلى 5.0  جيجابت/ثانية (625  ميجابايت/ثانية) باستخدام قناتين (قناتان للضغط وقناتان لفك الضغط). أما بطاقة AHA364-PCIe فهي نسخة مخصصة للتشفير فقط، مصممة لموازنات الأحمال الخارجية ، وتحتوي على مجموعات سجلات متعددة تسمح بـ 32 قناة ضغط افتراضية مستقلة تغذي محركي ضغط فعليين. تتوفر برامج تشغيل الأجهزة لأنظمة Linux و Microsoft Windows و OpenSolaris لكلا البطاقتين الجديدتين، بالإضافة إلى مكتبة نظام zlib مُعدلة، بحيث يمكن للتطبيقات المرتبطة ديناميكيًا استخدام دعم الأجهزة تلقائيًا دون الحاجة إلى تعديل داخلي. PCI-ID: 193f:0367تُشبه لوحة AHA367-PCIe لوحة AHA363-PCIe، لكنها تستخدم أربع رقاقات AHA3610 لتحقيق معدل ضغط مستدام يبلغ 10  جيجابت/ثانية (1250  ميجابايت/ثانية). وعلى عكس لوحة AHA362-PCIX، فإن محركات فك الضغط في لوحتي AHA363-PCIe وAHA367-PCIe متوافقة تمامًا مع معيار deflate.
  • تحتوي معالجات Nitrox و Octeon من شركة Cavium, Inc. على محركات ضغط وتفريغ عالية السرعة متوافقة مع كل من ZLIB و GZIP مع بعض الأجهزة القادرة على التعامل مع تدفقات بيانات متعددة في وقت واحد.
  • تطبيق HDL-Deflate GPL على FPGA.
  • ZipAccel-C from CAST Inc. This is a Silicon IP core supporting Deflate, Zlib and Gzip compression. ZipAccel-C can be implemented in ASIC or field-programmable gate array (FPGAs), supports both Dynamic and Static Huffman tables, and can provide throughputs in excess of 100 Gbit/s. The company offers compression/decompression accelerator board reference designs for Intel FPGA (ZipAccel-RD-INT) and Xilinx FPGAs (ZipAccel-RD-XIL).
  • Intel Communications Chipset 89xx Series (Cave Creek) for the IntelXeon E5-2600 and E5-2400 Processor Series (Sandy Bridge-EP/EN) supports hardware compression and decompression using QuickAssist Technology. Depending on the chipset, compression and decompression rates of 5 Gbit/s, 10 Gbit/s, or 20 Gbit/s are available.[18]
  • IBM z15 CPUs incorporate an improved version of the Nest Accelerator Unit (NXU) hardware acceleration from the zEDC Express input/output (I/O) expansion cards used in z14 systems for hardware Deflate compression and decompression as specified by RFC1951.[19][20]
  • Starting with the POWER9 architecture, IBM added hardware support for compressing and decompressing Deflate (as specified by RFC 1951) to the formerly crypto-centric Nest accelerator (NX) core introduced with POWER7+. This support is available to programs running with AIX 7.2 Technology Level 4 Expansion Pack or AIX 7.2 Technology Level 5 Service Pack 2 through the zlibNX library.[21][22]

Decoder, decompressor

Inflate is the decoding process that takes a Deflate bitstream for decompression and correctly produces the original full-size data or file.

Inflate-only implementations

The normal intent with an alternative Inflate implementation is highly optimized decoding speed, or extremely predictable random-access memory (RAM) use for microcontrollerembedded systems.

أجهزة فك التشفير المادية

  • Serial Inflate GPU from BitSim. Hardware implementation of Inflate. Part of the Bitsim Accelerated Display Graphics Engine (BADGE) controller offering for embedded systems.
  • HDL-Deflate GPL FPGA implementation.
  • ZipAccel-D from CAST Inc. This is a Silicon IP core supporting decompression of Deflate, Zlib and Gzip files. The ZipAccel-D IP core that can be implemented in ASIC or FPGAs. The company offers compression/decompression accelerator board reference designs for Intel FPGA (ZipAccel-RD-INT) and Xilinx FPGAs (ZipAccel-RD-XIL).
  • IBM z15 CPUs incorporate an improved version of the Nest Accelerator Unit (NXU) hardware acceleration from the zEDC Express input/output (I/O) expansion cards used in z14 systems for hardware Deflate compression and decompression as specified by RFC1951.[19][20]
  • Starting with the POWER9 architecture, IBM added hardware support for compressing and decompressing Deflate (as specified by RFC 1951) to the formerly crypto-centric Nest accelerator (NX) core introduced with POWER7+. This support is available to programs running with AIX 7.2 Technology Level 4 Expansion Pack or AIX 7.2 Technology Level 5 Service Pack 2 through the zlibNX library.[21][22]

See also

Notes

  1. ↑Deflate is widely referenced as a compression algorithm, even though the specification (RFC 1951) defines it as a "data format". For example, the CompressionStream Web API specification uses the term "The DEFLATE algorithm".[3] In practice, the data format is the output of the algorithm, so neither definition is wrong.

References

  1. ↑The Go Authors. "flate package - compress/flate - Go Packages". The Go Programming Language. Google. Retrieved 5 September 2023. Package flate implements the Deflate compressed data format, described in RFC issue 1951.
  2. ↑"PDF 32000-1:2008: Document management — Portable document format — Part 1: PDF 1.7"(PDF). Adobe Open Source. Adobe Inc. p. 23. Retrieved 5 September 2023. FlateDecode [...] Decompresses data encoded using the zlib/deflate compression method
  3. ↑ "التنسيقات المدعومة" . ضغط WHATWG .
  4. 1 2 دويتش، ل. بيتر (مايو 1996). مواصفات تنسيق البيانات المضغوطة Deflate، الإصدار 1.3 . فريق عمل هندسة الإنترنت (IETF). ص 1. القسم 1. ملخص. doi : 10.17487/RFC1951 . RFC 1951. تاريخ الاسترجاع : 23 أبريل 2014 .   
  5. ↑ براءة اختراع أمريكية رقم 5051745 ، كاتز، فيليب دبليو ، "باحث عن السلاسل، وضاغط يستخدم نفس الشيء"، نُشرت في 24-09-1991، صدرت في 24-09-1991، مُخصصة لشركة PKWare Inc. 
  6. ↑ سالومون، ديفيد (2007). ضغط البيانات: المرجع الكامل ( الطبعة الرابعة). سبرينغر. ص 241. ISBN   978-1-84628-602-5.
  7. ↑ الاتفاقيات العامة . IETF . ص 5. doi : 10.17487/RFC1951 . RFC 1951 . 
  8. ↑ تفاصيل تنسيق الكتلة . IETF . ص 9. doi : 10.17487/RFC1951 . RFC 1951 . 
  9. ↑ "الجوهر الثنائي - Deflate64" . مؤرشف من الأصل في 21 يونيو 2017. تم الاطلاع عليه في 22 مايو 2011 .{{cite web}}: CS1 maint: bot: حالة عنوان URL الأصلي غير معروفة ( رابط )
  10. ↑ "مقارنات ضغط Binary Essence – "Calgary Corpus"" . مؤرشف من الأصل في 27 ديسمبر 2017. تم الاطلاع عليه في 22 مايو 2011 .{{cite web}}: CS1 maint: bot: حالة عنوان URL الأصلي غير معروفة ( رابط )
  11. ↑ "-m (تعيين طريقة الضغط) مفتاح" . sevenzip.osdn.jp . مؤرشف من الأصل بتاريخ 2022-04-09 . تم الاسترجاع بتاريخ 2023-01-21 .
  12. ↑ تاريخ خوارزميات ضغط البيانات بدون فقدان البيانات – Deflate64
  13. ↑ الأسئلة الشائعة حول zlib – هل يدعم zlib تنسيق "Deflate64" الجديد الذي قدمته PKWare؟
  14. ↑ "خطة 9 من /n/sources/plan9/sys/src/libflate" من مختبرات بيل . plan9.bell-labs.com . شركة لوسنت تكنولوجيز. مؤرشف من الأصل بتاريخ 15 مارس 2006.
  15. ↑ "ضغط Deflate عالي الأداء مع تحسينات لمجموعات البيانات الجينومية" . برمجيات إنتل . 1 أكتوبر 2019. تم الاطلاع عليه في 18 يناير 2020 .
  16. ↑ "libdeflate" . مكتبة مُحسَّنة للغاية لضغط وفك ضغط DEFLATE/zlib/gzip .
  17. ^ مازوليني ، أندريا (21 فبراير 2023). "أمادفانس/أدفانسكومب" . جيثب .
  18. ↑ "معالجات Intel Xeon من سلسلة E5-2600 وE5-2400 مع مجموعة شرائح الاتصالات Intel من سلسلة 89xx" . تم الاطلاع عليه بتاريخ 18 مايو 2016 .
  19. 1 2 "تقديم IBM z15 - منصة المؤسسات للحوسبة السحابية الهجينة متعددة السحابات ذات المهام الحرجة" . IBM . 12 سبتمبر 2019. تم الاطلاع عليه بتاريخ 1 نوفمبر 2021 .
  20. 1 2 لاسكو، أوكتافيان (28 أبريل 2021). الدليل التقني لجهاز IBM z15 (8562)، الصفحة 97. منشورات IBM Redbooks. ISBN 9780738458991تم الاطلاع عليه بتاريخ 2021-11-01 .
  21. 1 2 "ضغط البيانات باستخدام مكتبة zlibNX - وثائق IBM" . IBM . تم الاطلاع عليه بتاريخ 1 نوفمبر 2021 .
  22. 1 2 "استغلال التسريع الداخلي لمعالجات POWER لنظام AIX" . تم الاطلاع عليه بتاريخ 2021-11-01 .