Mengapa pengkodean Huffman menghilangkan entropi yang tidak dimiliki Lempel-Ziv?

Algoritma DEFLATE populer menggunakan Huffman coding di atas Lempel-Ziv.

Secara umum, jika kita memiliki sumber data acak (= 1 bit entropi / bit), tidak ada pengkodean, termasuk Huffman, yang cenderung memampatkannya secara rata-rata. Jika Lempel-Ziv "sempurna" (yang mendekati untuk sebagian besar kelas sumber, karena panjangnya hingga tak terbatas), posting pengkodean dengan Huffman tidak akan membantu. Tentu saja, Lempel-Ziv tidak sempurna, setidaknya dengan panjang yang terbatas, dan masih ada beberapa redundansi yang tersisa.

Ini adalah redundansi yang tersisa dimana pengkodean Huffman menghilangkan sebagian dan dengan demikian meningkatkan kompresi.

Pertanyaan saya adalah: Mengapa sisa redudansi ini berhasil dihilangkan dengan pengkodean Huffman dan bukan LZ? Apa sifat Huffman versus LZ yang membuat ini terjadi? Apakah hanya menjalankan LZ lagi (yaitu, pengkodean data terkompresi LZ dengan LZ kedua kalinya) mencapai sesuatu yang serupa? Jika tidak, mengapa tidak? Demikian juga, akan lebih dulu mengompresi dengan Huffman dan kemudian setelah itu dengan LZ bekerja, dan jika tidak, mengapa

UPDATE: Jelas bahwa bahkan setelah LZ, beberapa redundansi akan tetap ada. Beberapa orang telah menyatakan hal itu. Yang tidak jelas adalah: Mengapa sisa redundansi lebih baik ditangani oleh Huffman daripada LZ? Apa yang unik tentang itu berbeda dengan redundansi sumber asli, di mana LZ bekerja lebih baik daripada Huffman?

Ini awalnya komentar, tapi terlalu lama.

Jika Anda melihat DEFLATE, apa yang sedang dikompresi oleh Huffman adalah output dari LZ77; LZ77 bekerja dengan (saat ini membutuhkan bit lebih sedikit dari data mentah) mengirim pointer lebih awal ke string yang dikompresi, dan panjang kecocokan yang memberitahu berapa banyak simbol yang harus diambil setelah pointer. Teori ini menunjukkan bahwa, bahkan tanpa kompresi tambahan, teknik ini pada akhirnya menyatu dengan entropi sumber. Namun, dalam kompresi data, setiap kali Anda memiliki distribusi yang tidak sepenuhnya acak, Anda mungkin perlu mengompresnya. Tidak ada alasan untuk percaya bahwa output LZ77 - pointer dan panjang pertandingan - sepenuhnya acak. Mereka harus bertemu untuk menyelesaikan keacakan dalam batas asimptotik, karena LZ77 optimal asimptotik, tetapi dalam praktiknya Anda hanya menggunakan kamus terbatas, jadi mereka mungkin tinggal cukup jauh dari benar-benar acak sehingga Anda menang dengan melakukan kompresi lebih lanjut pada mereka. Secara alami, Anda menggunakan satu kode Huffman untuk pointer dan lainnya untuk panjang pertandingan, karena kedua proses ini memiliki statistik yang berbeda.

Mengapa menggunakan Huffman daripada LZ untuk putaran kedua kompresi? Keuntungan besar yang dimiliki LZ dibandingkan Huffman adalah dalam merawat ketergantungan antar simbol. Dalam bahasa Inggris, jika satu huruf adalah 'q', yang berikutnya sangat mungkin menjadi 'u', dan seterusnya. Jika simbol adalah peristiwa independen, maka Huffman lebih sederhana dan berfungsi dengan baik atau lebih baik untuk string pendek. Untuk keluaran LZ77, intuisi saya adalah bahwa simbol-simbolnya harus cukup independen, jadi Huffman harus bekerja lebih baik.

Kompresi data sebenarnya tentang dua hal: pemodelan dan pengodean. Algoritma dari keluarga LZ memodelkan teks sebagai gabungan dari pengulangan yang tepat, yang secara asimtotik optimal untuk banyak sumber acak dan cukup baik untuk banyak teks nyata. Namun untuk beberapa input, model ini bisa sangat buruk. Misalnya, Anda tidak dapat menggunakan LZ untuk mengompres array suffix secara langsung, meskipun array suffix sama kompresinya dengan teks aslinya.

$(p, \ell, c)$$p$$\ell$$c$

$\log n$$n$

Jadi singkatnya, Huffman mengalahkan LZ dalam mengompresi tupel, karena modelnya (distribusi tetap vs pengulangan yang tepat) lebih cocok untuk data.

Saya percaya jawabannya terletak pada ukuran kamus pencarian.

Data memiliki sense of locality (artinya, jika sepotong data telah digunakan, kemungkinan akan segera digunakan kembali), dan algoritma LZ mengambil keuntungan dari hal ini dalam pembuatan kamus pencarian. Ini menghasilkan sebuah trie dengan jumlah node yang mungkin terbatas, untuk menjaga pencarian tetap cepat . Ketika menyentuh batas ukuran, itu membuat trie lain, "lupa" tentang yang sebelumnya. Jadi itu harus membangun lagi tabel pencarian untuk karakter yang lebih sederhana, tetapi jika beberapa kata tidak digunakan lagi, mereka tidak disimpan dalam memori lagi, sehingga pengkodean yang lebih kecil dapat digunakan.

Oleh karena itu, output LZ dapat dikurangi lebih jauh dengan pengkodean Huffman, untuk redundansi dalam pembuatan percobaan pencarian ini dapat dideteksi dengan analisis statistik.

Mungkin saya keluar jalur di sini, tetapi pengkodean Huffman melihat seluruh input untuk membangun tabel pengodeannya (pohon), sedangkan Lempel-Ziv mengkodekan saat berjalan. Ini merupakan keuntungan dan kerugian bagi Huffman. Ketidaksukaan itu menyimpang, yaitu bahwa kita harus melihat seluruh masukan sebelum kita mulai. Keuntungannya adalah bahwa Huffman akan memperhitungkan statistik akun yang terjadi di mana saja di input, sedangkan Lempel-Ziv harus membangunnya secara progresif. Atau dengan kata lain, Lempel-Ziv memiliki "arah" yang tidak dimiliki Huffman.

Tetapi semua ini hanyalah cara naif saya untuk membayangkan bagaimana keadaannya. Kita akan membutuhkan bukti nyata di sini untuk melihat bagaimana sebenarnya Huffman mengungguli Lempel-Ziv.

Jawaban singkatnya adalah, LZ adalah algoritma "universal" karena tidak perlu mengetahui distribusi sumber yang tepat (hanya perlu asumsi bahwa sumbernya diam dan ergodik). Tapi Huffman tidak; perlu mengetahui distribusi yang tepat dari mana sumber sampel (untuk membuat pohon Huffman). Informasi tambahan ini membuat Huffman mendapatkan jaminan kompresi yang ketat. Namun untuk algoritma kompresi file praktis Huffman mungkin kurang menguntungkan karena pertama-tama perlu mengumpulkan statistik empiris file dan kemudian melakukan kompresi yang sebenarnya di babak kedua, sementara LZ dapat diimplementasikan secara online.

Rincian lebih lanjut dapat ditemukan dalam teks teori informasi standar, misalnya, Elemen Teori Informasi oleh Cover dan Thomas.