Huffman Kodu – Veri sıkıştırmanın temelleri

Huffman Kodu, 1952′de MIT’de bir Doktora öğrencisiyken David A. Huffman tarafından bulunmuş kayıpsız bir sıkıştırma algoritmasıdır. Pek çok algoritmanın üstüne geliştirildiği, veri sıkıştırmayı anlamak için temel oluşturan bir veri sıkıştırma tekniğidir. Bu algoritmanın sorduğu iki basit soru vardır;

  • Karakterler kodlamak için sabit uzunluk (aynı sayıda bit) kullanmalı mıyız?
  • Sabit uzunluk kullanmayacaksak iki karakter arasındaki farkı nasıl anlayacağız?

Değişken uzunluklu kodlamanın gerekliliği

Bu iki soruyu açıklamak için ASCII kodlaması üzerinden gideceğim. Yoksa Huffman Kodu, resimlerin sıkıştırılmasında da (JPEG), ses kütüklerinin sıkıştırılmasında da (MP3) kullanılmaktadır. Varsayalım ki, Not Defteri’ni açtınız ve bir yazı yazmaya başladınız. Bu yazıda tahminen tüm ASCII karakterlerini kullanmayacaksınız. Örneğin kısa bir yazı yazmış ve 28 farklı ASCII karakteri kullanmış olduğunuzu düşünelim. Bu sayıda karakteri kodlamak için kendi kod kelimelerinizi atasanız, beş bit ile her karakteri kodlamanız mümkün olabilir (2^5 = 32 > 28). Yani pek de bir algoritmaya bile ihtiyacınız olmadan %62,5′luk (5/8) bir sıkıştırma oranına erişmeniz mümkün.

450px-international_morse_codesvg

Morse Kodu sözcükleri (Kaynak: Wikipedia)

Yazacağınız yazıda her karakterin aynı sıklıkta yer alması pek olası değildir. Bilgisayarın bulunmasından yıllar önce Morse, telgraf için yarattığı kodlamada İngilizcedeki harflerin sıklıklarını ele almıştır. Örneğin sık kullanılan E harfi tek bir kısa sinyal (*) ile kodlanırken seyrek kullanılan J harfi bir adet kısa ve üç adet uzun  sinyal (* – - – ) ile kodlanmaktadır. Bunun sonucunda da iletişim süreleri azaltılmıştır. Huffman da, sıkıştırmayı arttırabilmek için bunu dinamik bir şekilde verilen girdiye göre yapmayı öngörmüştür.

Neden önek ağacı?

Fakat Morse Kodu’nun da dezavantajı ilk başta sorduğumuz ikinci soruda gizli. Morse kodunda her bir kod sözcüğünden sonra boşluk bırakılmazsa kod sözcükleri birbirine karışabilmektedir. Bunun sebebi bir kod sözcüğünün tamamının başka bir kod sözcüğünün ön kısmı olabilmesidir. Örneğin arada boşluk bırakılmadığı düşünülürse tek başına J harfinin kodu (* – - -); ATT (* – - – ( A= * – , T = -)), ETTT ya da WT gibi pek çok farklı şekilde yorumlanabilir. Bunu engelleyebilmek ancak, hiçbir kod sözcüğünün(A’nın) başka bir kod sözcüğünün(J’nin) ön eki olmamasını sağlamakla mümkündür. Ayrıca bu özellik Morse Kodu’ndaki her iki karakter arasındaki üç kısa sinyal süresince boşluk koymanın oluşturduğu ek yükü de ortadan kaldıracaktır. Örneğin, Morse kodunda ardarda iki adet E harfi, bir kısa sinyal üç kısa sinyallik bekleme ve bir kısa sinyal (* . . . *) olarak iletilebilir. Oysaki gönderdiğimiz sinyalin sadece %40′ı veridir. Örnek katar uzadıkça ek yük de ona göre artmaktadır.

