Our social:

24 Ocak 2014 Cuma

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

0 yorum: