Алгоритмы сжатия данных
Курсовая работа, 27 Декабря 2011, автор: пользователь скрыл имя
Описание работы
Основоположником науки о сжатии информации принято считать Клода Шеннона. Его теорема об оптимальном кодировании показывает, к чему нужно стремиться при кодировании информации и на сколько та или иная информация при этом сожмется. Кроме того, им были проведены опыты по эмпирической оценке избыточности английского текста. Он предлагал людям угадывать следующую букву и оценивал вероятность правильного угадывания. На основе ряда опытов он пришел к выводу, что количество информации в английском тексте колеблется в пределах 0.6 — 1.3 бита на символ.
Содержание работы
Введение
Общие сведения
Энтропия и количество информации
Комбинаторная, вероятностная и алгоритмическая оценка количества информации
Моделирование и кодирование
Некоторые алгоритмы сжатия данных
Алгоритм LZ77
Алгоритм LZ78-LZW84
Алгоритм PPM
BWT - преобразование и компрессор
Кодирование Хаффмана
Арифметическое кодирование
Алгоритм арифметического кодирования
Реализация алгоритма арифметического кодирования
Реализация модели
Доказательство правильности декодирования
Приращаемая передача и получение
Отрицательное переполнение
Переполнение и завершение
Адаптивная модель для арифметического кодирования
Эффективность сжатия
Заключение
Список литературы