13 Aralık 2013 Cuma

Huffman Kodlama (Veri sıkıştırma yöntemleri)

Huffman kodlama en çok kullanılan veri sıkıştırma yöntemlerinden biridir.

Sembollerin olasılıklarına göre azalan sırada sıralanmasıyla başlar ve aşağıdan yukarıya her yaprakta bir sembol olacak şekilde ağaç oluşturulur.

Her adımda en düşük olasılıklı iki sembol seçilir ve kısmi ağacın tepesine eklenir, listeden silinir ve her iki sembolü de ifade eden tek bir sembolle yer değiştirir.

Listede tek bir sembol kalana kadar devam eder. Sembollerin kodlarını elde etmek için ağaç bir uçtan diğerine dolaşılır.

ÖRNEK

0.4 , 0.2 , 0.1 , 0.2 , 0.1 olasılıklara sahip veriler verilsin.

Yukarıdan aşağıya doğru olasılıkları büyükten küçüğe sıralıyoruz.

Ardından aşağıdan başlayarak toplayarak ilerliyoruz. Alt tarafa 0, üst tarafa 1 diyoruz.

Aynı işlemi a3 ve a4 + a5 in toplamı için yapıyoruz. Yine alt tarafa 0, üst tarafa 1 diyoruz.

Şimdi 0.2 ile 0.4'ü topluyoruz. Burada alt tarafa yani 0.4'ün olduğu tarafa 1, 0.2'nin olduğu tarafa ise 0 diyoruz. Bunun nedeni de 0.4'ün 0.2'den büyük olması.

Son olarak 0.4 ile 0.6'yı topluyoruz. Yine büyük tarafa 1, küçük tarafa 0 veriyoruz.

1.0 sonucuna ulaştık ve toplama işlemlerimiz bitti. Şimdi sıra sembolleri sıkıştırılmış halde ifade etmeye geldi.

Bunu yapabilmek için 1.0'dan ifade etmek istediğimiz sembole giden yolu takip etmemiz gerekiyor.

a1 için

1.0'dan 0 ile doğrudan a1'e gidilebiliyor.

a1 = 0 olur.

a2 için

a2'ye gidebilmek için önce 0.6'ya 1 ile ardından da 0.2'ye 0 ile gidilebiliyor.

a2 = 10 olur.

a3 için

Önce 1 ile 0.6'ya, sonra 0.6'dan 1 ile 0.4'e, son olarak da 1 ile 0.2'ye gidilebiliyor.

a3 = 111 olur.

a4 için

Önce 1 ile 0.6'ya, sonra 1 ile 0.4'e, sonra 0 ile 0.2'ye, son olarak da 1 ile 0.1'e gidilir.

a4 = 1101 olur.

a5 için

Önce 1 ile 0.6'ya, sonra 1 ile 0.4'e, sonra 0 ile 0.2'ye, son olarak da 0 ile 0.1'e gidilir.

a5 = 1100 olur.