Membuat utilitas kompresi berbasis kode Huffman dengan Haskell

 (lazamar.github.io)
1 poin oleh GN⁺ 2024-07-06 | 1 komentar | Bagikan ke WhatsApp
  • Menunjukkan struktur untuk mengimplementasikan kompresor Huffman coding dengan sekitar 150 baris Haskell, yang menangani encoding dan decoding file biner arbitrer dengan memori konstan
  • Kode Huffman menetapkan deretan bit pendek untuk nilai yang sering muncul, dan kondisi prefix-free code membuat decoder dapat menafsirkan deretan bit tanpa ambiguitas
  • Implementasinya membangun tree dari tabel frekuensi dengan FreqMap, HTree, CodeMap, lalu menghasilkan output secara bertahap lewat lazy evaluation pada concatMap dan decoder rekursif
  • File biner diperlakukan sebagai byte layaknya Char dengan Data.ByteString.Char8; di depan hasil kompresi, tabel frekuensi diserialisasi, sementara deretan bit disimpan dengan padding per byte
  • Dalam pengujian, War and Peace menyusut dari 3,2M menjadi 1,9M, binary ghcup 106M menjadi 84M, dan maximum resident set size teramati di bawah 300KB

Ide dasar kompresi kode Huffman

  • Tujuannya adalah mengimplementasikan utilitas kompresi data dengan sekitar 150 baris Haskell menggunakan Huffman coding
  • Kode lengkapnya tersedia di repositori GitHub
  • Kode Huffman menetapkan deretan bit unik untuk setiap karakter atau nilai
    • Nilai yang sering muncul menggunakan deretan bit pendek
    • Nilai yang jarang muncul menggunakan deretan bit panjang
    • Efek kompresi muncul karena nilai yang umum direpresentasikan dengan bit lebih sedikit daripada representasi aslinya
  • Pada contoh aaab, jika a = 1 dan b = 0, hasilnya menjadi 1110
    • Ini contoh string yang membutuhkan 4 byte dalam UTF-8 direpresentasikan dengan setengah byte

Prefix-free code dan Huffman tree

  • Agar decoding tidak ambigu, tidak boleh ada codeword yang menjadi prefiks dari codeword lain
    • Misalnya pada aaabc, jika ditetapkan a = 1, b = 10, c = 01, maka 101 bisa ambigu apakah berarti ac atau ba
  • Prefix-free code dapat dibuat sebagai complete binary tree
    • Semua nilai ditempatkan pada leaf
    • Edge kiri diberi label 1, edge kanan diberi label 0
    • Jalur dari root ke leaf menjadi codeword untuk nilai tersebut
  • Huffman tree dibuat dengan cara menggabungkan dari bawah mulai dari nilai dengan frekuensi rendah
    • Setiap karakter dibuat menjadi node bersama weight berupa jumlah kemunculannya
    • Dua node dengan weight terkecil digabung menjadi tree
    • Weight tree baru adalah jumlah weight kedua node
    • Proses diulang sampai hanya tersisa satu tree
  • Melalui proses ini, nilai yang lebih sering muncul menjadi lebih dekat ke root sehingga memiliki codeword yang lebih pendek

Struktur encoder Haskell

  • Tipe utama dalam implementasi adalah Bit, Code, FreqMap, CodeMap, Weight, HTree
    • Bit adalah One atau Zero
    • Code adalah [Bit]
    • FreqMap adalah Map Char Int yang menyimpan jumlah kemunculan per karakter
    • CodeMap adalah Map Char Code yang menyimpan codeword per karakter
    • HTree adalah Leaf Weight Char atau Fork Weight HTree HTree
  • HTree dibuat dapat dibandingkan berdasarkan weight untuk menyederhanakan proses pengurutan dan penyisipan saat membangun tree
  • countFrequency menghitung jumlah kemunculan setiap karakter dalam string
  • buildTree mengubah FreqMap menjadi daftar leaf, mengurutkannya, lalu berulang kali menggabungkan dua node terkecil untuk membuat Huffman tree
  • buildCodes menelusuri tree sambil menambahkan One di kiri dan Zero di kanan untuk menghasilkan codeword setiap karakter
  • encode :: FreqMap -> String -> [Bit] membuat tree dan code map dari FreqMap, lalu mengganti setiap karakter input dengan codeword untuk membuat daftar bit

