Geri Dön

Devising a coding mechanism for compression algorithms

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

  1. Tez No: 856577
  2. Yazar: MUHAMMED MUSTAFA AŞŞIK
  3. Danışmanlar: DOÇ. DR. FATİH ABUT
  4. Tez Türü: Doktora
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Kanonik Huffman, Adaptif Huffman, Kodlama, Evrimsel Stratejiler, Veri Sıkıştırma, Canonical Huffman, Adaptive Huffman, Encoding, Evolution Strategies, Data Compression
  7. Yıl: 2024
  8. Dil: İngilizce
  9. Üniversite: Çukurova Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 93

Özet

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.

Özet (Çeviri)

Canonical Huffman Coding is a data compression algorithm still widely used in many applications. Originally, to produce canonical Huffman codes, first, the code tree is created, then from the leaves to the root, code lengths are obtained. Canonical codes are then calculated from these lengths. Instead of this multi-stage process, Algebraic Canonical Huffman Coding (ACHC), which calculates the code lengths in one stage through direct calculation, is proposed in this thesis. After the calculation of the lengths, the codewords corresponding to each length are calculated by binary addition. Time complexity is O(n) for ACHC and is O(n(logn+l)) for classical canonical Huffman coding. Space complexity is O(5n) standard for Huffman coding and O(n) for ACHC. This means memory saving is 80%. However, the average bit length per symbol is not usually optimal but is much closer to the optimal than similar methods. Therefore, the second algorithm (ES_ACHC) that optimizes the ACHC algorithm with the Evolutionary Strategies algorithm, is also proposed in this thesis. With this algorithm, optimum canonical codes were obtained with shorter loops. The adaptive application of the ACHC algorithm (A_ACHC) is the third contribution of this thesis to the existing literature. With the A_ACHC algorithm, 80% of memory savings have been achieved with the same compression ratio compared to the well-known Vitter algorithm.

Benzer Tezler

  1. Liderlik etkinliğinin ölçümü için bir model önerisi

    Başlık çevirisi yok

    ZEYNEP DİDEM DEMİRÖZLÜ

    Yüksek Lisans

    Türkçe

    Türkçe

    1998

    Endüstri ve Endüstri Mühendisliğiİstanbul Teknik Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    DOÇ. DR. TUFAN VEHBİ KOÇ

  2. Farklı karbon vergisi uygulamalarının piyasa takas fiyatı ve fosil kaynaklı üretim üzerine etkisi

    Potential impacts of a carbon tax on the day-ahead market prices and the electricity generation mix

    ELİFNUR TOMA

    Yüksek Lisans

    Türkçe

    Türkçe

    2020

    Enerjiİstanbul Teknik Üniversitesi

    Enerji Bilim ve Teknoloji Ana Bilim Dalı

    PROF. DR. ÜNER ÇOLAK

  3. Advanced cross-layer secure communication designs for future wireless systems

    Geleceğin kablosuz sistemlerinde katmanlar arası ileri güvenli haberleşme tasarımları

    JEHAD MAHMOUD AMIN HAMAMREH

    Doktora

    İngilizce

    İngilizce

    2018

    Elektrik ve Elektronik Mühendisliğiİstanbul Medipol Üniversitesi

    Elektrik-Elektronik Mühendisliği Ana Bilim Dalı

    PROF. DR. HÜSEYİN ARSLAN

  4. Hücresel yapay sinir ağları için iki öğrenme algoritması ve görüntü işleme uygulamaları

    Two learning algorithms for cellular neural networks and their image processing applications

    SİNAN KARAMAHMUT

    Yüksek Lisans

    Türkçe

    Türkçe

    1994

    Elektrik ve Elektronik Mühendisliğiİstanbul Teknik Üniversitesi

    DOÇ.DR. CÜNEYT GÜZELİŞ