Sıkıştırma Algoritmaları-Huffman Sıkıştırma Algoritması


    2. Huffman Ağacının Oluşturulması
    Huffman ağacı Huffman sıkıştırma tekniğinin temel yapısını oluşturur. Huffman ağacını oluşturmak için 1. basamakta elde ettiğimiz karakter sayılarını kullanacağız.

    Genel bir bilgi olması için, Huffman ağacı ikili bir ağaçtır (binary tree). Düğüm (node) diye adlandırdığımız yapılardan oluşur. Düğümler bir veri ve an az 0, en fazla 2 daldan oluşur. Her dal başka bir düğüme bağlanır. Ağacın kök (root) diye adlandırdığımız bir baş düğümü vardır ve en alt düzeye ise yaprak denir. Yaprakların hiç dalı yoktur.

    Örnek:

    Şimdi geçelim Huffman ağacını oluşturmaya;

    Karakter sayıları belirlenir,

    En küçük 2 sayı veya düğüm seçilir ve bu seçilen sayı veya düğümlerden yeni bir düğüm oluşturulur. Oluşturulan düğüm dizinin en sonuna konur ve seçilen elemanlar da diziden dışarı atılır. Düğümün değeri seçilen en küçük ikilinin toplamıdır. 2. aşamaya geri dönülür ve işlem dizide bir eleman kalıncaya kadar devam eder.

    En son kalan eleman Huffman ağacının köküdür. Dikkat edilirse algoritmanın her aşamasında 2 eleman elimine edilir ve 1 yeni eleman eklenir. Böylece dizide n eleman varsa n aşamada işlem bitmiş olur.

    Yukarıdaki örnek için;

    Dikkat edilirse verinin karakterleri huffman ağacında birer yaprak haline geldi.

    Ayrıca şunu da belirtmek gerekir ki huffman ağacı oluşturabilir fakat bunların hepsi denktir.

Tarih:
Hit: 4704
Yazar: renegadealien



Yorumlar


Siftahı yapan siz olun
Yorum yapabilmek için üye girişi yapmalısınız.