Home / Algoritmalar / LZW Algoritması Konu Anlatımı (Python Kodu ile Birlikte)

LZW Algoritması Konu Anlatımı (Python Kodu ile Birlikte)

LZW Algoritması kayıpsız (Lossless) bir sıkıştırma algoritmasıdır. Temel mantığı sıklıkla tekrar eden verileri daha küçük bir veri ile tanımlayıp sözlük oluşturmak ve bu sözlüğü karşı tarafa göndererek gönderilecek verinin küçültülmesi esasına dayanır. Kayıpsız bir algoritma olmasından ötürü temel amaç elbette hiçbir veri kaybının olmamasıdır. Şöyle düşünün karşı tarafa bir yazı göndereceksiniz, bu yazının bir bölümünün kaybolması göze alınabilir mi? elbette alınamaz, bu yüzden metin belgeleri için üretilmiş algoritmalarda hiçbir veri kaybının olması göze alınamaz.

LZW algoritmasının temel mantığı Gönderilecek metin belgesine dayanan bir sözlük oluşturma esasına dayanır. Aslında bizlerin bilgisayarında zaten bir sözlük bulunur, buna ASCII adını veriyoruz. Bilgisayarımızda yazdığımız karakterler (esasında ingilizce karakterler) ASCII kodlaması esasıyla oluşturulur. Mesela 0 (sıfır) karakterinin ASCII kodu 48’dir. A (büyük A) karakterinin kodu ise 65’tir. Bunları tabii ki ezberlemeyeceğiz. Biz burada yalnızca bilgisayarımızda yazdığımız karakterlere karşılık gelen numaraların olduğunu söylemeye çalıştık. LZW algoritmasında ise biz ASCII’yi değil, kendi sözlüğümüzü oluşturmak suretiyle çözüme gideceğiz.

LZW Algoritması Örneği (Video)

Yukarıdaki video’da örnekli anlatımı zaten yaptık, uzun uzun aynı örneği zaten anlatmayacağım, onu yerine bu yazıda sözde kodu anlatmaya çalığacağım.

LZW Algoritması Pseudo Kod (Sözde Kod)

Şimdi yukarıdaki sözde kod bize ne anlatmaya çalışıyor onu irdeleyelim. Satır satır anlatıyorum;

String s; ==> Bu satırda s isimli bir string değişken tanımlanmış. String değişkenler karakterleri tutabilen değişkenlerdi.

char ch; ==> Burada ise karakter değişkeni tanımlanmış. Karakter değişkeninin string’den farkı tek bir karakteri tutabilmesidir. ‘a’ gibi ya da ‘0’ gibi. Yani karakter değişkeninde (dizi olmayan) ‘ab’ gibi bir ifade tutamazsınız.

s = empty string; ==> Bu satırda esasen daha önce oluşturmuş olduğumuz s değişkenine varsayılan olarak boş değer atanmış. Yani s = “”; denmek istenmiş.

while(there is still data to be read) ==> Yani diyor ki, girilen String’de karakter var oldukça döngü dönsün, sonra dursun. Çünkü biz LZW algoritmasında girilen herbir karakteri ayrı ayrı okuyacağız.

ch = read a character; ==> Girilen stringden bir karakter oku ve ch değişkenin ata diyor.

if (dictionary contains s + ch) ==> Eğer mevcut sözlüğümüzde s + ch ifadesi varsa bu bloğa gir diyor. Video’yu izlediyseniz, LZW algoritmasını uygulamaya başlamadan önce bir sözlük oluşturmanız gerektiğini görmüşsünüzdür.

s = s + ch; ==> Eğer if satırındaki şart sağlandıysa yani s + ch ifadesi sözlükte varsa s değerine s + ch atanıyor. Türkçesi eğer s değeri “at”, ch değeri ‘a’ ise, yeni s değerimiz “ata” oluyor.

encode s to output file; ==> Yukarıdaki if şartı sağlanmıyorsa artık else bloğuna girer, ilk satırda ise şunu diyor, s değerinin sözlükteki değerini ekrana bas, ya da kaydet.

add s+ch to dictionary; ==> s + ch ifadesini sözlüğümüze ekliyoruz. Burada tabii index numaralarına falan dikkat etmek gerekiyor.

s = ch; ==> okunan karakteri s değişkenine atıyoruz.

encode s to output file; Bu satırı daha önce de yazmıştık ancak dikkat edin bu en son satırdaki ifade, yani while döngüsünün dışında yer alıyor. Eğer bunu yazmazsanız LZW algoritması son işlemi gerçekleştirmez, bu yüzden de veri kaybı olur.

 

LZW Algoritması Python Kodu

(3.6)

2 comments

  1. peki “_” alttire yerine boşluk ” ” nasıl ekleyebiliriz.

    • algoritmauzmani

      boşluk da aynı şekilde bir karakter. Onu da herhangi bir sayı ile tanımlayabilirsiniz. Ascii kodu 32’dir.

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir