LZW Sıkıştırma Algoritması

LZW Algoritması her şeyden önce sözlük üzerinden ilerler. Tekrar eden verileri sözlüğe ekleyerek bir çıktı oluşturur. Bu sözlüğe sahip olan kişi veriyi decompression eder, yani açarak içerisindeki veriyi okur. 

Bilgisayarlarımızda bu sözlük ASCII tablosudur. Yani aslında direkt bu tabloyu kullanarak LZW algoritması temeline dayanan bir yazılım oluşturmamız mümkündür. Ancak biz LZW algoritması örneği verirken kendi sözlüğümüzü oluşturacağız. Küçük sözlükler konuyu anlamamız için daha iyi olacaktır.

Öncelikli olarak şunu bilmemiz lazım, hiçbir sıkıştırma algoritması mükemmel değildir. Hele lossless sıkıştırma algoritmaları asla değildir. Teorik olarak veriyi küçültmek yerine büyütme ihtimali de mevcuttur. Ancak bu olasılık küçük olduğu için genelde veriyi küçültür. 

Öncelikli olarak bir tane ifademiz olsun "delidelideli"

Bu ifadenin sözlüğünü oluşturalım

e = 1
d = 2
i = 3
l = 4

Dikkat edin, diğer harfler zaten sözlükte olduğu için eklenmiyor. her harf için bir sayı.

1. Bir Harf Alınır

2. Alınan Harf Sözlükte Varsa Çıktıya Değeri Basılır ve Sonraki Harfle Kombinasyon Yapılır (ilk harf her zaman sözlükte vardır!)

3. Alınan Harf Kombinasyonu Sözlükte Yoksa Eklenir.

4. Kombinasyon içerisinden Son Çıktıdaki Harf Kombinasyonu Çıkartılır ve ikinci adımdan devam edilir.

Şimdi LZW Algoritması Mantığı üzerinden, örneğimize devam edelim, elimizde "delidelideli" diye bir ifade var.

1. Adım:
Harf Kombinasyonundan Son Output'u çıkar! (ilk adımda işlem görmez!)
Bir harf alıyoruz. Delidelideli
Sözlükte Var mı? Var! Değeri 2
output[0] = 2

2. Adım:

D Var olduğu için diğer harfle birleştiriyoruz! DElidelideli
Sözlükte Var mı? Yok!
Sözlüğe DE = 5 diye Ekliyoruz!
Sözlüğe Ekleme Yapıldıysa output verilmez!

3. Adım

Sözlüğe ekleme yapıldıysa Harf Kombinasyonundan Son Output'u(D) çıkar! geriye E Kaldı. dElidelideli
E Sözlükte Var mı? Var. Değeri 1
output[1] = 1

4. Adım

E olduğu için diğer harfle birleştir. dELidelideli
Sözlükte Var mı Yok!
Sözlüğe EL = 6 diye ekleme yapılıyorurz.
Output Yok!

5. Adım

Sözlüğe ekleme yapıldığı için son outputu (E) çıkardık. geriye; deLidelideli
L sözlükte var mı? Var! L'nin değeri 4
output[2] = 4
6. Adım

Sözlüğe ekleme olmadığından birleştirme yapıyoruz. deLİdelideli
Sözlükte var mı? Yok!
Sözlüğe Lİ = 7 diye ekledik.
output yok!

7. Adım

Son outputu çıkardık. delİdelideli
i sözlükte var mı? var!
output[3] = 3

8. Adım

Birleştirme yapıyoruz! (bir önceki adımda sözlüğe ekleme olmadığından) delİDdelideli
Sözlükte Var mı? (İD) YOK!
İD = 8 olarak sözlüğe ekliyoruz!
output yok!

9. Adım

Sözlüğe ekleme yaptığımız için son outputu çıkarıyoruz (i) geriye deliDelideli
D sözlükte var mı?
Var Ama daha önce output vermişiz! o halde output vermiyoruz!!!

10. Adım

Birleştirme yapıyoruz. deliDElideli
DE sözlükte var mı? Var! (5)
output[4] = 5

11. Adım

DE sözlükte olduğu için bir birleştirme daha yapıyoruz. deliDELideli
DEL sözlükte var mı? Yok
DEL = 9
output yok!

12. Adım

Son outputu çıkarıyoruz! L kalıyor! delideLideli
L sözlükte var mı? Var ama outputu da var.
output yok!

13. Adım

L sözlükte olduğu için Lİ kalıyor. delideLİdeli
Lİ sözlükte var mı? Var! 7
output[5] = 7

14. Adım

Lİ sözlükte olduğundan birleştirme yapıyoruz! delideLİDeli
LİD Sözlükte var mı? Yok!
LİD = 10 oldu.
output yok!

15. Adım

son outputu çıkarıyoruz! delideliDeli
D sözlükte var mı? Var
Ama outputu yok! çünkü daha önce output vermiş!

16. Adım.

birleştiriyoruz. delideliDEli
DE Sözlükte var mı? var!
Ama daha önce output verdiği için yeni output vermiyoruz!

17. Adım

Birleştiriyoruz! delideliDELi
DEL sözlükte var mı? Var!
output[6] = 9

18. Adım

geriye tek bir harf kaldığı için daha önce output vermiş olsa da ekliyoruz! delidelidelİ

output[7] = 3


Evet bu kadar :) Tam deli işi oldu gerçekten de.

Şimdi sözlüğümüzü tekrar yazalım.

e = 1
d = 2
i = 3
l = 4
de = 5
el = 6
li = 7
id = 8
del = 9
lid = 10

LZW sözlük yapısı bu şekilde oluştu. Şimdi bir de outputlarımızı yazalım

LZW Output: 2 1 4 3 5 7 9 3

peki şimdi ne oldu diyeceksiniz :) Şimdi gelin "delidelideli" ifadesini sözlüğümüzün ilk haliyle yazmaya çalışalım

sözlüğün ilk hali ile: 1 2 4 3 1 2 4 3 1 2 4 3

Her sayıya 1 byte desek etti mi 12 byte. Halbuki bizim outputumuzun herbir sayısı 1 byte olsa 8 byte oluyor. Üstelik tek bir veri kaybı yok. Hemen deneyelim isterseniz.

(outputtaki sayıları birleştirelim) 2 = D 1 = E 4 = L 3 = İ 5 = DE 7 = Lİ 9 = DEL 3 = İ

Gördüğünüz üzere, tekrar eden karakterleri kombine ederek sıkıştırma mantığı içeriyor. Basit ama işlevsel. Unutmayın, eğer ASCII tablosunu kullanmak yerine kendiniz sözlük oluşturduysanız bu sözlüğü karşı tarafa göndermeden o dosyayı açamazsınız.

LZW Algoritması Flowchart