ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Oleg Khovayko [SPAM trap - don't re  2:5020/400     20 Apr 2003  09:47:37
 To : S.A. Samokhodkin
 Subject : Re: estimate Huffman compression rate
 -------------------------------------------------------------------------------- 
 

 S.A. Samokhodkin wrote:
 
 > I'm stuck.
 > Как теоретически оценить размер файла {x_i}, сжатого по Хаффмену,
 > если для него известно распределение P(x) ?
 
 Кроме распределениявероятностей, неплохо бы знать еще и размер
 входного файла. Если это известно, то ответ таков:
 
 Hаа основании P(x) надо построить само дерево Хаффмана,
 а потом получить массив длин всех возможных символов L(x), ибо
 длина символа есть не что иное как число шагов от корня дерева
 до текущей терминальной ноды.
 
 Hу а далее - совсем просто:
 
 Size_out = Size_in * sum( P(x) * L(x) )
                     для всех x
 
 -- 
 #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)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор