Bu site emekli olmuştur. Arşiv amaçlı olarak BT AKADEMİ sponsorluğunda yayın hayatına devam etmektedir.




C#nedir?com
 
YAZAR HAKKINDA
Sefer Algan
Sefer Algan
http://www.seferalgan.com
İletişme geçmek için tıklayın.
71 Makalesi yayınlanmakta.
Yazar hakkında detaylı bilgi için tıklayın.
Yayınlanan diğer makaleleri için tıklayın.
İlgili etiketler:  C# / VC#/.NET Sefer Algan
 
YAZI HAKKINDA
Türü : Makale
Serbest Köşede C#nedir?com üyelerinin hazırladıkları yazılar yayınlanır. Bu yazılar editör incelemesine girmeden yayınlanır.
Seviyesi : İleri
Kategori : C# / VC#/.NET
Yayınlanma Tarihi : 8.8.2004
Okunma Sayısı : 76238
Yorum Sayısı : 18     yorum yaz
Site İçi AramaSİTE İÇİ ARAMA
Üye Girişini AçÜye GİRİŞİ
Üye girişi için tıklayın.
Kullanıcı Adı
Şifre
 
Beni her zaman hatırla
Bir hafta boyunca kullanıcı bilgilerinizi kullanıcı çıkışı yapana kadar hatırlar. (Paylaşılan bilgisayarlarda önerilmez.)
 
Şifremi / Kullanıcı Adımı unuttum.
 
.net TV RSS Serbest KÖŞE (?)
Serbest Köşede C#nedir?com üyelerinin hazırladıkları yazılar yayınlanır. Bu yazılar editör incelemesine girmeden yayınlanır.
emre TAŞ
Silindi
emre TAŞ
yazının devamı >
emre TAŞ
silindi
emre TAŞ
yazının devamı >
emre TAŞ
silindi
emre TAŞ
yazının devamı >
emre TAŞ
silindi
emre TAŞ
yazının devamı >
emre TAŞ
silindi
emre TAŞ
yazının devamı >
Makale Gönder Bende Yazmak İstiyorum
.net TV RSSBlogroll
Burak Selim Şenyurt
Kurumsal Yazılımcının Oyun Geliştirme ile İmtihanı 28.3.2024
Burak Selim Şenyurt
Matematik ve Oyun Programlama - Missile Command - Final 28.3.2024
Turhal Temizer
Conda install environment.yml Package 28.3.2024
Turhal Temizer
Mac OS/X Removing CUDA 28.3.2024
  Diğer Herşey
Sponsorlar
BT Akademi
Medya Portakal
Video Hosting Sponsoru
Csharpnedir.com bir Ineta üyesidir
Uzman Abi
Her Yönüyle C# - Sefer Algan
Huffman Veri Sıkıştırma Algoritması ve Uygulaması
 
Kapat
Sayfayı Yazdır Sık Kullanılanlara Ekle Arkadaşıma Gönder MySpace Del.Ico.Us Digg Facebook Google Mixx Reddit StumbleUpon
Bu makalede bilgisayar bilimlerinin önemli konularından biri olan veri sıkıştırma algoritmalarından Huffman algoritmasını inceledikten sonra uygulamasını gerçekleştirip sonuçlarını göreceğiz.

Sayısal haberleşme tekniklerinin önemli ölçüde arttığı günümüzde, sayısal verilen iletilmesi ve saklanması bir hayli önem kazanmıştır. Sayısal veriler çeşitli saklayıcılarda saklanırken hedef daima minimum alanda maksimum veriyi saklamadır. Veriler çeşitli yöntemlerle sıkıştırılarak kapladığı alandan ve iletim zamanından tasarruf edilir. Sayısal iletişim(digital communication) kuramında veriler çok çeşitli yöntemlerle sıkıştırılabilir. Bu yöntemlerden en çok bilineni David Huffman tarafından öne sürülmüştür. Bu yazıda bu teknik "Huffman algoritması" olarak adlandırılacaktır. Bu yazıda Huffman Algoritması detaylı olarak açıklandıktan sonra bu algoritmanın C# dili ile ne şekilde uygulanacağı gösterilecektir.

Sıkıştırma algoritmaları temel olarak iki kategoride incelenir. Bunlar, kayıplı ve kayıpsız sıkıştırma algoritmalarıdır. Kayıplı algoritmalarda sıkıştırılan veriden orjinal veri elde edilemezken kayıpsız sıkıştırma algoritmalarında sıkıştırılmış veriden orjinal veri elde edilebilir. Kayıplı sıkıştırma tekniklerine verilebilecek en güzel örnekler MPEG ve JPEG gibi standartlarda kullanılan sıkıştırmalardır. Bu tekniklerde sıkıştırma oranı artırıldığında orjinal veride bozulmalar ve kayıplar görülür. Örneğin sıkıştırılmış resim formatı olan JPEG dosyalarının kaliteli yada az kaliteli olmasının nedeni sıkıştırma katsayısıdır. Yani benzer iki resim dosyasından daha az disk alanı kaplayan daha kötü kalitededir deriz. Kayıpsız veri sıkıştırmada durum çok farklıdır. Bu tekniklerde önemli olan orjinal verilerin aynen sıkıştırılmış veriden elde edilmesidir. Bu teknikler daha çok metin tabanlı verilen sıkıştırılmasında kullanılır. Bir metin dosyasını sıkıştırdıktan sonra metindeki bazı cümlelerin kaybolması istenmediği için metin sıkıştırmada bu yöntemler kullanılır.

