Bagaimana untuk Menyimpan Pokok Huffman dengan Cekap untuk Pengekodan Bertambah?

Penyimpanan Pokok Huffman yang Cekap

Apabila melaksanakan pengekodan/penyahkodan Huffman, adalah penting untuk mencari cara yang cekap untuk menyimpan pokok Huffman untuk meminimumkan saiz fail output.

Dua Senario

Terdapat dua senario yang perlu dipertimbangkan:

• Storan Pokok Tunggal : Apabila keseluruhan fail diproses sekaligus, hanya satu pokok perlu disimpan.
• Penyimpanan Pokok Bertambah: Apabila memproses data besar dalam ketulan, pokok baharu perlu disimpan untuk setiap ketul. Dalam kes ini, penjimatan ruang adalah penting.

Cadangan Penyelesaian

Untuk penyimpanan pokok tambahan, pendekatan berasaskan bit disyorkan:

1. Nod Daun: Output 1 bit aksara/bait N-bit.
2. Nod Bukan Daun: Output 0 bit, kemudian kodkan kedua-dua nod anak secara rekursif .

Penyahkodan

Penyahkodan dilakukan seperti berikut:

1. Baca 1 bit. Jika 1, baca N bit dan kembalikan nod baharu tanpa anak.
2. Jika 0, nyahkod nod anak kiri dan kanan dan kembalikan nod baharu tanpa nilai.

Kelebihan

• Saiz pokok boleh dikira lebih awal.
• Ia menghilangkan keperluan untuk menyimpan frekuensi, yang tidak penting untuk penyahkodan.
• Ia membolehkan pengekodan dan penyahkodan yang cekap.

Penilaian

Untuk contoh konkrit "AAABBBCCCDE," output yang terhasil menggunakan pendekatan ini ialah:

001A1B001B1C1D01E = 59 bits (Tree)
000110010111 = 18 bits (Data)
Total: 77 bits = 10 bytes

Walaupun cekap, adalah penting untuk ambil perhatian bahawa untuk data yang sangat kecil, overhed untuk menyimpan pokok itu mungkin melebihi sebarang penjimatan.

Atas ialah kandungan terperinci Bagaimana untuk Menyimpan Pokok Huffman dengan Cekap untuk Pengekodan Bertambah?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!