Re: Задачка по кодированию Хаффмана.

Сайт о сжатии >> Форум #Компрессор# >> [Ответить] [Ответы]

Автор: Олег,
30 июля 2003 года в 17:00:32

В ответ на : Re: Задачка по кодированию Хаффмана. от Maxim Smirnov в 28 июля 2003 года в 09:33:58:

> > Всем привет!

> > Условия следующие: известен кодируемый алфавит,
> > и длины кодовых слов для каждого символа (кодовые
> > слова получены по алгоритму Хаффмана). Вопрос:
> > можно ли как-нибудь оценить вероятности символов
> > алфавита?

> Оценить -- да, лобовое решение.
> Узнать -- нет.
> оценка p = 1/(2^(длина слова))
> В качестве домашнего задания :-)
> предлагается определить
> верхнюю границу ошибки.

Спасибо. Это самая "тонкая" оценка?
В принципе, я встречал оценку сверху
вероятностей, получается, ошибка имеет
тот же порядок по длине кодового слова
О(1/2^(длина слова)). Хотелось бы
получить что-нибудь поточнее...

Тогда другой вопрос: возможно ли только
по сжатому файлу определить параметры
кода Хаффмана (мощность алфавита, сами
кодовые слова)? Статистика сжатого файла
все-таки отличается от идеальной
равновероятной схемы, и интуиция
подсказывает, что по характеру отличия
можно восстановить используемое дерево
Хаффмана (по крайней мере попытаться :).
Предположим, статистику исходного файла
мы знаем.


Ответы:



Ответить на это сообщение

Тема:

Имя (желательно полное):

E-Mail:

URL:

Город:

Страна:

Вежливый и подробный комментарий:
(Форматируйте его, пожалуйста, как почту - короткими строками
Еnter в конце строки, пустая строка между параграфами).

Пожалуйста, заполните все поля.
И не нажимайте по два раза на кнопку! Дождитесь ответа сервера.