Huffman Algoritması

Veri Sıkıştırma

Sıkıştırma bir dosyanın büyüklüğünü azaltır.Veri saklarken disk alanından tasarruf etmemizi,veriyi iletirken zamandan tasarruf etmemizi ve birçok dosyada gereksiz veriler olduğu için bunları temizler.

Binary Data ⇒ Compress ⇒ C(B) ⇒ Expand ⇒ B

Sıkıştırma oranı Bits in C(B) / Bits in B.

%50-75 iyi bir oran mesela verinin yarısını sıkıştırmış oluruz.

Örnek olarak gen alfabesini düşünelim;

Gen Alfabesi:{A,C,T,G}

N Karakter gen: ATAGATGC

Şimdi bu verilere göre bir tablo oluşturalım.

Burada harflerin farklı gösterimleri mevcuttur.Asıl amaç bu harfleri minimum bitler ile ifade etmektir.

Derinlemesine Huffman

Bir mesajı, rakamları kullanarak kodlayacak olsanız, en az rakam kullanarak nasıl açıklarsınız? David Huffman 1952 yılında A Method for the Construction of Minimum-Redundancy Codes başlıklı makalede bu soruya cevap aramış, ve bir metot ortaya atmış. Bu me tot insanların çok etkilemiş olacak ki, png, jpeg, mp3 gibi dosya formatlarında, ayrıca HTTP’nin standard sıkıştırma metotlarından deflate veri formatında, deflate formatı da gzip ve zlib kütüphanelerinde kullanılmış.

Huffman kodlaması temelinde bir prefix kodlamadır. Prefix kodlamaya örnek olarak, şekildeki örneği inceleyelim.

Prefix kodlamada, kodlanmak istenen her karaktere, bir veya daha çok rakamdan oluşan kodlar atanır. Bu kodlar atanırken, herhangi bir kodun, kendinden uzun başka bir kodun başlangıcı olmaması gerekiyor. Böylece, bu kodlar arka arkaya dizildiğinde, mükemmel şekilde geri ayrıştırılabilir. Yukarıdaki tabloda, en kısa kod, a karakterine atanmış. a karakterine atanan kod 1 olduğu için, diğer kodların hiçbiri 1 ile başlayamıyor. Aynı şekilde, c karakterine kod olarak 01 atandığı için, diğer kodların hiçbiri 01 ile başlayamıyor. Bu özelliklere sahip kodlar oluşturmak için, yukarıdaki gibi bir ağaç oluşturarak, ağacın yapraklarına kodlanacak karakterler yerleştirip, her yol ayrımında bir yöne 0, diğerine 1 atayabilirsiniz. Tepeden başlayıp, istediğiniz karaktere gelene kadar geçtiğiniz rakamlar, o karakterin kodunu verir.

Huffman kodlamasının amacı, prefix ağacını, sıkıştıracağımız metinde en çok kullanılan karakterlere, (veya sıkıştıracağımız veride en çok kullanılan byte’lara) en kısa kodu verecek şekilde oluşturmaktır. Bunun için kullanılacak algoritma şu şekilde.

1. Karakterleri, metin içinde görülme sıklığına göre sıralanır.
2. En küçük iki karakteri grupla, bunları görülme sıklıklarını toplayarak, sıraya tekrar dahil edilir.
3. Tek bir grup kalana dek, gruplamaya devam edilir.

Huffman algoritması, bir veri kümesinde daha çok rastlanan sembolü daha düşük uzunluktaki kodla, daha az rastlanan sembolleri daha yüksek uzunluktaki kodlarla temsil etme mantığı üzerine kurulmuştur. Bir örnekten yola çıkacak olursak : Bilgisayar sistemlerinde her bir karakter 1 byte yani 8 bit uzunluğunda yer kaplar. Yani 10 karakterden oluşan bir dosya 10 byte büyüklüğündedir. Çünkü her bir karakter 1 byte büyüklüğündedir. Örneğimizdeki 10 karakterlik veri kümesi “aaaaaaaccs” olsun. “a” karakteri çok fazla sayıda olmasına rağmen “s” karakteri tektir. Eğer bütün karakterleri 8 bit değilde veri kümesindeki sıklıklarına göre kodlarsak veriyi sembolize etmek için gereken bitlerin sayısı daha az olacaktır. Söz gelimi “a” karakteri için “0” kodunu “s” karakteri için “10” kodunu, “c” karakteri için “11” kodunu kullanabiliriz. Bu durumda 10 karakterlik verimizi temsil etmek için

