|
|
Yayınlandı 3.01.2022 13:54:23
|
|
|
|
HBO'nun "Silicon Valley" dizisi izledikten sonra, sıkıştırma algoritmalarına her zaman ilgi duydum. Richard Hendricks ve içindeki orta çıkış sıkıştırma algoritması elbette sahte, ama Google'da zor bir araştırma yaptıktan sonra gerçek hayatta böyle bir sıkıştırma algoritması dahisi olduğunu gördüm.
Yann Collet, 2011 yılında LZ4 sıkıştırma algoritmasını icat etti. Elbette, LZ4 algoritması ortadan çıkış kadar harika değil, ancak belirli bir sıkıştırma oranı garanti edilebildiğinde yenilmez sıkıştırma hızı ve daha hızlı dekompresyon hızıyla bilinir.
Sıkıştırma hızının değerlendirilmesiyle ilgili detaylara girmeyeceğim, ilgileniyorsanız şu karşılaştırma makalesini okuyabilirsiniz:Bağlantı girişi görünür.
Ayrıca LZ4'ün github adresi de eklenir:Bağlantı girişi görünür.
Bu makale, LZ4 sıkıştırma algoritmasının prensibini açıklamaya odaklanmaktadır. Büyük bir tanrı daha önce LZ4 algoritmasının açıklamasını yazmıştı:Bağlantı girişi görünür.Ama daha önce çalışırken, bu makalenin acemiler için pek dostça olmadığını hissettim, bu yüzden benim gibi acemiler için başka bir makaleye başladım.
Tek bir cümleyle özetlerseniz, LZ4, 16k boyutunda bir hash tablosu olan bir sözlük depolayan ve geri almayı basitleştiren bir LZ77'dir.
LZ4, çekirdek başına 500 MB/s > sıkıştırma hızı sunan kayıpsız bir sıkıştırma algoritmasıdır ve çok çekirdekli CPU'larla ölçeklenebilir. Çekirdek başına birkaç GB/s hıza sahip son derece hızlı kodlayıcılara sahiptir ve çok çekirdekli sistemlerde genellikle RAM hız sınırlarına ulaşır.
Hız dinamik olarak ayarlanabilir ve sıkıştırma oranını daha yüksek hıza değiştiren bir "ivmelenme" faktörü seçilir. Öte yandan, CPU süresi pahasına sıkıştırmayı artırmak için yüksek sıkıştırma türevi LZ4_HC de sağlanır. Tüm sürümlerde aynı dekompresyon hızı var.
Peki LZ77 nedir?
LZ77 sıkıştırma ve prensip
LZ77, sıkıştırma için bir sözlük uygulayan bir algoritmadır. Basit bir ifadeyle, programın şu anda gördüğü verilerin önceki verilerle çoğaltıp çoğaltılmadığını gözlemlemesini (sözlüğe bakmasını sağlamak) ve eğer öyleyse, çoğaltılmış alanların mesafesini (ofset) ve uzunluğunu kaydederek çoğaltılmış alanların yerine veri sıkıştırılır.
referansBağlantı girişi görünür.
A A B C B B B A B C harflerinden oluşan bir dizide ikinci A okunduğunda program (1,1) (öncekinden 1 rakam, uzunluğu 1) kaydeder ve benzer şekilde, ikinci B okunduğunda program (2,1) (mesafe 2, uzunluk 1) kaydeder.
Ancak dizi daha uzunsa ve program verileri sürekli sözlüğe kaydediyorsa, tekrarlanan alanların araması son derece zaman alıcı hale gelir, çünkü en kötü durumda program her yeni harf okunduğunda tüm sözlüğü gözden geçirir. LZ77, bu sorunu çözmek için kaydırmalı pencere yöntemi kullanır.
TCP'nin kaydırmalı pencere kullanma başlangıç noktasına benzer şekilde, kaydırmalı pencere önbellek alanını küçülterek aynı anda çok fazla önbelleklenmiş veriyi işlemez. LZ77'de sözlük her zaman artmaz, ancak sözlük tarafından belirlenen maksimum boyutu aştığında sözlüğe eklenen ilk karakterleri atar ve böylece sözlük boyutu her zaman belirlenen maksimum boyutta korunur.
Diyelim ki sözlük uzunluğu 3
| Sözlük |
| A | A B C B B A B C
Çıkış (0,0,A)
| A A | B C B B A B C
Çıkış(1,1)
| A A B | C B B A B C
Çıkış (0,0,B)
A | A B C | B B A B C
Çıkış (0,0,C)
A A | B C B | B A B C
Çıkış(2,1)
Kaydırma penceresinin diğer kısmı ise aranacak önbellektir (bak ileriye bakan buffer'ın resmi bir çevirisi yoktur). Araştırılacak önbellek, sözlüğe en yakın sıkıştırılmamış uzunluk kısmıdır. LZ77 algoritması, karakterin bu kısmındaki sözlükle aynı olan en uzun diziyle eşleşir. Önceki örnek, 1'in ileriye bakma tamponu olarak değerlendirilebilir.
Diyelim ki sözlük uzunluğu 5 ve aranan önbellek boyutu 3
| Sözlük | İleriye Bakın Buffer |
A | A B C B B B | A B C |
Çıkış(5,3)
Eşleşen en uzun ip ABC'dir
Tam sıkıştırma süreci:
Diyelim ki sözlük uzunluğu 5 ve aranan önbellek boyutu 3
| Sözlük | İleriye Bakın Buffer |
| A A B | C B B A B C
Çıkış (0,0,A)
| A | A B C | B B A B C
Çıkış(1,1)
| A A | B C B | B A B C
Çıkış (0,0,B)
| A A B | C B B | A B C
Çıkış (0,0,C)
| A A B C | B B A | B C
Çıkış(2,1)
| A A B C B | B A B | C
Çıkış(1,1)
A | A B C B B B | A B C |
Çıkış(5,3)
A A B C | B B A B C | 。。。 |
Sözlüğü kompresörün çıktı dosyasına kaydetmeye gerek yoktur, çünkü dekompresyon programı çıkış birimlerini eşleştirerek sözlüğü geri getirir.
Dekompresyon süreci
LZ77 algoritmasının büyük avantajlarından biri, çok hızlı çözülebilmesidir.
İlk eşleşen birim (0,0,A) ise, A çıktıdır.
İkinci eşleştirme birimi (1,1)'dir; çıktı dizisinde önceki biti kopyalar ve kopyalama uzunluğu 1 ise A çıkarır.
。。。
Son eşleşen birim (5,3) ise, kopyalama çıkış dizisinde 5 bit geriye bakılır ve kopyalama uzunluğu 3 ise, A, B, C çıktısı alın.
LZ77 algoritmasının sıkıştırılmasının en çok zaman alan kısmı, önbellekte aranan en uzun eşleşen karakteri bulmaktır. Eğer sözlük ve aranacak önbellek çok kısa, eşleşme bulma şansı düşüktür. Bu nedenle, LZ4, LZ77 için eşleştirme algoritmasını değiştirmiştir.
İlk olarak, LZ4 algoritmasının sözlüğü bir hash tablosudur. Sözlükteki anahtar 4 baytlık bir dizedir, her anahtar sadece bir slota karşılık gelir ve yuvadaki değer bu dizinin konumudur.
Önbelleği aramak yerine, LZ4 giriş dosyasından bir seferde dört bayt okur ve ardından hash tablosunda diziye karşılık gelen yuvayı arar; bundan sonra bu dizi mevcut dizi olarak adlandırılacaktır.
Son 12 karaktere ulaştıysanız, onları doğrudan çıktı dosyasına ekleyin.
Slotta değer atanmamışsa, dört bayt ilk kez ortaya çıkar, bu dört bayt ve konumları hash tablosuna ekler ve aramaya devam eder.
Slotta bir atama varsa, bu eşleşen bir değer bulduğumuz anlamına gelir.
Slottaki değer artı kaydırıcı pencerenin boyutu < mevcut karakterin konumu ise, eşleşme pozisyonu blokun boyutunu aşar ve program hash slotundaki değeri mevcut dizinin konumuna günceller.
LZ4, bir hash çakışması olup olmadığını kontrol edecek. Slottaki 4 bayt mevcut diziyle aynı değilse, bir hash çatışması olmalı. Yazarın kendi xxhash'ı da verimliliğiyle bilinir, ancak çatışmalar kaçınılmazdır. Bir çatışma durumunda, program ayrıca hash slotundaki değeri dizinin mevcut konumuna günceller
Son olarak, eşleşmenin geçerli olduğunu teyit edebiliriz ve program, eşleşen dizide sonraki karakterlerin aynı olup olmadığını görmeye devam eder. Son olarak, önceki geçerli eşleşmenin sonundan bu geçerli eşleşmenin başına kadar olan tüm karakterleri sıkıştırılmış dosyaya kopyalayın ve bu geçerli eşleşmenin eşleşme dizisini ekleyin.
Collet, LZ4 ile çıkan eşleşen birimleri diziler olarak çağırır ve bunlar LZ4 sıkıştırılmış dosyayı oluşturur. Detaylar şunlardır:
Token 1 bayt uzunluğundadır; ilk 4 kelime kelimenin gerçek uzunluğu, son 4 kelime ise eşleşme uzunluğudur. Daha önce belirtildiği gibi, önceki geçerli eşleşmenin sonundan bu geçerli eşleşmenin başlangıcına kadar olan tüm karakterler sıkıştırılmış bir dosyaya kopyalanacaktır; bu sıkıştırılmamış dosyalar literaldır ve uzunlukları literal uzunluktur.
Kelimenin tam anlamıyla ardından sapma geliyor. LZ77'de olduğu gibi, sapma ve eşleşme uzunluğu, mevcut dizinin eşleşmesinden olan uzunluğunu, eşleşme uzunluğu ise mevcut dizinin sözlükteki aynı diziye olan eşleşme uzunluğunu ifade eder. Dekompresyonda, kopyalanacak ipi ve kopyalanacak uzunluğu bulmak için üzerinden geçmektir. Sapmanın büyüklüğü sabittir.
Şekilde, literal uzunluk+ ve eşleşme uzunluğu+, eğer token'daki kelimenin literal veya eşleşme uzunluğu 4 kelimesi yeterli değilse, karşılık gelen pozisyonlarda artmaya devam edecektir. 4 kelime 0-15'i temsil edebilir ve daha fazla kelime varsa, bir bayt ekleyin, yani bayt 255'ten küçük olana kadar boyuta 255 ekleyin. Eşleşme uzunluğunda 0, 4 baytı temsil eder.
Son 12 bayt kelimenin tam anlamıyla doğrudan kopyalandığı için bitiyor.
Kodlara bakalım (python daha soyut bir dilidir)
Özet Tüm bunları söyledikten sonra, LZ4'ün neden bu kadar hızlı olduğunu hâlâ özetlemedim. Önce LZ77 ile LZ4 arasındaki sözlük aramasını karşılaştıralım. Yerel LZ77, aranan önbellekte ve sözlükte en büyük eşleşmeyi arayarak sözlükleri arar. Bu, iki telde en büyük aynı diziyi bulma sorunudur. Dinamik programlama kullanmazsak, en kötü ihtimalle bir dizinin tüm alt dizileri dikkate alınıp başka bir dizide eşleştirilmeli. Eğer ×dinamik programlama kullanırsak, dinamikte en uzun eşleşmeyi tutmak için bir tablo kullanırız, bu da sadece O(m*n) durumunda eşleşmeyi tamamlamamıza izin verir. Ve bu sadece arama önbelleği ve sözlükler için. En kötü durumda, eşleşme yoksa, LZ77 (tüm dosyanın uzunluğu - aranan önbelleğin uzunluğu) bu tür birçok eşleşme problemi olarak saymak zorunda kalacaktır. LZ4 aslında daha büyük bir dinamik programlama seviyesi kullanır: 4 bayt ve konumlarını bir hash tablosunda saklar, ardından her seferinde yeni 4 bayt veriyi eşleştirerek hash tablosundaki değerlerin geçerli olup olmadığını kontrol eder. Geçerli bir eşleşme değeri bulunduktan sonra, iki eşleşme değer kümesinin takip verilerine bakarsanız, en uzun eşleşmesini de bulabilirsiniz. LZ4 hash tablosunun her anahtarı sadece 1 slota karşılık geldiğinden, hash tablosunu bulup toplama ve değiştirme işi sadece O(1) gerektirir. Eşleşmeden sonra daha fazla eşleşme bulunursa, daha fazla grup karşılaştırması gerekir, ancak toplam sürede bu karşılaştırmalar hash tablosunu arama süresinin daha fazla yerini alır, böylece LZ4 algoritmasının toplam süresi sadece O(n)'dir. Collet'in algoritmasının güzelliğine hayran kalmalıyım! Algoritmayı daha da hızlandırmak için Collet, varsayılan hash tablosu boyutunu 16k olarak ayarlıyor; bu boyutun 32k'yi aşmaması önerilir, böylece neredeyse tüm CPU'ların (Intel) L1 önbelleğine konabilmektedir. Herkes CPU L1 önbelleğinin hızı ve bellek oranının çok farklı olduğunu bilir, bu yüzden LZ4'ün hızlı uçması şaşırtıcı değil, ayrıca LZ4'ün hash tablosunda kullanılan hash denkleminin hâlâ en hızlı xxhash olması da şaşırtıcı değil. Elbette, böyle bir tasarımın dezavantajları da vardır. Hash tablosu ne kadar küçükse, o kadar az anahtara sahiptir. Bu da daha fazla hash çatışmasının yaşanacağı anlamına gelir ki bu kaçınılmazdır. Ve daha fazla hash çarpışması, daha az eşleşme demek. Ve daha küçük bir hash tablosu ayrıca daha küçük bir kaydırma penceresi anlamına gelir, bu da daha fazla eşleşmenin çok uzakta olduğu için atılacağı anlamına gelir. Daha az eşleşme daha düşük bir sıkıştırma oranını temsil eder, bu yüzden LZ4'ün sıkıştırma oranı daha az belirgindir. Geleceğe Bakıyorum: LZ4 çok çeşitli uygulama senaryolarına sahip. Silikon Vadisi'nde VR'da ortadan çıkış kullanıldığı gibi, LZ4 de çok düşük gecikme pahasına daha az işlem cihazı getirerek bant genişliği kullanımını artırabilir. Ayrıca küçük bir varsayım var: Seviye 1'de daha büyük önbelleğe sahip bir CPU varsa, LZ4 hızdan ödün vermeden sıkıştırma oranını artırabilir mi?
Özgün:Bağlantı girişi görünür. |
Önceki:TrueNAS Core, anlık görüntü konumlarına bakıyorÖnümüzdeki:Java, HTTP ağ istekleri göndermek için OkHttp kullanır
|
