AtasoyWeb | Anasayfa | Arşiv | Dosya Deposu | Anketler | RSS Besleme | Tema Seçim Sayfası

Sık Kullanılanlara Ekle | Hakkında | İletişim

   Huffman ağacı ile nasıl sıkıştırma yapılabileceğine dair zamanında yazdığım basit bir örnek.

   Sıkıştırma metotlarının geneli ile ilgili kısa kısa bilgiler yazayım. Bu metotların neredeyse tümünün başarısı, harflerin veya harf dizilerinin tekrar etme sıklığı arttıkça artar. Ayrıca veri miktarı arttıkça verilerin tekrar etme sıklığı arttığından sıkıştırma oranı da artar. Sıkıştırılmış bir verinin bir daha sıkıştırılamamasının sebebi tekrarlı verilerin zaten ortadan kaldırılmış olmasıdır.

   Lzip gibi sözlük tabanlı sıkıştırma metotlarının temelinde de programda kullandığımız mantık vardır. Ancak bu oldukça başarlı algoritmalar veriyi sıkıştırırken, tekrarlı veriler yerine yazılan benzersiz simgelemeleri bir sözlük içerisinde saklarlar ve sadece tekrar eden harferi değil, belli boyutlara kadar harf dizilerini de daha kısa veriler ile değiştirerek ortadan kaldırırlar...

   Huffman ağacı deyip duruyoruz, neden ağaç dediğimizi de açıklayalım. Şekilde görülen 1 ve 0lardan meydana gelmiş merdiven, aslında bir ikili ağaçtır. Veriler kağıda döküldüğünde durum daha iyi anlaşılır. Oluşturduğumuz ikili ağaçta 0, düğümlere ayrılmayan bir düğüme gider; 'çıkmaz sokak'tır. 1 ise bizi, düğümlere ayrılmaya devam eden bir düğüme götürür.

   Bu oluşturduğumuz şey, aslında ağacın en basit halidir. Ağaç çok daha değişik yollarla oluşturulabilir. Tek kısıtlama bir bit dizisinin diğerinin içinde bulundurulmamasının gerekliliğidir. (Bu bana hep 'tunç kafiye' kavramını anımsatır :), tunç kafiye bir kelimenin veya hecenin, diğer satırdaki başka bir kelimenin içinde yer alması ile oluşan kafiyeye deniyor.) Örneğin 1101 kodu A harfini, 11011 de B harfini simgelesin. Bilgisayar, bitleri değerlendirmeye başladı; ağacın kökünden alt düğümlere doğru 1101 kodunu okuyana kadar ilerledi. Şimdi bilgisayar ağaçta gezinmeyi sonlandırıp 'bu A karakteridir' mi desin, yoksa diğer düğüme geçip 11011 kodunu okuduktan sonra 'bu B karakteridir' mi desin?...
#include <iostream>
#include <string>
using namespace std;

void Arttir(int dizi[],string gelen)
{
    if (gelen=="a") dizi[0]++;
    else if (gelen=="b") dizi[1]++;
    else if (gelen=="c") dizi[2]++;
    else if (gelen=="d") dizi[3]++;
    else if (gelen=="e") dizi[4]++;
    else if (gelen=="f") dizi[5]++;
    else if (gelen=="g") dizi[6]++;
    else if (gelen=="h") dizi[7]++;
    else if (gelen=="i") dizi[8]++;
    else if (gelen=="j") dizi[9]++;
    else if (gelen=="k") dizi[10]++;
    else if (gelen=="l") dizi[11]++;
    else if (gelen=="m") dizi[12]++;
    else if (gelen=="n") dizi[13]++;
    else if (gelen=="o") dizi[14]++;
    else if (gelen=="p") dizi[15]++;
    else if (gelen=="r") dizi[16]++;
    else if (gelen=="s") dizi[17]++;
    else if (gelen=="t") dizi[18]++;
    else if (gelen=="u") dizi[19]++;
    else if (gelen=="v") dizi[20]++;
    else if (gelen=="y") dizi[21]++;
    else if (gelen=="z") dizi[22]++;
    else if (gelen==" ") dizi[23]++;
}

int HangiSira(string harf)
{
    if (harf=="a") return 0;
    else if (harf=="b") return 1;
    else if (harf=="c") return 2;
    else if (harf=="d") return 3;
    else if (harf=="e") return 4;
    else if (harf=="f") return 5;
    else if (harf=="g") return 6;
    else if (harf=="h") return 7;
    else if (harf=="i") return 8;
    else if (harf=="j") return 9;
    else if (harf=="k") return 10;
    else if (harf=="l") return 11;
    else if (harf=="m") return 12;
    else if (harf=="n") return 13;
    else if (harf=="o") return 14;
    else if (harf=="p") return 15;
    else if (harf=="r") return 16;
    else if (harf=="s") return 17;
    else if (harf=="t") return 18;
    else if (harf=="u") return 19;
    else if (harf=="v") return 20;
    else if (harf=="y") return 21;
    else if (harf=="z") return 22;
    else if (harf==" ") return 23;
}