Bu yazının konusu olan Huffman sıkıştırma algoritması kayıpsız bir veri sıkıştırma tekniğini içerir. Bu yüzden bu yöntemin en elverişli olduğu veriler metin tabanlı verilerdir. Bu yazıda verilecek örnek programdaki hedef metin tabanlı verilerin sıkıştırılması olacaktır.

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. Burada dikkat edilmesi gereken nokta şudur : Veri kümesindeki sembol sayısına ve sembollerin tekrarlanma sıklıklarına bağlı olarak Huffman sıkıştırma algoritması %10 ile %90 arasında bir sıkıştırma oranı sağlayabilir. Örneğin içinde 2000 tane "a" karakteri ve 10 tane "e" karakteri olan bir veri kümesi Huffman tekniği ile sıkıştırılırsa %90’lara varan bir sıkıştırma oranı elde edilir.

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.

Bir veri kümesini Huffman tekniği ile sıkıştırabilmek için veri kümesinde bulunan her bir sembolün ne sıklıkta tekrarlandığını bilmemiz gerekir. Örneğin bir metin dosyasını sıkıştırıyorsak her bir karakterin metin içerisinde kaç adet geçtiğini bilmemiz gerekiyor. Her bir sembolün ne sıklıkta tekrarlandığını gösteren tablo frekans tablosu olarak adlandırılmaktadır. Dolayısıyla sıkıştırma işlemine geçmeden önce frekans tablosunu çıkarmamız gerekmektedir. Bu yönteme Statik Huffman tekniği de denilmektedir. Diğer bir teknik olan Dinamik Huffman tekniğinde sıkıştırma yapmak için frekans tablosuna önceden ihtiyaç duyulmaz. Frekans tablosu her bir sembolle karşılaştıkça dinamik olarak oluşturulur. Dinamik Huffman tekniği daha çok haberleşme kanalları gibi hangi verinin geleceği önceden belli olmayan sistemlerde kullanılmaktadır. Bilgisayar sistemlerindeki dosyaları sıkıştırmak için statik huffman metodu yeterlidir. Nitekim bir dosyayı baştan sona tarayarak herbir sembolün hangi sıklıkla yer aldığını tespit edip frekans tablosunu elde etmemiz çok basit bir işlemdir.

Huffman sıkıştırma tekniğinde frekans tablosunu elde etmek için statik ve dinamik yaklaşımlarının olduğunu söyledik. Eğer statik yöntem seçilmişse iki yaklaşım daha vardır. Birinci yaklaşım, metin dosyasının diline göre sabit bir frekans tablosunu kullanmaktır. Örneğin Türkçe bir metin dosyasında "a" ve "e" harflerine çok sık rastlanırken "ğ" harfine çok az rastlanır. Dolayısıyla "ğ" harfi daha fazla bitle "a" ve "e" harfi daha az bitle kodlanır. Frekans tablosunu elde etmek için kullanılan diğer bir yötem ise metni baştan sona tarayarak her bir karakterin frekansını bulmaktır. Sizde takdir edersinizki ikinci yöntem daha gerçekçi bir çözüm üretmekle beraber metin dosyasının dilinden bağımsız bir çözüm üretmesi ile de ön plandadır. Bu yöntemin dezavantajı ise sıkıştırılan verilerde geçen sembollerin frekansının da bir şekilde saklanma zorunluluğunun olmasıdır. Sıkıştırılan dosyada her bir sembolün frekansıda saklanmalıdır. Bu da küçük boyutlu dosyalarda sıkıştırma yerine genişletme etkisi yaratabilir. Ancak bu durum Huffman yönteminin kullanılabililiğini zedelemez. Nitekim küçük boyutlu dosyaların sıkıştırılmaya pek fazla ihtiyacı yoktur zaten.

Frekans tablosunu metin dosyasını kullanarak elde ettikten sonra yapmamız gereken "Huffman Ağacını" oluşturmaktır. Huffman ağacı hangi karakterin hangi bitlerle temsil edileceğini(kodlanacağını) belirlememize yarar. Birazdan örnek bir metin üzerinden "Huffman Ağacını" teorik olarak oluşturup algoritmanın derinliklerine ineceğiz. Bu örneği iyi bir şekilde incelediğinizde Huffman algoritmasının aslında çok basit bir temel üzerine kurulduğunu göreceksiniz.


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

Bir huffman ağacı aşağıdaki adımlar izlenerek oluşturulabilir.

Bu örnekte aşağıdaki frekans tablosu kullanılacaktır.


Sembol(Karakter)
Sembol Frekansı
a
50
b
35
k
20
m
10
d
8
ğ
4
Bu tablodan çıkarmamız gereken şudur : Elimizde öyle bir metin dosyası varki "a" karakteri 50 defa, "b" karakteri 35 defa .... "ğ" karakteri 2 defa geçiyor. Amacımız ise her bir karakteri hangi bit dizileriyle kodlayacağımızı bulmak.

1 - Öncelikle "Huffman Ağacını" ndaki en son düğümleri(dal) oluşturacak bütün semboller frekanslarına göre aşağıdaki gibi küçükten büyüğe doğru sıralanırlar.



