ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Oleg Khovayko [SPAM trap - don't re  2:5020/400     21 Apr 2003  05:08:44
 To : S.A. Samokhodkin
 Subject : Re: estimate Huffman compression rate
 -------------------------------------------------------------------------------- 
 

 S.A. Samokhodkin wrote:
 
 > Valentin Davydov пишет:
 >>
 >>
 >>Если x_i - независимые случайные величины, то сосчитай по определению
 >>(через логарифм вероятности) количество информации в этом файле. Вот
 >>столько бит и будет в сжатом файле.
 
 Этот способ хорош для оценки коэффициента сжатия арифметического кодера.
 Для Хаффмана же этот способ дает ошибку в ситу того, что для 
 представления каждого символа используется целое число бит, и 
 избыточность подавляется не полностью. Полное подавление избыточности
 (и адекватность предложеной формулы) для кодера Хаффмана возможны только
 в том случае, когда вероятности символов есть степени двойки. Во всех 
 остальных случаях происходит огрубление, "потеря точности", то есть
 и после хаффмановского кодирования файл содержит избыточность.
 
 Пример: Допустим, сообщение состоит из 999 букв "А" и одной буквы "Б".
 При этом хаффмановский деревостроитель назначит на букву А битовый 
 нолик, а на Б - единичку (или наоборот). Естественно, после кодирования
 таким кодером наш выходной файл будет содержать 1000 битов.
 Причем это будет блок нулей с единственной единичкой.
 Понятно, что такое кодирование не будет особо эффективным...
 
 Так что такие вот дела -- код Хаффмана - действительно оптимальный
 префиксный код, но после кодирования им все равно избыточность остается.
 
 > 
 > Я уже нашел статью, где говорится что на данный момент аналитическое 
 > выражение для субжа неизвестно. Там, где это нужно, действительно, 
 > аппроксимируют именно шенноновской формулой.
 
 Вот-во! Чтобы формула работала всегда, пользуйтесь арифметическим 
 кодером. Тогда и формула будет, и жаться будет получше ;))
 -- 
 #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)
 
 

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