Автор: Maxim Smirnov, <ms@compression.ru>
SPb, 01 августа 2003 года в 10:26:23
В ответ на : Re: Задачка по кодированию Хаффмана. от Олег
в 30 июля 2003 года в 17:00:32:
> > > Условия следующие: известен кодируемый алфавит,
> > > и длины кодовых слов для каждого символа (кодовые
> > > слова получены по алгоритму Хаффмана). Вопрос:
> > > можно ли как-нибудь оценить вероятности символов
> > > алфавита?> > Оценить -- да, лобовое решение.
> > Узнать -- нет.
> > оценка p = 1/(2^(длина слова))
> > В качестве домашнего задания :-)
> > предлагается определить
> > верхнюю границу ошибки. > Спасибо. не за что :-) > Это самая "тонкая" оценка? Нет, были поточнее, учитывающие, как
минимум, мощность алфавита и уровень.
Но, насколько помню, для заданной
конфигурации и заданной длины надежных
оценок мне не попадалось. Если
скорость не важна, и аналитическая
оценка как таковая не нужна, то,
наверное, лучше в лоб провести
оптимизацию p с учетом ограничений,
налагаемых особенностями дерева.
> В принципе, я встречал оценку сверху
> вероятностей, получается, ошибка имеет
> тот же порядок по длине кодового слова
> О(1/2^(длина слова)). Хотелось бы
> получить что-нибудь поточнее...
С ходу сказать не могу, давно этим
не занимался. Можно попробовать
поискать, отталкиваясь от обзорной
статьи Абрахамс и статьи Де Сантиса
(есть на сайте). И мне кажется,
что оценки эти я видел именно в статьях
Де Сантиса. > Тогда другой вопрос: возможно ли только
> по сжатому файлу определить параметры
> кода Хаффмана (мощность алфавита, сами
> кодовые слова)? Статистика сжатого файла
> все-таки отличается от идеальной
> равновероятной схемы, и интуиция
> подсказывает, что по характеру отличия
> можно восстановить используемое дерево
> Хаффмана (по крайней мере попытаться :). Дохлый номер, имхо. Особенности
определятся несоответствием модели и
источника. > Предположим, статистику исходного файла
> мы знаем.
|