2 - En küçük frekansa sahip olan iki sembolün frekansları toplanarak yeni bir düğüm oluşturulur. Ve oluşturulan bu yeni düğüm diğer varolan düğümler arasında uygun yere yerleştirilir. Bu yerleştirme frekans bakımından küçüklük ve büyüklüğe göredir. Örneğin yukarıdaki şekilde "ğ" ve "d" sembolleri toplanarak "12" frakansında yeni bir "ğd" düğümü elde edilir. "12" frekanslı bir sembol şekilde "m" ve "k" sembolleri arasında yerleştirilir. "ğ" ve "d" düğümleri ise yeni oluşturulan düğümün dalları şeklinde kalır. Yeni dizimiz aşağıdaki şekilde olacaktır.



3 - 2.adımdaki işlem tekrarlanarak en küçük frekanslı iki düğüm tekrar toplanır ve yeni bir düğüm oluşturulur. Bu yeni düğümün frekansı 22 olacağı için "k" ve "b" düğümleri arasına yerleşecektir. Yeni dizimiz aşağıdaki şekilde olacaktır.




4 - 2.adımdaki işlem tekrarlanarak en küçük frekanslı iki düğüm tekrar toplanır ve yeni bir düğüm oluşturulur. Bu yeni düğümün frekansı 42 olacağı için "b" ve "a" düğümleri arasına yerleşecektir. Yeni dizimiz aşağıdaki şekilde olacaktır. Dikkat ederseniz her dalın en ucunda sembollerimiz bulunmaktadır. Dalların ucundaki düğümlere özel olarak yaprak(leaf) denilmektedir. Sona yaklaştıkça Bilgisayar bilimlerinde önemli bir veri yapısı olan Tree(ağaç) veri yapısına yaklaştığımızı görüyoruz.




5 - 2.adımdaki işlem tekrarlanarak en küçük frekanslı iki düğüm tekrar toplanır ve yeni bir düğüm oluşturulur. Bu yeni düğümün frekansı 77 olacağı için "a" düğümünden sonra yerleşecektir. Yeni dizimiz aşağıdaki şekilde olacaktır. Dikkat ederseniz her bir düğümün frekansı o düğümün sağ ve sol düğümlerinin frekanslarının toplamına eşit olmaktadır. Aynı durum düğüm sembolleri içinde geçerlidir.



6 - 2.adımdaki işlem en tepede tek bir düğüm kalana kadar tekrar edilir. En son kalan düğüm Huffman ağacının kök düğümü(root node) olarak adlandırılır. Son düğümün frekansı 127 olacaktır. Böylece huffman ağacının son hali aşağıdaki gibi olacaktır.



Not : Dikkat ederseniz Huffman ağacının son hali simetrik bir yapıda çıktı. Yani yaprak düğümler hep sol tarafta çıktı. Bu tamamen seçtiğimiz sembol frekanslarına bağlı olarak rastlantısal bir sonuçtur. Bu rastlantının oluşması oluşturduğumuz her bir yeni düğümün yeni dizide ikinci sıraya yerleşmesinden kaynaklanmaktadır. Sembol frekanslarında değişiklik yaparak ağacın şeklindeki değişiklikleri kendinizde görebilirsiniz.

7 - Huffman ağacının son halini oluşturduğumuza göre her bir sembolün yeni kodunu oluşturmaya geçebiliriz. Sembol kodlarını oluşturuken Huffman ağacının en tepesindeki kök düğümden başlanır. Kök düğümün sağ ve sol düğümlerine giden dala sırasıyla "0" ve "1" kodları verilir. Sırası ters yönde de olabilir. Bu tamamen seçime bağlıdır. Ancak ilk seçtiğiniz sırayı bir sonraki seçimlerde korumanız gerekmektedir. Bu durumda "a" düğümüne gelen dal "0", "bkmğd" düğümüne gelen dal "1" olarak seçilir. Bu işlem ağaçtaki tüm dallar için yapılır. Dalların kodlarla işaretlenmiş hali aşağıdaki gibi olacaktır.



 

8 - Sıra geldi her bir sembolün hangi bit dizisiyle kodlanacağını bulmaya. Her bir sembol dalların ucunda bulunduğu için ilgili yaprağa gelene kadar dallardaki kodlar birleştirilip sembollerin kodları oluşturulur. Örneğin "a" karakterine gelene kadar yalnızca "0" dizisi ile karşılaşırız. "b" karakterine gelene kadar önce "1" dizisine sonra "0" dizisi ile karşılaşırız. Dolayısıyla "b" karakterinin yeni kodu "10" olacaktır. Bu şekilde bütün karakterlerin sembol kodları çıkarılır. Karakterlerin sembol kodları aşağıda bir tablo halinde gösterilmiştir.


Frekans
Sembol(Karakter)
Bit Sayısı
Huffman Kodu
50
a
1
0
35
b
2
10
20
k
3
110
10
m
4
1110
8
d
5
11111
4
ğ
5
11110
Sıkıştırılmış veride artık ASCII kodları yerine Huffman kodları kullanılacaktır. Dikkat ederseniz hiçbir Huffman kodu bir diğer Huffman kodunun ön eki durumunda değildir. Örneğin ön eki "110" olan hiç bir Huffman kodu mevcut değildir. Aynı şekilde ön eki "0" olan hiç bir Huffman kodu yoktur. Bu Huffman kodları ile kodlanmış herhangi bir veri dizisinin "tek çözülebilir bir kod" olduğunu göstermektedir. Yani sıkıştırılmış veriden orjinal verinin dışında başka bir veri elde etme ihtimali sıfırdır. (Tabi kodlamanın doğru yapıldığını varsayıyoruz.)

Şimdi örneğimizdeki gibi bir frekans tablosuna sahip olan metnin Huffman algoritması ile ne oranda sıkışacağını bulalım :

