Veri sıkıştırma, veri sıralama, veri arama, hata düzeltme gibi amaçlarla coding tree’ler kullanılır. Bu yazıda, veri sıkıştırmak için en çok kullanılan algoritmalardan biri olan Huffman Coding Tree‘yi inceleyeceğiz.
Huffman Coding Tree
[A, C, D, B, B, A, D, E, A, C, A, D, A, D] karakter dizisi veya string’i; her bir karakter bellekte 8 bit yer kaplamak üzere, toplamda 14*8 = 112 bit’lik yer kaplamaktadır. Bu stringi huffman coding tree kullanarak daha düşük maliyetle bellekte saklayabiliriz.
Huffman coding tree’de her karakter bir yaprakta tutulur. Her bir karakterin string’de kaç adet olduğu (frekansı) bulunur. Düşük frekansa sahip olan karakterler sola, yüksek frekansa sahip karakterler ise sağa yerleşir.
[A, C, D, B, B, A, D, E, A, C, A, D, A, D] stringi için huffman coding tree oluşturalım:
Öncelikle stringde’ki karakterlerin frekansını bulalım. Küçükten büyüğe bu frekansları sıralayalım.
Frekansları sıraladığımıza göre ağacı oluşturmaya başlayabiliriz.
Öncelikle; en düşük frekansa sahip E ve B’yi, düşük frekans solda olacak şekilde ekleyelim ve bu iki node’un frekansları toplamından bir parent node oluşturalım. Bu parent node’un değerini frekans listesine ekleyelim.
Sırada C var. C’yi 3 node’unun soluna ekleyelim. Bu iki node’un toplamından bir parent node oluşturup değerini frekans listesine ekleyelim.
D ve A’ya geldik. Bu iki karakterin frekanslarını yan yana koyarak bir parent oluşturmalıyız. Eğer node’ları 5’in soluna koyarsak, toplamları 9 olacak ve parent’a yazılacak. fakat bir de en sonda 5 node’u var. Bu durumda 5 ve 9 node’u yan yana gelmiyor. Yani ağaç tamamlanmıyor. Öyleyse node’ları 3’ün soluna koyalım. 3’ün soluna koyduğumuzda, parent’ları 9 olacak ve 5 node’unun yanına yerleşecek. En son 5 ve 9’dan 14 parent’ı oluşacaktır.
Ağacı düzgün bir şekilde oluşturduysak kök değeri toplam frekansı değerine eşit olacaktır.
Şimdi, oluşturduğumuz Huffman codin tree’yi analiz edelim.
Ağaçta node’ların sol kenarlarına 0, sağ kenarlarına 1 değerlerini verelim. Bu değerlere göre kökten başlayarak karakterlerin yollarını belirtelim. Ardından her bir karakterin (1 ve 0, birer bit yer kapladığından) toplam 1 ve 0 değeriyle frekansını çarparak bellekte kapladığı alanı bulalım. En son her bir karakterin bellekte kapladığı alanları toplayıp toplam bellek maliyetini elde edelim. Elde edilen maliyeti ilk maliyetle karşılaştıralım.