Pemrosesan bertahap dengan lazy evaluation

  • Transformasi inti dalam encoding adalah concatMap codeFor str
    • Secara konseptual, ini adalah proses mengubah [Char] menjadi [[Bit]] lalu meratakannya kembali menjadi [Bit]
    • Berkat lazy evaluation Haskell, ini tidak bekerja dengan cara meng-encode seluruh input terlebih dahulu lalu menggabungkannya
  • List-list kecil diproses dari kiri ke kanan dan diratakan ke list hasil yang besar
    • Tail dari list hasil tetap berupa thunk yang belum dievaluasi
    • Bagian berikutnya dihitung ketika nilai yang dibutuhkan diminta
  • Decoder juga menghasilkan hasil secara bertahap dengan cara yang sama
    • decode :: FreqMap -> [Bit] -> String bergerak ke kiri atau kanan pada tree sesuai bit
    • Ketika mencapai leaf, karakter dikeluarkan dan proses dimulai lagi dari root
    • Proses diulang sampai jumlah total karakter yang di-decode sama dengan weight Huffman tree
  • Decoder berhenti berdasarkan jumlah karakter, bukan akhir dari daftar bit input
    • Ini karena pada tahap serialisasi, bit padding ditambahkan di akhir untuk penyelarasan byte
  • Ketika mencapai leaf, fungsi go mengembalikan list yang head-nya sudah diketahui dan tail-nya berupa pemanggilan rekursif, sehingga hasil dapat dievaluasi sebelum seluruh rekursi selesai

Pemrosesan file biner dan serialisasi

  • Data biner dapat dilihat sebagai pengulangan salah satu dari 256 kemungkinan byte
  • Data.ByteString.Char8 memungkinkan ByteString diperlakukan dengan operasi Char, dan setiap Char dipotong menjadi 8 bit
    • Berkat sifat ini, coder untuk teks dapat diterapkan juga ke data biner tanpa banyak perubahan
  • File terkompresi diawali dengan FreqMap yang diperlukan untuk decoding, lalu diikuti deretan bit yang telah di-encode
  • serializeFreqMap mencatat tabel frekuensi dalam format berikut
    • Panjang map disimpan sebagai Word8, tetapi disimpan setelah dikurangi 1 untuk penyesuaian rentang representasi
    • Setiap entri menyimpan key sebagai Word8 dan nilai frekuensi sebagai integer 64-bit big-endian
  • serialize membuat ByteString dengan monad Put dari paket binary
    • Membaca bit satu per satu untuk mengisi satu byte
    • Ketika 8 bit terisi, mencatatnya dengan putWord8
    • Byte terakhir diberi padding Zero pada ruang yang tersisa

Deserialisasi dan strategi memori konstan

  • deserializeFreqMap membaca tabel frekuensi yang diserialisasi dengan Data.Binary.Get
    • Pertama membaca panjang, lalu menambahkan 1 untuk menghitung jumlah entri sebenarnya
    • Dari setiap entri, key Word8 dan nilai frekuensi 64-bit dibaca untuk memulihkan FreqMap
  • Sisa seluruh input tidak diproses dengan Get; bagian setelah offset diambil dari ByteString lalu diubah menjadi daftar bit
  • deserialize mengembalikan (FreqMap, [Bit]), dan [Bit] adalah lazy list yang tidak langsung dihitung seluruhnya
    • Meminta panjang list ini akan memaksa evaluasi seluruh list, jadi harus dihindari
  • Alasan tidak menggunakan Get untuk seluruh input adalah karena bind pada monad memaksa urutan
    • Strukturnya menjadi baru dapat mengembalikan list setelah seluruh input selesai diproses
  • Strategi memori konstan bekerja dengan hanya mengevaluasi bagian kecil berikutnya dari input setiap kali menulis bit output
    • Sebagian ByteString dievaluasi dan potongan file terkait dibaca
    • Output yang sudah diproses ditulis ke file
    • Potongan input dan daftar bit yang tidak lagi dirujuk dapat dikumpulkan oleh garbage collector
  • FreqMap memiliki maksimal 256 entri berdasarkan byte, sehingga tetap menjadi overhead berukuran konstan

