Huffman Coding

  Huffman Encoding, kayıpsız bir veri sıkıştırma tekniğidir. Sıkıştırılan veri setinde daha çok rastlanan bir karaktere daha az uzunluktaki kod, daha az rastlanan karaktere daha büyük uzunluktaki kodla temsil edilmesine dayanır.

Hadi birlikte adım adım nasıl kodlandığını kısaca görelim.

• Verileri tekrar sıklığına göre sıkıştıracağımız için öncelikle frekans tablosu oluşturacağız. 

• Sonra bu verilerle bir ikili ağaç oluşturup bu ağaç sayesinde hangi verinin nasıl temsil edileceğini bulacağız.

  Örneğin "ARABALAR" kelimesi için bir frekans tablosu oluşturalım.

  

   Daha sonra her karakteri ve frekansını bir ağaç düğümünde tuttuğumuzu düşünelim.

   Bu düğümleri küçükten büyüğe doğru sıralayalım.

   Sıraladığımız düğümlerden en soldaki iki düğümü birleştirelim(frekanslarını topluyoruz).

    Tekrar en soldaki iki düğümü birleştirelim(R(2) düğümünü ve L B(2) düğümünü).

   Yani bütün düğümler birleşene kadar, önce küçükten büyüğe sıralıyoruz sonra da en soldaki iki düğümü birleştiriyoruz. Son olarak A(4) düğümünü de ağaca ekleyelim.

   Ağacın kök düğümünden başlayarak sol bağlantılarına 0, sağ bağlantılarına 1 yazalım. Tam tersini de kullanabiliriz(sol bağlantılara 1, sağ bağlantılara 0). Fakat sıkıştırılan veri setini tekrar çözeceğimiz zaman sıkıntı yaşamamak için kararlı bir şekilde yerleştirmeye dikkat edelim.

Hangi karakterin nasıl oluştuğunu, ikili ağaçta kök düğümden o karakteri tutan düğüme giderken geçtiğimiz bağlantıların üzerindeki sayıları ardı ardına yazarak buluyoruz. Karakterlerin ikili kod karşılıklarını frekans tablomuza ekleyip, sıkıştırılmış ve sıkıştırılmamış veri setlerinin kapladıkları alanları karşılaştıralım.
Yeni oluşan frekans tablomuz:

 

   Tabloda da görüldüğü gibi "A" karakterini artık "0" bitiyle
                                              "R" karakterini "1 0 " bitleriyle
                                              "B" karakterini "1 1 0 " bitleriyle

                                              "L" karakterini "1 1 1 " bitleriyle temsil edeceğiz.

   1 karakter 8 bit yer kapladığı için "ARABALAR" kelimesi 8*8=64 bit yer kaplıyordu.

   Huffman Encoding ile bu alan ("A" için) 4*1 + ("R" için) 2*2 + ("B" için) 1*3 + ("L" için) 1*3 =14 bite düştü.

Bizim bu basit örneğimizde yaklaşık alan kazancı %79 çıktı. Bu kazanç, veri setindeki sembollerin frekansları arttıkça daha da artmaktadır.

Run-Length Encoding

 Run-Length Encoding (RLE),  basit ve kayıpsız veri sıkıştırma algoritmalarından biridir. Bir veri setinde aynı veri dizilerinin sık kullanıldığı durumlar için uygundur. Karmaşık veri setlerinde iyi bir sıkıştırma oranı vermez.

Basit birkaç örnek üzerinde inceleyelim.

 Run-Length Encoding sıkıştırılacak dosyanın özelliklerine uyum sağlamak için birçok yolla ifade edilebilir.

Örnek 1                                                                                                                                                                

veri seti:  AAAAAAAAAAAAAAAAAAAASAAAAAAAAAAS   ( 32 byte )

veri setinde verilen harflerin önce tekrar sıklığını sonra da harfi yazalım.

sıkıştırılmış veri seti:  20A1S10A1S ( 10 byte )

 Veri setinin boyutu 32 byte'tan 10 byte'a düştü.



Örnek 2                                                                                                                                                                

veri seti: 11  13  13  13  13  13  13  13  13  14  14  14  14  15  ( 28 byte )

Bu kez verilen byte dizisi sayılardan oluştuğu için kaçış karakteri kullanarak bu veri setini sıkıştıralım. Eğer tekrar eden byte dizileri varsa başına tekrar ettiğini anlamak için kaçış karakteri koyalım, tekrar etmeyenleri de olduğu gibi yazalım. Kodlama şu şekilde olacak: kaçış karakteri(*), tekrar edilen veri, tekrar sıklığı.

sıkıştırılmış veri seti: 11  *  13  08  *  14  04  15  ( 14 byte )

Veri setinin boyutu 28 byte'tan 14 byte'a düştü.

Peki neden karmaşık veri setlerinde iyi sıkıştırma oranı alamayız?


Eğer birbirini tekrar eden semboller dizisi yoksa veya dizinin tekrar sıklığı üçten küçükse,  RLE verimli bir sonuç vermez. Bu durumu örneklerle inceleyelim.


Örnek 3                                                                                                                                                                

veri seti:  QWERTYY ( 7 byte )

sıkıştırılmış veri seti:  1Q1W1E1R1T2Y  (  14 byte )

 Veri setinin boyutu 7 byte'tan 14 byte'a yükseldi.

Örnek 4                                                                                                                                                               

veri seti:  11  12  12  13  14  14  15   ( 7 byte ) 

sıkıştırılmış veri seti:  11  *  12  02  13  *  14  02  15  ( 16 byte )

 Bu da veri setinin boyutunu kısaltmaktan çok uzatan bir örnek oldu. Veri setinin boyutu 7 byte'tan 16 byte'a yükseldi.

 Örnek 3 ve Örnek 4'te gördüğümüz gibi bu basit algoritma bazı durumlarda fazla verimsiz olduğu gibi doğru yerde kullanıldığında çok büyük oranlarda dosya sıkıştırmaya yardımcı olabilir. 

 Örnek 1 gibi, birbirini tekrar eden binlerce karakterden oluşan bir text dosyası olduğunu düşünürsek, sıkıştırma oranın ne kadar yüksek olabileceğini hayal edebiliriz.