söndür - Deflate

Bu makale, veri sıkıştırma algoritması ile ilgili. Başlığın diğer anlamları için bkz Deflasyon (anlam ayrım) .

Olarak işlem , Deflate a, kayıpsız veri sıkıştırma dosya biçimi bir arada kullanan LZSS ve Huffman kodlama . Phil Katz tarafından PKZIP arşivleme aracının 2. sürümü için tasarlanmıştır . Söndürme daha sonra RFC 1951'de (1996) belirtildi.

Katz ayrıca Deflate akışlarını oluşturmak için kullanılan orijinal algoritmayı da tasarladı. Bu algoritma edildi patentli olarak ABD Patenti 5.051.745 ve atanan PKWARE, Inc. olarak Deflate dosyaları üreten bir algoritma yaygın patent kapsamında olmayan bir şekilde uygulanabilir olduğu düşünüldü, RFC belgesinde belirtti. Bu, Katz'ın orijinal olarak tasarladığı ZIP dosya formatına ek olarak, örneğin sıkıştırılmış gzip dosyalarında ve PNG resim dosyalarında yaygın kullanımına yol açtı . Patentin süresi dolmuştur.

Akış biçimi

Deflate akışı bir dizi bloktan oluşur. Her bloktan önce 3 bitlik bir başlık gelir:

  • İlk bit: Yayın içi son blok işaretçisi:
    • 1: Bu, akıştaki son bloktur.
    • 0: Bundan sonra işlenecek daha çok blok var.
  • İkinci ve üçüncü bitler: Bu blok türü için kullanılan kodlama yöntemi:
    • 00: 0 ila 65.535 bayt uzunluğunda depolanmış (ham veya değişmez olarak da bilinir) bir bölüm
    • 01: RFC'de tanımlanan önceden kararlaştırılmış bir Huffman ağacını kullanan statik bir Huffman sıkıştırılmış blok
    • 10: Birlikte verilen Huffman tablosuyla birlikte sıkıştırılmış bir blok
    • 11: Ayrılmış—kullanmayın.

Depolanmış blok seçeneği en az ek yük ekler ve sıkıştırılamaz olan veriler için kullanılır.

En nitelikteki veri sona erecek yöntemi kullanılarak kodlanmaktadır 10, dinamik Huffman tek tek her veri bloğu için özel bir optimize Huffman ağacı üreten kodlama. Gerekli Huffman ağacını oluşturmaya yönelik talimatlar, blok başlığını hemen takip eder. Statik Huffman seçeneği, ağacı atlayarak elde edilen sabit tasarrufun, optimal olmayan (dolayısıyla teknik olarak Huffman değil) bir kod kullanılmasından kaynaklanan yüzde sıkıştırma kaybından daha ağır bastığı kısa mesajlar için kullanılır.

Sıkıştırma iki adımda gerçekleştirilir:

  • Yinelenen dizelerin işaretçilerle eşleştirilmesi ve değiştirilmesi.
  • Sembollerin, kullanım sıklığına göre yeni, ağırlıklı sembollerle değiştirilmesi.

Bit azaltma

Ana madde: Huffman kodlaması

İkinci sıkıştırma aşaması, yaygın olarak kullanılan sembollerin daha kısa gösterimlerle ve daha az yaygın olarak kullanılan sembollerin daha uzun gösterimlerle değiştirilmesinden oluşur. Kullanılan yöntem , her bir dizinin uzunluğunun, o sembolün kodlanması gereken olasılığının logaritması ile ters orantılı olduğu, örtüşmeyen aralıkların ön eksiz bir ağacını oluşturan Huffman kodlamasıdır . Bir sembolün kodlanması ne kadar olasıysa, bit dizisi o kadar kısa olacaktır.

288 sembol için boşluk içeren bir ağaç oluşturulur:

  • 0–255: 0–255 arasındaki değişmez baytları/sembolleri temsil eder.
  • 256: blok sonu – son blok ise işlemeyi durdur, aksi takdirde sonraki bloğu işlemeye başla.
  • 257–285: ekstra bitlerle birleştirilmiş, 3–258 baytlık bir eşleşme uzunluğu.
  • 286, 287: kullanılmamış, ayrılmış ve yasa dışı ama yine de ağacın bir parçası.

