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.