Huffman kodlaması, girilen veriyi sıkıştırmak amacıyla kullanılan bir sıkıştırma algoritmasıdır. David A. Huffman tarafından 1952 yılında geliştirilmiştir. Günlük hayatta bize gösterilen verilerde her karakterin 8 bitlik ASCII karşılığı vardır. Her bir karakter bellekte 8 bitlik değer ile saklanmaktadır. Ancak bu durum bellek sıkıntısı olan uygulamalar için sıkıntı yaratmaktadır. Huffman’ın geliştirdiği algoritmada, veri içerinde kullanılan her bir karakterin belli bir frekansı (kullanım sıklığı) vardır. Bir karakterin frekansı ne kadar fazla ise bellekte yer aldığı alan o kadar fazladır. Bu sebepten ötürü Huffman, frekansı büyük olan karakterlerin bellekte 8 bit yerine daha az bitle saklanması durumunda yerden kazanılabileceğini düşünmüş ve algoritmasını geliştirmiştir.   Algoritma şu basamakları takip ederek uygulayabiliriz: Karakterler kodlanmadan önce veri içerisindeki her karakter tek tek taranır, frekansları belirlenir. Karakterler frekanslarına göre azalan ya da artan sırada sıralanırlar. (Sıralama için  sıralama algoritmalarından herhangi biri kullanılabilir.   Sıralamanıza göre en küçük 2 frekanslı karakter alınarak ikili ağaç oluşturulur. Frekansları toplamı kök düğüme yazılır. Sonra tekrar sıralama yapılır (ağaçları sıralarken kök düğümdeki değer önemsenir), en küçük 2 birimden tekrar ikili ağaç oluşturulur.  Sıralama işlemi sırada sadece ve sadece tek bir ağaç kalana kadar devam eder. Ağaçta dikkat edilmesi noktalardan biri yaprakların hepsinde harf vardır. Harfler arada dallarda yer almamaktadır. Ağaç oluşturulduktan sonra ağacın kollarına numaralar verilir. Her kök düğümden çıkan sol dala 1, sağ dala 0 ya da sol dala 0, sağ dala 1 verilir. Kök düğümden yapraklara inerken her dal üstündeki karakter okunur, böylece karakterin  yeni değeri ortaya çıkar. Örnek olarak yukarıdaki ağaçta yer alan örneklerin yeni değerleri: 'g'     00 'o'     01 'p'     1110 'h'     1101 'e'     101 'r'      1111 's'     1100 '  '     100 Yukarıdaki gibi kodları elde ettikten sonra veri içerisindeki tüm veriler baştan okunur. Her karaktere karşılık gelen kod yerine yerleştirilir. Böylece veri verimizin boyutunu düşürmüş olduk. Tags: , , , , , | Categories: Algoritma