Sıkıştırma öncesi gereken bit sayısını bulacak olursak : Her bir karakter eşit uzunlukta yani 8 bit ile temsil edildiğinden toplam karakter sayısı olan (50+35+20+10+8+4) = 127 ile 8 sayısını çarpmamız lazım. Orjinal veriyi sıkıştırmadan saklarsak 127*8 = 1016 bit gerekmektedir.

Huffman algoritmasını kullanarak sıkıştırma yaparsak kaç bitlik bilgiye ihtiyaç duyacağımızı hesaplayalım : 50 adet "a" karakteri için 50 bit, 35 adet "b" karakteri için 70 bit, 20 adet "k" karakteri için 60 bit....4 adet "ğ" karakteri için 20 bite ihtiyaç duyarız. (yukarıdaki tabloya bakınız.) Sonuç olarak gereken toplam bit sayısı = 50*1 + 35*2 + 20*3 + 10*4 + 8*5 + 4*5 = 50 + 70 + 60 + 40 + 40 + 20 = 280 bit olacaktır.

Sonuç : 1016 bitlik ihtiyacımızı 280 bite indirdik. Yani yaklaşık olarak %72 gibi bir sıkıştırma gerçekleştirmiş olduk. Gerçek bir sistemde sembol frekanslarınıda saklamak gerektiği için sıkıştırma oranı %72’ten biraz daha az olacaktır. Bu fark genelde sıkıştırılan veriye göre çok çok küçük olduğu için ihmal edilebilir.

Huffman Kodunun Çözülmesi

Örnekte verilen frekans tablosuna sahip bir metin içerisindeki "aabkdğmma" veri kümesinin sıkıştırılmış hali her karakter ile karakterin kodu yer değiştirilerek aşağıdaki gibi elde edilir.

a a b    k     d         ğ        m       m      a
0 0 10  110  11111  11110  1110   1110  0    --> 00101101111111110111011100

Eğer elimizde frekans tablosu ve sıkıştırılmış veri dizisi varsa işlemlerin tersini yaparak orjinal veriyi elde edebiliriz. Şöyleki; sıkıştırılmış verinin ilk biti alnır. Eğer alınan bit bir kod sözcüğüne denk geliyorsa, ilgili kod sözcüğüne denk düşen karakter yerine koyulur, eğer alınan bit bir kod sözcüğü değilse sonraki bit ile birlikte ele alınır ve yeni dizinin bir kod sözcüğü olup olmadığına bakılır. Bu işlem dizinin sonuna kadar yapılır ve huffman kodu çözülür. Huffman kodları tek çözülebilir kod olduğu için bir kod dizisinden farklı semboller elde etmek olanaksızdır. Yani bir huffman kodu ancak ve ancak bir şekilde çözülebilir. Bu da aslında yazının başında belirtilen kayıpsız sıkıştırmanın bir sonucudur.

C# ile Huffman Algoritmasının Gerçekleştirilmesi

Huffman algoritması bilgisayar bilimlerinde genellikle metin dosyalarının sıkıştırılmasında kullanılır. Bu yazıda örnek bir program ile Huffman algoritmasının ne şekilde uygulanacabileceğini de göreceğiz. Dil olarak tabiki C#’ı kullanılacaktır.

Huffman algoritmasının uygulanmasındaki ilk adım frekans tablosunun bulunmasıdır. Bu yüzden bir dosyayı sıkıştırmadan önce dosyadaki her bir karakterin ne sıklıkla yer aldığını bulmak gerekir. Örnek programda sembol frekanslarını bellekte tutmak için System.Collections isim alanıdan bulunan Hashtable koleksiyon yapısı kullanılmıştır. Örneğin "c" karakterinin frekansı 47 ise,

CharFrequencies["c"] = 47

şeklinde sembolize edilir. Örnek programda frekans tablosu aşağıdaki metot ile elde edilebilir. Sıkıştırılacak dosya baştan sona taranarak frekanslar hashtable nesnesine yerleştirilir.

[Not : Örnek uygulamada kullandığım değişken ve metot isimlerini bazı özel nedenlerden dolayı İngilizce yazmak zorunda kaldığım için tüm okurlardan özür dilerim.]


private Hashtable CharFrequencies = new Hashtable();

private void MakeCharFrequencies()
{
       FileStream fs = File.Open(file,FileMode.Open,FileAccess.Read);        StreamReader sr = new StreamReader(fs,System.Text.Encoding.ASCII);

       int iChar;
       char ch;
       while((iChar = sr.Read()) != -1)
       {
              ch = (char)iChar;
              if(!CharFrequencies.ContainsKey(ch.ToString()))
              {
                     CharFrequencies.Add(ch.ToString(),1);
              }
              else
              {
                     int oldFreq = (int)CharFrequencies[ch.ToString()];
                     int newFreq;
                     newFreq = oldFreq + 1;
                     CharFrequencies[ch.ToString()] = newFreq;
              }
       }

       sr.Close();
       fs.Close();
       sr = null;
       fs = null;
}

Frekans tablosunu yukarıdaki metot yardımıyla oluşturduktan sonra huffman algoritmasının en önemli adımı olan huffman ağacının oluşturulmasına sıra geldi. Huffman ağacının oluşturulması en önemli ve en kritik noktadır. Huffman ağacı oluşturulurken Tree(ağaç) veri yapısından faydalanılmıştır. Ağaçtaki her bir düğümü temsil etmek için bir sınıf yazılmıştır. Huffman ağacındaki düğümleri temsil etmek için kullanılabilecek en basit düğüm sınıfının yapısı aşağıdaki gibidir.