CLI kompresi dan dekompresi file

  • compress membaca file input dua kali
    • Pass pertama membuat FreqMap
    • Pass kedua meng-encode data dengan FreqMap tersebut
  • Jika file hanya dibaca sekali dan referensi yang sama diberikan ke encode, setelah pembuatan tabel frekuensi selesai pun referensi ke seluruh file input harus dipertahankan, sehingga seluruh file harus berada di memori
  • Dengan membaca dua kali, memori yang sudah diproses dapat dibebaskan selama pembuatan tabel frekuensi maupun encoding
  • decompress membaca file terkompresi, mendapatkan FreqMap dan daftar bit dengan deserialize, lalu menyimpan hasil decode ke file
  • CLI menerima argumen berikut
    • compress FILE FILE
    • decompress FILE FILE
  • Karena hanya menggunakan paket yang disertakan dalam GHC, ini dapat dikompilasi tanpa cabal dengan ghc -O2 Main.hs -o main

Hasil eksekusi dan penggunaan memori

  • Dalam pengujian file teks War and Peace karya Tolstoy, hasil diff setelah kompresi dan dekompresi identik
    • Asli WarAndPeace.txt: 3,2M
    • File terkompresi: 1,9M
    • File hasil dekompresi: 3,2M
    • Ukurannya berkurang sekitar 40%
  • Kompresi dan dekompresi juga berjalan pada file biner ghcup yang lebih besar
    • Asli ghcup: 106M
    • File terkompresi: 84M
    • File hasil dekompresi: 106M
    • Waktu kompresi sekitar 15,173 detik, waktu dekompresi sekitar 14,555 detik
  • Berdasarkan +RTS -s, maximum resident set size selama pemrosesan ghcup berada di bawah 300KB
  • Kedua proses menggunakan memori kurang dari 10MB saat berjalan
  • Bagian yang memakan waktu dapat dilihat pada profil terpisah

Titik yang masih dapat ditingkatkan

  • Tujuan implementasi ini adalah utilitas kompresi yang sesederhana dan sejelas mungkin; untuk meningkatkan efisiensi, implementasi yang lebih kompleks diperlukan
  • Beberapa peningkatan yang memungkinkan adalah sebagai berikut
    • Multithreading: men-decode bagian-bagian file secara paralel, tetapi karena batas codeword pada posisi arbitrer tidak bisa diketahui, tambahkan tabel batas segmen dan ukuran decoding yang diharapkan di awal file terkompresi
    • Encoding satu pass: mulai dari tabel frekuensi awal dengan semua byte memiliki frekuensi 1, lalu setiap kali melihat byte, encode terlebih dahulu baru perbarui tabel frekuensi
    • Canonical Huffman codes: alih-alih menelusuri tree dalam O(log n) saat decoding, code dapat digunakan sebagai indeks vektor untuk menargetkan akses O(1); pembahasan terkait ada di Canonical Huffman code
    • Pembuatan code yang lebih cepat: pada encoding satu pass, pembuatan CodeMap harus dibuat jauh lebih cepat, dan ada cara yang lebih cepat untuk menghasilkan codeword tanpa membangun tree
  • Di masa depan, dengan menggunakan LZ77, metode kamus adaptif, gzip dapat diimplementasikan bersama kode Huffman

Bacaan terkait

