Shannon - Fano sıkıştırma algoritması

Veri sıkıştırma algoritmalarından Shannon-Fano algoritmasının nasıl kullanıldığını anlatacağım.

Daha önce Huffman Kodlama yazısında Huffman veri sıkıştırma algoritmasını anlatmıştım.

Shannon-Fano algoritması da Huffman algoritmasına benzer. Huffman da olduğu gibi olasılıklar büyükten küçüğe doğru sıralanır. Daha sonra olasılıklar toplanır ve ikiye bölünür. İkiye bölerken olasılık toplamlarının birbirine en yakın şekilde bölünmesi gerekmektedir.

Bu şekilde anlatıldığında tam olarak anlaşılamayabilir ancak örnek üzerinden anlattığımda ne kadar basit olduğunu göreceksiniz.

Örnek

A, B, C, D ve E olaylarımız olsun. Bu olayların frekansları da sırasıyla 6, 7, 15, 6 ve 5 olsun.

İlk olarak frekansları büyükten küçüğe doğru sıralıyoruz.

Şimdi frekansları birbirine en yakın olacak şekilde ikiye bölüyoruz. 

15 + 7 = 22 ve 6 + 6 + 5 = 17 yani 22 ve 17 birbirine en yakın olduklarından dolayı B'den sonra bir çizgi çiziyorum ve çizginin üstünde kalanlara 1 altında kalanlara 0 yazıyorum.

Aynı işlemi tekrarlamaya devam ediyorum. Çizginin yukarısında iki tane olay kaldığı için tek bir çizgi çiziyorum ve C'nin yanına 1 B'nin yanına 0 yazıyorum.

Aşağı kısımda ise tekrar ikiye bölmeye devam ediyorum. 6+6 / 5 veya 6 / 6+5 şeklinde bölünebilir. Ancak toplamların birbirine en yakın halini almak gerektiğinden 6 / 6+5 şeklinde bölüyorum. Yani A'nın altından bir çizgi çekiyorum. Çizginin üstüne 1 altına 0 değerini veriyorum.

C, B ve A ile işimiz bitti. Yalnızca D ve E'nin arasına bir çizgi çiziyorum ve D'nin yanına 1, E'nin yanına 0 ekliyorum.

İşlemlerin sonuna geldik. Şimdi olayları Shannon-Fano kodlarıyla ifade edelim.

C : 11

B : 10

A : 01

D : 001

E : 000

Read More

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.

Read More