Constantine_a_w

BİLGİSAYARDA SIKIŞTIRMA ALGORİTMALARI
– Huffman Sıkıştırma Tekniği – 1 –
Fatih GELGİ, 2001
________________________________________

Bilgisayarda veri sıkıştırma işleminin uygulanmasının temel nedeni, sıkıştırılmış verinin daha az yer kaplamasıdır. Çoğu kişinin merak ettiği konulardan bir tanesi de budur; veriler nasıl sıkıştırılır, acaba verileri mengeneye koyarsak sıkışırmı? gibi.
Neyse fazla uzatmadan sıkıştırma yöntemimize geçelim. Bazı sıkıştırma yöntemleri sıkıştırma işlemi sırasında veri kaybına yol açar, bazılarında ise bu durum gerçekleşmez. Biz bu yazımızda hiç veri kaybına sebebiyet vermeyen çok sağlam bir sıkıştrıma tekniğinden bahsedeceğiz; Huffman veri sıkıştırma tekniği.
Huffman sıkıştırma tekniği ASCII kod tablosundaki karakterlerin bir veri parçasındaki sayısına göre yeniden kodlanması esasına dayanır. Sıkıştırma yöntemi temel olarak şu basamaklardan oluşur;
• Veri parçası içindeki karakterlerin sayılması
• Huffman ağacının oluşturulması
• Oluşturulan ağaca göre yeni kod tablosunun oluşturulması
• Verinin yeni kod tablosuna göre yeniden yazılması
Şimdi bu basamakları daha ayrıntılı olrak inceleyelim.
1. Veri Parçası İçindeki Karakterin Sayılması
Elimizdeki verinin içerdiği aynı karakterden kaç tane olduğu sayılır. Mesela, elimizde ’abcabbbcdaabccdaabb’ verisi var. Bu veride 6 tane a, 7 tane b, 4 tane c ve 2 tane de d harfi vardır.
2. Huffman Ağacının Oluşturulması
Huffman ağacı Huffman sıkıştırma tekniğinin temel yapısını oluşturur. Huffman ağacını oluşturmak için 1. basamakta elde ettiğimiz karakter sayılarını kullanacağız.
Genel bir bilgi olması için, Huffman ağacı ikili bir ağaçtır (binary tree). Düğüm (node) diye adlandırdığımız yapılardan oluşur. Düğümler bir veri ve an az 0, en fazla 2 daldan oluşur. Her dal başka bir düğüme bağlanır. Ağacın kök (root) diye adlandırdığımız bir baş düğümü vardır ve en alt düzeye ise yaprak denir. Yaprakların hiç dalı yoktur.
Örnek:
[Linkleri sadece kayıtlı üyelerimiz görebilir.ForumTR üyesi olmak için tıklayınız]

Şimdi geçelim Huffman ağacını oluşturmaya;
HUFFMAN AĞACI OLUŞTURMA ALGORİTMASI
1. Karakter sayıları belirlenir,
2. En küçük 2 sayı veya düğüm seçilir ve bu seçilen sayı veya düğümlerden yeni bir düğüm oluşturulur. Oluşturulan düğüm dizinin en sonuna konur ve seçilen elemanlar da diziden dışarı atılır. Düğümün değeri seçilen en küçük ikilinin toplamıdır.
3. 2. aşamaya geri dönülür ve işlem dizide bir eleman kalıncaya kadar devam eder.
En son kalan eleman Huffman ağacının köküdür. Dikkat edilirse algoritmanın her aşamasında 2 eleman elimine edilir ve 1 yeni eleman eklenir. Böylece dizide n eleman varsa n aşamada işlem bitmiş olur.
Yukarıdaki örnek için;
[Linkleri sadece kayıtlı üyelerimiz görebilir.ForumTR üyesi olmak için tıklayınız]
Dikkat edilirse verinin karakterleri huffman ağacında birer yaprak haline geldi.
Ayrıca şunu da belirtmek gerekir ki huffman ağacı oluşturabilir fakat bunların hepsi denktir.
3. Yeni Kod Tablosunun Oluşturulması
Kodlama kısmı gayet basittir. Sol dala ‘0’ sağ dala da ‘1’ dediğimizi varsayalım. Her harf için Huffman ağacının kökünden başlayıp sağa yada sola giderek o harfe ulaştığımızda elde ettiğimiz kodlar yeni kod tablosunu oluşturacaktır.
Örnek için;
[Linkleri sadece kayıtlı üyelerimiz görebilir.ForumTR üyesi olmak için tıklayınız]
a için önce sağa sonra sola gitmemiz gerekir ve a’nın değeri 10 olmuş olur. Bu işlemi her harf için tekrarladığımızda;
a = 10
b = 0
c = 110
d = 111
elde ederiz.
4. Verinin Kod Tablosuna Göre Yeniden Yazılması
Veri parçasındaki harflerin kodu sırayla tekrar yazılır. Bildiğiniz gibi 1 bayt 8 bittir. Sonuçta elde edilen ‘1’ ve ‘0’ lardan oluşan veri 8 haneli parçalara bölünür ve 8 haneli kısım ASCII koduna çevrilir.
a b c a b b b c d a a b c c d a a b b
-- - --- -- - - - --- --- -- -- - --- --- --- -- -- - -
10 0 110 10 0 0 0 110 111 10 10 0 110 110 111 10 10 0 0
10011010 00011011 11010011 01101111 01000000
-------- -------- -------- -------- --------
1.bayt 2.bayt 3.bayt 4.bayt 5.bayt
154 27 179 55 64
Ü ® | 7 @
Ve böylece ’abcabbbcdaabccdaabb’ olan 19 baytlık veri sadece ’Ü®|7@’ 5 baytta elde edilmiş olur

(A L I N T I D I R)
R_E_D-O________________X

resultecim

Tesekkurler

sefozturk2002

Teşekkürler kardeş

metaladam

sagol dostum yararlı bilgiler.

cemdurgut

harika. tam aradığım şey. birde örneklerin resimleri açılsaydı çok daha memnun olacaktım. yinede çok teşekkürler. ödevim bitti