string HangiHarf(int sira)
{
    if (sira==0) return "a";
    else if (sira==1) return "b";
    else if (sira==2) return "c";
    else if (sira==3) return "d";
    else if (sira==4) return "e";
    else if (sira==5) return "f";
    else if (sira==6) return "g";
    else if (sira==7) return "h";
    else if (sira==8) return "i";
    else if (sira==9) return "j";
    else if (sira==10) return "k";
    else if (sira==11) return "l";
    else if (sira==12) return "m";
    else if (sira==13) return "n";
    else if (sira==14) return "o";
    else if (sira==15) return "p";
    else if (sira==16) return "r";
    else if (sira==17) return "s";
    else if (sira==18) return "t";
    else if (sira==19) return "u";
    else if (sira==20) return "v";
    else if (sira==21) return "y";
    else if (sira==22) return "z";
    else if (sira==23) return " ";
}

void Sirala(int gelendizi[],int sirali[])
{
    int enbuyuk,dizi[24];
    for(int i=0; i<24; i++) dizi[i] = gelendizi[i];

    for(int i=0; i<24; i++)
    {
        enbuyuk=-1;
        for(int j=0; j<24; j++)
        {
            if(dizi[j]>enbuyuk)
            {
                enbuyuk=dizi[j];
                sirali[i]=j; //indisi sakla. Bağlantılı liste uygulaması da yapmış olduk.
            }
        }
        dizi[sirali[i]]=-1; //az önceki en büyüğü -1 yap ki ondan sonraki en büyüğü bulabilesin
    }
}

string Kodla(string yazi,int sirali[],string yenidegerler[])
{
    int uzunluk=yazi.length(),indis;
    string yanit="";

    for(int i=0; i<uzunluk; i++)
    {
        indis=HangiSira(yazi.substr(i,1));
        int j=0;
        while(sirali[j]!=indis) j++; //sıralı dizide hangi sırada?
        yanit+=yenidegerler[j];
    }
    return yanit;
}

void YeniDegerleriBelirle(string yenidegerler[])
{
    yenidegerler[0]="0";
    for(int i=1; i<24; i++)
        yenidegerler[i]="1"+yenidegerler[i-1];
}

string Coz(string kod,int sirali[])
{
    int uzunluk=kod.length(),i=0;
    string yanit="";

    while(i<uzunluk)
    {
        int birsayisi=0;
        while(kod.substr(i,1)!="0" && i<uzunluk)
        {
            i++;
            birsayisi++;
        }
        i++;
        yanit+=HangiHarf(sirali[birsayisi]);
    };
    return yanit;
}

int main()
{
    int bulunma[24],sirali[24];
    string yenidegerler[24],kodlanmis;
    for(int i=0; i<24; i++) bulunma[i]=0;

    string yazi="dal kalkar kartal sarkar kartal kalkar dal sarkar";

    int uzunluk=yazi.length();

    for (int i=0; i<uzunluk; i++) Arttir(bulunma,yazi.substr(i,1)); //her harfin metinde kaç kere tekrar ettiği bul.

    Sirala(bulunma,sirali); //en çok bulunandan en az bulunana sıralayıp doğru sirali dizisine yaz.

    YeniDegerleriBelirle(yenidegerler); //her harfi, bulunma sayısına göre simgeleyecek bitleri belirle, yani huffman ağacını oluştur.

    cout<<endl<<"Tekrar etme sayilari ve olusturulan agac: "<<endl<<endl;
    for(int i=0; i<24; i++)
        cout<<"'"<<HangiHarf(sirali[i])<<"' -->"<<" "<<bulunma[sirali[i]]<<" -->  "<<yenidegerler[i]<<endl;

    cout<<endl<<endl;
    cout<<"Orjinal yazi: "<<yazi<<endl;

    cout<<endl<<endl;

    kodlanmis=Kodla(yazi,sirali,yenidegerler);
    cout<<"Kod(Bitler): "<<endl<<endl<<kodlanmis<<endl;

    cout<<endl<<endl;

    cout<<"Geri cozulan yazi: "<<Coz(kodlanmis,sirali)<<endl;

    cout<<endl<<endl;

    cout<<"Kodlanmadan Onceki Uzunluk: "<<uzunluk<<endl;
    cout<<"Kodlandiktan Sonraki Uzunluk: "<<kodlanmis.length()/8<<endl;
    double oran;
    oran = kodlanmis.length();
    oran /= 8;
    oran /= uzunluk;
    oran *=100;
    cout<<"Oran: %"<<100-oran<<endl<<endl;

    return 0;
}
   Yukarıda oluşturduğumuz ağaç aslında bir sözlük olarak düşünülebilir.  Normalde bu sözlük sıkıştırılımış verinin içine yazılır ve bu da sıkıştırma oranını düşürür. Örnekte, sözlük boyutunun 24 byte olduğunu görebilirsiniz. (Karakterlerin en çok tekrar edenden, en az tekrar edene doğru sıralanması sözlüğün oluşturulması için yeterlidir. Çünkü sözlük boyutu sabittir ve sadece tekrar eden harfler elenmektedir.) Eğer tüm karakterleri dahil etmek istersek, boyut 256 byte'a kadar yükselir. Sıkıştırılacak verinin boyutu arttırıldıkça, 1 KB göze batmayacak bir boyut olur ve sıkıştırma oranına etkisi önemsenmez. Karakter dizilerini de sözlüğe dahil eden metotlarda sözlük boyutunun veri boyutuna bağlı olarak birkaç MB'a kadar ulaşabileceğini de ekleyelim...
Onaylı yorum bulunmuyor.

Atasoy Blog v3.0 © 2009-2012 Hüseyin Atasoy | Tema Tasarımı: Hüseyin Atasoy

AtasoyWeb Anasayfa | Yukarı Çık