Huffman Algoritması
Huffman 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 algoritmasının amacı, buradaki P karakterini saklamak için harcanan 8 bitlik alanı azaltmaya yöneliktir.
Huffman Algoritması Uygulanışı
İlk olarak sıkıştırılmak istenilen metindeki harflerin frekansını yani tekrar etme sayıları bulunur. Örnek olarak "MERHABA" kelimesini ele alalım. Bu kelimede:
2 adet A
1 adet M
1 adet R
1 adet E
1 adet H
1 adet B
harfleri bulunmaktadır.
Adım 1: En az tekrar eden 2 harfi birleştirelim. Birden çok sayıda harf 1 kere tekrar ettiği için herhangi birini seçebiliriz. M ve E yi birleştirdik.
Adım 2: Artık ME bir bütün halinde oldu ve birleştirme işleminde artık frekansını 2 olarak kabul edeceğiz. En az tekrar eden diğer 2 eleman olarak R ve H seçelim.
Adım 3: Şimdi ise B ve AA kısmını birleştirelim ve frekansı 3 olan bir eleman elde edelim.
Adım 4: Frekansı ez az olan ME ve RH elemanlarını birleştirelim.
Adım 5: Son olarak ise geriye kalan frekansı 3 olan AAB elemanını ve frekansı 4 olan MERH elemanını birleştirip Huffman ağacını oluşturmuş olalım.
Gördüğünüz gibi Huffman ağacımızı oluşturduk ağacın her düğümünün sağ tarafına 1 sol tarafına ise 0 sayısını yerleştirdik. Huffman ağacında ovaller düğüm olmaktadır.
Normalde her bir harfi saklamak için 8 bitlik alana ihtiyacımız vardı. MERHABA için 8x7 den 56 bitlik bir alan gerekiyordu.
Şimdi ise örnek olarak A harfi için 01000001 yerine ağaçtan okları takip ederek A harfini bulalım. Sadece 01 yani 2 bitlik alanda A harfini saklamış olduk.
Huffman Algoritması sayesinde bu şekilde verileri sıkıştırarak bellekten büyük kazanç elde edebiliriz.
Ayrıca "Selection Sort Sıralama Algoritması" dersi için buraya tıklayın.
"Huffman Algoritması" adlı bu makaleyi beğendiyseniz yorum yapmayı ve paylaşmayı unutmayın.
Kaynak: Pubtekno