Bagaimana untuk Menyimpan Pokok Huffman dengan Cekap untuk Pemampatan Data?

Storan Pokok Huffman yang Cekap untuk Pemampatan Data

Pengekodan Huffman mengoptimumkan data dengan memberikan kod yang lebih pendek kepada aksara yang lebih kerap. Untuk menyimpan pokok Huffman yang dibina, pelbagai pendekatan wujud.

Kaedah untuk Meminimumkan Saiz Pokok

Jika data input kecil, pertukaran wujud antara kecekapan dan overhed . Untuk set data yang lebih besar, pertimbangkan kaedah berikut:

• Jangan simpan frekuensi.

• Untuk setiap nod:

  • Jika ia adalah nod daun , keluarkan 1 bit diikuti dengan aksara/bait (N bit).
  • Jika bukan nod daun, keluarkan 0 bit dan kodkan kedua-dua nod anak secara rekursif.

Prosedur Penyahkodan:

• Baca sedikit.
• Jika 1, baca aksara/bait N-bit dan buat nod daun.
• Jika 0, baca nod anak kiri dan kanan secara rekursif.

Contoh

Pertimbangkan input "AAAABCCCCCCDDEEEEE."

• Pokok:

              20
      ----------
      |        8
      |     -------
      12     |     3
  -----   |   -----
  A   C   E   B   D
  6   6   5   1   2

• Laluan:

  • A: 00
  • B: 110
  • C: 01
  • D: 111
  • E: 10

• Output Dikodkan:

  • Pokok: 001A1C01E01B1D (49 bit)
  • Data: 0000000000001100101010101011111111101010101 (43 bit)
  • Jumlah
  Jumlah
🎜>

Perbandingan

Tanpa pengekodan Huffman:

• 20 aksara * 8 bit = 160 bit (20 bait)

Dengan pengekodan Huffman:

• 12 bait overhed

Pertimbangan untuk Data Kecil

Untuk data input yang lebih kecil, pendekatan yang menyimpan frekuensi mungkin lebih cekap ruang. Kira:

• Saiz Pokok = 10 * Bilangan Aksara - 1
• Saiz Dikodkan = Jumlah(Kekerapan setiap aksara * Panjang laluan ke aksara)

Pendekatan ini meminimumkan kebarangkalian ruang terbuang.

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