lzw
-
ks. lempel ziv welch.. bu 3 herifin buldugu bir compression algoritmasi. birbirini tekrar eden string'leri tokenize etmeye dayanan bir mantigi wardir. rle'den sonraki en hizli algoritmalardan biridir. iyi compression ratio icin cok memory'ye ihtiyac duyar.
-
(bkz: lz77)
-
huffmandan biraz daha versatil olan sıkıştırma yöntemi. zira huffman ile sıkıştırdığınız nanenin sözlüğünü de yanında eklemek zorundasınızdır adam fal açamaz sizin kodlarınızı çözmek için. fakat lempel-ziv tekniğiyle kodları çözerken ilgili sözlüğü oluşturabilirsiniz, böyle bir güzelliği vardır algoritmanın
huffman, sıkıştırmadan önce dosyanın tamamını kapsayan alengirli işlemler yaparken, lempel-ziv baştan başlar, bir geçişte sözlüğü de oluşturur, dosyayı da sıkıştırır. bu şartlar altında, açarken de tek geçişte açabilirsiniz dosyayı. -
winzip, gzip... benzeri sıkıştırma programlarının kullandığı algoritma. sıkıştırılacak (ve tersi) her dosya için o dosyaya özel bir kodlama yaratılır. böylelikle pek çok farklı çeşit dosyaya sıkıştırma yapılabilir.
-
-
-
gif resim formatında kullanılan sıkıştırma algoritması. patenti 2003 yılında dolduğundan beleşe kullanılabilecek hede. algoritma kısaca aşağıdaki gibi özetlenebilir:
1. hash tablosunu bütün 1 bytelık değerleri alacak şekilde ascii kodlarına göre eşle. {a->65, b->66,.., a->97,..}
2. sıkışacak veriden hash tablosunda bulunan en uzun bloğu(w) al. veri kalmadıysa çık.
3. w yu hash tablosundaki indexe göre kodla.
4. hash tablosuna w+bir sonraki bloğun ilk karakterini ekle.
5. 2.adıma git.
animasyon için: http://www.data-compression.com/lempelziv.html -
metinden bir harf al
sözlükte harfi ara
metindeki sıradaki harfi aldığında sözlükteki bir kayda karşılık geliyorsa metinden harf almaya devam et
şimdiye kadar uyan sözlük değerini sonuca bas
uyumu bozan yeni harfle birlikte şimdiye kadar uyan sözlük kaydını, yeni sözlük kaydı olarak ekle
metin bitmediyse 2. adımdan uymayan bu yeni harf ile devam et.
bu durumu aşağıdaki örnek üzerinden inceleyelim.
sıkıştırmak istediğimiz mesajımız: “sadisadisadi” olsun.
öncelikle yukarıda bulunan harflerimizi içeren bir sözlük oluşturuyoruz. bu sözlük her iki tarafta da bulunmalıdır. bu örnekte sadece 4 farklı harf olduğu için 4 harf içeren bir sözlüğümüzün olması yeterlidir. ancak genel kullanımda, örneğin ascii tablosu böyle bir sözlük olarak bütün bilgisayarlarda kayıtlıdır ve ilave bir transfere ihtiyaç duyulmaz.
a-1,d-2,i-3,s-4 şeklinde 4 harflik alfabemizi ve karşılığı olan sayıları belirleyelim.
mesajımızı işlemeye başlıyoruz. aşağıda : işaretinin sol tarafı sıkıştırılacak olan metin ve sağ tarafı sıkıştırma işleminin sonucu olarak düşünülebilir. mesajın ilk harfinden başlayalım:
sadisadisadi
buradaki s harfi sözlüğümüzde zaten bulunuyor ve çıktımıza sözlükten 4 sayısını koyuyoruz:
sadisadisadi : 4
yukarıda, sözlükten ilk harfi sonuca koyduk ve sıradaki harfi aldık. sözlüğümüzde s harfi bulunmakta ve şimdiye kadar karşılaştığımız en uzun sözlük kaydı bu harf olmaktadır. yeni gelen a harfi ile birlikte bir s harfi olmadığı için bu harfi sonuca harf olarak 1 şeklinde yazıyoruz, ilk kez karşılaştığımız durumu sözlüğe ekliyoruz ve sa için 5 kaydını giriyoruz. sözlüğün yeni hali ve mesaj aşağıdaki şekildedir:
sözlük : a-1,d-2,i-3,s-4,sa-5
sadisadisadi : 4 1
şu anda a harfiyle başlayan bir kelime üzerinde işlem yapıyorduk. bu kelime sadece a harfini içeren sözlük girdisiydi ve yeni bir harf olarak d harfi geldi. bu durumda ad ile başlayan bir sözlük girdisi olmadığı için sözlüğe bu yeni kaydı ekleyip, sonuç kısmına d harfini olduğu gibi alıyoruz:
sözlük : a-1,d-2,i-3,s-4,sa-5,ad-6
sadisadisadi : 4 1 2
yukarıdaki durumlara benzer şekilde, i harfi ilk defa karşılaştığımız bir durum. sözlükteki d harfini işlerken karşılaştığımız için di kaydını ekliyor ve i harfini sonuca alıyoruz:
sözlük : a-1,d-2,i-3,s-4,sa-5,ad-6,di-7
sadisadisadi : 4 1 2 3
aynı durum is için geçerlidir, i harfini sonuca alıp, sözlüğe ilk karşılaştığımız is durumunu ekliyoruz:
sözlük : a-1,d-2,i-3,s-4,sa-5,ad-6,di-7,is-8
sadisadisadi : 4 1 2 3 5
işte yukarıdaki sa durumunda ilk defa sözlükte iki harfi birden bulunan bir kayıt yakalıyoruz. sa harfleri 5. kayıtta bulunuyor. bu durumda sözlükte olmayan bir harf bulana kadar işlemeye devam ediyoruz ve d harfine gelince sözlükteki kaydın dışına çıkılmış olunuyor:
sözlük : a-1,d-2,i-3,s-4,sa-5,ad-6,di-7,is-8,sad-9, dis-10
sadisadisadi : 4 1 2 3 5 7
benzer şekilde di kaydının, sözlükte olmayan bir hale gelmesi, sıkıştırılacak metindeki s harfinin eklenmesi ile sağlanıyor. sözlüğe ekleyip mesajın kalanına devam ediyoruz.
sözlük : a-1,d-2,i-3,s-4,sa-5,ad-6,di-7,is-8,sad-9, dis-10,sadi-11
sadisadisadi : 4 1 2 3 5 7 9
yukarıda, ilk defa sözlükte 3 harfli bir kayıt yakaladık. bu kaydın metinle uyuşmayan ilk durumu sondaki i harfi gelmesidir. yukarıdaki durumlara benzer şekilde uyan kısmını sözlükten alıp sonuca yazıyor, uymayan halini de uymayan kelimeyi ekleyerek sözlüğe yazıyoruz.
son olarak sonda tek harf olan i kalıyor ve bunu da sözlük karşılığı olan 3 yazarak sonuca alıyoruz.
sözlük : a-1,d-2,i-3,s-4,sa-5,ad-6,di-7,is-8,sad-9, dis-10,sadi-11
sadisadisadi : 4 1 2 3 5 7 9 3
görüldüğü üzere metin 12 harfliyken sonuç mesajında 8 sayı bulunmaktadır. dolayısıyla bu örnekte %33 başarı sağladığımızı söyleyebiliriz.
algoritmanın açması
yukarıda sıkıştırılması anlatılan mesajın, nasıl açıldığını anlatmaya çalışalım.
algoritma açma işlemi sırasında, sıkıştırılmış mesajdan bir değer okur ve bunun karşılığını sözlükten bularak açılmış mesaj olarak çıkartır. ayrıca sözlüye her yeni gelen harfi, sözlükten bulduğu bir önceki kayda ekleyerek sözlüğe yeni bir kayıt olarak ekler.
bu durumu müsvedde kod olarak yazmaya çalışırsak:
şifreli mesajdan bir sembol oku
sözlükte karşılığını ara
sözlükte karşılığını bulduğun sürece sıkıştırılmış metni okumaya devam et.
farklı harfe kadar bulduğun sözlük girdisini açılmış mesaja ekle, farklı harfi sözlük girdisine ilave ederek sözlüğe kaydet
metin bitmediyse 2. adımdan yeni harf ile devam et
yukarıdaki açma algoritmasının daha önceden sıkıştırdığımız mesajı nasıl açtığını inceleyelim:
açmak istediğimiz mesaj “4 1 2 3 5 7 9 3” olarak verilmiş olsun ve ilk sözlüğümüz a-1,d-2,i-3,s-4 şeklinde 4 harf içersin.
mesajı işlemeye ilk sembol olan 4 ile başlıyor ve sonucu hemen sözlükten bulup yazıyoruz.
sözlük: a-1,d-2,i-3,s-4,sa-5
4 1 2 3 5 7 9 3 : s
şifreli mesajda bir sonraki sembole geçildiğinde bu iki sembolün birleşimini yukarıda görüldüğü üzere sözlüğe ekliyoruz (4-s ve 1-a harfleri olduğu için sözlüğe yeni bir sa kaydı ekleniyor) ve sembol karşılığı sonuca yazılıyor. aynı durum sonraki adımlarda da devam ediyor:
sözlük: a-1,d-2,i-3,s-4,sa-5,ad-6
4 1 2 3 5 7 9 3 : s a
sözlük: a-1,d-2,i-3,s-4,sa-5,ad-6,di-7
4 1 2 3 5 7 9 3 : s a d
sözlük: a-1,d-2,i-3,s-4,sa-5,ad-6,di-7,is-8
4 1 2 3 5 7 9 3 : s a d i
buraya kadar olan örneklerde hep tek harfli kayıt sözlükten bulunmuş ve yazılmıştır. ilk defa çok harfli bir kayıt olan 5. kayda rastlanmıştır. algoritma aynı yaklaşımla açmaya devam edecek ve sözlük kaydını sonuca yazdıktan sonra yeni kaydı sözlüğe ekleyecektir:
sözlük: a-1,d-2,i-3,s-4,sa-5,ad-6,di-7,is-8,sad-9
4 1 2 3 5 7 9 3 : s a d i sa
yukarıdaki örnekte dikkat edilecek bir husus, 5 girdisinden sonra 7 gelince bu iki girdiyi birleştirerek sadi şeklide sözlüğe bir kayıt girmek yerine, 5 girdisinin sonuna 7 girdisindeki ilk harfi eklemektir. buna dikkat edilmesi gerekir çünkü lzw algoritması her adımda tek bir harf ilave etmektedir.
sözlük: a-1,d-2,i-3,s-4,sa-5,ad-6,di-7,is-8,sad-9,dis-10
4 1 2 3 5 7 9 3 : s a d i sa di
sözlük: a-1,d-2,i-3,s-4,sa-5,ad-6,di-7,is-8,sad-9,dis-10,sadi-11
4 1 2 3 5 7 9 3 : s a d i sa di sad
sözlük: a-1,d-2,i-3,s-4,sa-5,ad-6,di-7,is-8,sad-9,dis-10,sadi-11
4 1 2 3 5 7 9 3 : s a d i sa di sad i
ekşi sözlük kullanıcılarıyla mesajlaşmak ve yazdıkları entry'leri
takip etmek için giriş yapmalısın.
hesabın var mı? giriş yap