Лабораторная работа №8. Лабораторная работа 8 Сжатие данных. Алгоритм rle
 Скачать 175.98 Kb.
|
|
Лабораторная работа № 8 Сжатие данных. Алгоритм RLE. Цель работы: Освоение терминологии, используемой при сжатии данных, характеристик алгоритмов сжатия данных, принципов работы алгоритмов сжатия без потерь, детальное освоение алгоритма сжатия без потерь, использующего исключение повторов (RLE). Задание Прочитать учебную информацию, разобрать примеры решения задач. В соответствии со своим номером варианта, решить задания из каждого блока. В отчет включить решенные задачи.
Учебная информация Сжатие данных в вычислительной технике и системах связи (используются также термины архивация данных, когда сжатие применяется к готовым документам; программные средства, выполняющие эти операции, называют архиваторами, например, WinZip, WinRAR, WinArj, PKZIP.EXE, RAR.EXE, ARJ.EXE; используется и синонимы слова сжатие упаковка, компрессия) - это процесс кодирования массивов данных таким образом, чтобы объем занимаемый полученным кодом в запоминающих устройствах, был бы, по возможности минимальным. При этом процесс сжатия должен быть полностью или частично обратимым, т.е. должна существовать обратная процедура, называемая декодированием (распаковкой, разархивацией), позволяющая восстановить из сжатых данных набор данных, в той или иной мере соответствующий исходным данным. Такое определение под сжатием понимает следующие процедуры преобразования данных: неискажающее сжатие цифровых данных, сжатие цифровых данных с регулируемыми потерями, получение экономного представления входного аналогового сигнала. При неискажающем сжатии цифровых данных исходный массив цифровых данных (исходное сообщение) представляется таким образом, чтобы получить минимизированный объем закодированных данных. Сжатие должно быть полностью обратимым, т.е. должна существовать процедура, позволяющая восстановить из сжатых данных точную копию исходного массива данных. Подчеркивая эту особенность, такой процесс часто называют сжатием без потерь, обратимым сжатием. Исходные данные представляются каким-либо двоичным кодом: коды символов текста, команд процессора, яркости точек растрового изображения, амплитуды аналогового сигнала, ссылки на другие фрагменты данных. При сжатии цифровых данных с регулируемыми потерями обеспечивается экономное представление цифровых данных, но процедура сжатия не является полностью обратимой, т.е. распаковка не позволяет во всех случаях восстановить исходный массив данных до отдельного бита. Как правило, потери допускаются только в той части данных, которая не является существенной при дальнейшем использовании распакованного сообщения. Ясно, что в общем случае «существенность» потерь данных оценить невозможно, поэтому сжатие с потерями допускается только для данных, которые допускают некоторую потерю. Обычно это аналоговые по своей природе данные, например, оцифрованные изображения или звук: цифровые фотографии, видеоряды, звукозаписи. Алгоритмы сжатия без потерь Для сжатия без потерь доказаны следующие теоремы. 1. Для любой последовательности данных существует теоретический предел сжатия, который не может быть превышен без потери части информации. 2. Для любого алгоритма сжатия можно найти такую последовательность данных, для которой он обеспечит лучшую степень сжатия, чем другие алгоритмы. 3. Для любого алгоритма сжатия можно найти такую последовательность данных, для которой данный алгоритм вообще не позволит получить сжатия. Из сформулированных теорем следует, что наивысшую эффективность алгоритмы сжатия демонстрируют для разных типов данных и разных объемов данных. Поэтому разработано в настоящее время достаточно большое количество алгоритмов сжатия без потерь. Наиболее распространенные алгоритмы сжатия без потерь приведены на рис. 1.  Алгоритмы сжатия, использующие исключение повторов Алгоритмы сжатия, использующие исключение повторов (RLE = Run-Length Encoding) чрезвычайно просты и ориентированы на быстрое сжатие данных, содержащих много идущих подряд одинаковых символов. В основу алгоритмов RLE положен принцип выявления групп подряд идущих одинаковых символов и замены их структурой, в которой указывается код символа и число повторов, т.е. группа идущих подряд одинаковых символов заменяется на пару кодов вида <код символа; число 13 повторов>. Максимальное число одинаковых символов, которое можно закодировать одной такой парой, определяется длиной кода числа повторов. В качестве примера рассмотрим реализацию RLE а графическом формате PCX. Группа повторяющихся байтов заменяется на байт-счетчик и байт данных. В байте-счетчике старшие два бита содержат единицы, в младших шести битах хранится число повторов. Неповторяющиеся значения, меньшие 0C0h = 0C016 = 110000002, записываются в сжатые данные без изменений. Для неповторяющихся значений, больших 0C016 = 110000002, (т.е. с двумя единицами в старших разрядах) такой подход недопустим, так как при распаковке такой байт будет восприниматься как байт-счетчик повторов. Поэтому такие байты при записи в сжатый поток предваряются байтом-счетчиком с числом повторов, равным единице (11000001 = С116). Проблему при сжатии алгоритмами RLE представляют данные, содержащие незначительное количество повторяющихся символов. К одиночным символам также приходится добавлять счетчик повторов, что вместо сжатия дает увеличение объема данных. Поэтому в практических реализациях алгоритмы RLE несколько усложняются, чтобы уменьшить увеличение объема сжатых данных в случае не очень подходящих данных. Пример. Сжатие Исходные данные: 01BD2F154FDBE01015FDEO1ED1001A0A 10 1C 61 EF 01 D0 11 33 33 33 33 33 33 33 34 Последовательно проверяем каждый байт, и формируем сжатый поток согласно алгоритму RLE. 01 – первый байт исходных данных. Следующий за ним байт BD, это означает, что первый байт не входит в цепочку повторяющихся байтов. Старшие два бита байта 01 не равны единицам. Следовательно, первый байт исходных данных переписываем в сжатый поток без изменений. BD 2F 15 4F – следующие за первым байты, аналогично первому, переписываем в сжатый поток без изменения. Два следующих байта DB16=110110112 и E016=111000002 – это байты, старшие два бита которых содержат единицы. Поэтому, эти байты, при записи в сжатый поток, предваряем байтами-счетчиками, с числом повторов равным единице (C116=110000012). 10 15 – эти байты не содержат единицы в старших битах и не входят в цепочку повторяющихся байтов. Переписываем их в сжатый поток без изменения. Два следующих бита FD16=111111012 E016=111000002 – это байты, старшие два бита которых содержат единицы. Поэтому, эти байты, при записи в сжатый поток, предваряем байтами-счетчиками, с числом повторов равным единице (C116=110000012). 1E – этот байт не содержит единиц в старших битах и не входит в цепочку повторяющихся байтов. Переписываем его в сжатый поток без изменения. Следующий байт D116=110100012 – это байт, старшие два бита которого содержат единицы. Поэтому, этот байт, при записи в сжатый поток, предваряем байтом-счетчиком, с числом повторов равным единице (C116=110000012). 00 1A 0A 10 1C 61 – эти байты не содержат единицы в старших битах и не входят в цепочку повторяющихся байтов. Переписываем их в сжатый поток без изменения. Следующий байт EF16=111011112 – это байт, старшие два бита которого содержат единицы. Поэтому, этот байт, при записи в сжатый поток, предваряем байтом-счетчиком, с числом повторов равным единице (C116=110000012). 01 – этот байт не содержит единиц в старших битах и не входит в цепочку повторяющихся байтов. Переписываем его в сжатый поток без изменения. Следующий байт D016=110100002 – это байт, старшие два бита которого содержат единицы. Поэтому, этот байт, при записи в сжатый поток, предваряем байтом-счетчиком, с числом повторов равным единице (C116=110000012). 11 – этот байт не содержит единиц в старших битах и не входит в цепочку повторяющихся байтов. Переписываем его в сжатый поток без изменения. Далее идёт группа повторяющихся байтов 33 33 33 33 33 33 33, её заменяем на байт-счетчик и байт данных C7 33. Последний байт 34 не содержит единицы в старших битах, переписываем его в сжатые данные без изменения. Сжатые данные: 01 BD 2F 15 4F C1 DB C1 E0 10 15 C1 FD C1 EO 1E C1 D1 00 1A 0A 10 1C 61 C1 EF 01 C1 D0 11 C7 33 34 Пример 2 выполнения РАСПАКОВКА Сжатые данные: 01 10 11 A2 B2 C2 D2 C1 FF D3 21 Последовательно проверяем каждый байт. 01 10 11 А2 B2 – не являются байтами-счетчиками, их записываем в распакованные данные без изменения. Следующий байт С216=110000102 – это байт-счетчик (с числом повторов равным двум), байт значения которого D2. В распакованные данные записываем D2 D2. Затем идет С1 – это байт-счетчик (с числом повторов равным единице), байт значения которого FF. В распакованные данные записываем FF. D3 – это байт-счетчик (т.к. D316=110100112, с числом повторов равным 0100112=1910), байт, значение которого 21. В распакованные данные записываем девятнадцать раз байт 21. Распакованные данные: 01 10 11 A2 B2 D2 D2 FF 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 Контрольные вопросы: 1. Приведите определение процесса сжатия данных. 2. Приведите определение неискажающего сжатия цифровых данных (сжатие без потерь). 3. Приведите определение сжатия цифровых данных с регулируемыми потерями. 4. Приведите определение архиватора. Приведите примеры распространенных архиваторов. 5. Какие алгоритмы сжатия без потерь Вам известны? 6. Сформулируйте теоремы для сжатия без потерь. 7. Сформулируйте идею сжатия данных статистическими алгоритмами. 8 Какой принцип положен в основу алгоритмов RLE? |