АЛГОРИТМЫ СЖАТИЯ

ТеорияПрактикаКонтроль знанийДемонстрация
Содержание
Введение
Классификация
-Критерии оценки
-Надёжность и сложность
-Методы сжатия
-Методы кодирования
Сжатие без потерь
-RLE
-Семейство LZ
-LZ77
-LZSS
-LZ78
-LZW
-LZM
-LZB
-LZH
-LZC
-LZT
-LZMV
-LZJ
-LZFG
-Унарное кодирование
-Метод Хаффмана
-Арифметическое кодирование
-Вероятностное сжатие
-BWT
Сжатие с потерями
-Звук и видео
-Изображения
Алгоритмы сжатия с потерями
-JPEG
-JPEG2000
-Wavelet
-Фрактальный
Предметный указатель

Обзор алгоритмов сжатия без потерь

Вероятностное сжатие

Чрезвычайно интересный и самый быстрый из известных (наряду с RLE) методов сжатия информации, дающий, к тому же неплохие результаты. Вероятностное сжатие во многом напоминает гадание на кофейной гуще или предсказание погоды, только более эффективно.

Работает алгоритм следующим образом: имеется достаточно большая, динамически обновляющаяся таблица предсказаний, в которой для каждой возможной пары последовательных входных символов указывается предсказываемый следующий (третий) символ. Если символ предсказан правильно – генерируется код в виде однобитного префикса, равного 1. Если же мы не угадали – выдается код в виде префикса, равного 0 и неугаданного символа. При этом неугаданный символ замещает в таблице бывший там до этого, обеспечивая постоянное обновление статистической информации. Алгоритм является адаптивным и поэтому он однопроходный и не требует хранения таблицы совместно со сжатым текстом.

Декомпрессор работает по аналогичной программе, поддерживая и обновляя таблицу синхронно с компрессором. Если поступил префикс 1, очередная выходная буква извлекается из таблицы по индексу, полученному из двух предыдущих букв, иначе – просто копируется код из входного потока в выходной. Для небольшого повышения степени сжатия рекомендуется инициализировать таблицу перед началом работы какими-нибудь часто встречающимися буквосочетаниями.


НазадК cодержаниюВперёд
2006 All Rights Reserved