“Ön ek”lerin birbirinden farklı olmasının sağlanması için Huffman ön ek ağacı kullanmıştır. Bu ağaç yapısında veri içeren düğümler yaprak(çocuğu olmayan) konumunda bulundukları için hiçbir kod kelimesi başka bir harfin kod kelimesinin ön eki olamaz. Aynı zamanda çocuğu olan hiç bir düğüm bir kod kelimesine karşılık gelmez.

Ön ek ağaçlarının kullanıldığı bir yer de uluslararası telefon numaralarıdır. +90 ile Türkiye’ye 312 ile Ankara’ya yönlendirilirsiniz fakat Huffman kodlamasının zıttına sabit uzunluklu bir kodlama yönetimidir(her telefon numarası aynı uzunluğa sahiptir). Eğer ki +90 ardından 313 çevirerek Cumhurbaşkanlığı’na doğrudan ulaşabilseydik, ve 313′ün ardından gelen numaralar anlamsız olsaydı, değişken uzunluklu kodlamadan(Huffman benzeri) bahsedebilirdik.

Huffman Ağacının Oluşturulması – Algoritma

  1. Karakterlerin sıklıkları bulunur ve seyrekten sıka doğru bir öncelik kuyruğuna konulur.
  2. En düşük sıklığa sahip iki düğüm yeni bir düğümün çocukları olmak üzere kuyruktan alınır.
  3. Yeni oluşturulan düğüm kuyruğa eklenir.
  4. Kuyrukta bir adet düğüm kalana kadar ikinci adımdan itibaren bu işleme devam edilir.

Huffman Ağacının Oluşturulması – Örnek

Elimizde aşağıdaki örnek katarın olduğunu düşünelim;

  • aaaabbbccddddeeefa

Öncelikle algoritmanın ilk adımını işleterek her bir karakterin sıklığını bulup karakterleri küçükten büyüğe bir öncelik kuyruğuna koyarız. Bu kuyruk şöyle olacaktır;

  • f = 1 -> c = 2 -> b = 3 -> e = 3 -> d = 4 -> a = 5

Buradan sonra Visio’da çizdiğim çizgeler üzerinden ilerleyeceğiz. Solda dikey olarak gösterilen öncelik kuyruğu, sağ taraf ise kuyruktaki düğümlerin oluşturduğu ağaçları simgelemektedir. Ayırd edilebilmesi için o adımda oluşturulan düğümleri turuncu, girdi katarında bulunmayan düğümleri (yani yeni oluşturduklarımızı) sarı ile renklendirdim.

huffman1

1. Adım

İlk adımda öncelik kuyruğundan en az sıklığa sahip iki düğüm alınır ve bunlar yeni bir düğümün altında birleştirilir. Yeni oluşturulan düğüm birleştirilen iki düğümün toplam sıklığına sahip olur.
f(1) + c(2) = fc (3).Bu yeni oluşturulan düğüm öncelik sırasına konulduğunda, f ve c artık kuyruktan çıkarıldığı için, ilk sırada yer alacaktır.

huffman2

2. Adım

Kuyruktaki en az sıklıklı iki düğüm(b ve fc) birleştirilir.Önceki adımda oluşturduğumuz fc düğümü de diğer düğümlerle aynı şekilde ele alınır.

Bu sefer oluşturduğumuz yeni düğüm (bfc) sıklık değeri olarak 6′ya sahiptir ve kuyrukta en son sıraya yerleşir.

huffman3

3. Adım

Her adımda tekrarlandığı gibi gene en düşük sıklıklı iki düğüm birleştirilir.

Bu adımda görülebileceği gibi yeni oluşturulan düğüm önceden birbirine bağladığımız düğümlerden farklı bir ağaç yapısı oluşturabilir. Bu aykırı bir durum oluşturmaz, çünkü yeni düğüm kuyruğa konulacağı için eninde sonunda önceki yapı ile birleşecektir.

huffman4

4. Adım

Artık sona yaklaştık. Kuyruğumuzda sadece girdide en sık kullanılan ‘a’ karakterinin düğümü kalmış bu karakter de sonradan oluşturduğumuz bfc ile birleştirilerek geriye iki düğümümüzün kaldığı son adıma geçiyoruz.

huffman5

5. Adım

