Haskell kullanarak Huffman kodu tabanlı bir veri sıkıştırma yardımcı programı geliştirmek

Huffman kodlaması kullanan bir veri sıkıştırma programının uygulanması

• Huffman kodu nedir?
  • Her karakteri benzersiz bir bit dizisine eşleyerek veri sıkıştırması gerçekleştirir
  • Sık görülen karakterleri kısa bit dizilerine, nadir görülen karakterleri ise uzun bit dizilerine eşler
  • Örnek: aaab dizgesi için a, 1; b ise 0 olarak eşlenir ve 1110 şeklinde sıkıştırılır

Öneksiz kod

• Öneksiz kod nedir?
  • Hiçbir kod sözcüğünün başka bir kod sözcüğünün ön eki olmamasını sağlar
  • Örnek: aaabc için a, 1; b, 00; c ise 01 olarak eşlenir ve 1110001 şeklinde sıkıştırılır

Öneksiz kod üretimi

• Öneksiz kod oluşturma yöntemi
  • Tüm karakterler tam ikili ağacın yapraklarına yerleştirilir
  • Sol dal 1, sağ dal 0 olarak etiketlenir
  • Kökten yaprağa giden yol, her karakterin kod sözcüğünü tanımlar

Kodlayıcının yazılması

• Tür tanımları

  • Bit, Code, FreqMap, CodeMap, Weight, HTree türleri tanımlanır
  • HTree, Leaf ve Fork yapılarından oluşur

• Kodlama işlevi

  • Dizgeyi bitlere dönüştüren işlev
  • FreqMap kullanarak her karakterin frekansını hesaplar ve buna dayanarak Huffman ağacını oluşturur
  • Huffman ağacından her karakter için kod sözcükleri üretir

• Kod çözme işlevi

  • Bitleri özgün dizgeye dönüştüren işlev
  • Huffman ağacını kullanarak bitleri sırayla çözer

İkili dosyalarla entegrasyon

• İkili veri kodlama
  • Baytları karakter olarak okumak için Data.ByteString.Char8 modülü kullanılır
  • Metin kodlayıcı kullanılarak ikili veri kodlanır

Serileştirme

• Serileştirme işlevi
  • FreqMap ve bitleri gerçek baytlara dönüştürüp dosyaya kaydeder
  • Put monadı kullanılarak verimli bir ByteString oluşturulur

Ters serileştirme

• Ters serileştirme işlevi
  • Dosyadan okunan veriyi FreqMap ve bitlere dönüştürür
  • Get monadı kullanılarak FreqMap ters serileştirilir

Tüm kodun birleştirilmesi

• Dosya sıkıştırma ve açma işlevleri
  • compress işlevi: dosyayı okur, frekans haritasını oluşturur, veriyi kodlayıp sıkıştırılmış dosya olarak kaydeder
  • decompress işlevi: sıkıştırılmış dosyayı okur, veriyi çözüp özgün dosya olarak kaydeder

İyileştirmeler

• Çok iş parçacıklılığı

  • Dosyanın bölümlerini paralel olarak çözer
  • Bölüm sınırlarını ve beklenen çözme boyutunu belirten bir tablo ekleyerek paralel işlemeyi mümkün kılar

• Tek geçişli kodlama

  • Frekans haritasını gerçek zamanlı oluştururken aynı anda kodlama yapar
  • Dosyanın başında frekans haritasını bulundurmayı gerektirmez

• Kanonik Huffman kodu

  • Ağacı dolaşmak yerine vektör indeksleyerek O(1) zaman karmaşıklığıyla kod çözme sağlar

• Daha hızlı kod üretimi

  • Tek geçişli kodlama denenecekse, kod haritası üretim hızı artırılmalıdır

GN⁺ görüşü

• Huffman kodlamasının avantajları

  • Sık görülen karakterleri kısa bit dizilerine eşleyerek verimli veri sıkıştırması sağlar
  • Bellek kullanımını en aza indirirken büyük verileri işleyebilir

