Энтропия и количество информации. Комбинаторная, вероятностная и алгоритмическая оценка количества информации. Моделирование и кодирование. Некоторые алгоритмы сжатия данных. Алгоритм арифметического кодирования. Приращаемая передача и получение.
Аннотация к работе
Общие сведения Энтропия и количество информации Комбинаторная, вероятностная и алгоритмическая оценка количества информации Моделирование и кодирование Некоторые алгоритмы сжатия данных Алгоритм LZ77 Алгоритм LZ78-LZW84 Алгоритм PPM BWT - преобразование и компрессор Кодирование Хаффмана Арифметическое кодирование Алгоритм арифметического кодирования Реализация алгоритма арифметического кодирования Реализация модели Доказательство правильности декодирования Приращаемая передача и получение Отрицательное переполнение Переполнение и завершение Адаптивная модель для арифметического кодирования Эффективность сжатия Заключение Список литературы Приложение 1. Интерфейс программы Введение Основоположником науки о сжатии информации принято считать Клода Шеннона. На основе ряда опытов он пришел к выводу, что количество информации в английском тексте колеблется в пределах 0.6 - 1.3 бита на символ. Настоящим прорывом было изобретение Лемпелем и Зивом в 1977 г. словарных алгоритмов. Дело в том, что алгоритм сложен и требует больших ресурсов, в первую очередь больших объемов памяти, что было серьезной проблемой в то время. Во-первых, широко используемые методы сжатия, как правило, устарели и не обеспечивают достаточной степени сжатия. При реализации алгоритма арифметического кодирования использовался язык C# и визуальная среда программирования Microsoft Visual Studio 2005. Согласно этому подходу, если переменная х может принадлежать к множеству из N элементов, то энтропия переменного H(x) = log2 N.