Lossless bir sıkıştırma algoritması olan Huffman sıkıştırma algoriması, Huffman Kodlaması ismiyle de bilinmektedir.
Temel mantığı, bir yazı dizisi içerisinde geçen harflerin kullanılma sıklığına göre belirli bir algoritma ekseninde ağaç oluşturmaktır. Bu algoritmada sıkça kullanılan harfler daha az yer kaplarken, az sayıda kullanılan harfler ise daha çok yer kaplar. Bu da teorik olarak alandan yer kazanılması anlamına gelmektedir.
Huffman Ağacı Nasıl Oluşturulur?
Huffman ağacı oluşturulmadan önce, sıkıştırılacak içerikteki harflerin sıklığı bulunmalıdır. Sıklığı en düşük olanlar en başa, en fazla olanlar ise en sona yazılmalıdır. Bu örneğimizde kullanacağımız ifadenin texti aşağıda verilmiştir.
dede camii gec
e = 1
g = 1
c = 2
i = 2
m = 3
a = 3
Harflerin sıklıkları bu şekilde düzenlenir.
Sürekli olarak en düşük sıklığa sahip iki harf alınır ve yeni bir toplam oluşturulur. Bu toplam ağacımızın node'unu oluşturur. Birleştirilen harfler ise tek tek child nodeları oluşturmaktadır. Huffman Ağacı bu şekilde oluşturulmaktadır.
Huffman Ağacı Örneği Adım Adım
İrdelenecek yazı
dede camii gec
Öncelik sırası ise: e=1, g=1, c=2, i=2, m=3, a=3
Uyarı!!! Algoritmanın ilk adımında bu öncelik sırası oluşturulmalıdır. En az sıklığa sahip olan en önceliklidir!
2. Adım:
En düşük iki harf birleştirilir. e=1, g=1, c=2, i=2, m=3, a=3
e1 + g1 = eg2
Yeni ifade listeye eklenir. (öncelik sırasına göre) c=2, i=2, eg=2, m=3, a=3;
2
/ \
e g
ilk ağacımız yukarıdaki şekilde oluştu.
3. Adım:
Güncellenmiş listede en küçük iki harfi birleştir c=2, i=2, eg=2, m=3, a=3;
c2 + i2 = ci=3
listeye ekle: eg=2 m=3 a=3 ci=4
Ağaç Oluştur
4
/ \
c i
bu da ikinci ağacımız
4. Adım:
En küçük iki harfi birleştir: eg=2 m=3 a=3 ci=4
eg2+m3 = egm5
kisteye ekle; a=3 ci=4 egm=5
Ağaç Oluştur
5
/ \
m 2
/ \
e g
Ağaç oluşturduk ama biraz değişik yaptık. Neden? Çünkü eg2 birleşik bir ifade. Bu ifadeye bağlı daha önce oluşturulmuş bir ağaç olduğu için o ağacı buraya ekledik.
5. Adım
En küçük iki ifadeyi birleştir. a=3 ci=4 egm=5
a3 + ci4 =aci7
listeye ekle: egm=5 aci=7
Ağaç oluştur.
7
/ \
a 4
/ \
c i
6. Adım
En Küçük iki ifadeyi birleştir: egm=5 aci=7
egm5+aci7=egmaci12
Sona geldiğimiz için son ağacımızı oluşturuyoruz.
Berbat bir çizim farkındayım ama esas amacı sağlıyor :) Biz bu ağacı oluşturarak veriyi küçültmüş olduk
Etiketler: huffman algoritması, Huffman Kodlaması, huffman sıkıştırma algoritması, kayıpsız sıkıştırma
