|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Oleg Khovayko [SPAM trap - don't re 2:5020/400 02 Apr 2003 04:40:59
To : Dmitry Lipovoi
Subject : Re: максимальная "длина символа" в коде Хаффмана
--------------------------------------------------------------------------------
> С кодами Хаффмана, надеюсь, все знакомы? Внимание, вопрос: какова
> максимальная глубина дерева построенного по этому алгоритму (естественно, коды
> символов лежат в интервале [0; 255]).
Естественно, что 255!
Это возникает, если: F[N] >= Sum(F[0..N-1])
При этом дерево вырождается в линейный список.
Hу вот тебе ряд частот:
1 1 2 4 8 16 32 64 128 256 512 1024
Посмотри для него глубину дерева.
> Я с этой задачей уже два дня маюсь --
> больше 8 не получалось, так что, в принципе, достаточно будет входных
> параметров (частот), при которых глубина дерева будет > 8.
Дя чего достаточно?
> ... В действительности все не так, как на самом деле.
Ага
--
#include <best/regards>
Oleg Khovayko http://olegh.spedia.net
PS/ATTN: Reply to reverted address net.comcast@olegh
--- ifmail v.2.15dev5
* Origin: http://www.ftc.gov/opa/2001/04/spam.htm (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: максимальная "длина символа" в коде Хаффмана