LZW Sıkıştırma algoritması

Yazan : Şadi Evren ŞEKER

Bilgisayar bilimlerinde kullanılan kayıpsız sıkıştırma (lossless compression) algoritmalarından birisidir. İsmini, algoritmayı 1978 yılında bulan Lempel Ziv ve Welch isimli kişilerin baş harflerinden almıştır.

Algoritma, sıkıştırılacak metin içerisinde harf harf ilerleyerek, mümkün olan en fazla harfi içeren kelimeyi sözlüğe eklemeye çalışmakta ve bu sırada da sözlükteki karşılığı ile metni değiştirmektedir. Böylelikle sıkıştırma işlemi gerçekleşmiş olur. Örneğin 4 harf uzunluğunda bir kelimeyi sözlüğe eklemeyi başardıysak, karşı tarafa gönderilen mesajda tek bir sembol bu dört harflik mesajı içerecektir.

Algoritmanın bir özelliği sözlüğün karşı tarafa iletilmesini gerektirmemesidir. Yani yollanan mesaj içerisinde harflerden oluşan bir sözlük bulunmakla birlikte çok harfli kelimeleri içeren sözlük dinamik olarak oluşturulur ve açan taraf da bu sözlüğü yine dinamik bir şekilde oluşturarak mesajı açar.

Algoritmanın sıkıştırması

Algoritma sıkıştırma işlemi sırasında basitçe, sıkıştırılacak olan metin üzerinde, sözlükte olan bir kelimeyle uyuşan harfler bulduğu sürece ilerler. Farklı bir harfe rastladığı zaman, o ana kadar uyumlu bulduğu harflerden oluşan kelimenin kodunu sonuca yazar ve yeni harfi içeren kelimeyi sözlüğe ekler.

Müsvedde kod (pseudo code) olarak aşağıdaki şekilde yazılabilir:

1. Metinden bir harf al
2. Sözlükte harfi ara
3. Metindeki sıradaki harfi aldığında sözlükteki bir kayda karşılık geliyorsa metinden harf almaya devam et
4. Şimdiye kadar uyan sözlük değerini sonuca bas
5. Uyumu bozan yeni harfle birlikte şimdiye kadar uyan sözlük kaydını, yeni sözlük kaydı olarak ekle
6. 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

saDİsadisadi : 4 1 2

Yukarıdaki durumlara benzer şekilde, İ harfi ilk defa karşılaştığımız bir durum. Sözlükteki d harfini işlerken karşılaştığımız için Dİ 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

sadİSadisadi : 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

İş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

sadisaDİsadi : 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:

1. Şifreli mesajdan bir sembol oku
2. Sözlükte karşılığını ara
3. Sözlükte karşılığını bulduğun sürece sıkıştırılmış metni okumaya devam et.
4. 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
5. 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. İlk 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