by

Huffman Sıkıştırma Algoritması

İyi günler.

Bu yazımda sizlere [Huffman Sıkıştırma Algoritması](http://tr.wikipedia.org/wiki/Huffman_kodu)ndan bahsedeceğim.

İlk olarak Huffman algoritmasından bahsetmek istiyorum. Huffman algoritması temel olarak bir metinde yer alan karakterlerin frekanslarını bularak belli bir düzende Huffman ağacına yerleştirilmesine ve buradan erişilmesine dayanıyor. Biraz daha açıklayıcı konuşalım. Bilgisayarda karakterler 8bit(1 byte) olarak saklanır. Huffman algoritmasındaki asıl amaç karakterlerin kapladığı alanı azaltarak sıkıştırma yapmak.

Mesela bir örnek vermek gerekirse diyelim “AAAABBBCC” diye bir metnimiz var. Normalde bu metin herbir karakter 8bit kaplayacak şekilde yani toplamda 8*9 bitte saklanır. Huffman algoritmasına göre ise şu şekilde saklıyoruz:

**1-**Öncelikle karakterlerin metinde bulunma sıklığı(frekans) larını buluyoruz.
A karakteri metinde 4 kere geçmiş yani frekansı 4
A:  4   ,   B:  3   , C:   2
**2-**Bundan sonra yapılacak işlem en düşük frekansa sahip iki elemanı seçerek onlardan ağaç oluşturma işlemi

[![](http://www.onurbaysan.com/blog/wp-content/uploads/2010/09/tree1.jpg “tree1”)](http://www.onurbaysan.com/blog/wp-content/uploads/2010/09/tree1.jpg)

[![](http://www.onurbaysan.com/blog/wp-content/uploads/2010/09/tree2.jpg “tree2”)](http://www.onurbaysan.com/blog/wp-content/uploads/2010/09/tree2.jpg)

**3-** Şimdide bu karakterlerin yeni hallerinin ne olacağına. Ağaçta kökten itibaren eğer karakterimiz sol alt ağaçta bulunuyorsa koda 0 ekliyoruz , eğer karakter sağ alt ağaçta ise 1 ekliyoruz. Buna göre:

A: 0 oluyor
B: 11
C: 10

**Sonuç:** Normalde “AAAABBBCC” metinini 8*9 bit ile saklıyorduk. Şimdi ise bu metni şu şekilde saklıyoruz.

AAAA  = 0000
BBB = 111111
CC = 1010

“AAAABBBCC” = 00001111111010 yani 14 bit.

Sıkıştırma oranı ((72- 14) / 72) * 100 = %80 oranında sıkıştırdık.