LZ -алгоритмы распаковки данных.

⇐ ПредыдущаяСтр 10 из 18Следующая ⇒

1. LZ77, длина словаря 8 байт (символов). Коды сжатого сообщения (0,0,К) (0,0,Р) (0,0,А) (0,0,С) (0,0,Н) (5,1, 'Я')(0,0, ' ') (0,4, 'К') (0,0, 'А')

2. LZSS. длина словаря 8 байт (символов). Коды сжатого 0'К' 0'Р' 0'А' 0'С' 0'Н' 1(5,1) 0'Я' 0' ' 1(0,4) 1(4,1) 1(0,1)

3. LZ78, длина словаря 16 фраз. Коды сжатого сообщения

(0, 'К') (0, 'Р') (0, 'А') (0, 'С') (0, 'Н') (3, 'Я') (0, ' ') (1, 'Р') (3, 'С') (1, 'А')

4. LZW, длина словаря 500 фраз. Коды сжатого сообщения 0'К' 0'Р' 0'А' 0'С' 0' Н' 0'А' 0'Я ' 0' ' (256) (258) 0' К' 0'А '

При распаковке нужно придерживаться следующего правила. Словарь пополняется после считывания первого символа идущего затекущим кодом, т.е. изфразы, соответствующей следующему после раскодированного кода, берется первый символ. Это правило позволяет избежать бесконечного цикла при раскодировании сообщений вида wKwK. где w - фраза, а. К-символ. Конкретным примером такого сообщения является любая последовательность трех одинаковых символов, пары которых ранее не встречались.

Лекция 8. Программы сжатия.

Особенности программ-архиваторов.

Если коды алгоритмов типа LZ передать для кодирования (адаптивному) алгоритму Хаффмана или арифметическому, то полученный двухшаговый (конвейерный, а не двухпроходный) алгоритм даст результаты сжатия подобные широко известным программам G ZIP, ARJ, РКZIP и подобным.

Наибольшую степень сжатия дают двухпроходные алгоритмы, которые исходные данные последовательно сжимают два paза, но они работают до двух раз медленнее однопроходных при незначительном увеличении степени сжатия.

Большинство программ-архиваторов сжимает каждый файл по отдельности, но некоторые сжимают файлы в общем потоке, что дает увеличение степени сжатия, но одновременно усложняет способы работы с полученным архивом, например, замена в таком архиве файла на его более новую версию может потребовать перекодирования всего архива. Примером программы, имеющей возможность сжимать файлы в общем потоке, является RAR. Архиваторы ОС Unix (gzip, gzip2, ...) сжимают файлы в общем потоке практически всегда.

В 1992 году фирма WEB Technologies объявила о выходе новой программы сжатия Data Files/16, которая якобы может при неоднократном использовании сжать любое количество данных до 1024 байт, Информация об этом прошла из солидного издания, журнала Byte.

Конечно же, никакой алгоритм сжатия не может уплотнить произвольные данные. Для доказательства этого проделаем следующий мысленный эксперимент. Предположим, что на жестком диске компьютера хранятся все возможные разные файлы длиной ровно 100 байт (таких файлов будет всего 2⁸⁰⁰). И пусть существует идеальная программа сжатия данных, которая сожмет каждый из них хотя бы на один байт. Но тогда, так как всего разных файлов длиной меньшей 100 байт существует не более чем 1 + 2⁸ + 2¹⁶ + … + 2⁷⁹² = (2⁸⁰⁰ - 1)/255 < 2⁸⁰⁰, то неизбежно получится, что два разных файла упакуются в идентичные файлы. Следовательно, не может существовать программы сжатия данных, которая может сжать любые исходные данные.

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

В следующей таблице приводятся некоторые типичные расширения, соответствующие им программы-архиваторы и методы сжатия данных.

Практически все форматы файлов для хранения графической информации используют сжатие данных. Формат графического файла также, как правила, идентифицируется расширением имени файла.

В следующей таблице приводятся некоторые типичные расширения графических файлов и соответствующие им методы сжатия данных.

Сжатие RLE (Run Length Encoding - кодирование переменной длины) это простейший метод сжатия, в общем случае очень неэффективный, но дающий неплохие результаты на типичной графической информации. Оно основано в основном на выделении специального кода-маркера, указывающего сколько раз повторить следующий байт.

Сжатие и распаковка в реальном времени используется в программах-драйверах для "уплотнения" носителей информации, позволяющих увеличить емкость носителя приблизительно в 2 paзa. Наиболее известной программой такого рода является DriverSpace для MS-DOS и Microsoft Windows.

Дата добавления: 2022-01-22; просмотров: 23; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 5 6 7 8 91011 12 13 14 Следующая ⇒

Мы поможем в написании ваших работ!