deniz.in

Piyasalar

Hava durumu

Hava durumu yükleniyor

· kaynak Hacker News – Front Page (native)

LZ0: sıfır bellek tahsisli, ~150 satırlık C decoder'ı olan açık kaynaklı bir kayıpsız format

Hacker News'te tanıtılan yeni bir açık kaynaklı kayıpsız sıkıştırma formatı olan LZ0, ağır işi encoder'a yükleyerek C decoder'ının heap tahsisi gerektirmemesini ve yaklaşık 150 satıra sığmasını sağlıyor.

LZ0: sıfır bellek tahsisli, ~150 satırlık C decoder'ı olan açık kaynaklı bir kayıpsız format

Decoder'dan geriye doğru tasarlanan bir format

21 Kasım'da Hacker News ana sayfasında bir Show HN gönderisiyle ortaya çıkan LZ0 adlı proje, referans bir C uygulamasına sahip yeni bir açık kaynaklı kayıpsız sıkıştırma formatı. GitHub README'sine göre projenin düzenleyici fikri kasıtlı bir asimetri: sıkıştırıcı karmaşık ve hesaplama açısından maliyetli olabilsin ki açıcı (decompressor) olabildiğince küçük ve basit kalabilsin.

Bunun getirisi, README'nin yaklaşık 150 satırlık C kodu olarak tanımladığı bir decoder. Dinamik bellek tahsisi yapmıyor, yalnızca birkaç durum parçası tutuyor — çıktı tamponundaki yazma konumu, en son kullanılan eşleşme ofseti (başlangıçta 1) ve küçük bir bit okuyucu — ve tamamen çağıranın verdiği tamponlar içinde çalışıyor. Açık LZ token'larını saniyede yüzlerce megabayt hızla işliyor. LZ0, tipik olarak birkaç yüz kilobayttan birkaç megabayta kadar olan küçük ve orta ölçekli ikili verileri ve yapılandırılmış verileri hedefliyor; README, önyükleyiciler, mikrodenetleyiciler, retro donanım ve çekirdek alanını böyle kompakt bir decoder için doğal yaşam alanları olarak gösteriyor.

Dört işlemli bir token dilbilgisi

Decoder yalnızca dört işlem anlıyor:

  • LiteralRun: sıkıştırılmamış baytlardan oluşan bir diziyi doğrudan akıştan kopyala.
  • MatchLast: önceki kullanılan ofsetten L bayt kopyala.
  • MatchNew: yeni bir ofset oku, onu hatırla, sonra o mesafeden L bayt kopyala.
  • EOF: akışı düzgün biçimde sonlandır.

Eşleşmeler bayt bayt kopyalanır, dolayısıyla bir eşleşme uzunluğu ofsetini aştığında önceki baytlar tekrarlanır — 1'lik bir ofset ve 8'lik bir uzunluk, tek bir baytı 8 baytlık bir diziye genişletir. README, standart bir çakışmayan memcpy'nin burada yanlış olacağı konusunda uyarıyor.

Ham bit akışı hiçbir magic baytı, başlık veya uzunluk metadata'sı taşımıyor. Bitler önce en anlamlı bayt gelecek şekilde paketlenir; literal bayt yükleri ve her ofsetin düşük 8 biti, akışta hizalanmamış ham baytlar olarak yer alır. Uzunluklar Elias gamma değişken uzunluklu tamsayılar kullanırken, ofsetler ters Elias gamma koduyla kodlanmış bir yüksek kısım ve ham bayt olarak yazılan 8 bitlik bir kalan olarak bölünür; decoder ofseti msb çarpı 256 eksi o bayt olarak yeniden yapılandırır. Uzunluğu 2 ile 8 arasında olan yeni ofset eşleşmeleri üç sabit bite paketlenir; daha uzun diziler için bir kaçış öneki ve ek bir Elias kodu kullanılır. Akışın ilk karar biti bile atlanır, çünkü her akış bir literal dizisiyle başlamak zorundadır. Diskte depolama için CLI, yükü 8 baytlık bir container başlığına sarar: dört baytlık bir magic dizisi olan LZ01 ve ardından little-endian 32 bit tamsayı olarak sıkıştırılmamış boyut.

ZX0 ve UPKR arasındaki konum

README, LZ0'yu iki mevcut tasarım arasındaki bir nişe yerleştiriyor. ZX0, minimal decoder'lı LZ sıkıştırmasında referans noktası olmuştu; bayt bayt çakışan kopyalamalı bir decoder'ı optimal bir dinamik programlama ayrıştırıcısıyla birleştiriyordu — ancak kapsamlı araması, girdiler yaklaşık 1 MiB'yi aştığında birkaç dakika sürebiliyor. LZ0, ZX0'ın decoder basitliğini ve Elias tabanlı tamsayı kodlamasını korurken encoder'ı daha hızlı bir mimariyle değiştiriyor: hash zincirleri, O(N) SA-IS sonek dizisi ve seyrek bir dinamik programlama ayrıştırıcısının birleşimi. README'ye göre sonuç, dakikalar yerine saniyeler içinde 5 MiB girdilerde karşılaştırılabilir sıkıştırma oranları.

UPKR ters bir dengi tercih ediyor. Daha yüksek oranlara ulaşmak için LZ eşleştirmesini uyarlamalı rANS/rABS entropi kodlamasıyla birleştiriyor, ancak decoder'ı her token'da olasılık dağılımlarını korumak ve entropi durumunu güncellemek zorunda. LZ0 uyarlamalı entropi kodlamasını tamamen atlıyor, biraz daha kötü oranları, yalnızca ham bitlere dokunan bir decoder uğruna kabul ediyor; README'ye göre bu, dallanma yanlış tahminlerini ve token başına ek yükü en aza indiriyor.

Bir başka tasarım tercihi de format bağımsızlığı: bit akışı yalnızca yeniden yapılandırma talimatlarını tanımlıyor, böylece encoder — daha iyi arama, daha akıllı budama, yeni sezgisel yöntemler — halihazırda dağıtılmış decoder'ları bozmadan veya karmaşıklaştırmadan gelişebilir.

Neden önemli

Sıkıştırma çalışmalarının çoğu genel amaçlı donanımda oranı veya verimliliği optimize eder. LZ0 ise açıcının kendisinin kısıt olduğu durumları optimize ediyor: kullanılabilir heap yok, en düşük kod boyutu ve satır satır denetlenebilecek kadar küçük bir yordam. Bu, aygıt yazılımı, önyükleme yolları ve gömülü hedefler açısından önemli; ~150 satırlık, sıfır tahsisli bir decoder küçük bir hata ve güvenlik yüzeyi sunuyor ve bellek baskısı altında öngörülebilir davranıyor. Encoder tarafındaki esneklik ayrıca sıkıştırma kalitesinin, cihazlarda halihazırda gönderilmiş decoder'lara dokunmadan zamanla iyileşebileceği anlamına geliyor. Proje açıkça deneysel olarak etiketlendi ve gerçek dünyada benimsenmesi araçing ve bağımsız kıyaslamalara bağlı olacak — ancak decoder öncelikli, asimetrik sıkıştırma tasarımının belgelenmiş bir alıştırması olarak LZ0 net ve ilginç bir veri noktası.

  • #compression
  • #open-source
  • #c
  • #embedded-systems
  • #algorithms

İlgili yazılar