Huffman Kodu, 1952′de MIT’de bir Doktora öğrencisiyken David A. Huffman tarafından bulunmuş kayıpsız bir sıkıştırma algoritmasıdır. Pek çok algoritmanın üstüne geliştirildiği, veri sıkıştırmayı anlamak için temel oluşturan bir veri sıkıştırma tekniğidir. Bu algoritmanın sorduğu iki basit soru vardır;
- Karakterler kodlamak için sabit uzunluk (aynı sayıda bit) kullanmalı mıyız?
- Sabit uzunluk kullanmayacaksak iki karakter arasındaki farkı nasıl anlayacağız?
Değişken uzunluklu kodlamanın gerekliliği
Bu iki soruyu açıklamak için ASCII kodlaması üzerinden gideceğim. Yoksa Huffman Kodu, resimlerin sıkıştırılmasında da (JPEG), ses kütüklerinin sıkıştırılmasında da (MP3) kullanılmaktadır. Varsayalım ki, Not Defteri’ni açtınız ve bir yazı yazmaya başladınız. Bu yazıda tahminen tüm ASCII karakterlerini kullanmayacaksınız. Örneğin kısa bir yazı yazmış ve 28 farklı ASCII karakteri kullanmış olduğunuzu düşünelim. Bu sayıda karakteri kodlamak için kendi kod kelimelerinizi atasanız, beş bit ile her karakteri kodlamanız mümkün olabilir (2^5 = 32 > 28). Yani pek de bir algoritmaya bile ihtiyacınız olmadan %62,5′luk (5/8) bir sıkıştırma oranına erişmeniz mümkün.
Yazacağınız yazıda her karakterin aynı sıklıkta yer alması pek olası değildir. Bilgisayarın bulunmasından yıllar önce Morse, telgraf için yarattığı kodlamada İngilizcedeki harflerin sıklıklarını ele almıştır. Örneğin sık kullanılan E harfi tek bir kısa sinyal (*) ile kodlanırken seyrek kullanılan J harfi bir adet kısa ve üç adet uzun sinyal (* – - – ) ile kodlanmaktadır. Bunun sonucunda da iletişim süreleri azaltılmıştır. Huffman da, sıkıştırmayı arttırabilmek için bunu dinamik bir şekilde verilen girdiye göre yapmayı öngörmüştür.
Neden önek ağacı?
Fakat Morse Kodu’nun da dezavantajı ilk başta sorduğumuz ikinci soruda gizli. Morse kodunda her bir kod sözcüğünden sonra boşluk bırakılmazsa kod sözcükleri birbirine karışabilmektedir. Bunun sebebi bir kod sözcüğünün tamamının başka bir kod sözcüğünün ön kısmı olabilmesidir. Örneğin arada boşluk bırakılmadığı düşünülürse tek başına J harfinin kodu (* – - -); ATT (* – - – ( A= * – , T = -)), ETTT ya da WT gibi pek çok farklı şekilde yorumlanabilir. Bunu engelleyebilmek ancak, hiçbir kod sözcüğünün(A’nın) başka bir kod sözcüğünün(J’nin) ön eki olmamasını sağlamakla mümkündür. Ayrıca bu özellik Morse Kodu’ndaki her iki karakter arasındaki üç kısa sinyal süresince boşluk koymanın oluşturduğu ek yükü de ortadan kaldıracaktır. Örneğin, Morse kodunda ardarda iki adet E harfi, bir kısa sinyal üç kısa sinyallik bekleme ve bir kısa sinyal (* . . . *) olarak iletilebilir. Oysaki gönderdiğimiz sinyalin sadece %40′ı veridir. Örnek katar uzadıkça ek yük de ona göre artmaktadır.
“Ön ek”lerin birbirinden farklı olmasının sağlanması için Huffman ön ek ağacı kullanmıştır. Bu ağaç yapısında veri içeren düğümler yaprak(çocuğu olmayan) konumunda bulundukları için hiçbir kod kelimesi başka bir harfin kod kelimesinin ön eki olamaz. Aynı zamanda çocuğu olan hiç bir düğüm bir kod kelimesine karşılık gelmez.
Ön ek ağaçlarının kullanıldığı bir yer de uluslararası telefon numaralarıdır. +90 ile Türkiye’ye 312 ile Ankara’ya yönlendirilirsiniz fakat Huffman kodlamasının zıttına sabit uzunluklu bir kodlama yönetimidir(her telefon numarası aynı uzunluğa sahiptir). Eğer ki +90 ardından 313 çevirerek Cumhurbaşkanlığı’na doğrudan ulaşabilseydik, ve 313′ün ardından gelen numaralar anlamsız olsaydı, değişken uzunluklu kodlamadan(Huffman benzeri) bahsedebilirdik.
Huffman Ağacının Oluşturulması – Algoritma
- Karakterlerin sıklıkları bulunur ve seyrekten sıka doğru bir öncelik kuyruğuna konulur.
- En düşük sıklığa sahip iki düğüm yeni bir düğümün çocukları olmak üzere kuyruktan alınır.
- Yeni oluşturulan düğüm kuyruğa eklenir.
- Kuyrukta bir adet düğüm kalana kadar ikinci adımdan itibaren bu işleme devam edilir.
Huffman Ağacının Oluşturulması – Örnek
Elimizde aşağıdaki örnek katarın olduğunu düşünelim;
- aaaabbbccddddeeefa
Öncelikle algoritmanın ilk adımını işleterek her bir karakterin sıklığını bulup karakterleri küçükten büyüğe bir öncelik kuyruğuna koyarız. Bu kuyruk şöyle olacaktır;
- f = 1 -> c = 2 -> b = 3 -> e = 3 -> d = 4 -> a = 5
Buradan sonra Visio’da çizdiğim çizgeler üzerinden ilerleyeceğiz. Solda dikey olarak gösterilen öncelik kuyruğu, sağ taraf ise kuyruktaki düğümlerin oluşturduğu ağaçları simgelemektedir. Ayırd edilebilmesi için o adımda oluşturulan düğümleri turuncu, girdi katarında bulunmayan düğümleri (yani yeni oluşturduklarımızı) sarı ile renklendirdim.
|İlk adımda öncelik kuyruğundan en az sıklığa sahip iki düğüm alınır ve bunlar yeni bir düğümün altında birleştirilir. Yeni oluşturulan düğüm birleştirilen iki düğümün toplam sıklığına sahip olur.


f(1) + c(2) = fc (3).Bu yeni oluşturulan düğüm öncelik sırasına konulduğunda, f ve c artık kuyruktan çıkarıldığı için, ilk sırada yer alacaktır.
|Kuyruktaki en az sıklıklı iki düğüm(b ve fc) birleştirilir.Önceki adımda oluşturduğumuz fc düğümü de diğer düğümlerle aynı şekilde ele alınır.


Bu sefer oluşturduğumuz yeni düğüm (bfc) sıklık değeri olarak 6′ya sahiptir ve kuyrukta en son sıraya yerleşir.
|Her adımda tekrarlandığı gibi gene en düşük sıklıklı iki düğüm birleştirilir.


Bu adımda görülebileceği gibi yeni oluşturulan düğüm önceden birbirine bağladığımız düğümlerden farklı bir ağaç yapısı oluşturabilir. Bu aykırı bir durum oluşturmaz, çünkü yeni düğüm kuyruğa konulacağı için eninde sonunda önceki yapı ile birleşecektir.
|Artık sona yaklaştık. Kuyruğumuzda sadece girdide en sık kullanılan ‘a’ karakterinin düğümü kalmış bu karakter de sonradan oluşturduğumuz bfc ile birleştirilerek geriye iki düğümümüzün kaldığı son adıma geçiyoruz.|
|Son adımımızda kuyrukta kalan iki düğüm de birleştiriliyor ve ‘ed’ düğümünün kök konumunda olduğu alt ağaç diğer yapıyla birleşmiş ve Huffman ağacımızın son durumunu oluşturmuş oluyor.|
|Kuyrukta tek düğüm kaldığında Huffman ağacı oluşturma algoritması tamamlanmış oluyor. Kuyrukta kalan tek düğüm artık bizim kök düğümümüz oluyor.


Ağacımızın kenarlarına gerekli değer ataması görselleştirildiğinde her bir karakterin kod sözcüğü bulunabilir (örnekte sol kenarlar 0, sağ kenarlar 1 olarak atanmıştır).
Huffman Ağacında Kod Sözcüklerinin Bulunması
Yukarıdaki örnek ağaca bakıldığında kökten yaprak(çocuğu olmayan) düğümlere gidilirken izlenen yolların değerleri ard arda birleştirildiğinde o düğümün(karakterin) kodu elde edilmiş olur. Örneğin;
f karakterinin kodunu bulurken;
- edabfc -> abfc 1
- abfc -> bfc 11
- bfc -> fc 110
- fc -> f 1100
Diğer yaprak düğümler için de aynı algoritma çalıştırıldığında her bir karakterin kod sözcüğü bulunabilir.
Burada dikkat edilmesi gereken, Huffman’ın algoritması sonucunda düşük sıklığa sahip olan karakterlerin ağacın diplerinde (yani daha uzun kod sözcükleriyle), yüksek sıklığa sahip olan karakterin ise ağacın üstlerinde (yani daha kısa kod sözcükleriyle) bulunmasıdır. Huffman’ın sıkıştırma gücü de buradan gelmektedir.
Huffman kodu ile sıkıştırılmış katarın eski haline getirilmesi
Önek ağacı kullanıldığı ve yaprak düğümler harici veri saklanılmadığı için Huffman Ağacında kod sözcüklerinin çözülmesi oldukça kolaydır. Kodlanmış verinin çözülmesi için kök düğümden başlanarak ve her gelen bit’e karşılık kodlanmış veride bir ilerlenerek yaprak düğüme ulaşılır. Yaprak düğüme ulaşıldığında bir sonraki koda geçildiği anlaşılır ve tekrar kök düğümden başlanarak aynı işlem kodlanmış veri bitene kadar tekrarlanır.
Huffman Kodu ile kodlanmış elimizde bu katarın olduğunu düşünelim; “101111111111101110101”
Yukarıdaki Huffman ağacından faydalanarak bu katarın ilk karakterden başlayıp yolları takip ettiğimizde;
- 1 -> abfc
- 0 -> a (hiç çocuğu yok, köke dön)
- 1 -> abfc
- 1 -> bfc
- 1 -> b (hiç çocuğu yok, köke dön)
İlk iki karakteri üstteki algoritmayı işleterek çözdük, devamı da ağaç takip edilerek çözülebilir.


Bu yazı Hacettepe Üniversitesi Bilgisayar Mühendisliği Bölümü Bil236 Programlama Laboratuvarı 5. Ödevine kaynak olması amacıyla hazırlanmıştır. Derste kullanılan sunuma ulaşmak için;
Huffman Kodu
|Tamamı kopyalanmaksızın kısmen, kaynak gösterilerek kullanılabilir. Yiğitcan Aksarı|