Skip to content

Huffman Encoding

         Zaman ilerleyip veri iletişiminin kapsamı genişledikçe, aktarılan verilerin boyutları da gittikçe büyümeye başladı. Bu da verilerin sıkıştırılıp gönderildikten sonra ulaştığı yerde sıkıştırma algoritmasının tersi bir algoritmayla açılmasına ihtiyaç doğurdu. Bu yazıda, daha çok metin dosyaları için uygun bir kayıpsız sıkıştırma yöntemi olan Huffman Kodlama Ağacı’ndan bahsedeceğim.

        Huffman kodlaması, David Huffman tarafından 1952 yılında bulunmuştur. Temelde bir metin içindeki karakterlerin frekanslarına göre sınıflandırılarak belirli bir kuralla oluşturulan bir ağaca göre atanmış bitlerle temsil edilmesine dayanır. Algoritma, en yüksek frekanslı karakterin en az bitle, en düşük frekanslının da en çok bitle temsiline dayanan bir yol izlemektedir. Bir örnek ile bunun nasıl bellek alanından kazanç sağladığını görelim. Örneğin, sıkıştırılacak metnimiz “BİLGİSAYAR” olsun. (Karakterleri temsil edecek bitleri şimdilik rastgele atayacağız.) Bu metni sıkıştırmadan bellekte saklamak istersek toplamda karakter sayısı kadar bayt’a ihtiyacımız var. 10 karakter = 10 bayt. 1 bayt, 8 bit’e karşılık geldiğinden toplamda 80 bitlik bir alana ihtiyacımız olmakta. Huffman ile sıkıştırma için frekans tablosunun şu şekilde olduğunu varsayalım.

Karakter

Frekans

Bit ile Temsili

B

1

0000

İ

2

11

L

1

100

G

1

111

S

1

010

A

2

001

Y

1

011

R

1

0001

Bu durumda BİLGİSAYAR sözcüğünün sıkıştırılmış hali 000011100111110100010110010001 dir. Toplamda 30 bit kullanılmıştır. Bu da bize %62,5’luk bir yer kazancı sağlar.

Peki bu bitler gerçekten rastgele mi elde ediliyor? Tabii ki hayır. Şimdi de her harfin bit temsilini nasıl elde ettiğimizi daha geniş kapsamlı bir örnekle inceleyelim.

                PAPAĞAN sözcüğündeki harflerin frekans tablosu yukarıdaki gibidir.

 

                Daha sonra, her karakteri ve frekansını içeren ağaç düğümleri frekanslarına göre artan sırayla yazılır.(i) En düşük frekanslı ilk iki düğüm toplanır ve toplanan düğümlerin içerdiği semboller ve toplam frekans bir düğüme yazıldıktan sonra toplanan elemanlar sol ve sağ çocuk olarak bu düğüme eklenir.(ii) En üst seviyedeki düğümler arasında bu işlem devam eder.(iii)

En üst seviyede bir düğüm kaldığında ağaç tamamlanmış olur.(iv) Huffman ağacının oluşması için bit atamalarının da yapılması gerekiyor. Bunun için de, ağaçta sol çocukların bağlandığı bağlara ‘0’, sağ çocukların bağlandığı bağlara da ‘1’ atanır. (v)

                Yukarıdaki görselde sıkıştırılmış hali görüyorsunuz. Sarı renk ile boyanmış düğümler asıl işimize yarayanlar. Bir harfe (sarı düğüme) kökten başlayıp hiç geri dönmeden ulaşırken izlenilen yolda karşılaşılan bitler de o harfin bit temsili oluyor. Örneğin N harfi için bir kez sağa gittikten sonra iki kez sol taraftan ilerleniyor ve böylece 100 kodu elde edilmiş oluyor.

Sıkıştırılan metnin geri açılması da benzer şekilde gerçekleştirilir. Algoritma bitleri tarar ve herhangi bir karaktere karşılık gelen bir bit serisi bulduğunda o karakteri dosyaya yazdırır. Huffman kodlamasında her sıkıştırma işlemi eşsizdir. Yani bir bit serisinin birden fazla açılımı olamaz.

Günümüzde Huffman algoritması genellikle Lempel-Ziv-Welch algoritması ile birlikte kullanılır. Bu algoritmanın birçok türü vardır, bunlardan L278 türünü örnek vermek gerekirse, bu türde karakter dizilerinin en küçük eşsiz parçalara ayrıldıktan sonra bir ağaç oluşturulması şeklinde kodlama gerçekleştirilir.

Kaynakça:

http://en.wikipedia.org/wiki/Huffman_coding

http://members.comu.edu.tr/boraugurlu/courses/bm223/content/week6/hafta6.pdf

Published inVeri Yapıları

Be First to Comment

Leave a Reply