ºÝºÝߣ

ºÝºÝߣShare a Scribd company logo

Lz77 / Lempel-Ziv Algorithm

•
•
Veysi Ertekin
Veysi Ertekin

An introduction to LZ77 algorithm.

1 of 10
Downloaded 27 times
LZ77 (Lempel-Ziv Algoritması) @veysiertekin
TARİHÇE * Abraham Lempel and Jacob Ziv tarafından 1977-78 yılları arasında yapılan çalışmanın ürünü olduğu için LZ77 adı verilmiştir. [1] * Algoritmaya kod adının verilmesindeki neden birçok varyasyonu arasından ayırt etmek. * Sınırsız veri akışının (yani verinin gerçek boyutu bilinmeden) daha az yer kaplayacak şekilde kodlanmasını sağlar. * Kayıpsız bir sıkıştırma algoritmasıdır. [1] J.Ziv and A.Lempel,“Compression of individual sequences by variable rate coding,“IEEETrans. InformationTheory, 1978.
Verinin ilk defa verimli şekilde aktarımının yolunu açması, günümüz internetinin yaygınlaşmasındaki ivmeyi beraberinde getirdi
• Günümüzde duyduğumuz/kullandığımız birçok sıkıştırma-kodlama algoritmasının temelinde yer almakta: zip, bzip, gzip,WinRAR, LZMA,LZO, LZ4, 
 JPEG, PNG, GIF … 1- LZ ile başlayanlar hemen hemen aynı algoritmayı farklı yöntemler kullanarak uyguluyorlar (ör: direk dönüşüm yerine binary hale çevirip algoritmayı uygulamak yada verinin işleniş sıralamalarında değişiklik yapmak gibi) 
 2- Diğer algoritmalar (zip, JPEG vs) bu algoritma üzerine Huffman kodlaması gibi ek yöntemlere başvuruyorlar
Algoritma Oran Sıkıştırma Açma memcopy 1.000 4200 MB/s 4200 MB/s LZ4* 2.101 385 MB/s 1850 MB/s LZO 2.06 2.108 350 MB/s 510 MB/s QuickLZ 1.5.1.b6 2.238 320 MB/s 380 MB/s Snappy 1.1.0 2.091 250 MB/s 960 MB/s LZF v3.6 2.073 175 MB/s 500 MB/s zlib 1.2.8 -1 2.730 59 MB/s 250 MB/s LZ4* HC 2.720 22 MB/s 1830 MB/s zlib 1.2.8 -6 3.099 18 MB/s 270 MB/s Kaynak: https://github.com/Cyan4973/lz4 Benchmark; *LZ4Yann Collet tarafından 2011 yılında tanıtıldı
Benchmark;
Yahoo’da Hadoop Cluster'larında kullanılan sıkıştırma algoritmalarının oranları
Lz77 / Lempel-Ziv Algorithm
Algoritma (Pseudo Code) begin görünümü gelen veri ile doldur while (görünüm boş olmadığı sürece) do begin görünümün başındaki veriden arama tamponundaki en uzun eşleşmeyi bul i := arama tamponunda bulunan kaydın indeksi j := eşleşme uzunluğu X := eşleşen veriden hemen sonraki veri çıktıyaAktar(i,j,X) arama tamponunun başlangıç indeksini eşleşen veriden sonrasına taşı end end
Örnek Arama önbelleği Gelen veri Satır 121110 9 8 7 6 5 4 3 2 1 0 1 2 3 4 5 6 7 8 9 … Çıktı 1 a a b b c a b c b b (0,0,a) 2 a a b b c a b c b b c (1,1,b) 3 a a b b c a b c b b c a c (1,1,c) 4 a a b b c a b c b b c a c b c (4,2,c) 5 a a b b c a b c b b c a c b c c a ∅ (6,4,c) 6 a a b b c a b c b b c a c b c c a ∅ (4,2,c) 7 b c a b c b b c a c b c c a ∅ (5,1,null)

