LZW Algoritması
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:
- 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.
Nasıl Çalışır?
LZW algoritmasının temelinde sözlük(dictionary) yapısı vardır. ASCII tabloda olan bütün karakterler bu sözlük yapısına eklenir. Sonrasında metin taranmaya başlanır. Geçici bir karakter dizisi oluşturulur ve bilinmeyen bir karakter dizisi elde edilene kadar bu diziye eklenir. Bilinmeyen bir karakter dizisine rastlandığında bu sözlüğe eklenir ve en son karakterden devam edilir.
Yukarıdaki aşamaları bira örnekle açıklayalım. Elimizdeki karakter dizisi “aaab” olsun. İçi başta boş olan bir W karakter dizimiz olsun.
- “a” karakter dizisi sözlükte mevcut o yüzden es geçildi.
- Bir sonraki karakter ‘a’ ve W’ye eklendi. “aa” sözlükte mevcut değil o yüzden yeni eleman olarak eklendi. Bir yandan da “a” karakter dizisi sonuca eklendi. W’ye de son eleman olan “a” atandı.
- Bir sonraki karakter olan “a”, W’ye eklendi. Fakat “aa” artık sözlükte o yüzden es geçiyoruz. Sonraki karakter olan “b”, W’ye ekleniyor. Oluşan “aab” sözlükte mevcut değil ve yeni eleman olarak ekleniyor. “aa” sonuca eklenirken son eleman olan “b” W’ye atandı.
- Bu aşamada karakter dizimiz bitti W’de kalan son karakteri de sonuca ekliyoruz.
Örnek Uygulaması
Örnek cümlemiz a b a c a d a b a c a a b a a c a şeklinde harflerden oluşan bir cümle verilsin.
Dictionary(sözlük)’de a:1 b:2 c:3 d:4 default olarak gelsin.Şimdi bir topla oluşturcaz bu tablonun temel mantığında StrChar column’una Temp+Input ifadesini yazıcağız.Temp column’a ise eğer sözlükta yoksa strchar var ise inputu ekliceğiz.
Başlıyalım;
StrChar=Temp+Input
Temp=Intable==N ? input : StrChar
Out[i]=Table[i-1].Intable==Y ? Table[i-1].Strchar : Table[i-1].Input
| Step | Input | StrChar | Intable | Temp | ATTD | OUT |
| 1 | a | a | – | a | – | – |
| 2 | b | ab | N | b | ab(5) | a |
| 3 | a | ba | N | a | ba(6) | b |
| 4 | c | ac | N | c | ac(7) | a |
| 5 | a | ca | N | a | ca(8) | c |
| 6 | d | ad | N | d | ad(9) | a |
| 7 | a | da | N | a | da(10) | d |
| 8 | b | ab | Y | ab | – | – |
| 9 | a | aba | N | a | aba(11) | ab |
| 10 | c | ac | Y | ac | – | – |
| 11 | a | aca | N | a | aca(12) | ac(7) |
| 12 | a | aa | N | a | aa(13) | a(1) |
| 13 | b | ab | Y | ab | – | – |
| 14 | a | aba | Y | aba | – | – |
| 15 | a | abaa | N | a | abaa(14) | aba(11) |
| 16 | c | ac | Y | ac | – | – |
| 17 | a | aca | Y | aca | – | – |
| aca(12) |
Dictionary Table
| 1 | a |
| 2 | b |
| 3 | c |
| 4 | d |
| 5 | ab |
| 6 | ba |
| 7 | ac |
| 8 | ca |
| 9 | ad |
| 10 | da |
| 11 | aba |
| 12 | aca |
| 13 | aa |
| 14 | abaa |
Şimdi biz bu cümleyi 17 karakter her karakter 3 bit olsa 17×4=51 bit ile ifade edebilirdik.Biz 17 karakteri 14 ‘e düşürdük ve tüm karakterlerin boyutu ayrı bit uzunluğunda ifade etmek lazım.
Burada önemli nokta kelime ne kadar uzunsa o kadar sıkıştırma oranı artacaktır.
Karşılaştırma(Huffman vs Lzw)
Bir özde LZW, tekrarların sıklığı ile ilgilidir ve Huffman, tek bayt oluşum sıklığı ile ilgilidir.
LZW sözlük tabanlıdır – giriş verilerini kodlarken, daha önce oluşan alt dizeleri sözlüğe referanslarla değiştirerek sıkıştırmayı başarır.
Cümleler tekrarlanmazsa (veriler az çok rastgele sırada bir sembol akışıdır), LZW verileri çok iyi sıkıştıramaz.
Buna karşılık, belirli semboller (karakterler veya baytlar) diğerlerinden daha sık ortaya çıkarsa, Huffman Coding verileri önemli ölçüde sıkıştırabilir.
Kod karmaşıklığı kodlarda yer almaktadır.Her iki algoritmanın //Worst Case big o (n^2)