Bir maç uzunluğu kodunun ardından her zaman bir mesafe kodu gelir. Okunan mesafe koduna bağlı olarak, son mesafeyi üretmek için daha fazla "ekstra" bit okunabilir. Mesafe ağacı 32 sembol için boşluk içerir:

  • 0–3: mesafeler 1–4
  • 4-5: 5-8 arası mesafeler, 1 ekstra bit
  • 6–7: 9–16 arasındaki mesafeler, 2 ekstra bit
  • 8–9: 17–32 arasındaki mesafeler, 3 ekstra bit
  • ...
  • 26–27: uzaklıklar 8.193–16.384, 12 ekstra bit
  • 28–29: mesafeler 16.385–32.768, 13 ekstra bit
  • 30–31: Kullanılmamış, ayrılmış ve yasa dışı ama yine de ağacın bir parçası.

2–29 eşleşme mesafesi sembolleri için ekstra bit sayısının şu şekilde hesaplanabileceğini unutmayın .

İki kod (288 sembol uzunluğu/harf ağacı ve 32 sembol mesafe ağacı), her bir sembol için kodun bit uzunluğunu vererek kurallı Huffman kodları olarak kodlanmıştır . Bit uzunluklarının kendileri , mümkün olduğunca kompakt bir temsil üretmek için kodlanmış çalışma uzunluğudur . Ağaç gösterimini dahil etmeye bir alternatif olarak, "statik ağaç" seçeneği, standart sabit Huffman ağaçları sağlar. Statik ağaçları kullanan sıkıştırılmış boyut, dinamik ağaçları oluşturmak için kullanılanla aynı istatistikler (her sembolün görünme sayısı) kullanılarak hesaplanabilir, bu nedenle kompresörün hangisi daha küçükse onu seçmesi kolaydır.

Yinelenen dize eleme

Ana maddeler: LZ77 ve LZ78 ve LZSS

Sıkıştırılmış bloklar içinde, yinelenen bir bayt dizisi tespit edilirse (tekrarlanan bir dize), bunun yerine aynı dizenin önceki konumuna bağlanan bir geri referans eklenir. Daha önceki bir dizeyle kodlanmış bir eşleşme, kopyanın başlangıcına 8 bitlik bir uzunluk (3–258 bayt) ve 15 bitlik bir mesafeden (1–32,768 bayt) oluşur. Mesafe, kodu çözülen sıkıştırılmamış verilerin son 32 KiB'si ( kayan pencere olarak adlandırılır ) içinde göründüğü sürece, herhangi bir sayıda blok boyunca göreceli geri referanslar yapılabilir  .

Mesafe uzunluktan daha azsa, kopya kendi kendine üst üste binerek tekrarı gösterir. Örneğin, 10 özdeş baytlık bir çalışma, bir bayt olarak kodlanabilir, ardından önceki bayttan başlayarak 9 uzunlukta bir kopya gelebilir.

Önceki metni yinelenen alt dizeler için aramak, DEFLATE algoritmasının hesaplama açısından en pahalı kısmı ve sıkıştırma düzeyi ayarlarının etkilediği işlemdir.

Enkoder/kompresör

Sıkıştırma aşaması sırasında, eşleşen dizeleri aramak için harcanan süreyi seçen kodlayıcıdır . zlib/gzip başvuru uygulaması , kullanıcının olası sonuç sıkıştırma düzeyine karşılık kodlama hızının kayan ölçeğinden seçim yapmasına olanak tanır. Seçenekler 0(sıkıştırmayı denemeyin, yalnızca sıkıştırılmamış olarak saklayın) ile 9zlib/gzip'te başvuru uygulamasının maksimum kapasitesini temsil etmeye kadar değişir .

Hepsi de mevcut herhangi bir Deflate kod çözücü tarafından sıkıştırılabilen uyumlu bir veri akışı üretecek olan başka Deflate kodlayıcıları üretilmiştir . Farklı uygulamalar, üretilen nihai kodlanmış bit akışında büyük olasılıkla varyasyonlar üretecektir. Bir kodlayıcının zlib olmayan sürümlerinin odak noktası normalde daha verimli bir şekilde sıkıştırılmış ve daha küçük kodlanmış bir akış üretmek olmuştur.

Söndür64/Gelişmiş Söndürme