More Related Content

Lz77 / Lempel-Ziv Algorithm

  • 2. TARÄ°HÇE * Abraham Lempel and Jacob Ziv tarafından 1977-78 yılları arasında yapılan çalışmanın ürünü olduÄŸu için LZ77 adı verilmiÅŸtir. [1] * Algoritmaya kod adının verilmesindeki neden birçok varyasyonu arasından ayırt etmek. * Sınırsız veri akışının (yani verinin gerçek boyutu bilinmeden) daha az yer kaplayacak ÅŸekilde kodlanmasını saÄŸlar. * Kayıpsız bir sıkıştırma algoritmasıdır. [1] J.Ziv and A.Lempel,“Compression of individual sequences by variable rate coding,“IEEETrans. InformationTheory, 1978.
  • 3. Verinin ilk defa verimli ÅŸekilde aktarımının yolunu açması, günümüz internetinin yaygınlaÅŸmasındaki ivmeyi beraberinde getirdi
  • 4. • Günümüzde duyduÄŸumuz/kullandığımız birçok sıkıştırma-kodlama algoritmasının temelinde yer almakta: zip, bzip, gzip,WinRAR, LZMA,LZO, LZ4, 
 JPEG, PNG, GIF … 1- LZ ile baÅŸlayanlar hemen hemen aynı algoritmayı farklı yöntemler kullanarak uyguluyorlar (ör: direk dönüşüm yerine binary hale çevirip algoritmayı uygulamak yada verinin iÅŸleniÅŸ sıralamalarında deÄŸiÅŸiklik yapmak gibi) 
 2- DiÄŸer algoritmalar (zip, JPEG vs) bu algoritma üzerine Huffman kodlaması gibi ek yöntemlere baÅŸvuruyorlar
  • 5. Algoritma Oran Sıkıştırma Açma memcopy 1.000 4200 MB/s 4200 MB/s LZ4* 2.101 385 MB/s 1850 MB/s LZO 2.06 2.108 350 MB/s 510 MB/s QuickLZ 1.5.1.b6 2.238 320 MB/s 380 MB/s Snappy 1.1.0 2.091 250 MB/s 960 MB/s LZF v3.6 2.073 175 MB/s 500 MB/s zlib 1.2.8 -1 2.730 59 MB/s 250 MB/s LZ4* HC 2.720 22 MB/s 1830 MB/s zlib 1.2.8 -6 3.099 18 MB/s 270 MB/s Kaynak: https://github.com/Cyan4973/lz4 Benchmark; *LZ4Yann Collet tarafından 2011 yılında tanıtıldı
  • 7. Yahoo’da Hadoop Cluster'larında kullanılan sıkıştırma algoritmalarının oranları
  • 9. Algoritma (Pseudo Code) begin görünümü gelen veri ile doldur while (görünüm boÅŸ olmadığı sürece) do begin görünümün başındaki veriden arama tamponundaki en uzun eÅŸleÅŸmeyi bul i := arama tamponunda bulunan kaydın indeksi j := eÅŸleÅŸme uzunluÄŸu X := eÅŸleÅŸen veriden hemen sonraki veri çıktıyaAktar(i,j,X) arama tamponunun baÅŸlangıç indeksini eÅŸleÅŸen veriden sonrasına taşı end end
  • 10. Örnek Arama önbelleÄŸi Gelen veri Satır 121110 9 8 7 6 5 4 3 2 1 0 1 2 3 4 5 6 7 8 9 … Çıktı 1 a a b b c a b c b b (0,0,a) 2 a a b b c a b c b b c (1,1,b) 3 a a b b c a b c b b c a c (1,1,c) 4 a a b b c a b c b b c a c b c (4,2,c) 5 a a b b c a b c b b c a c b c c a ∅ (6,4,c) 6 a a b b c a b c b b c a c b c c a ∅ (4,2,c) 7 b c a b c b b c a c b c c a ∅ (5,1,null)