Yazan : Şadi Evren ŞEKER

Bilgisayar bilimlerinde veri sıkıştırmak için kullanılan bir kodlama yöntemidir. Kayıpsız (lossless) olarak veriyir sıkıştırıp tekrar açmak için kullanılır. Huffman kodlamasının en büyük avantajlarından birisi kullanılan karakterlerin frekanslarına göre bir kodlama yapması ve bu sayede sık kullanılan karakterlerin daha az, nadir kullanılan karakterlerin ise daha fazla yer kaplamasını sağlamasıdır.

Şayet bütün karakterlerin dağılımı eşitse yani aynı oranda tekrarlanıyorsa, bu durumda Huffman kodlaması aslında blok sıkıştırma algoritması (örneğin ASCII kodlama) ile aynı başarıya sahiptir. Ancak bu teorik durumun gerçekleşmesi imkansız olduğu için her zaman daha başarılı sonuçlar verir.

Örneğin sadece 8 sembolden oluşan bir dilimiz olsun (Örneğin a,b,c,d,ef,g,h harflerinden oluşan bir dil düşünelim) Bu dili kodlamak için 3 bit yeterlidir (23=8 olduğuna göre 8 farklı dili ikilik tabanda kodlayabiliriz)

Bu durumda örneğin harflerin değerlerini aşağıdaki şekilde oluşturabiliriz:

a 000

b 001

c 010

d 011

e 100

f 101

g 110

h 111

Her harf için farklı bir kodlama yapılan dilde örneğin “baba caddede gec” mesajını kodlayacak olursak:

001000001000 010000011011100011100 110100010

şeklinde bir sonuç elde ederiz. Görüldüğü üzere kodlama sonucunda harf sayısının üç misli kadar bit kullanılmak zorundadır (14 harf için 14×3=52 bit gerekmektedir).

Huffman kodlaması ile bu mesajı sıkıştıracak olsaydık. Öncelikle harflerin mesajdaki sıklıklarını gösteren biraşağıdaki istatistiğin çıkarılması gerekirdi:
a3
b2
c2
d3
e3
f0
g1
h0

Yukarıda her harfin kullanılma sıklıkları sıralanmıştır. Bu istatistiksel veriye dayanarak bir ağaç oluşturulması gerekir.

Yukarıdaki ağaçta dikkat edilirse dilimizdeki harfler ve her harf düğümlerinin birleşim noktalarında ise o harflerin mesajdaki tekrar sayıları bulunmaktadır. Ayrıca istatistiksel olarak birbirine denk olan sıklıktaki düğümler aynı seviyede bulunmaktadır. Örneğin g+b = 3 sıklığa sahip ve d’de 3 sıklığa sahiptir. Bu durumda d ile g ve b’nin birleştiği düğüm aynı seviyede olmaktadır.

Yukarıdaki bu ağaca göre her harfi veren kodlama karşılığı çıkarılır. Bu çıkarma işlemi sırasında ağaçtaki her sağ kola hareket 1, her sol kola hareket 0 olarak okunur. Örneğin g harfinin değeri 010’dır çünkü kökteki 14 değerinin solunda (yani 0) 6 değerinin sağında (yani 1) ve 3 değerinin solundadır yani toplamda 010 değerine sahiptir.

Bu şekilde her harfin kodlama değeri aşağıda verilmiştir:

a 111

b 011

c 110

d 00

e 10

g 010

Yukarıdaki bu kodlamaya göre ilk mesajımızın yeni değeri :

011111011111 1101110000100010 01010110

Şeklinde bulunmuş olur. Dikkat edilirse bu mesajın boyutu 36 bittir ve ilk baştaki 52 bit uzunluğundan daha kısadır.
Huffman Ağacının Oluşturulması

Genel bir soru üzerine, ağacın oluşturulma algoritmasını yayınlıyorum. Ağacı oluşturmanın çeşitli algoritmaları olduğu gibi, en basit olanı, bir rüçhan sırası (öncelik sırası, priority queue) kullanmaktır. Bu sırada, en düşük olasılığa sahip olan düğüm (node), en yüksek rüçhana sahip olacaktır. Algoritmanın adımları aşağıdaki şekildedir:

1. Algoritma tarafından kodlanacak olan her sembol için birer yaprak düğüm, rüçhan sırasına eklenir.
2. Sırada, birden fazla düğüm kaldığı sürece aşağıdaki adımlar döngü halinde yapılır.
a. Sıradan, en yüksek rüçhana sahip iki düğüm alınır. (bu düğümlerin en az kullanım sıklığına sahip olduğunu hatırlayınız)
b. Yeni bir iç düğüm (internal node) oluşturulup, değer olarak bu alınan iki düğümün toplamı atanır.
c. Yeni düğüm ağaca ve sıraya eklenir.
3. Döngü bitip tek düğüm kaldıysa, bu düğüm, kök düğüm yapılır ve algoritma sona erer.