PKWARE tarafından belirtilen Deflate64, Deflate'in tescilli bir çeşididir. Temelde aynı algoritma. Değişen, sözlük boyutunun 32 KB'den 64 KB'ye çıkarılması, mesafe kodlarının 64 KB aralığına hitap edebilecek şekilde 16 bit'e çıkarılması ve uzunluk kodunun 16 bit'e genişletilmesidir. üç ila 65.538 baytlık uzunlukları tanımlayabilir. Bu, Deflate64'ün Deflate'den daha uzun bir sıkıştırma süresine ve potansiyel olarak biraz daha yüksek bir sıkıştırma oranına sahip olmasına yol açar. 7-Zip gibi birkaç ücretsiz ve/veya açık kaynaklı proje Deflate64'ü desteklerken, zlib gibi diğerleri, prosedürün özel doğası ve Deflate'e göre çok mütevazı performans artışının bir sonucu olarak desteklemez.

Deflate'i yeni yazılımda kullanma

Deflate uygulamaları birçok dilde ücretsiz olarak mevcuttur. C programları tipik olarak zlib kitaplığını kullanır (hem ücretsiz hem de özel yazılımla kullanıma izin veren zlib Lisansı altında lisanslanmıştır ). Pascal'ın Borland lehçeleri kullanılarak yazılan programlar paszlib'i kullanabilir; 7-Zip / AdvanceCOMP'un bir parçası olarak bir C++ kitaplığı dahil edilmiştir . Java, standart kitaplığın bir parçası olarak desteği içerir (java.util.zip içinde). Microsoft .NET Framework 2.0 temel sınıf kitaplığı, System.IO.Compression ad alanında bunu destekler . Programlar Ada kullanabilir Posta-Ada (saf) ya da ZLib-Ada zlib bağlanma kalınlıktadır.

Enkoder uygulamaları

  • PKZIP : Phil Katz tarafından PKZip'in bir parçası olarak yapılan ilk uygulama .
  • zlib / gzip : kaynak kodunun herkese açık olması ve diğer yazılımlara dahil edilmesine izin veren bir lisans sayesinde büyük miktarda yazılımda kullanılan standart referans uygulaması.
  • Crypto++ : C++'da, temel olarak potansiyel güvenlik açıklarını azaltmayı amaçlayan bir kamu malı uygulaması içerir . Yazar Wei Dai, " Bu kod daha az akıllıdır, ancak umarım daha anlaşılır ve [zlib'den] daha sürdürülebilirdir " diyor.
  • 7-Zip / AdvanceCOMP : Igor Pavlov tarafından C++ ile yazılmıştır , bu sürüm özgürce lisanslanmıştır ve CPU kullanımı pahasına zlib'den daha yüksek sıkıştırma elde etme eğilimindedir. DEFLATE64 depolama biçimini kullanma seçeneği vardır.
  • PuTTY 'sshzlib.c': Simon Tatham tarafından tam kod çözme, ancak yalnızca statik ağaç oluşturma yeteneğine sahip bağımsız bir uygulama. MİT lisanslıdır .
  • Bell Labs işletim sisteminin libflate'sinden Plan 9, deflate sıkıştırmasını uygular.
  • Hyperbac : DEFLATE64 depolama biçimini uygulama seçeneği ile kendi tescilli kayıpsız sıkıştırma kitaplığını (C++ ve Assembly ile yazılmıştır) kullanır.
  • Zopfli : Google'ın CPU kullanımı pahasına en yüksek sıkıştırmayı sağlayan C uygulaması. ZopfliPNG ile kullanılmak üzere Zopfli bir varyasyonu PNG'ler . Apache lisanslıdır .
  • igzip, Intel tarafından MIT Lisansı altında yayınlanan x86 derlemesinde yazılmış bir kodlayıcı . zlib -1'den 3 kat daha hızlı. Genomik verileri sıkıştırmak için kullanışlıdır.

AdvanceCOMP, gzip , PNG , MNG ve ZIP dosyalarının yeniden sıkıştırılmasını sağlamak için 7-Zip (veya son sürümlerde isteğe bağlı olarak Zopfli) tarafından uygulanan Deflate'in daha yüksek sıkıştırma oranlı sürümünü kullanır. ayarlar.