(a kodundaki bit sayısı)*(verideki a sayısı) + (c kodundaki bit sayısı)*(verideki c sayısı) + (s kodundaki bit sayısı)*(verideki s sayısı) = 1*7 + 2*2 + 2*1 = 12 bit

gerekecektir. Halbuki bütün karakterleri 8 bit ile temsil etseydik 8*10 = 80 bite ihtiyacımız olacaktı. Dolayısıyla %80 ‘in üzerinde bir sıkıştırma oranı elde etmiş olduk.

Huffman tekniğinde semboller(karakterler) ASCII’de olduğu gibi sabit uzunluktaki kodlarla kodlanmazlar. Her bir sembol değişken sayıda uzunluktaki kod ile kodlanır.

Run-Length Encoding

def decode(string):
    if len(string) <= 1:    return string
    output = ""
    digits = ""

    if string[0].isdigit():
        digits += string[0]
    else:
        output += string[0]


    for i in range(1, len(string)):
        if string[i].isdigit():
            digits += string[i]
        else:
            if digits == "":
                output += string[i]
            else:
                n = int(digits)
                for cnt in range(0, n):
                    output += string[i]
            digits = ""


    return output


def encode(string):
    if len(string) <= 1:    return string
    output = ""
    char_running = string[0]
    cnt_char_running = 1
    for i in range(1, len(string)):
        if string[i] != char_running:
            if cnt_char_running == 1:
                output += char_running
            else:
                output += str(cnt_char_running) + char_running

            char_running = string[i]
            cnt_char_running = 1

        else:
            cnt_char_running += 1

    if cnt_char_running == 1:
        output += char_running
    else:
        output += str(cnt_char_running) + char_running


    return output

Şimdi yukarıdaki kodu açıklayalım bu kod run-length coding algoritmasının python da yazılmış halidir.

Veri denince 0 ve 1 lerden oluşan bir sayı dizisini düşünmeliyiz.Şimdi 00 11 00 1111111 0 1 sayısını düşünelim.20 21 20 71 10 11 şeklinde ifade edebiliriz.Bu kodu açarsak Sağ taraf sayıyı sol taraf kaç adet olduğunu belirtir. Temel run-length encoding işlemi bundan ibarettir fakat günümüzde tarih eseri olduğu için kimse kullanmıyor bu sebeple bizim asıl konumuz olan Huffman-Coding algoritmasına geçelim.

Huffman Coding Prefix

Temelinde yazının konusu olan veri sıkıştırma yer alır.Bu tarz sıkıştırmalarda bir encoding işlemi vardır.Huffman Coding de encoding için bir ağaç yapısı kullanılır.

Huffman Coding Pseudo Code

1. Her sembol için bir yaprak düğüm ekle
2. Sırada,birden fazla düğüm kaldığı sürece döngüler halinde;
   1. En az sıklıkla kullanılan iki düğüm alınır.
   2. Yeni bir iç düğüm oluşturulur ve değer olarak iki düğümün toplamı alınır.
3. Döngü bitip tek düğüm kaldıysa bu düğüm kök düğüm yapılır

Algoritmayı Çalıştırmak

Şimdi verimiz AVNİ KAŞIKÇI olsun,her bir karakter oluşturacağımız ağaçta bir karakteri temsil edecek.Burada ağaç tersten yani yapraklardan oluşuyor temel ağaç yapısı root’tan leaf’lere şeklindedir fakat huffman leaf’den root’a doğru ilerler.Şimdi metin türkçe olduğu için türkçe metindir.Türkçe alfabesini yazarız baştan sonra daha sonra hangi harften kaç kere kullanılmış bunları not alırız.

Bu metin içindeki geçebilecek karakterleri önceden sözlük gibi bir yapıya atmamız gerekir.

Bu kodlamadaki temel mantık frekansı yüksek harfleri az bitlerle frekansı düşük harfleri daha çok bitlerle ifade etmek gerekir.

Şimdi ağacı oluşturmak için aşağıdaki görseli inceleyiniz.

İlk önce frekansı az olan düğümleri belirledik, n c s v 1 ‘er frekansı olan 1 ‘er bitlik char ifadeler bu sebeple bunların birleşiminden 2 bitlik root düğümler oluşturduk daha sonra bu düğümlerin 2 + A(2 frekanlı) 4 bitlik rootlar oluştu böyle ağaç tamamlandı daha sonra ağaçta sol 0 sağ 1 olacak şekilde kodlama yapıldı ve harflere gidene kadar izlenen yol o harfin kodu oldu.

Son

Buraya kadar okuduğunuz için teşekkürler.Herkese sağlıklı günler.