Son adımımızda kuyrukta kalan iki düğüm de birleştiriliyor ve ‘ed’ düğümünün kök konumunda olduğu alt ağaç diğer yapıyla birleşmiş ve Huffman ağacımızın son durumunu oluşturmuş oluyor.

huffman6

Huffman ağacı

Kuyrukta tek düğüm kaldığında Huffman ağacı oluşturma algoritması tamamlanmış oluyor. Kuyrukta kalan tek düğüm artık bizim kök düğümümüz oluyor.

Ağacımızın kenarlarına gerekli değer ataması görselleştirildiğinde her bir karakterin kod sözcüğü bulunabilir (örnekte sol kenarlar 0, sağ kenarlar 1 olarak atanmıştır).

Huffman Ağacında Kod Sözcüklerinin Bulunması

Yukarıdaki örnek ağaca bakıldığında kökten yaprak(çocuğu olmayan) düğümlere gidilirken izlenen yolların değerleri ard arda birleştirildiğinde o düğümün(karakterin) kodu elde edilmiş olur. Örneğin;

f karakterinin kodunu bulurken;

  • edabfc -> abfc 1
  • abfc -> bfc 11
  • bfc -> fc 110
  • fc -> f 1100

Diğer yaprak düğümler için de aynı algoritma çalıştırıldığında her bir karakterin kod sözcüğü bulunabilir.

Burada dikkat edilmesi gereken, Huffman’ın algoritması sonucunda düşük sıklığa sahip olan karakterlerin ağacın diplerinde (yani daha uzun kod sözcükleriyle), yüksek sıklığa sahip olan karakterin ise ağacın üstlerinde (yani daha kısa kod sözcükleriyle) bulunmasıdır. Huffman’ın sıkıştırma gücü de buradan gelmektedir.

Huffman kodu ile sıkıştırılmış katarın eski haline getirilmesi

Önek ağacı kullanıldığı ve yaprak düğümler harici veri saklanılmadığı için Huffman Ağacında kod sözcüklerinin çözülmesi oldukça kolaydır. Kodlanmış verinin çözülmesi için kök düğümden başlanarak ve her gelen bit’e karşılık kodlanmış veride bir ilerlenerek yaprak düğüme ulaşılır. Yaprak düğüme ulaşıldığında bir sonraki koda geçildiği anlaşılır ve tekrar kök düğümden başlanarak aynı işlem kodlanmış veri bitene kadar tekrarlanır.

Huffman Kodu ile kodlanmış elimizde bu katarın olduğunu düşünelim; “101111111111101110101”

Yukarıdaki Huffman ağacından faydalanarak bu katarın ilk karakterden başlayıp yolları takip ettiğimizde;

  • 1 -> abfc
  • 0 -> a (hiç çocuğu yok, köke dön)
  • 1 -> abfc
  • 1 -> bfc
  • 1 -> b (hiç çocuğu yok, köke dön)

İlk iki karakteri üstteki algoritmayı işleterek çözdük, devamı da ağaç takip edilerek çözülebilir.


Bu yazı Hacettepe Üniversitesi Bilgisayar Mühendisliği Bölümü Bil236 Programlama Laboratuvarı 5. Ödevine kaynak olması amacıyla hazırlanmıştır. Derste kullanılan sunuma ulaşmak için;

Huffman Kodu
ftp://ftp.cs.hacettepe.edu.tr/pub/dersler/BIL2XX/BIL236_PL-II/08-09/5/Huffman Kodu.pdf


Tamamı kopyalanmaksızın kısmen, kaynak gösterilerek kullanılabilir. Yiğitcan Aksarı
Digg This
Reddit This
Stumble Now!
Buzz This
Vote on DZone
Share on Facebook
Bookmark this on Delicious
Kick It on DotNetKicks.com
Shout it
Share on LinkedIn
Bookmark this on Technorati
Post on Twitter
Google Buzz (aka. Google Reader)
This entry was written by yaksari , posted on Pazartesi Nisan 20 2009at 02:04 pm , filed under Dersler and tagged , , , , , , . Bookmark the permalink . Post a comment below or leave a trackback: Trackback URL.

