Huffman kodu algoritması, veri sıkıştırma için kullanılan bir algoritma çeşididir. David A. Huffman tarafından 1952 yılında geliştirilmiştir. Her bir karakterin ascii tablosundaki karşılığının ikili tabanda bir değeri vardır. Örnek olarak P harfinin ascii tablosundaki karşılığı 80 sayısıdır. 80 sayısı bellekte 01010000 şeklinde 8 bitlik yer kaplar. Huffman kodu algoritmasının amacı, buradaki P karakterini saklamak için harcanan 8 bitlik alanı azaltmaya yöneliktir. Bu yazı içerisinde huffman kodu algoritmasının akış diyagramını ve akış diyagramının analizini paylaşarak algoritmayı nasıl gerçekleyeceğimize de bakacağız. Ayrıcak huffman kodu algoritmasının C programlama dilindeki kodlanışı için yazının en altındaki bağlantıyı takip edin.
Huffman Kodu Algoritması
Bir verinin huffman kodunu oluşturmak için öncelikle o veride geçen karakterlerin frekanslarını yani tekrar etme sıklıklarını bilmemiz gerekmekte. Daha sonra karakterler frekanslarına göre sıralamalı ve huffman ağacını oluşturmalıyız. Huffman kodu algoritması ile bir string sıkıştırmaya çalıştığımızı varsayarsak uygulamamız gereken adımlar sırası ile aşağıdaki gibi olmalıdır.
— Stringin içerisindeki karakterlerin tekrar etme sayıları (frekans) bulunur.
— Karakterler frekans büyüklüklerine göre küçükten büyüğe sıralanır.
— Şimdi ise frekanslarına göre sıralı karakterlerden huffman ağacı oluşturulması gerekmekte. Huffman ağacını oluşturmak içinde sırası ile aşağıdaki 3 maddeyi uygulamamız gerekiyor.
Huffman ağacı oluşturmak için ard arda gelen elemanları toplayıp yeni bulduğumuz sayıyı frekansların saklandığı sayı dizisi içerisinde uygun gelen yerlere yerleştirin.
Elemanları toplarken daha önce toplanmamış elemanlardan seçilmek zorunda ve daha önce bir toplama işleminden elde edilen sayılarda kullanılmalı.
Bu işlemler tamamlandıktan sonra dizinin sağ tarafından yani büyük olan kısımdan başlayıp bir binary tree (ikili ağaç) şeklinde düşünerek ağaca yerleştirilmeli.
Örnek: Sayı dizisi –> 10 15 20 olsun. Toplama işleminden sonra yeni sayı dizisi: 10 15 20 25 45 olur. Bu frekansları ağaca yerleştirdiğimizde ise aşağıdaki gibi bir görüntü oluşur.
45
/ \
20 25
/ \
10 15
— Huffman ağacı oluşturulurken gördüğünüz gibi 45 sayısını oluşturan sayılardan 20 sol tarafa 25 sağ tarafa, 25 sayısını oluşturan 10 ve 15 sayılarından 10 sol tarafa ve 15 sağ tarafa geldi. Bu şekilde küçükleri hep sola büyükleri hep sağa veya tam tersi şekilde yapabilirsiniz.
— Yukarıdaki ağaç için 20 kere tekrar eden karakterin huffman kodu 0, 10 kere tekrar eden karakterin huffman kodu 01 ve 15 kere tekrar eden karakterin huffman kodu ise 11 olur.
Bir string üzerinde huffman kodu algoritması ile kayıpsız veri sıkıştırma işleminin adımları kısaca yukarıdaki gibi özetlenebilir. Şimdi huffman kodu algoritmasına bir örnek ile devam edelim. Daha sonrasında ise huffman kodu algoritmasının akış diyagramına bir göz atalım ve akış diyagramı üzerinden huffman kodu algoritmasının nasıl gerçeklenebileceğini görelim.
Huffman Kodu Algoritması Örneği
Elimizde bir string olan “MERHABA” kelimesinin olduğunu varsayalım. Normalde bir “char” karakteri depolayabilmek için bilgisayarlarımızda ayrılan alan 8 bittir. “MERHABA” kelimesinde 7 harf olduğundan bu kelimeyi depolayabilmemiz için toplamda 56 bit alana ihtiyacımız vardır. Şimdi huffman kodu algoritması ile ihtiyaç duyduğumuz bu alanı nasıl azaltacağımızı görelim.
2 adet A
1 adet M
1 adet R
1 adet E
1 adet H
1 adet B
Elimizde yukarıdaki harfler bulunmaktadır. Bu harflerin frekanslarına göre sıralı hali aşağıdadır.
1 1 1 1 1 2
Şimdi yukarıdaki huffman kodu algoritmasının adımlarını anlatırken bahsettğimiz ard arda gelen ve daha önce bir toplama işlemine tabii tutulmamış elemanları toplayarak frekans dizisi içerisinde uygun yerlere yerleştirme işlemini yapalım. Burada iki sayının toplamı ile oluşmuş elemanları belirtmek için başına “-” işareti koyacağız.
Frekans dizimizin son hali aşağıdaki gibi olur.
1 1 1 1 1 2 2 2 3 4 7
Şimdi toplama işleminden sonra elde ettiğimiz frekans dizisinin elemanları huffman ağacına yerleştirelim.
7
/ \
3 4
/ \ / \
2 1 2 2
A M / \ / \
1 1 1 1
R H B E
Huffman ağacını oluştururken sağ taraftan başlayarak en büyük elemanı köke yerleştirdik ve kökü oluşturan elemanları küçük olan sol tarafa gelecek şekilde ekledik. Buradan sonra aynı işlem sürekli tekrarlanarak huffman ağacı elde edilir.
Şimdi yukarıda oluşturduğumuz huffman ağacından huffman kodlarını elde edelim.
Huffman Kodları:
A — 00
M — 01
R — 100
H — 101
B — 110
E — 111
“MERHABA” kelimesi içerisindeki her bir karakter için huffman kodu algoritmasını kullanarak elde ettiğimiz huffman kodları yukarıdaki gibidir. Normalde bu kelimeyi saklayabilmek için 56 bit alana ihtiyacımız vardı. Şimdi ise 16 bitlik bir kısımda bu kelimeyi saklayabileceğiz. Yaklaşık %70’lik bir alan tasarrufu sağladık. Bir başka örnek için huffman kodu algoritmasının nasıl çalıştığını görelim.
Aşağıdaki harfler, bir metinde karşılarına verilen sayıda geçmiş olsun,
A — 20
E — 30
ı — 5
i — 8
O — 10
Bu değerleri küçükten büyüğe sıralayalım:
5 8 10 20 30
Burada yukarıdaki değerleri bir ikili ağaca yerleştireceğiz. Ancak bundan önce şu işlemi gerçekleştireceğiz; Ard arda gelen her ikili sayıyı birbiri ile toplayıp küçükten büyüğe sıra bozulmayacak şekilde diziye yerleştireceğiz. Bir kere toplamada kullanılan sayı bir daha kullanılmayacak.
Toplamların belli olması için başına “-“ işareti koyalım.
5 8 10 -13 20 -23 30 -43 -73
Şimdi huffman ağacımızı oluşturalım.
Huffman ağacımızda her bir harf için aşağıdaki huffman kodlarını elde ederiz.
A — 10
E — 0
ı — 100
i — 101
O — 111
Bu şekilde 2 farklı örnek üzerinden huffman kodu algoritmasının mantığını, çalışma prensibini öğrendik. Şimdi de huffman kodu algoritmasını nasıl gerçekleyebileceğimizi akış diyagramı üzerinde görelim.
Huffman Kodu Algoritması Akış Diyagramı
Huffman kodu algoritması akış diyagramının analizi aşağıdaki gibidir.
— Kullanıcıdan frekans dizisini ve dizinin boyutunu aldık. Burada frekans dizisini 2 satırlı bir matriste saklıyoruz. Matrisin bir satırında frekans dizisi varken diğer satırında ileride kullanacağımız, sayının bir frekans mı yoksa frekansların veya diğer toplamların toplamından oluşmuş bir sayımı olduğunu, 0 ve 1 sayıları ile işaretleyerek saklıyoruz.
— Daha sonra frekansları sıralıyoruz. Burada gördüğünüz gibi selection sort algoritması ile frekansları sıraladık.
— For döngüsü ile başlayan kısımda tmp isimli bir değişkene ard arda gelen elemanların toplamını atıyoruz ve bu elemanı frekans dizisi içerisinde ilerleyerek uygun yere yerleştiriyoruz.
— “hfAgac” isimli 2 satırlı matris içerisinde huffman ağacımızı saklayacağız. “hfmn” matrisinde yer alan frekans dizisinin son elemanını “hfAgac” matrisinin ilk elemanı olarak atadık. Yani ilk elemanda en büyük eleman olacak olan kök saklandı.
— Sonrasında ise ard arda gelen 2 elemanın toplamı köke eşit olana kadar ve bu sayılar ağacın yaprağı olmadığı sürece ilerleyerek ikili sayılara bakıyoruz ve bunlar kökün “x2” ve “x2+1” sayılarındaki indislerine yerleştiriyoruz. Bu işlemi bütün elemanlar için yaptığımızda huffman ağacını elde ederiz.
— Son olarak ise huffman kodlarını bulmak kaldı. Bu işlem için “hfcode” isimli matris kullanıldı ve bir sayının indisinin 2 tabanında modu sürekli alınarak sonuç “hfcode” matrisinde uygun yerde saklandı. Bir örnek vermek gerekirse 5. indisteki sayı için, 5 mod 2 = 1, (5, 2 ye bölünür) 2 mod 2 = 0, (2, 2 ye bölünür, çıkan sayı 2’den küçük akış durur) elde ettiğimiz değer “10”. Değerin doğruluğunu kontrol edelim.
x (0)
/ \ 1
(1) x x (2)
/ \ /0 \
x x x x
(3) (4) (5) (6)
5. indisteki eleman görüldüğü gibi 1 ve 0 sayılarının huffman ağacı üzerinde sırası ile takibi sonrası elde edilir. Yani algoritmamız doğru çalışıyor.
Kaynak