• Haskell'in avantajları

  • Fonksiyonel programlamanın avantajlarından yararlanarak modüler kod yazılabilir
  • Tembel değerlendirme sayesinde bellek kullanımı optimize edilebilir

• Benzer işlevlere sahip projeler

  • gzip, bzip2 gibi çeşitli veri sıkıştırma araçları bulunur
  • Her aracın artı ve eksilerini karşılaştırarak uygun aracı seçmek önemlidir

• Yeni teknoloji benimserken dikkat edilmesi gerekenler

  • Performans ve bellek kullanımını dikkate alarak uygun algoritma seçilmelidir
  • Tek geçişli kodlama gibi optimizasyon teknikleri uygulanarak verimlilik artırılabilir

[GN⁺]

Hacker News yorumu

• Ağaç tahsisi yapma ve pointer takip etme ihtiyacını azaltan, dizi tabanlı in-place algoritmalar mevcut

  • Üniversitede ağaç tabanlı yaklaşımı öğrenirken başka yöntemler olduğunu bilmiyordum
  • Ağaç yaklaşımı sezgisel ve öğretici, ancak çok miktarda veriyi hızlı işlemek gerektiğinde in-place dizi kullanmak daha mantıklı
  • Kaynak: "In-Place Calculation of Minimum-Redundancy Codes" (Moffat, Katajainen, 1995)

• Kod sözcüklerinin başka kod sözcüklerinin ön eki olmaması gerektiğini söylemek teknik olarak doğru değil

  • Eşsiz biçimde çözülebilen kod sınıfı, ön ek kodlarının bir üst kümesidir
  • Örneğin, bir ön ek kodunun ters çevrilmiş hâli yine de açık biçimde çözülebilir
  • Örnek kod:

    a 1
    b 00
    c 10
    

  • 'a' kodu, 'c' kodunun ön eki olsa da ters yönde işlendiğinde açık biçimde çözülebilir

• Haskell programları yazmanın daha ileri özelliklerini (monad transformer'lar, lens'ler vb.) ele alan benzer bir eğitim olup olmadığını merak ediyorum

• Coursera'nın fonksiyonel programlama kursu (Scala) benzer bir Huffman kodlama ödevi sunuyor

  • Bağlantı: Coursera Scala Functional Programming

• Huffman kodlarını kullanarak MICMAC işlemci makro programını asgari mikrodöngü ve mikrokomutla çalıştırdım

  • Makro komutların histogramını çıkardım ve buna dayanarak progressive decoding yapan bir mikrocode programı yazdım
  • Pratikte muhtemelen yavaş ve kullanışsız olurdu
  • Huffman kodlarının avantajı, değerlerin dağılımına göre ön ek derinliğini ayarlayabilmesidir
  • Taşmasız boru hattı olmayan bir işlemci modelinde branch prediction'ı ele almak zorundaydım

• Huffman kodlaması hakkında ek bilgi: Rosetta Code Huffman Coding

• Haskell programcılarına soru: optimize edilmiş kod yazmak isteyen bir programcı için Haskell'in performansı nasıl?

  • Özellikle matris işlemleri ve SIMD kullanan sayısal hesaplamaların performansını merak ediyorum

• Paylaştığınız için teşekkürler diyen bir yorum

• "Creating prefix-free codes" bölümündeki tabloda bir yazım hatası var

  • D, '0010' olmalı (şu anda yanlışlıkla '0110' yazıyor)
  • Bunun dışında harika bir okumaydı

• Aritmetik kodlama neredeyse her açıdan daha iyi

  • Daha az RAM ve daha az kodla uygulanabiliyor
  • Daha iyi sıkıştırma ve açma oranları sağlıyor
  • Akış sırasında farklı sembollerin görülme olasılığını dinamik olarak güncellemek daha kolay
  • Huffman kodları daha önce icat edildiği ve aritmetik kodlama patentli olduğu için kullanıldı
  • Patentler artık sona erdiğine göre daha iyi tasarımı kullanmalıyız