Sıkıştırma algoritması için bir kodlama mekanizmasının tasarlanması

Kanonik Huffman Kodlama halen birçok uygulamada kullanılan bir olasılık tabanlı veri sıkıştırma algoritmasıdır. Geleneksel uygulamada Kanonik Huffman kodlarını üretmek için önce kod ağacı oluşturulur, daha sonra yapraklardan köke doğru gidilerek kod sözcükleri ve bunların bit sayısı (uzunlukları) elde edilir. Daha sonra bu uzunluklardan Kanonik kodlar hesaplanır. Bu çok aşamalı işlem yerine, bu tezde, doğrudan hesaplama yoluyla kod uzunluklarını tek aşamada hesaplayan Cebirsel Kanonik Huffman Kodlaması (ACHC) önerilmiştir. Uzunluklar hesaplandıktan sonra ikili toplama ile her uzunluğa karşılık gelen kod sözcükleri hesaplanır. Klasik yöntemin O(n(logn+l)) zaman karmaşıklığına karşılık, ACHC algoritması O(n) zaman karmaşıklığına sahiptir. Uzay karmaşıklığı standart Huffman kodlaması için O(5n) ve ACHC için O(n)'dir. Bu da %80 bellek tasarrufu anlamına gelmektedir. Ancak sembol başına ortalama bit uzunluğu genellikle en iyi değer olmayıp, en iyi değere benzerlerinden çok daha yakındır. Bu nedenle, bu tezde ACHC algoritmasını Evrimsel Stratejiler algoritması ile en iyileştiren ikinci algoritma (ES_ACHC) önerilmiştir. Bu algoritmayla kısa döngü zamanında optimum kanonik kodlar elde edilmiştir. ACHC algoritmasının adaptif uygulaması (A_ACHC), bu tezin mevcut bilgilere üçüncü katkısıdır. A_ACHC algoritması ile çok bilinen Vitter algoritmasına göre ortalama olarak aynı sıkıştırma oranı ile %80 bellek tasarrufu sağlanmıştır. Anahtar Kelimeler: Kanonik Huffman, Adaptif Huffman, Kodlama, Evrimsel Stratejiler, Veri Sıkıştırma