1 komentar

 
GN⁺ 2024-07-06
Opini Hacker News

  • Untuk pekerjaan ini ada algoritma in-place berbasis array yang mengurangi alokasi tree dan penelusuran pointer.
    Saat mempelajari pendekatan berbasis tree di universitas, saya tidak tahu ada cara lain, dan saya penasaran apakah orang lain juga begitu.
    Cara tree memang intuitif dan membantu pemahaman, tetapi situasi ketika kompresi paling penting biasanya adalah saat datanya banyak dan kita ingin menjalankannya dengan cepat, jadi menangani ini dengan array in-place mungkin lebih masuk akal.
    In-Place Calculation of Minimum-Redundancy Codes, Moffat, Katajainen, 1995
    http://hjemmesider.diku.dk/~jyrki/Paper/WADS95.pdf

    • Secara umum, On the Implementation of Minimum Redundancy Prefix Codes oleh Moffat dan Turpin juga layak dijadikan rujukan.
      Charles Bloom sangat merekomendasikannya dan kemudian menambahkan penjelasan.
      https://cbloomrants.blogspot.com/2010/08/08-12-10-lost-huffm...
    • Karena algoritma ini dijelaskan dengan flowchart dalam standar JPEG ITU T.81 (1992), tampaknya pengetahuan tentang Huffman berbasis array sudah cukup dikenal bahkan pada era 80-an.
    • Hal ini disebutkan di bagian akhir tulisan dan dibiarkan sebagai latihan untuk pembaca.
    • Kalimat “saya penasaran apakah itu juga berlaku untuk beberapa dari kalian” terdengar seperti list comprehension.

  • Pernyataan bahwa “agar tidak ambigu, tidak boleh ada codeword yang menjadi prefiks codeword lain” secara ketat tidak tepat.
    Yang disebut uniquely decodable code tidak ambigu, dan merupakan superset dari prefix code.
    Contoh sederhana adalah kode yang merupakan kebalikan dari prefix code. Untuk contoh di tulisan itu, hasilnya menjadi a 1, b 00, c 10.
    Kode untuk a adalah prefiks dari kode c, tetapi jika rangkaian kode diproses dari arah terbalik, ia tetap bisa didekode tanpa ambigu. Akan menarik melihat uniquely decodable code yang bukan prefix code dan juga bukan kebalikannya.

    • Dengan mengomposisikan prefix code dan suffix code, kita bisa membuat kode seperti itu tanpa menjadi tidak efisien secara tidak perlu.
      Jika A 0, B 01, C 11, lalu a A 0, b BA 010, c BB 0101, d BC 0111, e C 11, maka menjadi {a=0,b=010,c=0101,d=0111,e=11}.
      Ini jelas uniquely decodable, karena kita bisa mendekode secara unik dari belakang seperti 0->A, lalu mendekode lagi secara unik dari depan seperti A->a.
      Dari sisi panjang, ini sama dengan prefix code optimal {a=0,b=110,c=1110,d=1111,e=10}, sehingga merupakan salah satu dari beberapa kode optimal untuk distribusi probabilitas yang sama.
      Pada saat yang sama, karena a=0 dan b=010, ini bukan prefix code maupun suffix code. Bahkan secara umum, decoding bertahap tidak mungkin dilakukan dari arah mana pun, dan untuk membedakan cee...ee? dengan bee...ee?, atau ?cc...cca dengan ?cc...ccb, bisa diperlukan lookahead tak hingga hanya untuk menentukan satu simbol.
      Saya tidak tahu apakah mengomposisikan prefix code yang optimal secara independen dan suffix code yang optimal secara independen selalu mempertahankan optimalitas, tetapi pada kasus-kasus paling sederhana yang terpikir, selain kode degeneratif 1:1, ini bekerja dengan baik.
    • Ini masalah yang lebih menarik daripada kelihatannya. Sebagai jawaban yang agak antagonis, contoh seperti a 101, b 1 bisa dibuat.
      Namun itu kode yang buruk, karena selalu lebih baik memakai a=1, b=0.
      Ketaksamaan Kraft memberi tahu himpunan panjang kode yang dapat dibuat uniquely decodable, dan Huffman coding bisa mencapai semua himpunan seperti itu. Jadi jika melakukan symbol coding, tidak ada alasan memakai kode non-prefiks kecuali beralih ke metode lain seperti ANS atau arithmetic coding.
      Namun saya tidak tahu apakah ada uniquely decodable code yang memiliki himpunan panjang sama dengan Huffman code optimal, tetapi bukan prefix code maupun kebalikannya, yaitu suffix code.
      Jika punya waktu, saya mungkin akan melihat https://en.wikipedia.org/wiki/Sardinas-Patterson_algorithm lalu mencari counterexample dengan brute force, atau mencoba menemukan pembuktiannya dari cara kerja algoritma tersebut.
    • Contoh yang aneh, tetapi bagaimana dengan a 1, b 101?
      Ini bukan prefix-free dan juga bukan suffix-free, tetapi setiap kali 0 muncul, itu berpadanan dengan kemunculan b.
      Tentu saja ini jelas tidak efisien, jadi pada akhirnya yang membuat penasaran adalah apakah ada kode optimal yang bukan prefix-free maupun suffix-free.
      Setelah mencari, https://blog.plover.com/CS/udcodes.html memberi contoh uniquely decodable code a 0011, b 011, c 11, d 1110.
      Satu-satunya relasi prefiks adalah c menjadi prefiks dari d, jadi ini “hampir” prefix-free. Jika pesan dimulai dengan 1, sepertinya cukup mencari 0 pertama lalu melihat apakah jumlah 1 sebelumnya ganjil atau genap, sehingga uniquely decodable-nya bisa dipahami.
      Namun pengetahuan saya tentang kriptografi sudah terlalu berkarat untuk mengingat cara menunjukkan distribusi probabilitas seperti apa yang membuat ini optimal.
    • Menarik, tetapi alasan biasanya tidak dipakai mungkin karena kita bisa harus membaca rangkaian bit yang sangat panjang sampai muncul bit yang menghilangkan ambiguitas.
      Misalnya untuk 100000000000000001, untuk tahu apakah kode pertama adalah a atau c, kita harus membaca semua sampai titik ketika deretan 0 berakhir.

  • Saya penasaran apakah ada materi di antara tutorial serupa yang menyusun program Haskell seperti tulisan ini, tetapi membahas fitur yang lebih lanjut seperti monad transformer atau lens.

    • Saya merekomendasikan buku Haskell in Depth. Monad transformer dibahas di bab 6, sedangkan lens di bab 3 dan 14.
      Buku ini juga membahas fitur lanjutan lain seperti Template Haskell dan concurrency, serta ada bab tentang menangani database SQL di Haskell.
    • https://github.com/turion/rhine-koans layak dilihat.
      Ini adalah tutorial untuk library FRP Rhine, dengan komentar dan test yang baik.

  • Kursus Pemrograman Fungsional berbasis Scala di Coursera juga punya tugas Huffman coding yang cukup mirip, lengkap dengan penilai otomatis, jadi cocok untuk yang ingin mencobanya sendiri
    https://www.coursera.org/learn/scala-functional-programming?...

  • Terakhir kali saya memakai kode Huffman adalah untuk macroprogram pada prosesor MICMAC, yaitu untuk mengeksekusi teks assembly dengan jumlah microcycle dan microinstruction seminimal mungkin
    Saya mulai dari histogram macroinstruction yang dieksekusi, dan seingat saya pertama-tama menulis interpreter dalam C untuk menghitung berapa kali tiap instruksi dijalankan
    Setelah itu saya membuat program microcode decoding bertahap yang mengimplementasikan semua operasi makro ISA yang diperlukan. Sepertinya ISA macroinstruction yang saya buat berorientasi bit, bukan byte
    Di dunia nyata mungkin akan lambat dan merepotkan, tetapi keunggulan kode Huffman adalah kedalaman prefix bisa disesuaikan menurut distribusi nilai, sehingga tidak perlu membuat kode yang berat sebelah hanya karena prefix 1 bit
    Selain itu, microprogram tersebut adalah model prosesor pipeline nonsuperscalar, jadi juga harus menangani prediksi cabang. Jika cabang salah diprediksi, siklus akan terbuang karena pipeline stall sementara cabang yang benar merambat ke depan

  • https://rosettacode.org/wiki/Huffman_coding

  • Sepertinya akan ada banyak programmer Haskell berkumpul, jadi ingin bertanya: seberapa cepat Haskell saat ini jika digunakan oleh programmer yang peduli optimisasi?
    Khususnya penasaran dengan performa pekerjaan yang mendapat manfaat dari komputasi numerik dan SIMD, seperti operasi matriks

    • Kecepatan Haskell bisa bersaing dengan bahasa sistem, tetapi perlu diingat bahwa keunggulan utamanya adalah kemudahan abstraksi
      Intinya adalah mudah merangkai berbagai bagian menjadi program yang konsisten dan tertata baik. Ini penting bukan hanya untuk loop yang ketat, tetapi juga untuk keseluruhan program
      Haskell punya FFI yang bagus, jadi bagian yang secara inheren membutuhkan optimisasi imperatif bisa diturunkan ke bahasa tanpa garbage collection. Jika bagian seperti itu dibungkus sebagai library dengan tipe yang baik, performa mentahnya bisa dimanfaatkan di mana pun dalam kode Haskell yang tipenya cocok
      Itulah yang kami lakukan saat membuat aplikasi Haskell berperforma tinggi di Meta. Kami menulis program Haskell yang indah, besar, dan cepat, tetapi memasukkan komponen C++ untuk beberapa bagian khusus. 99% waktu digunakan di sisi Haskell untuk merangkainya menjadi aplikasi yang lebih berguna
    • Untuk pekerjaan backend, web, dan CLI sehari-hari, performa Haskell memuaskan. Namun saat menulis kode yang berpusat pada performa, saya turun ke Rust
      Meski begitu, Haskell bukan termasuk lambat. Contohnya program kecil untuk menghitung jumlah bit 1 dalam sebuah file
      Jika dikompilasi dengan -msse4.2, ia memakai instruksi hardware popcount dengan benar dan memproses file input 1GB dalam 0m0,090s. Dengan pembulatan ke satuan MB, heap yang dipakai adalah 0
      Jika dikompilasi tanpa -msse4.2, waktunya 0m0,293s
      Saya belum mencoba komputasi matriks sendiri, tetapi sebagai titik awal mungkin akan melihat repa, accelerate, dan massiv
      https://hackage.haskell.org/package/repa
      https://hackage.haskell.org/package/accelerate
      https://hackage.haskell.org/package/massiv
    • Saya bertemu Sam Derbyshire di ZuriHac, dan mendengar bahwa semua pekerjaan arsitektur yang sulit untuk dukungan SIMD sudah selesai
      https://gitlab.haskell.org/ghc/ghc/-/issues/7741
      Ini mungkin masuk ke GHC 9.12. Namun targetnya hanya vektor 128-bit, dan kecuali ada kontribusi dari orang lain, tampaknya terutama akan berfokus pada operasi floating-point
      Patch-nya ada di sini
      https://gitlab.haskell.org/ghc/ghc/-/merge_requests/12860
    • Secara realistis, dalam bahasa apa pun termasuk C, kode yang dioptimalkan compiler tidak bisa secepat kode yang dioptimalkan manual dalam library seperti BLAS
      Pada tingkat tertentu, pilihan bahasa host tidak terlalu penting. Jika benar-benar serius soal kecepatan, komputasinya pada akhirnya akan diserahkan ke luar juga
      Ini juga alasan mengapa kode AI, yang kemungkinan termasuk salah satu pengguna sumber daya komputasi terbesar di dunia, boleh saja ditulis dalam Python kecuali library komputasi level rendahnya
      Jawaban langsungnya: compiler GHC sangat bagus. Kode level tinggi berjalan cukup baik, dan pada sebagian besar aplikasi realistis, bottleneck performa bukan soal operasi lebar tunggal vs SIMD, melainkan masalah arsitektur. “kedekatan asimtotik arsitektural” Haskell cukup menguntungkan
      Saya rasa GHC sudah memiliki, atau sedang menuju, dukungan SIMD, tetapi saya tidak akan menjadikannya fokus saat menilai performa
      Saya tidak akan menulis sendiri algoritma perkalian matriks di Haskell, tetapi kalau serius soal kecepatan, saya juga tidak akan menulisnya sendiri di Rust atau C
      Komputasi numerik sering dijadikan metrik performa, tetapi dalam praktiknya hampir tidak ada orang yang bottleneck-nya benar-benar di sana; dan kalau memang bottleneck-nya di sana, bahasa level tinggi apa yang dipakai tidak terlalu penting
    • Haskell benar-benar bersinar ketika ingin menulis kode deklaratif level tinggi
      Performa gaya seperti ini biasanya cukup untuk pekerjaan CLI atau backend web. Ada juga alat untuk menulis kode level rendah yang cukup cepat, tetapi agak kaku, jadi kalau hanya itu yang ingin dipakai, kemungkinan Haskell bukan alat terbaik
      Namun ketika ada beberapa hotspot terpusat yang perlu dioptimalkan, Haskell cukup bagus
      Tool profiling CPU-nya bagus, sehingga menemukan dan mengoptimalkan hotspot CPU relatif nyaman. Sebaliknya, melacak kebocoran memori aneh yang lebih mudah muncul karena lazy evaluation bisa sangat membuat frustrasi
      Jika melihat hasil benchmarks game, implementasi Haskell tercepat umumnya 2–5 kali lebih lambat daripada versi C tercepat, dan ditulis dengan gaya yang sangat imperatif
      https://benchmarksgame-team.pages.debian.net/benchmarksgame/...

  • Sepertinya ada typo pada tabel di bagian “Creating prefix-free codes”. D seharusnya 0010, bukan 0110

    • Karena itu saya sempat lama memikirkan bagaimana 0110 bisa tidak ambigu, tetapi sekarang paham

  • Penasaran apa yang ada di kaus perempuan pada gambar
    Tautan langsung: https://lazamar.github.io/images/data-compressor.svg