Şimdi, yukarıdaki bu algoritmaya göre ağacımızı oluşturalım. Harfler ve kullanım sıklıkları aşağıdaki şekildedir:

d3,e3,a3,b2,c2,g1

Buna göre bir rüçhan sırası yaparsak:

g1, b2, c2, a3, d3, e3 şeklinde en düşük sıklığan sahip olan en önde olacaktır.(ayrıca eşit öncelikli olanlar, kendi aralarında istenildiği gibi sıralanabilir.)

Algoritmanın 2. adımına geçiyor ve döngümüzü çalıştırmaya başlıyoruz.

Sıradaki en yüksek rüçhana sahip iki düğümü alalım: g1, b2

Toplamlarını hesaplayalım: 1+2 = 3

Yeni çıkan bu düğümü ağaca ve sıraya ekleyelim. Ağaç hali aşağıdaki şekildedir:

  3
 /  
g1  b2

Sıra için bu düğümlerden oluşan ağaca gb3 ismini verirsek, sıramız aşağıdaki hali alır:

c2, a3, d3, gb3, e3

Sıradan iki düğüm daha alıyoruz: c2, a3, toplamları : 2 + 3 = 5, ağaca ekliyoruz:

  5
 /  
c2  a3

d3, gb3, e3, ca5

Sıradan iki düğüm daha alıp ağaç oluşturuyoruz: d3, gb3

    6
  /  
 d3   3
     / 
   g1  b2

Yeni düğümü sıraya ekleyelim: e3, ca5, dgb5 Sıradaki düğümler: e3, ca5

   8
 /  
e3   5
    /  
   c2  a3

Sıraya ekleyelim:

dgb6, eca8

Bu iki düğümü alıp ağacı oluşturduğumuzda ise sonuç ağacımız çıkmaktadır:

Yorumlar

  1. Şadi Evren ŞEKER Article Author

    Yukarıdaki yazıda, ağacın nasıl oluşturulduğu konusu eksik kalmış. Dolayısıyla sorunuzun cevabı, yazı içerisinden anlaşılamıyor. Yukarıdaki yazıda eksik olan bu hususu tamamlıyorum.

    başarılar

  2. ali

    merhabalar bir şey sorucaktım..bir bit katarını

    111 000 000 110 1000 gibi birbirinden ayrık şekilde bir dosyada tutmak istiyorum..ancak araya ayrac koymak istemiyorum..bir sıkıştırma algoritması oldugu icin eger ayrac koyarsak dosya boyutu büyüyor bu yüzden bir yöntem ayırıyorum ama bulamadım..

    bunun icin huffman nodeını kullansam olurmu..bir arkadaşa huffman agacında her node 8 bit şeklinde oluşturulur bu yüzden her node icine 3 bit yazsanda 8 bit yer kaplar demişti..

    ama burdaki anlatımdan sadece 3 bitte saklanabilecegi yazıyor..yani her karekteri sadece 3 bit oalrakda temsil edebilirmişiz..bu dogrumudur..

    yani kodlamada kullanılan tüm classlar huffman agacının her node degerini bir karakter kadar oluşturuyor o zaman 8 bit yer kaplıyor ama bir karaktere 1 bit atasak ve bir node icinde bir bit olsa olmazmı..

    yardımcı olursanız sevinirim..

  3. Şadi Evren ŞEKER Article Author

    anladığım kadarıyla veri gösterimini iyileştirmek (optimisation) istiyorsunuz. Şimdi durum şöyle, değişken sayıda bit içeren grupları yollayacak ve araya ayıraç koymayacak ve alan kişinin de gruplamasını istiyorsanız bunu teorik olarak yapamazsınız. Örneğin ilk kelime 5 bit sonraki 8 bit ve bir sonraki 3 bit gibi rast gele uzunluklardaysa tek yolu ya iki tarafında bu uzunlukları bir şekilde biliyor olması (örneğin kelime uzunlukları arasında bir formül olması veya uzunlukların listesi olması gibi) ya da ayıraç koymaktır.

    Gelelim huffman kodlamasına. Bu yöntemde kelime boyutları sabit değil. Yani her node 8 bit tutulur ifadesi hatalı. Değişebilmektedir. Zaten nasıl değiştiğini yukarıda anlatmştım. Ancak huffman kodlamasının bir sakıncası, iki tarafta da huffman kodlamasına konu olan sözlüğün (kelime listesinin) bulunması gereğidir. Kısacası her iki tarafta da aynı huffman ağacı olacak ki alan kişi nasıl parçalayacağını ve parçalama sonucunda çıkan değerin hangi harfe karşılık geldiğini bilebilsin.

    Bu durumda huffman kodlaması kullanılan yerlerde ağaç ayrıca yer kaplar. Örneğin sıkıştırma amacıyla huffman kullandıysanız, sıkıştırılan dosyanın içinde bir yerlere ağacı koyarsınız. Veya veri transferi yapıyorsanız, veriyi yollamadan önce ağacı yollarsınız. Her durumda, ayıraçlardan yer tasarrufunuz olsa da ağaç için ilave bir yer kaybınız olur. Burada amaç veriyi küçültmekse hesabın iyi yapılması gerekir. Örneğin huffman ile 5 farklı kelime içeren 10 kelime boyundaki bir metni yollamak hiç mantıklı değildir. Buna karşılık 5 farklı kelime içeren onbin kelimelik bir metinde çok iyi sonuç elde edilebilir. Yani kelime çeşitliliği ve metin uzunluğu arasında bir bağlantı bulunur ve buna göre bazı durumlarda veriyi küçültürken bazı durumlarda da veriyi uzatabilmektedir.

    Amaç sadece sıkıştırma sonucunda veri küçültmek ise LZW algoritması kelime çeşitliliğinin yüksek olduğu küçük dosyalarda da iyi sonuç verebilir.

    http://www.bilgisayarkavramlari.com/2010/01/04/lzw-sikistirma-algoritmasi/

    Başarılar

  4. ali

    burda konu itibariyle..iki tarafın standart bir agac kullanamaz cünkü agaclar dinamik olarak oluşturuluyo…peki 2 tarafın kullanabilecegi standart agaclar nasıl oluşturulur..

  5. Şadi Evren ŞEKER Article Author

    Huffman için iki tarafta da aynı ağaç kullanmalıdır. Bunun tek yolu da veri iletişimi başlamadan önce ağacı göndermektir.

    Ancak ağacın yollanmadığı ve iki tarafında aynı ağacı kullandığı yöntemler bulunuyor. Bu yöntemlerde genelde ağaç çıkarmak için ortak bir algoritma geliştiriliyor. Örneğin bir önceki cevapta bahsettiğim LZW algoritması bu şekilde dinamik olarak kodlama yapmaktadır.

  6. ali

    şimdi her harfe 3 bit atıyoruz ya bir harfe boş degerini atasak yani icinde bir şey olmasa bunuda node diye gösterebiliriz..dimi

  7. Şadi Evren ŞEKER Article Author

    Hayır Huffman kodlamasında her harfin sayısal bir karşılığı olmak zorundadır. Bu kodlamanın çalışma şekli böyle ancak siz özel bir kodlama tasarlamak istiyorsanız huffman kodlamasının dışına çıkarak kendi algoritmanızı geliştirebilirsiniz.

  8. ali

    burda anlamadıgım birşey var..

    şöyle ki;cıktı olarak biz harf kodlaması olarak o harfe ulaşıncaya kadar aldıgımız yollardaki degerleri atıyoruz..

    ve sonucta sadece dllardaki sayıları oluşturan rakamlar kalıyor elimize peki soru şu esas en baştaki harf kdomasındaki degerler nereye gidiyor yani cıktının neresine yazıyoruz..degerler giderse iki degere nasıl ualşıyoruz..mesala c ile a yı toplayı ca’yı oluşturusak bu sefer yeni cA’de hangi bitin c’ye hangisinin a’ya ait olduugnu nerden bilecegiz..

  9. Şadi Evren ŞEKER Article Author

    Açıkçası, yazdıklarınızı anlayamadım, ama anladığım kadarıyla cevap vermeye çalışayım. Sanırım ilk başta her harf için atanan 3 bitlik sayıların nereye gittiğini sormuşsunuz. Cevap, bu sayılar hiç kullanılmıyor, artık bunların yerine huffman kodlamasından gelen sayıları kullanıyoruz. Dolayısıyla bu değerler çıktının hiçbir yerinde yoktur ve bu değerlere ulaşmak gibi bir derdimiz de yoktur. Ancak sorunuzu yanlış anlamış olabilirim, daha açık ve yazım hatası olmadan sorarsanız bildiğim kadarıyla cevaplamaya çalışırım.

  10. ali

    yok ali hocam sagolun dogru anlamısınız ve güzel cevaplandırmıssınız..ancak anlamadıgım nokta şu cıktıda kullanılmayan bu degerleri biz sıkıştırmaya çalışmıyormuyuz..yani bu degerlerin o zaman kaybolması gibi bir durum ortaya cıkmıyormu..

  11. ali

    yani o degerlere cıktıda ihtiyacımız yoksa

    a=01
    b=11
    c=10
    d=00

    desek normal bir bit katarını sonsuza kadar sıkıştırmış olmazmıyız..

  12. Şadi Evren ŞEKER Article Author

    evet aynen dediğiniz gibi sıkıştırmış olursunuz. Bakın bu mantıkta devam edersek ya d harfinden sonraki harfleri kabul etmeyeceğiz (ki bu durumda kayıplı sıkıştırma olur ve harflerin bir kısmını kaybederiz) ya da h harfine kadar olan harflere daha fazla bit ile sayı vermeniz gerekir. Kısacası her harfe farklı bir sayı vermeniz ve dolayısıyla h harfine kadar gittiğinizde, her harf için en az 3 bit kullanmanız gerekir. Bu da baştaki durum ile aynıdır.

    Diğer bir deyişle huffman kodlamasında sıkıştırılmak istenen veri baştaki sayılar değildir. Yani yazdıklarınızdan anladığım kadarıyla siz olayı, yazının başında geçen “001000001000 010000011011100011100 110100010” dizgisini (string) sıkıştırmak olarak görüyorsunuz. Problem tam bu noktada, huffman kodlaması aslında bu dizgiyi sıkıştırmak ile uğraşmıyor.

    Huffman kodlaması, başlangıçta elimizde olan “baba caddede gec” dizgisini (string) sıkıştırmaya çalışıyor ve geri açtığında da bu mesajı alması yeterli. İkilik tabanda verilen ve 42 bit uzunluğundaki bu sıkışmamış veri sadece problemin anlaşılması ve huffman kodlaması kullanılmadığı durumlarda verinin nasıl gösterileceğini temsil amaçlı verilmiştir. Aslında bu veri sıkıştırılan veri olmayıp sadece elimizde bir sıkıştırma algoritması olmasaydı verinin kaplayacağı uzunluğu göstermek amaçlıdır.

    Huffman kodlaması kullanıldıktan sonra artık harflerin ifade edildiği tamamen başka sayı karşılıkları bulunmaktadır.

    Başarılar

  13. ali

    ha anladım…cok sagolun..normalde huffman standart ascıı karakterlerinin hangi bit degerlerine sahip oldugunu biliyor..yalnız sıkıştırma yaparken bunlara kendine göre bit degerleri atıyor..sonra ona göre uzunlugu kodluyor..daha sonra ise uzunluktan harf çeşidlerini cıkartıyor harflerin bit karşılıgı ascıı olarak tekrar atıyarak yazıyor..

    huffmanı daha yeni ögrendim cok teşekkür ederim:)

  14. ali

    sadi hocam bir araştırmamın son halkası icin bana şöyle bir şey lazım..size bir sorayım dedim..algoritmaların üstadı sayılırsınız..şimdi elimde 16 adet harf katarı var..her biri 4 bit ve 4 çeşid bit katarı tutuyor.

    ve bu 4 çeşidi gösteren bir agac agacın her bir yükselkligi ve çeşidleri tanımıyor..

    1000->birinci yükseklik
    0100->ikinci yükseklik
    0010->ücüncü yükselik
    0001->dördnücü yükseklik

    ve 16 çeşid nodedan her biri yukardaki 4 çeşid bit katarından birine sahip ve sahip oldugu bit katarına göre o yükseklikde bulunuyor..

    diyelim 7,5 ve 9.ncu harfler 0100 degerine eşit ve agacın 2.yüksekliginde bulunuyorlar..

    bu agac yapısıyla bu harfleri nasıl 1 bytedan az olucak eşkilde sıkıştırırız..veya bizi buna götüren bir yöntem varmıdır..nelere bakmam lazım..

  15. Taha AHISKALI

    “Sıra için bu düğümlerden oluşan ağaca gb3 ismini verirsek, sıramız aşağıdaki hali alır:

    c2, a3, d3, gb3, e3”

    Burada gb3 neden ortada hocam c2, a3, d3, e3,gb3 veya c2,gb3,a3,d3, e3 olamaz mıydı ?

  16. abdulsamet

    Bir sıkıştırma programı yapmak üzere okuldan bir proje aldım. Sizden ricam yapmam gereken aşamalar nedir bilmiyorum.Buraya yazsanız çok faydalı olacaktır.Yardımcı olsanız da olmasanız da Şimdiden Teşekkürler…

ali için bir cevap yazın Cevabı iptal et

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir