Кодирование по методу Хаффмана
Краткое сожержание материала:
Размещено на
Размещено на
СОДЕРЖАНИЕ
ВВЕДЕНИЕ
РАЗДЕЛ 1 ОБЗОР СУЩЕСТВУЮЩИХ ПРОГРАММ СЖАТИЯ ДАННЫХ БЕЗ ПОТЕРЬ
1.1 Основа всех методов сжатия без потерь
1.2 Методы сжатия
1.2.1 Алгоритмы группы KWE
1.2.2 Lossless JPEG
1.2.3Кодирование по методу Хаффмана
РАЗДЕЛ 2 РАЗРАБОТКА ПРОГРАММЫ
2.1 Обзор составляющих компонентов
2.2 Разработка кода программы
ВЫВОДЫ
СПИСОК ИСПОЛЬЗОВАНОЙ ЛИТЕРАТУРЫ
ПРИЛОЖЕНИЯ
ВВЕДЕНИЕ
Архиватор -- это программный продукт, позволяющий объединить несколько файлов в один архив, а также позволяющий изменять путем сжатия размер архива. Создание архива происходит путём сжатия данных.
Сжатие -- это процесс перекодирования информации, в результате которого уменьшается объем файла. Сжатие бывает без потерь («lossless compression») и с потерями («lossy compression»). В случае сжатия данных без потерь, восстановление файла из архива происходит без изменения качества первоначального файла, во втором -- с небольшими потерями качества. Самым простым видом сжатия без потерь является метод под названием «running», подсчитывающий количество последовательных, «идущих друг за другом» повторов. Но этот метод уже недостаточен в случае наличия повторов, встречающихся в разных местах текста.
Развитие программ - архиваторов позволило добиться не только сжатия без потерь, но также возможности создания многотомных архивов и архивов в различных форматах. Архивы бывают сложной структуры, то есть многотомными. Кроме того, они бывают самораспаковывающимися, то есть процесс извлечения файла в данном случае происходит автоматически. Самораспаковывающиеся архивы имеют, как правило, расширение.exe и называются SFX-архивами (от слова «self-extracting»). Архивы также бывают «непрерывными» («solid»). Непрерывный архив -- это архив в формате RAR, упакованный таким образом, что все его файлы представляют непрерывный поток информации. Непрерывная архивация применяется только для формата RAR, для ZIP она недоступна. Плюсом непрерывной архивации является увеличение такого параметра компрессии как степень сжатия, минусом является увеличение параметра скорости расжатия, то есть непрерывный архив будет распаковываться гораздо медленнее. Кроме того, процессы добавления в исходный архив файла или наоборот удаления имеющегося файла будут также происходить медленнее.
Наиболее распространенные программы: WinRAR, WinZIP, 7-ZIP.
WinRAR - данный формат сжатия был разработан нашим соотечественником Евгением Рошалом, соответственно название формата является аббревиатурой, включающей первую букву фамилии разработчика и первые две буквы термина архиватор. Формат RAR имеет большую историю: он изначально разрабатывался под DOS, а затем и для других операционных систем, включая позже Microsoft Windows. Так появилась программа WinRAR -- функциональный, многоформатный архиватор.
WinZIP. Архиватор WinZIP был создан в 1990 году для платформы Windows компанией Nico Mak Computing, которая позже стала называться WinZip Computing. Данная программа-архиватор работает в основном по алгоритму сжатия PKZIP.
7-ZIP. Архиватор WinZIP был создан в 1990 году для платформы Windows компанией Nico Mak Computing, которая позже стала называться WinZip Computing. Данная программа-архиватор работает в основном по алгоритму сжатия PKZIP.
Сегодня пользователь может найти большое количество предлагаемых платных и условно бесплатных архиваторов. Наряду с ними существует немало бесплатных аналогов, которые менее известны, хотя зачастую даже более функциональны. Рассмотрим наиболее распространенные программы.
В работе необходимо провести анализ нескольких существующих программ сжатия данных без потерь. Подробно рассмотреть и реализовать алгоритм Хаффмена. Создать программу-архиватор, работающую на основе алгоритма Хаффмена.
сжатие алгоритм хаффман архиватор
РАЗДЕЛ 1 ОБЗОР СУЩЕСТВУЮЩИХ ПРОГРАММ СЖАТИЯ ДАННЫХ БЕЗ ПОТЕРЬ
1.1 Основа всех методов сжатия
В основе всех методов сжатия лежит простая идея: если представлять часто используемые элементы короткими кодами, а редко используемые - длинными кодами, то для хранения блока данных требуется меньший объем памяти, чем если бы все элементы представлялись кодами одинаковой длины.
Точная связь между вероятностями и кодами установлена в теореме Шеннона о кодировании источника, которая гласит, что элемент sh вероятность появления которого равняется p(s,), выгоднее всего представлять -1о& p(sj) битами. Если при кодировании размер кодов всегда в точности получается равным -log2 p(s,) битам, то в этом случае длина закодированной последовательности будет минимальной для всех возможных способов кодирования. Если распределение вероятностей F= {pis,} неизменно, и вероятности появления элементов независимы, то мы можем найти среднюю длину кодов как среднее взвешенное.
Это значение также называется энтропией распределения вероятностей F или энтропией источника в заданный момент времени.
Ни один компрессор не может сжать любой файл. После обработки любым компрессором размер части файлов уменьшится, а оставшейся части -увеличится или останется неизменным. Данный факт можно доказать исходя из неравномерности кодирования, т. е. разной длины используемых кодов, но наиболее прост для понимания следующий комбинаторный аргумент.
Существует 2л различных файлов длины п бит, где л = 0, 1, 2,... Если размер каждого такого файла в результате обработки уменьшается хотя бы на 1 бит, то 2л исходным файлам будет соответствовать самое большее 2л-1 различающихся сжатых файлов. Тогда, по крайней мере, одному архивному файлу будет соответствовать несколько различающихся исходных, и, следовательно, его декодирование без потерь информации невозможно в принципе.
1.2 Методы сжатия
Методы сжатия файлов бывают «открытыми» и «коммерческими». В первом случае алгоритм можно свободно исследовать и использовать, так как он сам по себе является ценностью. Во втором случае использование метода является закрытым: алгоритм засекречивается в виду того, что он применяется только в отдельных программных продуктах, и несанкционированное использование может вызвать последующие разбирательства по поводу авторских прав, что собственно неоднократно происходило в истории развития архиваторов.
В настоящее время существует очень много алгоритмов сжатия данных без потерь. Наиболее распространенными являются такие, как: Lossless JPEG, алгоритм Хаффмена, алгоритмы группы KWE:
- алгоритм LZ (Лемпеля-Зива);
- алгоритм LZW (Лемпеля-Зива-Велча);
1.2.1 Алгоритмы группы KWE.
Существует довольно много реализаций этого алгоритма, среди которых наиболее распространенными являются алгоритм Лемпеля-Зива (алгоритм LZ) и его модификация алгоритм Лемпеля-Зива-Велча (алгоритм LZW).Для алгоритма LZ основан на создании своеобразного словаря, где каждое слово получает свой порядковый номер, и в результате сжатый файл содержит не предложения, а последовательность чисел, что существенно сокращает его размер. Алгоритм начинает работу с почти пустым словарем, который содержит только одну закодированную строку, так называемая NULL-строка. Когда происходит считывание очередного символа входной последовательности данных, то он прибавляется к текущей строке. Это будет продолжаться до тех пор, пока текущая строка соответствует какой-нибудь фразе из словаря. В момент, когда текущая строка представляет собой последнее совпадение со словарем плюс только что прочитанный символ сообщения, кодер выдает код, который состоит из индекса совпадения и следующего за ним символа, который нарушил совпадение строк, а новая фраза, состоящая из совпадающего индекса и следующего за ним символа - записывается в словарь. Если эта фраза появляется еще раз, то она может быть использована для построения более длинной фразы. Это способствует повышению сжатия информации.
Семейство LZ-подобных алгоритмов могут различаться, например, методом поиска повторяющихся цепочек. В таблице1 приведены примеры LZ- алгоритмов.
Таблица1 Основные LZ-алгоритмы
|
Имя |
Авторы |
Год |
Отличия |
|
|
LZ77 |
Ziv and Lempel |
1977 |
Указатели и символы чередуются. Указатели адресуют подстроку среди предыдущих N символов. |
|
|
LZR |
Roden et al. |
1981 |
Указатели и символы чередуются. Указатели адресуют подстроку среди всех предыдущих символов. |
|
|
LZSS |
Bell |
1986 |
Указатели и символы различаются флажком- битом. Указатели адресуют подстроку среди предыдущих N символов. |
|
|
LZB |
Bell
Другие файлы:
Кодек телевизионного сигнала моноадресной телевизионной системы Кодирование: оптимальный код Хаффмана Эффективное кодирование Статический алгоритм Хаффмана Метод кодирования Хаффмана |
© 2006-2015 Студенческий сайт ТНУ им. В.И.Вернадского, TNU.in.UA