Donanım kodlayıcıları

  • Comtech AHA'dan AHA361-PCIX/AHA362-PCIX . Comtech , gelen sıkıştırılmamış veriler için Deflate kullanarak akışları 3.0 Gbit/s'ye (375 MB/s) kadar sıkıştırabilen bir PCI-X kartı (PCI-ID: 193f:0001) üretti . AHA361-PCIX için Linux çekirdek sürücüsüne eşlik eden, Apache'nin donanım sıkıştırmasını kullanabilen bir " ahagzip" yardımcı program ve özelleştirilmiş " mod_deflate_aha"dir . Donanım bir dayanmaktadır Xilinx Virtex FPGA ve dört özel AHA3601 ASIC . AHA361/AHA362 kartları yalnızca statik Huffman bloklarını işlemekle sınırlıdır ve destek eklemek için yazılımın değiştirilmesini gerektirir - kartlar tam Deflate özelliğini destekleyemedi, yani yalnızca kendi çıktılarının kodunu güvenilir bir şekilde çözebildiler (bir akış herhangi bir dinamik Huffman tip 2 bloğu içerir).
  • StorCompress 300 / MX3 gelen Indra Ağları . Bu, 3,6 Gbit/sn'ye (450 MB/sn) kadar olduğu iddia edilen işlem hızlarına sahip bir ila altı sıkıştırma motoruna sahip bir dizi PCI (PCI-ID: 17b4:0011) veya PCI-X kartıdır. Kartların bir sürümü, SAN veya yedekleme kullanımı yerine web hizmeti kullanımı için özel olarak tasarlanmış ayrı bir WebEnhance markasıyla mevcuttur ; bir PCIe revizyonu olan MX4E de üretilmiştir.
  • AHA363-PCIe / AHA364-PCIe / AHA367-PCIe . 2008 yılında Comtech, yeni bir donanım AHA3610 kodlayıcı çipi ile iki PCIe kartı ( PCI-ID: 193f:0363/ 193f:0364) üretmeye başladı . Yeni çip, sürekli 2,5 Gbit/sn'lik bir kapasiteye sahip olacak şekilde tasarlandı. Bu yongalardan ikisini kullanan AHA363-PCIe kartı, iki kanalı (iki sıkıştırma ve iki açma) kullanarak Söndürmeyi 5.0 Gbit/s'ye (625 MB/s) kadar bir hızda işleyebilir. AHA364-PCIe varyantı, kartın giden yük dengeleyiciler için tasarlanmış yalnızca kodlamalı bir sürümüdür ve bunun yerine iki fiziksel sıkıştırma motorunu besleyen 32 bağımsız sanal sıkıştırma kanalına izin vermek için birden fazla kayıt kümesine sahiptir . Her iki yeni kart için de Linux, Microsoft Windows ve OpenSolaris çekirdek aygıt sürücüleri ve değiştirilmiş bir zlib sistem kitaplığı mevcuttur, böylece dinamik olarak bağlantılı uygulamalar, dahili değişiklik yapmadan donanım desteğini otomatik olarak kullanabilir. AHA367-PCIe kartı ( PCI-ID: 193f:0367), AHA363-PCIe'ye benzer ancak 10 Gbit/s (1250 MB/s) sürekli sıkıştırma oranı için dört AHA3610 yongası kullanır. AHA362-PCIX'in aksine, AHA363-PCIe ve AHA367-PCIe kartlarındaki dekompresyon motorları tamamen söndürme uyumludur.
  • Cavium, Inc.'in Nitrox ve Octeon işlemcileri, aynı anda birden fazla veri akışını işleyebilen bazı cihazlarla hem ZLIB hem de GZIP ile uyumlu yüksek hızlı donanım söndürme ve şişirme motorlarını içerir.
  • HDL-Deflate GPL FPGA uygulaması.
  • ZipAccel-Cı gelen CAST Inc . Bu, Deflate, Zlib ve Gzip sıkıştırmasını destekleyen bir Silikon IP çekirdeğidir . ZipAccel-C, ASIC veya FPGA'larda uygulanabilir , hem Dinamik hem de Statik Huffman tablolarını destekler ve 100 Gbps'yi aşan verim sağlayabilir. Şirket, Intel FPGA ( ZipAccel-RD-INT ) ve Xilinx FPGA'lar ( ZipAccel-RD-XIL ) için sıkıştırma/açma hızlandırıcı kartı referans tasarımları sunmaktadır .
  • Intel İletişim Yonga Seti 89xx serisi için (Cave Creek) Intel Xeon E5-2600 ve E5-2400 İşlemci Serisi (Sandy Bridge-EP / TR) desteklere QuickAssist Teknolojisi kullanılarak donanım sıkıştırma ve dekompresyon. Yonga setine bağlı olarak 5Gbit/s, 10Gbit/s veya 20Gbit/s sıkıştırma ve açma hızları mevcuttur.

