Pohon Huffman dan kedalaman maksimum

Mengetahui frekuensi masing-masing simbol, apakah mungkin untuk menentukan ketinggian maksimum pohon tanpa menerapkan algoritma Huffman? Apakah ada formula yang memberikan tinggi pohon ini?

trees coding-theory user7060
sumber

Cobalah bermain-main dengan beberapa contoh, dan lihat apakah Anda dapat menemukan kriteria yang berguna. Itulah yang akan saya lakukan jika saya mencoba menjawab pertanyaan Anda, tetapi mungkin lebih baik bagi Anda untuk melakukannya sendiri ...

Yuval Filmus

Ya, saya sudah mencoba dengan banyak contoh, tapi saya sedang mencari ekspresi litteral, misalnya fungsi asimptotik, jumlah simbol ...

user7060

Dalam hal jumlah simbol, Anda tidak dapat melakukan apa pun yang lebih baik dari

n - 1

$n-1$ di satu sisi, dan

⌈ \log_{2} n ⌉

$\lceil \log_2 n \rceil$ di sisi lain.

Yuval Filmus

Maaf. Saya sedang memikirkan jumlah simbol dan frekuensinya. Misalnya, mungkin dimungkinkan untuk memberikan kedalaman maksimal dengan hanya melihat frekuensi terendah di antara semua simbol?

adalah ikatan yang terikat pada kedalaman, saya tertarik pada ikatan yang ketat.

n - 1

$n-1$

user7060

dan lihat apakah ini terkait dengan kedalaman. Anda juga dapat mencoba membuat rekursi yang sesuai dengan algoritma yang sebenarnya, dan melihat apakah itu memberi Anda sesuatu.

max - \log_{2} p_{i}

$\max -\log_2 p_i$

Yuval Filmus

Jawaban:

Pengodean Huffman (asimtotik) berada dalam satu bit dari entropi urutan. Ini berarti bahwa jika Anda menghitung entropi frekuensi simbol Anda, Anda akan (asimtotik) dalam satu bit dari panjang rata-rata (yaitu tinggi) dari kode Anda. Anda dapat menggunakan rata-rata ini untuk mengikat panjang terpanjang (rata-rata), atau Anda dapat menggunakan metode kombinatorial untuk mendapatkan batas determinitis.

Ari Trachtenberg
sumber

Kasus patologis akan terjadi ketika frekuensi simbol yang diurutkan menyerupai urutan Fibonacci. N: = # simbol. untuk N> 2, ketinggian maksimal maks: N-1. untuk N == 1 atau 2: 1

Bill Liu
sumber

Ini bukan pertanyaannya.

Tom van der Zanden

Memang. Pertanyaannya menanyakan kasus apa saja ketika Anda berbicara tentang kasus terburuk.

Raphael