10 Responses to “Huffman Kodu – Veri sıkıştırmanın temelleri”

  1. iyi günler. huffman koduyla yazmış olduğunuz örnek bir program var mı acaba? ya da herhangi bir dil üzerine uygulanmış örnek kod? verdiğiniz linkteki örnek çalışmıyor.

  2. Verdiğim bağlantı sadece derste kullanılan sunumu içeriyordu. Şimdi düzelttim, hatalı olduğunu farketmemiştim.

    Açıkcası böyle temel konularda çözüm mahiyetinde kodlar vermeyi etik açıdan doğru bulmuyorum. Buradaki yazının yazılma sebebi de bir laboratuvar ödevi olduğu için kodu vermem oldukça mantıksız olabilirdi.

    Tabi ki google’da birkaç arama yaparsanız kaynak kodlara ulaşmanız mümkün.

  3. paylaşmamak istememe nedeninizi anlayabiliyorum fakat benim de proje ödevim Huffman koduyla ilgili olduğu için yazmaya başlamadan önce bir örnek görmek istedim. yine de teşekkür ederim.

  4. Eyvallah çok güzel açıklamışın …Biz ege üniversitesinde bu hazır algoritmalar üzerinde pek durmuyoruz.Onu hocalar bize havale ediyorlar(Tabi bi de ALLAHA:D)..Ama derste değiniliyor.yani bu algoritma ne işer yarar yada yaramaz diye.anlaşılmasını bize bırakıyorlar.Bize “olan şey ile uğraşıp yaparsaınız..Maksat sizin hala olmayan şeyleri ortaya çıkarmanızdır.Sizi bu algoritmalar ile mezun edersek bilmiyeni değil sadece bilineneni öğrenirsiniz..”…
    BENCE HEM DOĞRU HEM YANLIŞ.ikisini bir arada götürsek daha iyi.Tabi hocalar daha iyi biliyor.Bilmeselerdi eğer biz yazılımda lider olmadık….biz bir ödev içerisinde kullanmadığımız metot kalmıyor.Emin olun piyasadaki bazen tüm algoları kullanıoz:D:D:D:D

  5. İnternette arama yapıp bu siteye ulaştığınıza göre referans olarak kullandığınız bir yazıya böyle bir yorum yapmanız ilginç geldi. Ege’den mezun arkadaşlarım da var ama hiçbiri bu kadar kendini kanıtlama derdinde değildi. Ne demişler ainesi iştir kişinin lafına bakılmaz. Bu sebeple, buralara yorum yazıp kendinizi kanıtlamaya uğraşacağınıza bir şeyler üreterek kendinizi kanıtlamanızı tavsiye ederim.

    Kısa bir açıklama;
    Bu ödev 2.sınıflara Assembly dilinde verilmişti. Amaç işlemci düzeyinde pointer kullanımını öğretmekti. Bu sebeple Huffman Kodu amaç değil araçtı. Kısacası üst düzey bir dilde Huffman Kodu öğretmek gayesi güden bir ödev değildir.

  6. çook sağolun süper anlattınız..yüksek lisansınız da başarılar..

  7. Mükemmel anlatmışsınız.Gerçekten çok yararlı bir yazı.Teşekkürler.

  8. VAy be eski anılarım depreşti. Huffman algoritmasını assembly de yapan kodu yazmıştık. Ben okurken Lab odeviydi. Sıkıştırma(compression) ve açma(decompression) yapıyordu. Hatta sıkıştırma oranını felan veriyordu. Bol bol hata alıp, iyice haşır neşir olmuştuk assembly ile. İyi çalışmalar Yiğitcan hocam.

  9. Allah senden razı olsun Yiğitcan.Çok yardımcı bir yazı olmuş.Kendine dikkat et.

  10. Güzel yazı olmuş. Wikipediadan buraya yönlendirildim. Özellikle yaprağa ulaşınca yeni kelimenin kodlarının artık gelmesine hayran kaldım. Huffman büyük adammış :D

Leave a Reply