Dekoder/dekompresör

Şişirme, açma için bir Deflate bit akışını alan ve orijinal tam boyutlu verileri veya dosyayı doğru şekilde üreten kod çözme işlemidir.

Yalnızca şişirme uygulamaları

Alternatif bir Şişirme uygulamasının normal amacı, yüksek düzeyde optimize edilmiş kod çözme hızı veya mikro denetleyici gömülü sistemler için son derece öngörülebilir RAM kullanımıdır.

  • toplantı
    • 6502 şişirme , Piotr Fusik tarafından 6502 montaj dilinde yazılmıştır .
    • SAMflate , Andrew Collier tarafından Z80 montaj dilinde SAM Coupé için isteğe bağlı bellek sayfalama desteği ile yazılmış ve BSD / GPL / LGPL / DFSG lisansları altında kullanıma sunulmuştur.
    • gunzip , Laurens Holst tarafından MSX için Z80 derleme dilinde yazılmış ve BSD altında lisanslanmıştır .
    • inflate.asm , bir hızlı ve verimli uygulanması M68000 içine Keir Fraser tarafından yazılan ve yayımlanan makine diline, Public Domain .
  • C / C++
    • kunzip , Michael Kohn tarafından yazılmıştır ve "KZIP" ile ilgisi yoktur. GNU LGPL lisansı altında C kaynak kodu ile birlikte gelir . Kullanılan GIMP yükleyici.
    • puff.c ( zlib ), zlib dağıtımının /contrib/puff dizininde bulunan küçük, numaralandırılmamış , tek dosyalı bir başvuru uygulaması.
    • Jørgen Ibsen tarafından ANSI C'de yazılmış tinf ve zlib lisansı ile birlikte gelir. Yaklaşık 2k kod ekler.
    • tinfl.c ( mininiz ), Kamu malı Şişirme uygulaması tamamen tek bir C işlevinde bulunur.
  • PCDEZIP, Bob Flanders ve Michael Holmes, PC Magazine 1994-01-11'de yayınlandı.
  • John Foderaro tarafından inflate.cl. GNU LGPL lisansı ile dağıtılan, bağımsız Common Lisp kod çözücü .
  • inflate.s7i / gzip.s7i , Thomas Mertes tarafından Deflate ve gzip dekompresyonunun saf Seed7 uygulaması. GNU LGPL lisansı altında kullanıma sunulmuştur .
  • pyflate , Paul Sladen'in saf Python bağımsız Deflate ( gzip ) ve bzip2 kod çözücüsü. Araştırma/prototipleme için yazılmış ve BSD / GPL / LGPL / DFSG lisansları altında kullanıma sunulmuştur.
  • deflatelua , Deflate ve gzip /zlib dekompresyonunun saf Lua uygulaması, David Manura tarafından.
  • şişirmek bir pure- JavaScript Chris Dickinson tarafından şişirmek uygulanmasını
  • pako : JavaScript hızı optimize edilmiş zlib bağlantı noktası. Yalnızca şişirme ile ayrı bir yapı içerir.

Donanım kod çözücüleri

  • BitSim'den Seri Şişirme GPU'su. Inflate'ın donanımsal uygulaması. BitSim'in gömülü sistemler için BADGE (Bitsim Hızlandırılmış Ekran Grafik Motoru) denetleyicisinin bir parçası.
  • HDL-Deflate GPL FPGA uygulaması.
  • ZipAccel-D den CAST Inc . Bu, Deflate, Zlib ve Gzip dosyalarının açılmasını destekleyen bir Silikon IP çekirdeğidir . ASIC veya FPGA'larda uygulanabilen ZipAccel-D IP çekirdeği . Şirket, Intel FPGA ( ZipAccel-RD-INT ) ve Xilinx FPGA'lar ( ZipAccel-RD-XIL ) için sıkıştırma/açma hızlandırıcı kartı referans tasarımları sunmaktadır .

Ayrıca bakınız

Referanslar

Dış bağlantılar