huffman kodu

kayıpsız veri sıkıştırma amacıyla david albert huffman tarafından geliştirilmiş bir algoritmadır.

temel olarak verinin içindeki karakterlerin görülme sıklığını baz alır. görülme sıklığı en az olan iki karakter bir ikili ağaç yapısının sol ve sağ düğümlerine yerleştirilir. ağacın kök düğümü ise bu iki karakterin görülme sıklıklarının toplamı olarak gösterilir. en son ortada tek bir ikili ağaç kalana kadar bu işlem tekrar edilir. örneğin, aaabbbccde şeklinde bir diziyi huffman ağacı haline getirirseniz, böyle bir ağaç elde edersiniz.



örnekte görüldüğü gibi ağacın sol dalları 0, sağ dalları ise 1 olarak nitelendirilir ve bir karakterin kodlamasını çözmek için o karaktere giden yol ağaçtan takip edilir. mesela bu ağaçta d harfinin kodlaması 110 a denk gelir. aaabbbccde verisinin kodlaması ise harflere denk gelen kodlamaların birleştirilmiş halidir.

görselin alındığı kaynak

birinci girdi yeterince açıklayıcı olmadığı için, biraz açıklayalım. öncelikli olarak bu ağacı oluşturmak için, karakterlerin histogramını çıkarmanız gerekmektedir. bundan sonra da en çok karşılaşılan karakter en kısa sürede ulaşabileceğiniz yaprak, bir ağaç yapısındaki çocuğu olmayan düğüm, olmalıdır. bu sayede sıkıştırmanız bir anlam kazanmaktadır. bir karakter için normal şartlarda 1 byte harcanırken, bu sayede daha az alan harcanabilir. tabii giriş seviyesinde bir programlama bilgisiyle kodlanabilecek bir şey değildir. zira bit seviyesinde işlem yapmanızı gerektirir. bit seviyesinde işlem yapmak da, c gibi etkili bir dili düzgün bir şekilde kullanmakla olur.