Yukarıdaki düğüm yapısı algoritmayı uygulamak için gereken en temel düğüm yapısıdır. Bu yapı istenildiği gibi genişletilebilir. Önemli olan minimum gerekliliği sağlamaktır. Düğüm sınıfındaki SagDüğüm ve SolDüğüm özellikleri de düğüm türündendir. Başlangıçtaki düğümler için bu değerler null dır. Her bir yeni düğümm oluşturulduğunda yeni düğümün sağ ve sol düğümleri oluşur. Ancak unutmamak gerekir ki sadece sembollerimizi oluşturan yaprak düğümlerde bu özellikler null değerdedir.

Örnek uygulamadaki HuffmanNode sınıfında ayrıca ilgili düğümün yaprak olup olmadığını gösteren IsLeaf ve ilgili düğümün ana(parent) düğümünü gösteren HuffmanNode türünden ParentNode özellikleri bulunmaktadır.

HuffmanNode düğüm sınıfının yapısı aşağıdaki gibidir.



using System; namespace Huffman
{
     public class HuffmanNode
     {
          private HuffmanNode leftNode;
          private HuffmanNode rightNode;

          private HuffmanNode parentNode;

          private string symbol;
          private int frequency;
          private string code = "";

          private bool isLeaf;

          public HuffmanNode LeftNode
          {
               get{return leftNode;}
               set{leftNode = value;}
          }

          public HuffmanNode RightNode
          {
               get{return rightNode;}
               set{rightNode = value;}
          }

          public HuffmanNode ParentNode
          {
               get{return parentNode;}
               set{parentNode = value;}
          }

          public string Symbol
          {
               get{return symbol;}
               set{symbol = value;}
          }

          public string Code
          {
               get{return code;}
               set{code = value;}
          }

          public int Frequency
          {
               get{return frequency;}
               set{frequency = value;}
          }

          public bool IsLeaf
          {
               get{return isLeaf;}
               set{isLeaf = value;}
          }


          public HuffmanNode()
          {

          }
     }

     public class NodeComparer : IComparer
     {
          public NodeComparer()
          {
          }

          public int Compare(object x, object y)
          {
               HuffmanNode node1 = (HuffmanNode)x;
               HuffmanNode node2 = (HuffmanNode)y;

               return node1.Frequency.CompareTo(node2.Frequency);
          }
     }
}

Başlangıçta sembol sayısı kadar HuffmanNode nesnesi yani huffman düğümü oluşturmamız gerekecektir. Oluşturulan bu düğümler Arraylist koleksiyon yapısında tutulmaktadır. Her bir yeni düğüm oluşturulduğunda Arraylist kolaksiyonun yeni bir düğüm eklenir ve iki düğüm çıkarılır. Yeni düğümün sağ ve sol düğümleri çıkarılan düğümler olacaktır. İlk oluşturulan düğümlerin sağ ve sol düğümlerinin null olduğunu hatırlayınız. Yeni düğüm eklendiğinde Arraylist sınıfının Sort() metodu yardımıyla düğümler frekanslarına göre küçükten büyüğe doğru sıralanır. Yani Arraylist elemanını ilk elemanı en küçük frekanslı düğümdür. Sort() metodu IComparer arayüzünü kullanan NodeComparer sınıfını kullanmaktadır. Yani bu sınıftaki Compare() metodu yukarıdaki kodda belirtildiği gibi düğüm nesnelerinin neye göre sıralancağını tanımlar.

Yukarıdaki tanımlar ışığında Huffman ağacı aşağıdaki metot yardımıyla bulunabilir. Dikkat ettiyseniz, metodun icrası bittiğinde Nodes koleksiyonunda tek bir düğüm nesnesi kalacaktır, bu da huffman ağacındaki kök düğümden(root node) başkası değildir.


private ArrayList Nodes;

public void MakeHuffmanTree()
{
     Nodes = new ArrayList();      //Başlangıç düğümleri oluşturuluyor.
     foreach(Object Key in CharFrequencies.Keys)
     {
          HuffmanNode node = new HuffmanNode();
          node.LeftNode = null;
          node.RightNode = null;
          node.Frequency = (int)(CharFrequencies[Key]);
          node.Symbol = (string)(Key);
          node.IsLeaf = true;
          node.ParentNode = null;

          Nodes.Add(node);
     }

     //Düğümlerin neye göre sıralanacağı NodeComparer sınıfındaki Compare metodunda tanımlıdır.
      Nodes.Sort(new NodeComparer());


     while(Nodes.Count > 1)
     {
          HuffmanNode node1 = (HuffmanNode)Nodes[0];
          HuffmanNode node2 = (HuffmanNode)Nodes[1];

          HuffmanNode newnode1 = new HuffmanNode();
          newnode1.Frequency = node1.Frequency + node2.Frequency;
          newnode1.IsLeaf = false;
          newnode1.LeftNode = node1;
          newnode1.RightNode = node2;
          newnode1.Symbol = node1.Symbol + node2.Symbol;

          node1.ParentNode = newnode1;
          node2.ParentNode = newnode1;

          Nodes.Add(newnode1);

          Nodes.Remove(node1);
          Nodes.Remove(node2);

            Nodes.Sort(new NodeComparer());
     }
}

