Mengembangkan utilitas kompresi data berbasis kode Huffman dengan Haskell

Implementasi program kompresi data menggunakan pengodean Huffman

• Apa itu kode Huffman?
  • Melakukan kompresi data dengan memetakan setiap karakter ke urutan bit yang unik
  • Karakter yang sering muncul dipetakan ke urutan bit yang pendek, sedangkan karakter yang jarang muncul dipetakan ke urutan bit yang panjang
  • Contoh: untuk string aaab, a dipetakan ke 1 dan b ke 0, sehingga dikompresi menjadi 1110

Kode tanpa prefiks

• Apa itu kode tanpa prefiks?
  • Memastikan tidak ada satu kata kode pun yang menjadi prefiks dari kata kode lain
  • Contoh: untuk aaabc, a dipetakan ke 1, b ke 00, dan c ke 01, sehingga dikompresi menjadi 1110001

Membuat kode tanpa prefiks

• Cara membuat kode tanpa prefiks
  • Menempatkan semua karakter sebagai daun pada pohon biner penuh
  • Cabang kiri diberi label 1, cabang kanan diberi label 0
  • Jalur dari akar ke daun menjelaskan kata kode untuk tiap karakter

Menulis coder

• Definisi tipe

  • Mendefinisikan tipe Bit, Code, FreqMap, CodeMap, Weight, HTree
  • HTree terdiri dari Leaf dan Fork

• Fungsi encoding

  • Fungsi untuk mengubah string menjadi bit
  • Menghitung frekuensi tiap karakter menggunakan FreqMap, lalu membuat pohon Huffman berdasarkan hasil tersebut
  • Menghasilkan kata kode untuk tiap karakter dari pohon Huffman

• Fungsi decoding

  • Fungsi untuk mengubah bit kembali menjadi string asli
  • Mendekode bit secara berurutan menggunakan pohon Huffman

Integrasi dengan file biner

• Encoding data biner
  • Menggunakan modul Data.ByteString.Char8 untuk membaca byte sebagai karakter
  • Mengodekan data biner menggunakan coder teks

Serialisasi

• Fungsi serialisasi
  • Mengubah FreqMap dan bit menjadi byte nyata lalu menyimpannya ke file
  • Menggunakan monad Put untuk menghasilkan ByteString secara efisien

Deserialisasi

• Fungsi deserialisasi
  • Mengubah data yang dibaca dari file menjadi FreqMap dan bit
  • Menggunakan monad Get untuk mendeserialisasi FreqMap

Integrasi seluruh kode

• Fungsi kompresi dan dekompresi file
  • Fungsi compress: membaca file, membuat peta frekuensi, mengodekan data, lalu menyimpannya sebagai file terkompresi
  • Fungsi decompress: membaca file terkompresi, mendekode data, lalu menyimpannya kembali sebagai file asli

Peningkatan

• Multithreading

  • Mendekode bagian-bagian file secara paralel
  • Menambahkan tabel yang menentukan batas tiap bagian dan ukuran decode yang diharapkan agar pemrosesan paralel dimungkinkan

• Encoding single-pass

  • Membuat peta frekuensi secara real-time sambil melakukan encoding
  • Tidak perlu menyertakan peta frekuensi di awal file

• Kode Huffman kanonis

  • Melakukan decoding dalam kompleksitas waktu O(1) dengan mengindeks vektor alih-alih menelusuri pohon

• Pembuatan kode yang lebih cepat

  • Jika mencoba encoding single-pass, kecepatan pembuatan code map perlu ditingkatkan

Opini GN⁺

• Kelebihan pengodean Huffman

  • Memungkinkan kompresi data yang efisien dengan memetakan karakter yang sering muncul ke urutan bit yang pendek
  • Dapat menangani data besar sambil meminimalkan penggunaan memori

• Kelebihan Haskell

  • Memungkinkan penulisan kode yang modular dengan memanfaatkan keunggulan pemrograman fungsional
  • Dapat mengoptimalkan penggunaan memori melalui evaluasi malas

• Proyek dengan fungsi serupa

  • Tersedia berbagai alat kompresi data seperti gzip dan bzip2
  • Penting untuk membandingkan kelebihan dan kekurangan tiap alat agar dapat memilih yang paling sesuai

• Hal yang perlu dipertimbangkan saat mengadopsi teknologi baru

  • Algoritme yang tepat harus dipilih dengan mempertimbangkan performa dan penggunaan memori
  • Efisiensi dapat ditingkatkan dengan menerapkan teknik optimasi seperti encoding single-pass

[GN⁺]

Komentar Hacker News

• Ada algoritme in-place berbasis array sehingga tidak perlu mengalokasikan tree dan menelusuri pointer sebanyak itu

  • Saat mempelajari pendekatan berbasis tree di kampus, tidak tahu bahwa ada cara lain
  • Pendekatan tree memang intuitif dan bermanfaat, tetapi ketika harus memproses banyak data dengan cepat, menggunakan array in-place lebih masuk akal
  • Referensi: "In-Place Calculation of Minimum-Redundancy Codes" (Moffat, Katajainen, 1995)

• Pernyataan bahwa codeword tidak boleh menjadi prefiks dari codeword lain tidak sepenuhnya akurat secara teknis

  • Kelas kode yang dapat didekodekan secara unik adalah superset dari prefix code
  • Misalnya, kebalikan dari prefix code tetap bisa didekodekan dengan jelas
  • Contoh kode:

    a 1
    b 00
    c 10
    

  • Kode untuk 'a' adalah prefiks dari kode untuk 'c', tetapi jika diproses secara terbalik, hasilnya tetap dapat didekodekan dengan jelas

• Penasaran apakah ada tutorial serupa yang membahas fitur lebih tingkat lanjut untuk menulis program Haskell, seperti monad transformer, lens, dan sebagainya

• Kursus functional programming Coursera (Scala) memberikan tugas Huffman coding yang serupa

  • Tautan: Coursera Scala Functional Programming

• Pernah menggunakan Huffman code untuk menjalankan program makro prosesor MICMAC dengan jumlah microcycle dan microinstruction minimum

  • Membuat histogram instruksi makro lalu, berdasarkan itu, menulis program microcode progressive decoding
  • Dalam praktiknya, itu kemungkinan lambat dan tidak praktis
  • Kelebihan Huffman code adalah kedalaman prefiks bisa disesuaikan dengan distribusi nilai
  • Harus menangani branch prediction dalam model prosesor non-overlapped pipeline

• Info tambahan tentang Huffman coding: Rosetta Code Huffman Coding

• Pertanyaan untuk programmer Haskell: seperti apa performa Haskell bagi programmer yang ingin menulis kode yang dioptimalkan?

  • Secara khusus tertarik pada performa komputasi numerik yang memanfaatkan operasi matriks dan SIMD

• Ada komentar yang mengucapkan terima kasih karena sudah berbagi

• Ada typo pada tabel di bagian "Creating prefix-free codes"

  • D seharusnya '0010' (saat ini salah tertulis '0110')
  • Selain itu, artikelnya sangat enak dibaca

• Arithmetic coding hampir lebih baik dalam segala hal

  • Bisa diimplementasikan dengan RAM dan kode yang lebih sedikit
  • Memberikan rasio kompresi dan dekompresi yang lebih baik
  • Lebih mudah memperbarui probabilitas kemunculan simbol lain secara dinamis di tengah stream
  • Huffman code dipakai karena ditemukan lebih dulu dan arithmetic coding dulu memiliki paten
  • Sekarang patennya sudah kedaluwarsa, jadi seharusnya memakai desain yang lebih baik