7.8.3. Shannon-Fano Kodlama Ağacı

Shannon-Fano kodlama ağacı Huffman kodlama ağacına benzer; ancak ağacı oluşturma şekli biraz farklıdır. Kodlama ağacı şu şekilde oluşturulur: Karakterler kullanım olasılıklarına göre yukarıdan aşağıya sıralanır ve tüm karakterler toplam kullanım olasılıkları eşit olacak şekilde iki altkümeye ayrılır; yani, bir altküme içerisinde kalan karakter sayısı önemli değildir, önemli olan altküme içerisindeki karakterlerin kullanım olasılıklarının eşit veya birbirine yakın olmasıdır. Yukarıda kalan alt küme içinde kalan karakterlere atanacak kodun ilk bit'i 0, aşağıda kalan altkümedekilere ise 1 atanır. Daha sonra, bu iki alt küme, aynı şekilde altkümelere bölünerek karakterlere atanacak kodlar bulunur. Bölme işlemi altkümelerde 1 karakter kalana kadar sürdürülür.