Algoritmanın son adımı ise Huffman kodlarının oluşturulmasıdır. Programatik olarak kodlamanın en zor olduğu bölüm burasıdır. Zira burada huffman ağacı öz-yineli(recursive) olarak taranarak her bir düğümün huffman kodu atanacaktır. Performansı artırmak için semboller ve kod sözcükleri ayrıca bir Hashtable koleksiyonunda saklanmıştır. Böylece her bir kodun çözülmesi sırasında ağaç yapısı taranmayacak, bunun yerine Hashtable’dan ilgili kod bulunacaktır. Kodlamayı yapan metot aşağıdaki gibidir.


private void FindCodeWords(HuffmanNode Node)
{
     HuffmanNode leftNode = Node.LeftNode;
     HuffmanNode rightNode = Node.RightNode;

     if(leftNode == null && rightNode == null)
          Node.Code = "1";      if(Node == this.RootHuffmanNode)
     {
          if(leftNode != null)
               leftNode.Code = "0";

          if(rightNode != null)
               rightNode.Code= "1";
     }
     else
     {
          if(leftNode != null)
               leftNode.Code = leftNode.ParentNode.Code + "0";

          if(rightNode != null)
               rightNode.Code= rightNode.ParentNode.Code + "1";
     }


     if(leftNode != null)
     {
          if(!leftNode.IsLeaf)
                  FindCodeWords(leftNode);
          else
          {
               CodeWords.Add(leftNode.Symbol[0].ToString(),leftNode.Code);
          }
     }

     if(rightNode != null)
     {
          if(!rightNode.IsLeaf)
                  FindCodeWords(rightNode);
          else
          {
               CodeWords.Add(rightNode.Symbol[0].ToString(),rightNode.Code);
          }
     }
}

Huffman algoritmasının temel basamakları bitmiş durumda. Bundan sonraki kodlar elde edilen sıkıştırılmış verinin ne şekilde dosyaya kaydedileceği ve sıkıştırılmış dosyanın nasıl tekrar geri elde edileceği ile ilgilidir. Bu noktada uygulamamız için bir dosya formatı belirlememiz gerekmektedir. Hatırlanacağı üzere sıkıştırılmış veriyi tekrar eski haline getirmek için frekans tablosuna ihtiyacımız vardır. Dolayısıyla sıkıştırılmış veriyi dosyaya yazmadan önce dosya formatımızın kurallarına göre sembol frekanslarını dosyaya yazmamız gerekir.

Benim programı yazarken geliştirdiğim dosya formatı aşağıdaki gibidir.

dosya.huff
-----------
1- ) İlk 4 byte --> Orjinal verideki toplam sembol sayısı.(ilk byte yüksek anlamlı byte olacak şekilde)
2 -) Sonraki 1 byte --> Data bölümünde bulunan son byte’taki ilk kaç bitin data’ya dahil olduğunu belirtir. (Data bölümündeki bitlerin sayısı 8’in katı olmayabilir.)
3 -) 2 byte Sembol + 4 byte sembol frekansı (bu bölüm ilk 4 byte’ta belirtilen sembol sayısı kadar tekrar edecektir.-ilk byte yüksek anlamlı byte olacak şekilde-)
4 -) Son bölümde ise sıkıştırılmış veri bit dizisi şeklinde yer alır.

Aşağıdaki metot yukarıda belirlenen kurallara göre sıkıştırılmış veriyi dosyaya .huff uzantılı olarak kaydedir.

[Not : Yazılacak programa göre bu dosya formatı değişebilir. Örneğin birden fazla dosyayı aynı anda sıkıştıran bir program için bu format tamamen değişecektir.]


public void WriteCompressedData()
{
     /// 4 byte ->(uint) Sembol Sayısı(K adet)
     /// 1 byte ->(uint) Data bölümünde bulunan son byte’taki ilk kaç bitin data’ya dahil olduğunu belirtir.
     ///
     /// ------------------SEMBOL FREKANS BÖLÜMÜ------------------------------------------
     ///
     /// 2 byte Sembol + 4 byte Sembol Frekansı
     /// .
     /// . K adet
     /// .
     /// 2 byte Sembol + 4 byte Sembol Frekansı
     ///
     ///
     /// ------------------DATA BÖLÜMÜ----------------------------------------------------
     ///
     /// Bu bölümde Sıkıştırılmış veriler byte dizisi şeklinde yer alır.
     ///
     /// Data bölümü (6*K + 6) numaralı byte’tan itibaren başlar.
     ///

     int K = CharFrequencies.Keys.Count;      /*K = 4 ise
     *
     * byte[0] = 0 0 0 0 0 1 0 0
     * byte[1] = 0 0 0 0 0 0 0 0
     * byte[2] = 0 0 0 0 0 0 0 0
     * byte[3] = 0 0 0 0 0 0 0 0
     *
     * K(bits) = 00000100 00000000 00000000 00000000
     * */

     byte[] byteK = BitConverter.GetBytes(K);


     FileStream fs = File.Open(this.NewFile,FileMode.Create,FileAccess.ReadWrite);

     byte[] CompressedByteStream = GenerateCompressedByteStream();
     WriteByteArrayToStream(byteK,fs);
     fs.WriteByte(RemainderBits);
     
     foreach(string sembol in CharFrequencies.Keys)
     {
          byte[] byteC = BitConverter.GetBytes((char)sembol[0]);
          byte[] bytesFreqs = BitConverter.GetBytes((int)CharFrequencies[sembol]);

          WriteByteArrayToStream(byteC,fs);
          WriteByteArrayToStream(bytesFreqs,fs);
     }

     WriteByteArrayToStream(CompressedByteStream,fs);

     fs.Flush();
     fs.Close();
}

