Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Последние темы форума

Показать новые сообщения »

Почтовая рассылка

Подписчиков: 11656
Последний выпуск: 19.06.2015

Моделирование при сжатии текстовых данных - Подсчет.

Во время конструирования статистических моделей необходимо производить оценку вероятностей. Обычно это осуществляется подсчетом количества появлений символа в образце, т.е. нахождением относительной частоты символа, которая используется для оценки его вероятности. Храненение счетчиков требует значительных объемов памяти из пространства, выделенного модели, однако, ее можно сократить.

Если n есть максимальное количество наблюдений, то счетчикам требуется log n битов памяти. Однако, можно применять меньшие регистры, если при угрозе переполнения делить значения счетчиков пополам. Понижение точности частот наносит небольшой ущерб, поскольку возникновение небольших ошибок в их предсказании почти не оказывает влияния на среднюю длину кода. На самом деле, масштабирование счетчиков часто улучшает сжатие, поскольку дает более старым счетчикам меньший вес, чем текущим, а последние статистики часто являются лучшей основой для предсказания следующего символа, чем более ранние. Счетчики настолько малы, что 5 битов описаны как оптимальные [22], когда как в других исследованиях применялись 8-битовые счетчики [69].

Для двоичного алфавита необходимо хранить только два счетчика. Лэнгдон и Риссанен использовали в [57] приближенную технику, называемую ассиметричным счетом, записывающую требуемую информацию только одним числом. Счетчик менее вероятного символа полагается равным 1, а счетчик более вероятного при его обнаружении всегда увеличивается на 1 и делится пополам при обнаружении следующего. Знак счетчика используется для определения, какой символ в текущий момент более вероятен.

Моррис в [70] предложил технику, при которой счетчики, достигшие значения n, помещаются в log(log(n)) битовый регистр. Принцип состоит в хранении логарифма счетчика и увеличении счетчика с вероятностью 2^-c, где c есть текущее значение регистра. Этот вероятностный подход гарантирует увеличение значения счетчика так часто, как следует, т.е. в среднем. Для анализа этой техники смотри Флажолета [29].

Назад | Оглавление | Вперед

Оставить комментарий

Комментарий:
можно использовать BB-коды
Максимальная длина комментария - 4000 символов.
 
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог