Huffman Sıkıştırma Algoritmasının Optimizasyonu
Huffman önek kodlamasını hız ve sıkıştırma oranı açısından inceleyen, dosya üzerinde çalışan masaüstü uygulaması ve optimizasyon deneyi.
Bu proje, Huffman sıkıştırma algoritmasını hem çalışma maliyeti hem de ortaya çıkan sıkıştırma oranı açısından incelemek için geliştirdiğim masaüstü uygulamasıdır.
Frekanslardan Önek Koduna
Huffman kodlamasında sembollerin görülme sıklıkları hesaplanır ve düşük frekanslı düğümler aşamalı olarak birleştirilerek ikili bir ağaç oluşturulur. Ağacın yapraklarına giden yollar değişken uzunluklu bit kodlarını belirler.
Sık görülen sembollerin daha kısa, seyrek sembollerin daha uzun kod alması toplam bit sayısını azaltabilir. Kodların prefix-free olması, akışın ayraç eklenmeden tek anlamlı biçimde çözülebilmesini sağlar.
Optimizasyon Problemi
Algoritmanın matematiksel fikri tek başına uygulama performansını belirlemez. Frekans tablosunun oluşturulması, en düşük ağırlıklı düğümlerin seçimi, ağaç yapısı, bitlerin paketlenmesi ve dosya G/Ç maliyeti toplam süreyi etkiler.
Bu projede hız ve sıkıştırma verimini birlikte değerlendirmeye çalıştım. Tarihsel kayıtta kullanılan test dosyasının sıkıştırılmış boyutunun başlangıç boyutunun yaklaşık %58'i olduğu belirtilmiştir.
Bu oran Huffman algoritmasının genel sıkıştırma oranı değildir. Sonuç tamamen giriş verisinin sembol dağılımına bağlıdır; zaten sıkıştırılmış veya yüksek entropili veri çok az kazanç sağlayabilir.
Teorik Bağlam
Huffman kodlama, kayıpsız ve olasılık/frekans tabanlı bir önek kodlama yöntemidir. Daha geniş algoritma ve veri yapısı çerçevesi Veri Yapıları ve Algoritma Analizi notlarımda yer alır.
Bugünkü performans yaklaşımımla aynı projeyi değerlendirirken sıkıştırma oranını, encode/decode süresini, bellek tüketimini ve kullanılan test veri kümesini ayrı metrikler halinde raporlamayı tercih ederim.
