1-) VERİYAPILARI - SIKIŞTIRMA ALGORİTMALARI

 Sıkıştırma ihtiyacı;

  1- Alan gereksinimini azaltmak için

  2- Zaman ve bant genişliği gereksinimini azaltmak için

Sıkıştırma türleri;

1- Kayıplı Sıkıştırma 

 Bilginin bir kısmı geri elde edilemez (MP3, JPEG, MPEG)  Genellikle ses ve görüntü uygulamalarında kullanılır. Çok büyük ses ve görüntü dosyalarında çok iyi sıkıştırma yapar ve kullanıcı kalitedeki azalmayı fark etmez. 

2- Kayıpsız Sıkıştırma

 Orijinal dosyalar tekrar ve tam olarak elde edilir (D(C(X)))=X, burada C sıkıştırılan dosyayı, D ise açılan dosyayı ifade eder.  .txt, .exe, .doc, .xls, .java, .cpp vs. gibi dosyalarda kullanılır.  Ses ve görüntü dosyalarında da kullanılabilir ancak kayıplı sıkıştırma kadar yüksek sıkıştırma oranına sahip olmaz.

KAYIPSIZ SIKIŞTIRMA

Kayıpsız sıkıştırma temel olarak üç algoritma altında toplanır

• Huffman – her karakter için değişken genişlikli bir kelime kodu (codeword) kullanır . 
• LZ277 – "sliding window (kayan pencere)" kullanır . Bir grup karakteri bir anda sıkıştırır. 
• LZ278/LZW – daha önce karşılaşılan işaretleri saklayan bir sözlük kullanır ve bir grup karakteri aynı anda sıkıştırır. 

Huffman Kodlama 

• Renksiz ve özelliksiz karakterlerden oluşan dosyaların sıkıştırılması için kullanılan kodlardır.
• Dosyadaki bir karakterin tekrar sayısına o karakterin frekansı denir ve karakterlerin tekrar frekansından faydalanarak ikili kodlar üretilir. 
• İki tip kodlama vardır: Sabit uzunluklu ve değişken uzunluklu. 
• Toplam 1.000.000.000 karakterden oluşan bilginin sadece 6 harften {a, b, c, d, e, f} oluştuğunu varsayalım. Karakterlerin kullanım sıklıkları:

• Değişken uzunluklu kodlamada, frekansı en yüksek olan karaktere en kısa kod ve diğer karakterlere benzer mantıkla kod verilirse, sabit uzunluklu kodlamaya göre daha başarılı bir sonuç elde edilir.
•  Kodlama ve kodlamayı çözmek için ön ek (prefix) kodlamadan faydalanılır.
• Kodu çözmek, sabit uzunluklu kodlamada oldukça kolaydır; değişken uzunluklu kodlamada ise, biraz daha zahmetlidir. 
• Sıkıştırılmış bir dosyanın kod ağacı tam dolu ikili ağaç ise, bu sıkıştırma işlemi optimaldir; aksi halde optimal değildir.  Sabit uzunluklu kodlama optimal değildir, çünkü ağacı tam dolu ikili ağaç değildir.

Değişken uzunlukta kodlama: Frekansa göre sıralanır ve her biri bir yaprağı temsil eder. En küçük iki değer bir atada toplanır ve geriye kalan yapraklar ile ata tekrar sıralanır.

adım1:

adım 2:

adım 3:

adım 4:

adım 5:

Toplam Çalışma süresi O(nlogn) olur.

ÖRNEK:

Veri setini ASCII kodu ile kodlanırsa, her karakter için 1 byte(8 bit)’lık alan gerektiğinden toplamda 155 byte(1240 bit)’a ihtiyaç olacaktı. 

Huffman kodlaması ile bu sayı :  60x1 + 40x2 + 25x3 + 20x4 +10x4= 335 bittir.  Görüldüğü gibi Huffman kodlaması ile 335/1240= %27’lik bir sıkıştırma oranı sağlanmaktadır. Bu kazanç, veri setindeki sembollerin frekansları arttıkça daha da artmaktadır