Huffman Encoding (Sıkıştırma Algoritması)

      Sıkıştırma algoritmaları temel olarak iki kategoride incelenir. Bunlar, kayıplı ve kayıpsız sıkıştırma algoritmalarıdır. Kayıplı algoritmalarda sıkıştırılan veriden orjinal veri elde edilemezken kayıpsız sıkıştırma algoritmalarında sıkıştırılmış veriden orjinal veri elde edilebilir.
   
    Kayıplı sıkıştırma tekniklerine verilebilecek en güzel örnekler MPEG ve JPEG gibi standartlarda kullanılan sıkıştırmalardır. Bu tekniklerde sıkıştırma oranı artırıldığında orjinal veride bozulmalar ve kayıplar görülür. Kayıpsız veri sıkıştırmada durum çok farklıdır. Bu tekniklerde önemli olan orjinal verilerin aynen sıkıştırılmış veriden elde edilmesidir. Bu teknikler daha çok metin tabanlı verilen sıkıştırılmasında kullanılır.
    Bir metin dosyasını sıkıştırdıktan sonra metindeki bazı cümlelerin kaybolması istenmediği için metin sıkıştırmada bu yöntemler kullanılır. Huffman sıkıştırma algoritması kayıpsız bir veri sıkıştırma tekniğini içerir.

Huffman sıkıştırma algoritması şöyle hesaplanır.
-> Dosyadaki her karakterin ne kadar geçtiği yüzde olarak bulunur.
-> Her bir karakter ve yüzdeyi bir ağaç düğümü kabul edilir ve yaprak düğümü olur.
-> Kök düğümler elde edilirken her zaman için küçük iki değere sahip düğüm birleştirilir.
-> Bütün düğümler birleştirilenedek ağaç oluşturulur.
-> Her düğümün sol elemanı 0 , sağ elamanı 1 olarak kabul edilerek kodlama yapılır.

Örnek;
Bir metinde geçen karakterlerin sayıları
A=250 B=350 C=500 D=900 E=1200 F=100 G=600 H=1100

Yüzdeleri hesaplıyoruz.
A=%5 B=%7 C=%10 D=%18 E=%24 F=%2 G=%12 H=%22

Şimdi ağacımızı oluşturuyoruz.

Şimdi hesaplamalarımızı yapıyoruz.

Dosyanın normal boyutu 5000 btye = 5000 x 8(bit ile ifade edildiğinde) =40 000 byte

Huffman algoritması 

= A(5x250)+ B(4x350) + C(3x500) + D(3x900) + E(2x1200) + F(5x100) + G(3x600) + H(2x1100)

=13750 byte sıkıştırılmış hali

Örnek metin "bahc" kodlaması "0001(b)00001(a)11(h)100(c)" "00010000111100" 

Kısaca huffman sıkıştırma algoritmasında karakterin bulunma sıkılığına göre ifade edildiği bit sayısı değişmektedir.

Algoritmanın kodu

Asimptotik Gösterim

Asimptotik Gösterim
    Algoritmaları karşılaştırabilmek için bir algoritmanın zorluk derecesi ölçümüne “Computational Complexity” denir. Aslında problem veya algoritmaların çözüme ulaşmadaki karmaşıklığını ölçmek için kullanılır.Fonksiyon içerisindeki önemsiz kısımlar ve katsayılar atılarak basitleştirilir ve gerçek fonksiyona göre yaklaşık bir değer bulunur. Elde edilen bu yeni etkinlik ölçümüne “Asymptotic Complexity” denir.

    Bunun üç türünü göreceğiz: büyük- \Theta Θ gösterimi, büyük-O gösterimi, ve büyük- \Omega Ω gösterimi.

Büyük-O gösterimi: Algoritmanın çalışabileceği en yüksek üst sınırı ifade eder.Yani bu üst sınırdan daha kötü çalışamayacağını gösterir.
Asymptotic upper bound
-f(n) = O(g(n)), eğer sabit bir c ve n0 değeri için
-f(n) >= c.g(n) bütün n >= n0 değerleri için doğruysa
-f(n) ve g(n) pozitif değere sahip fonksiyonlardır.

Örneğin; T(n)=3n²+8n+3 için O(n²) olduğunu gösterelim.
T(n)=3n²+8n+3   g(n)=n²
c.g(n) >= 3n²+8n+3
c.n² >= 3n²+8n+3
3n²+8n²+3n²  >= 3n²+8n+3
14n² >= T(n)

n0=1 c=14

Büyük- \Omega Ω :Bazen, üst sınır belirlemeden, bir algoritmanın en az belirli bir süre aldığını söylemek isteriz. Bu durumda büyük-Ω gösterimini kullanırız.
Asymptotic Lower Bound
-f(n) = W (g(n)), eğer sabit bir c ve n0 değeri için
-c.g(n) <= f(n) bütün n >= n0 değerleri için doğruysa

Örneğin; T(n)=4n³+2n²+3 için O(n³) olduğunu gösterelim.
T(n)=4n³+2n²+3   g(n)=n³
c.g(n) <= 4n³+2n²+3
c.n³ <= 4n³+2n²+3
4n³ <=  T(n)

Katsayılar atıldığında O(n³) bulunur.

Büyük- \Theta Θ gösterimi:Büyük-Θ gösterimi kullandığımızda, çalışma süresinin üzerinde asimptotik olarak sıkı bir sınır vardır diyebiliriz. "Asimptotik olarak" çünkü sadece n'nin yüksek değerleri için önemlidir. "Sıkı sınır" deriz; çünkü çalışma süresini üstten ve alttan sabit bir çarpana kadar indirebildik.
Asymptotic tight bound
-f(n) = Θ(g(n)), eğer sabit c1, c2, ve n0, değerleri için
-c1.g(n) <= f(n) <= c2.g(n) bütün n >= n0 değerleri için doğruysa

Örneğin;T(n)=2n²+3n+1 için O(n²) olduğunu gösterelim.
T(n)=2n²+3n+1 g(n)=n²
c1.g(n) <= 2n²+3n+1 <= c2.g(n)
c1.n² <= 2n²+3n+1 <= c2.n²
2n² <= 2n²+3n+1 <= 6n²

c1=2 c2=6 n0=1