Sıkıştırılan bir veri geri elde edilemediği sürece sıkıştırmanın bir anlam ifade etmeyeceği düşünülürse sıkıştırma işleminin tersinide yazmamız gerekmektedir. Sıkıştırma işlemi yaparken yaptığımız işlemlerin tersini yaparak orjinal veriyi elde edebiliriz. Sıkıştırılmış bir dosyayı açmak için aşağıdaki adımlar izlenir.

1 -) .huff uzantılı dosyadan sembol frekansları okunur ve Hashtable nesnesine yerleştirilir.
2 -) Frekans tablosu kullanılarak Huffman ağacı oluşturulur.
3 -) Huffman ağacı kullanılarak Huffman kodları oluşturulur.
4 -) .huff uzantılı dosyanın data bölümünden sıkıştırılmış veri dizisi okunarak huffman kodları ile karşılaştırılarak orjinal metin bulunur ve .txt uzantılı dosyaya yazılır.

2. ve 3. adımlardaki işlemler sıkıştırma yapıldığında kullanılan işlemler ile aynıdır. Burada ayrıca değenmeye gerek yoktur. Bu aşamada önemli olan verilen okunması ve yazılmasında izlenen yoldur. Verilerin okunmasında ve tekrar yazılmasında StringBuilder sınıfı kullanılmıştır. Bu sınıf string nesnesine göre oldukça iyi performans göstermektedir. Örneğin aynı işlemi string ile yaptığımda 75 K’lık bir dosya açma işlemi 30 sn sürerken StringBuilder kullandığımda 2 sn sürmektedir.

1.aşamdaki işlemi yapacak metot aşağıdaki gibidir.


private System.Text.StringBuilder CompressedData = new System.Text.StringBuilder("");

private void ReadCompressedFile()
{
     FileStream fs = File.Open(file,FileMode.Open,FileAccess.Read);      //İlk önce sembol sayısını bulalım.
     byte[] byteK = new byte[4];

     for(int i=0 ; i<4 ; i++)
     {
         byteK[i] = (byte)fs.ReadByte();
     }

     int SymbolCount = BitConverter.ToInt32(byteK,0);

     int RemainderBitCount = (byte)fs.ReadByte();

     for(int k = 0; k < SymbolCount ; k++)
     {
          //Sembollerin elde edilmesi(2 byte)
          byte[] symbolB = new byte[2];
          symbolB[0] = (byte)fs.ReadByte();
          symbolB[1] = (byte)fs.ReadByte();

          char cSymbol = BitConverter.ToChar(symbolB,0);

          //Frekans bilgisinin elde edilmesi(4 byte)
          byte[] freqB = new byte[4];
          for(int j=0 ; j<4 ; j++)
          {
               freqB[j] = (byte)fs.ReadByte();
          }

          int freq = BitConverter.ToInt32(freqB,0);

          CharFrequencies.Add(cSymbol.ToString(),freq);
     }     

     //Data bölümünün okunması
     int readByte;
     while((readByte = fs.ReadByte()) != -1)
     {
          byte b = (byte)readByte;

          bool[] bits = new bool[8];
          bits = GetBitsOfByte(b);
          BitArray ba = new BitArray(bits);

          for(int m=0 ; m < ba.Length ; m++)
          {
               if(ba[m])
                    CompressedData.Append("1");
               else
                    CompressedData.Append("0");
          }
     }

     //Son byte’taki fazla veriler atılıyor
     int removingBits = 8 - RemainderBitCount;

     if(RemainderBitCount != 0)
     {
          CompressedData.Remove(CompressedData.Length - removingBits, removingBits);
     }

     fs.Flush();
     fs.Close();
}

Dosyayı açarken son yapılması gereken adım okunan verilerin dosyaya yazılmasıdır. Bir önceki adımda okunan veriler aşağıdaki metot aracılığıyla yeni bir dosyaya kaydedilir.


System.Text.StringBuilder OriginalData = new System.Text.StringBuilder("");

private void WriteOrginalData()
{
     FileStream fs = File.Open(this.NewFile,FileMode.Create,FileAccess.ReadWrite);

     StreamWriter sw = new StreamWriter(fs,System.Text.Encoding.ASCII);      System.Text.StringBuilder sb = new System.Text.StringBuilder("");

     //Hashtable’ın performansından faydalanmak için kod sözcükleri ters çevrilip yeni bir hashtable oluşturuluyor.
     ReverseCodeWordsHashtable();

     for(int i=0 ; i < CompressedData.Length ; i++)
     {
          sb.Append(CompressedData[i]);

          string symbol = "";
          bool found = false;

          if(CodeWords.ContainsValue(sb.ToString()))
          {
               symbol = (string)ReversedCodeWords[sb.ToString()];
               found = true;
          }

          if(found)
          {
               OriginalData.Append(symbol);
               sb.Remove(0,sb.Length);
          }
     }

     sw.Write(OriginalData.ToString());

     sw.Flush();
     fs.Flush();
     sw.Close();
     fs.Close();
}

Yukarıdaki metotların tamamı Huffman isimli bir metotta toplanmıştır. Dosya sıkıştırma ve dosya açma için farklı nesnelerin kullanılması gerekmektedir. Huffman sınıfının örnek kullanımı aşağıda verilmiştir.



//Sıkıştırma
Huffman hf1 = new Huffman("deneme.txt");
hf1.Compress();

//Açma
Huffman hf2 = new Huffman("deneme.huff");
hf2.Decompress();
Uygulamayı 75 K’lık bir İngilizce metin tabanlı dosya üzerinde çalıştırdığımda dosyanın 43 K’ya düştüğünü aşağıdaki gibi gözlemledim.



Umarım faydalı bir prgram ve faydalı bir yazı olmuştur.

Uygulamanın bütün kodlarını ve proje dosyasını indirmek için tıklayınız.

Not : Bu makalenin son cümlesini yazdığımda programın açma modülünde Türkçe karakterler ile ilgili bir bug’ın olduğunu farkettim. Yani şu anda herhangi bir türkçe karakter içeren dosyayı sıkıştırıp dosyayı tekrar açtığınızda Türkçe karakterler yerine "?" karakterini görecekseniz. En kısa zamanda bug’ı düzeltip kaynak kodları yeniden yükleyeceğim. Bug’ın nedenini bulup düzelten kişiye süpriz bir ödül vereceğimide belirtmek isterim.


Makale:
Huffman Veri Sıkıştırma Algoritması ve Uygulaması C#, Visual C# ve .NET Sefer Algan
  • Yazılan Yorumlar
  • Yorum Yaz
MAY
20
2013
Merhaba, Proje kaynak kod linkini yenileyebilir misiniz?
MAY
6
2013
Proje dosya linki çalışmıyor. Yenileyebilir misiniz?
ARA
5
2012
Sefer hocam linki yenileyebilirmisiniz? ("Uygulamanın bütün kodlarını ve proje dosyasını indirmek için tıklayınız.")
MAY
12
2010
Yıllar sonra gelen edit,bu makaleye göre çalışacaklar için referans olur diye :) Sorunun kaynağı compress ve decompress işlemlerin de CharFrequencies tablosunun(HashTable) sırasının farklı olması bu nedenle aynı frekanslı elemanlar farklı sırayla sıralanabiliyor ve Huffman tree iki işlemde (Encode,Decode) farklı oluşturulmuş oluyor, Çözmek için mi; MakeHuffmanTree metodundan önce Frekans hash tablosunu frekanslara göre değilde karakterlere göre sıralayın ondan sonra o sıralamaya göre oluşturun ağacı sorun halloluyor.Çünkü frekans aynı olsada karakter compare'i aynı olma ihtimali yok.
MAR
20
2006
try this to read Turkish encoded text files. StreamReader DataFile = new StreamReader( (System.IO.Stream)File.OpenRead(op.FileName), System.Text.Encoding.GetEncoding(1254)) CodePage 1254 Microsofts Turkish encoding
ŞUB
7
2004
bu bug sanırım ferekans tablosunun bellekte tutuluş şekliyle ilgili. karakter yerine byte düzeyinde işlem yapılması daha mantıklı..
ŞUB
7
2004
Yanlı yazmışım az önce. 3 tane t ve 3 tane u vardı. Yani aynı sayıda olan karakterleri birbirine karıştırıyor açarken!
ŞUB
7
2004
\n ve \t için denedim. Dediğiniz gibi hatalı çalışıyor. Hem de çok hatalı! Türkçe olmayan karakterler bile hatalı. Denediğim dosyada 3 tane m ve 3 tane u karakteri vardı. u ların yerine t koyuyor. T lerin yerine kare şeklinde bir karakter koyuyor. \t ve \n leri ise yokmuş gibi varsayıyor. \n nin olduğu yere "ni" koyuyor! Neyse, üzerinde çalışacağım bunun...
ŞUB
6
2004
elbette sıkıştırma ve açmayı aynı kodlarla yapmak lazım..zaten sorun burda değil sizin denemediğiniz \n ve \t karakterlerinde :)
ŞUB
6
2004
Ben denerken tek satırlık küçük bir dosya kullanmıştım. Satır sonu ve tab ı deneyip sonucunu bildireyim. Yalnız şunu belirteyim ki kodun eski haliyle sıkıştırılmış dosya yeni haliyle düzgün açmıyor. Kodu düzeltip sıkıştırsanız sorunsuz açıyor.
ŞUB
6
2004
Unicode içinde geçerli.. deneyip sonucu bildireceğim
ŞUB
6
2004
utf8 değil ki benim cevabım unicode yazmıştım. Ayrıca değiştirip denersen sorunsuz çalıştığını görürsün
ŞUB
6
2004
içinde satır sonu(\n) ve tab(\t) ollan metinlerde doğru çalıştığına eminmisiniz.. eğer eminseniz kodu ve kullandığınız text dosyasını gönderirmisiniz bana.
ŞUB
5
2004
Ayrıca ben cevabımı size e-mail ile göndermiştim. O yüzden hediyemi bekliyorum:)
ŞUB
5
2004
Ben 3 ayrı yerdeki ASCII yi UTF8 olarak değiştirip denediğimde Türkçe karakterler hiç sorunsuz görünüyor.
Sayfalar : 1 2 
Yorum yazabilmek için üye girişi yapmalısınız. Üye girişi için tıklayın.
Üye değilseniz Üyel Ol linkine tıklayarak üyeliğinizi hemen başlatabilirisniz.
 
  • Bu Konuda Son 10
  • Eklenen Son 10
  • Bu Konuda Geçmiş 10
Bu Konuda Yazılmış Yazılmış 10 Makale Yükleniyor
Son Eklenen 10 Makale Yükleniyor
Bu Konuda Yazılmış Geçmiş Makaleler Yükleniyor