- Tutorial
Давным-давно, когда я был ещё наивным школьником, мне вдруг стало жутко любопытно: а каким же волшебным образом данные в архивах занимают меньше места? Оседлав свой верный диалап, я начал бороздить просторы Интернетов в поисках ответа, и нашёл множество статей с довольно подробным изложением интересующей меня информации. Но ни одна из них тогда не показалась мне простой для понимания - листинги кода казались китайской грамотой, а попытки понять необычную терминологию и разнообразные формулы не увенчивались успехом.
Поэтому целью данной статьи является дать представление о простейших алгоритмах сжатия тем, кому знания и опыт пока ещё не позволяют сходу понимать более профессиональную литературу, или же чей профиль и вовсе далёк от подобной тематики. Т.е. я «на пальцах» расскажу об одних из простейших алгоритмах и приведу примеры их реализации без километровых листингов кода.
Сразу предупрежу, что я не буду рассматривать подробности реализации процесса кодирования и такие нюансы, как эффективный поиск вхождений строки. Статья коснётся только самих алгоритмов и способов представления результата их работы.
RLE - компактность единообразия
Алгоритм RLE является, наверное, самым простейшим из всех: суть его заключается в кодировании повторов. Другими словами, мы берём последовательности одинаковых элементов, и «схлопываем» их в пары «количество/значение». Например, строка вида «AAAAAAAABCCCC» может быть преобразована в запись вроде «8×A, B, 4×C». Это, в общем-то, всё, что надо знать об алгоритме.Пример реализации
Допустим, у нас имеется набор неких целочисленных коэффициентов, которые могут принимать значения от 0 до 255. Логичным образом мы пришли к выводу, что разумно хранить этот набор в виде массива байт:unsigned char data = { 0, 0, 0, 0, 0, 0, 4, 2, 0, 4, 4, 4, 4, 4, 4, 4, 80, 80, 80, 80, 0, 2, 2, 2, 2, 255, 255, 255, 255, 255, 0, 0 };
Для многих гораздо привычней будет видеть эти данные в виде hex-дампа:
0000: 00 00 00 00 00 00 04 02 00 04 04 04 04 04 04 04
0010: 50 50 50 50 00 02 02 02 02 FF FF FF FF FF 00 00
Подумав, мы решили, что хорошо бы для экономии места как-то сжимать такие наборы. Для этого мы проанализировали их и выявили закономерность: очень часто попадаются подпоследовательности, состоящие из одинаковых элементов. Конечно же, RLE для этого подойдёт как нельзя кстати!
Закодируем наши данные, используя свежеполученные знания: 6×0, 4, 2, 0, 7×4, 4×80, 0, 4×2, 5×255, 2×0.
Пришло время как-то представить наш результат в понятном компьютеру виде. Для этого, в потоке данных мы должны как-то отделять одиночные байты от кодируемых цепочек. Поскольку весь диапазон значений байта используется нашими данными, то просто так выделить какие-либо диапазоны значений под наши цели не удастся.
Есть как минимум два выхода из этой ситуации:
- В качестве индикатора сжатой цепочки выделить одно значение байта, а в случае коллизии с реальными данными экранировать их. Например, если использовать в «служебных» целях значение 255, то при встрече этого значения во входных данных мы вынуждены будем писать «255, 255» и после индикатора использовать максимум 254.
- Структурировать закодированные данные, указывая количество не только для повторяемых, но и последующих далее одиночных элементов. Тогда мы будем заранее знать, где какие данные.
Итак, теперь у нас имеется два вида последовательностей: цепочки одиночных элементов (вроде «4, 2, 0») и цепочки одинаковых элементов (вроде «0, 0, 0, 0, 0, 0»). Выделим в «служебных» байтах один бит под тип последовательности: 0 - одиночные элементы, 1 - одинаковые. Возьмём для этого, скажем, старший бит байта.
В оставшихся 7 битах мы будем хранить длины последовательностей, т.е. максимальная длина кодируемой последовательности - 127 байт. Мы могли бы выделить под служебные нужды, допустим, два байта, но в нашем случае такие длинные последовательности встречаются крайне редко, поэтому проще и экономичней просто разбивать их на более короткие.
Получается, в выходной поток мы будем писать сперва длину последовательности, а далее либо одно повторяемое значение, либо цепочку неповторяемых элементов указанной длины.
Первое, что должно броситься в глаза - при таком раскладе у нас есть парочка неиспользуемых значений. Не может быть последовательностей с нулевой длиной, поэтому мы можем увеличить максимальную длину до 128 байт, отнимая от длины единицу при кодировании и прибавляя при декодировании. Таким образом, мы можем кодировать длины от 1 до 128 вместо длин от 0 до 127.
Второе, что можно заметить - не бывает последовательностей одинаковых элементов единичной длины. Поэтому, от значения длины таких последовательностей при кодировании мы будем отнимать ещё единичку, увеличив тем самым их максимальную длину до 129 (максимальная длина цепочки одиночных элементов по-прежнему равна 128). Т.е. цепочки одинаковых элементов у нас могут иметь длину от 2 до 129.
Закодируем наши данные снова, но теперь уже и в понятном для компьютера виде. Будем записывать служебные байты как , где T - тип последовательности, а L - длина. Будем сразу учитывать, что длины мы записываем в изменённом виде: при T=0 отнимаем от L единицу, при T=1 - двойку.
0, , 4, 2, 0, , 4, , 80, , 0, , 2, , 255, , 0
Попробуем декодировать наш результат:
- . T=1, значит следующий байт будет повторяться L+2 (4+2) раз: 0, 0, 0, 0, 0, 0.
- . T=0, значит просто читаем L+1 (2+1) байт: 4, 2, 0.
- . T=1, повторяем следующий байт 5+2 раз: 4, 4, 4, 4, 4, 4, 4.
- . T=1, повторяем следующий байт 2+2 раз: 80, 80, 80, 80.
- . T=0, читаем 0+1 байт: 0.
- . T=1, повторяем байт 2+2 раз: 2, 2, 2, 2.
- . T=1, повторяем байт 3+2 раз: 255, 255, 255, 255, 255.
- . T=1, повторяем байт 0+2 раз: 0, 0.
А теперь последний шаг: сохраним полученный результат как массив байт. Например, пара
, упакованная в байт, будет выглядеть вот так:
В итоге получаем следующее:
0000: 84
00 02
04 02 00 85
04 82
80 00
00 82
02 83
FF
0010: 80
00
Таким вот нехитрым образом на данном примере входных данных мы из 32 байт получили 18. Неплохой результат, особенно если учесть, что на более длинных цепочках он может оказаться гораздо лучше.
Возможные улучшения
Эффективность алгоритма зависит не только от собственно алгоритма, но и от способа его реализации. Поэтому, для разных данных можно разрабатывать разные вариации кодирования и представления закодированных данных. Например, при кодировании изображений можно сделать цепочки переменной длины: выделить один бит под индикацию длинной цепочки, и если он выставлен в единицу, то хранить длину и в следующем байте тоже. Так мы жертвуем длиной коротких цепочек (65 элементов вместо 129), но зато даём возможность всего тремя байтами закодировать цепочки длиною до 16385 элементов (2 14 + 2)!Дополнительная эффективность может быть достигнута путём использования эвристических методов кодирования. Например, закодируем нашим способом следующую цепочку: «ABBA». Мы получим « , A, , B, , A» - т.е. 4 байта мы превратили в 6, раздули исходные данные аж в полтора раза! И чем больше таких коротких чередующихся разнотипных последовательностей, тем больше избыточных данных. Если это учесть, то можно было бы закодировать результат как « , A, B, B, A» - мы бы потратили всего один лишний байт.
LZ77 - краткость в повторении
LZ77 - один из наиболее простых и известных алгоритмов в семействе LZ. Назван так в честь своих создателей: Абрахама Лемпеля (Abraham L empel) и Якоба Зива (Jacob Z iv). Цифры 77 в названии означают 1977 год, в котором была опубликована статья с описанием этого алгоритма.Основная идея заключается в том, чтобы кодировать одинаковые последовательности элементов. Т.е., если во входных данных какая-то цепочка элементов встречается более одного раза, то все последующие её вхождения можно заменить «ссылками» на её первый экземпляр.
Как и остальные алгоритмы этого семейства семейства, LZ77 использует словарь, в котором хранятся встречаемые ранее последовательности. Для этого он применяет принцип т.н. «скользящего окна»: области, всегда находящейся перед текущей позицией кодирования, в рамках которой мы можем адресовать ссылки. Это окно и является динамическим словарём для данного алгоритма - каждому элементу в нём соответствует два атрибута: позиция в окне и длина. Хотя в физическом смысле это просто участок памяти, который мы уже закодировали.
Пример реализации
Попробуем теперь что-нибудь закодировать. Сгенерируем для этого какую-нибудь подходящую строку (заранее извиняюсь за её нелепость):«The compression and the decompression leave an impression. Hahahahaha!»
Вот как она будет выглядеть в памяти (кодировка ANSI):
0000: 54 68 65 20 63 6F 6D 70 72 65 73 73 69 6F 6E 20 The compression
0010: 61 6E 64 20 74 68 65 20 64 65 63 6F 6D 70 72 65 and the decompre
0020: 73 73 69 6F 6E 20 6C 65 61 76 65 20 61 6E 20 69 ssion leave an i
0030: 6D 70 72 65 73 73 69 6F 6E 2E 20 48 61 68 61 68 mpression. Hahah
0040: 61 68 61 68 61 21 ahaha!
Мы ещё не определились с размером окна, но условимся, что он больше размера кодируемой строки. Попробуем найти все повторяющиеся цепочки символов. Цепочкой будем считать последовательность символов длиной более единицы. Если цепочка входит в состав более длинной повторяющейся цепочки, будем её игнорировать.
«The compression and t de leave[ an] i . Hah !»
Для пущей наглядности посмотрим на схему, где видны соответствия повторяемых последовательностей и их первых вхождений:
Пожалуй, единственным неясным моментом здесь будет последовательность «Hahahahaha!», ведь цепочке символов «ahahaha» соответствует короткая цепочка «ah». Но здесь нет ничего необычного, мы использовали кое-какой приём, позволяющий алгоритму иногда работать как описанный ранее RLE.
Дело в том, что при распаковке мы будем считывать из словаря указанное количество символов. А поскольку вся последовательность периодична, т.е. данные в ней повторяются с некоторым периодом, и символы первого периода будут находиться прямо перед позицией распаковки, то по ним мы можем воссоздать всю цепочку целиком, просто копируя символы предыдущего периода в следующий.
С этим разобрались. Теперь заменим найденные повторы на ссылки в словарь. Будем записывать ссылку в формате , где P - позиция первого вхождения цепочки в строке, L - её длина.
«The compression and t de leave i . Hah !»
Но не стоит забывать, что мы имеем дело со скользящим окном. Для большего понимания, чтобы ссылки не зависели от размера окна, заменим абсолютные позиции на разницу между ними и текущей позицией кодирования.
«The compression and t de leave i . Hah !»
Теперь нам достаточно отнять P от текущей позиции кодирования, чтобы получить абсолютную позицию в строке.
Пришло время определиться с размером окна и максимальной длиной кодируемой фразы. Поскольку мы имеем дело с текстом, редко когда в нём будут встречаться особо длинные повторяющиеся последовательности. Так что выделим под их длину, скажем, 4 бита - лимита на 15 символов за раз нам вполне хватит.
А вот от размера окна уже зависит, насколько глубоко мы будем искать одинаковые цепочки. Поскольку мы имеем дело с небольшими текстами, то в самый раз будет дополнить используемое нами количество бит до двух байт: будем адресовать ссылки в диапазоне из 4096 байт, используя для этого 12 бит.
По опыту с RLE мы знаем, что не всякие значения могут быть использованы. Очевидно, что ссылка может иметь минимальное значение 1, поэтому, чтобы адресовать назад в диапазоне 1..4096, мы должны при кодировании отнимать от ссылки единицу, а при декодировании прибавлять обратно. То же самое с длинами последовательностей: вместо 0..15 будем использовать диапазон 2..17, поскольку с нулевыми длинами мы не работаем, а отдельные символы последовательностями не являются.
Итак, представим наш закодированный текст с учётом этих поправок:
«The compression and t de leave i . Hah !»
Теперь, опять же, нам надо как-то отделить сжатые цепочки от остальных данных. Самый распространённый способ - снова использовать структуру и прямо указывать, где сжатые данные, а где нет. Для этого мы разделим закодированные данные на группы по восемь элементов (символов или ссылок), а перед каждой из таких групп будем вставлять байт, где каждый бит соответствует типу элемента: 0 для символа и 1 для ссылки.
Разделяем на группы:
- «The comp»
- «ression »
- «and t de»
- « leave »
- «i . Hah »
«{0,0,0,0,0,0,0,0} The comp{0,0,0,0,0,0,0,0} ression {0,0,0,0,0,1,0,0} and t de{1,0,0,0,0,0,1,0} leave {0,1,0,0,0,0,0,1} i . Hah {0} !»
Таким образом, если при распаковке мы встречаем бит 0, то мы просто читаем символ в выходной поток, если же бит 1, мы читаем ссылку, а по ссылке читаем последовательность из словаря.
Теперь нам остаётся только сгруппировать результат в массив байтов. Условимся, что мы используем биты и байты в порядке от старшего к младшему. Посмотрим, как пакуются в байты ссылки на примере :
В итоге наш сжатый поток будет выглядеть так:
0000: 00
54 68 65 20 63 6f 6d 70 00
72 65 73 73 69 6f #The comp#ressio
0010: 6e 20 04
61 6e 64 20 74 01 31
64 65 82
01 5a
6c n #and t##de###l
0020: 65 61 76 65 01 b1
20 41
69 02 97
2e 20 48 61 68 eave## #i##. Hah
0030: 00 15
00
21 00 00 00 00 00 00 00 00 00 00 00 00
###!
Возможные улучшения
В принципе, здесь будет верно всё, что описывалось для RLE. В частности, для демонстрации пользы эвристического подхода при кодировании, рассмотрим следующий пример:«The long goooooong. The loooooower bound.»
Найдём последовательности только для слова «loooooower»:
«The long goooooong. The wer bound.»
Для кодирования такого результата нам понадобится четыре байта на ссылки. Однако, более экономично было бы сделать так:
«The long goooooong. The l wer bound.»
Тогда мы потратили бы на один байт меньше.
Вместо заключения
Несмотря на свою простоту и, казалось бы, не слишком уж большую эффективность, эти алгоритмы до сих пор широко применяются в разнообразных областях IT-сферы.Их плюс - простота и быстродействие, а на их принципах и их комбинациях могут быть основаны более сложные и эффективные алгоритмы.
Надеюсь, изложенная таким образом суть этих алгоритмов поможет кому-нибудь разобраться в основах и начать смотреть в сторону более серьёзных вещей.
Кодирование длин серий (англ. Run-length encoding, RLE) или Кодирование повторов - простой алгоритм сжатия данных, который оперирует сериями данных, то есть последовательностями, в которых один и тот же символ встречается несколько раз подряд. При кодировании строка одинаковых символов, составляющих серию, заменяется строкой, которая содержит сам повторяющийся символ и количество его повторов.
Характеристики алгоритма RLE:
Коэффициенты компрессии : Первый вариант: 32, 2, 0,5. Второй вариант: 64, 3, 128/129. (Лучший, средний, худший коэффициенты). Класс изображений : Ориентирован алгоритм на изображения с небольшим количеством цветов: деловую и научную графику. Симметричность: Примерно единица.
Характерные особенности : К положительным сторонам алгоритма, пожалуй, можно отнести только то, что он не требует дополнительной памяти при архивации и разархивации, а также быстро работает. Интересная особенность группового кодирования состоит в том, что степень архивации для некоторых изображений может быть существенно повышена всего лишь за счет изменения порядка цветов в палитре изображения.
Первый вариант алгоритма
Данный алгоритм необычайно прост в реализации. Групповое кодирование - от английского Run Length Encoding (RLE) - один из самых старых и самых простых алгоритмов архивации графики. Изображение в нем (как и в нескольких алгоритмах, описанных ниже) вытягивается в цепочку байт по строкам растра. Само сжатие в RLE происходит за счет того, что в исходном изображении встречаются цепочки одинаковых байт. Замена их на пары <счетчик повторений, значение > уменьшает избыточность данных.
Алгоритм рассчитан на деловую графику - изображения с большими областями повторяющегося цвета. Ситуация, когда файл увеличивается, для этого простого алгоритма не так уж редка. Ее можно легко получить, применяя групповое кодирование к обработанным цветным фотографиям. Для того чтобы увеличить изображение в два раза, его надо применить к изображению, в котором значения всех пикселов больше двоичного 11000000 и подряд попарно не повторяются.
Второй вариант алгоритма
Второй вариант этого алгоритма имеет больший максимальный коэффициент архивации и меньше увеличивает в размерах исходный файл.
29. Алгоритм сжатия lzw
Название алгоритм получил по первым буквам фамилий его разработчиков - Lempel , Ziv и Welch .
LZW-алгоритм основан на идее расширения алфавита, что позволяет использовать дополнительные символы для представления строк обычных символов. Используя, например, вместо 8-битовых ASCII-кодов 9-битовые, вы получаете дополнительные 256 символов. Работа компрессора сводится к построению таблицы, состоящей из строк и соответствующих им кодов. Алгоритм сжатия сводится к следующему: программа прочитывает очередной символ и добавляет его к строке. Если строка уже находится в таблице, чтение продолжается, если нет, данная строка добавляется к таблице строк. Чем больше будет повторяющихся строк, тем сильнее будут сжаты данные. Возвращаясь к примеру с телефоном, можно, проведя весьма упрощенную аналогию, сказать, что, сжимая запись 233 34 44 по LZW-методу, мы придем к введению новых строк - 333 и 444 и, выражая их дополнительными символами, сможем уменьшить длину записи.
Характеристики алгоритма LZW: Коэффициенты компрессии : Примерно 1000, 4, 5/7 (Лучший, средний, худший коэффициенты). Сжатие в 1000 раз достигается только на одноцветных изображениях размером кратным примерно 7 Мб. Класс изображений : Ориентирован LZW на 8-битные изображения, построенные на компьютере. Сжимает за счет одинаковых подцепочек в потоке. Симметричность : Почти симметричен, при условии оптимальной реализации операции поиска строки в таблице.
Характерные особенности : Ситуация, когда алгоритм увеличивает изображение, встречается крайне редко. LZW универсален - именно его варианты используются в обычных архиваторах.
Процесс сжатия выглядит достаточно просто. Мы считываем последовательно символы входного потока и проверяем, есть ли в созданной нами таблице строк такая строка. Если строка есть, то мы считываем следующий символ, а если строки нет, то мы заносим в поток код для предыдущей найденной строки, заносим строку в таблицу и начинаем поиск снова.
Особенность LZW заключается в том, что для декомпрессии не надо сохранять таблицу строк в файл для распаковки. Алгоритм построен таким образом, что мы в состоянии восстановить таблицу строк, пользуясь только потоком кодов.
Используя алгоритм RLE, закодируйте последовательность символов BBBBBBACCCABBBBBBЗапишите результат в виде шестнадцатеричных кодов (каждый символ кодируется в виде байта, который представлен двумя шестнадцатеричными цифрами). Проверьте полученный результат с помощью программы RLE.
Раскодируйте последовательность, упакованную с помощью алгоритма RLE (приводятся шестнадцатеричные коды): 01 4D 8E 41 01 4D 8E 4116. Для определения символов по их шестнадцатеричным кодом используйте таблицу ASCII. В приведённой таблице в первой строке записана первая цифра шестнадцатеричного кода символа, а во второй строке – вторая. Например, символ «&» имеет шестнадцатеричный код 2616.
- почему не удается сжать рисунки в формате JPEG? почему для двух рисунков в формате BMP одинакового размера коэффициенты сжатия по алгоритму RLE так сильно отличаются? Подсказка: откройте эти рисунки в любой программе просмотра.
Оцените коэффициент сжатия с помощью RLE-алгоритма в худшем случае. Опишите этот худший случай.
Оформление документа
и оформите этим стилем формулу, набранную в формате LaТ Е Х.
Оформите заголовок «Литература» стилем «Заголовок 2 ». Информацию о книге Д. Кнута оформите в виде нумерованного списка.
Найдите информацию о книге «Все про Т Е Х» на сайте издательства «Вильямс» и сделайте название книги гиперссылкой на найденную страницу. Проверьте работу гиперссылки.
Алгоритм RLE
Используя алгоритм RLE, закодируйте последовательность символов
Запишите результат в виде шестнадцатеричных кодов (каждый символ кодируется в виде байта, который представлен двумя шестнадцатеричными цифрами). Проверьте полученный результат с помощью программы RLE.
Раскодируйте последовательность, упакованную с помощью алгоритма RLE (приводятся шестнадцатеричные коды): 01 4D 8E 41 01 4D 8E 41 16 . Для определения символов по их шестнадцатеричным кодом используйте таблицу ASCII. Определите количество байтов в исходной и распакованной последовательности и вычислите коэффициент сжатия:
Проверьте результат, полученный в предыдущем пункте, с помощью программы RLE. Предложите два способа проверки.
Постройте последовательности, которые сжимаются алгоритмом RLE ровно в 2 раза, в 4 раза, в 5 раз. Проверьте свои ответы с помощью программы RLE.
Несжатая последовательность
Сжатая последовательность
Коэффициент сжатия
2
4
5
Придумайте три последовательности, которые невозможно сжать с помощью алгоритма RLE:
Несжатая последовательность
«Сжатая» последовательность
Коэффициент сжатия
Используя программу RLE, примените RLE-сжатие к следующим файлам и найдите для каждого из них коэффициент сжатия:
Файл
Размер без сжатия
Размер после сжатия
Коэффициент сжатия
grad_vert.bmp
grad_horz.bmp
grad_diag.jpg
Объясните результаты, полученные в предыдущем пункте:
почему невыгодно сжимать рисунки в формате JPEG?
почему для двух рисунков в формате BMP одинакового размера коэффициенты сжатия по алгоритму RLE так сильно отличаются? Подсказка : откройте эти рисунки в любой программе просмотра.
Оцените максимально достижимый коэффициент сжатия с помощью рассмотренного в учебнике варианта RLE-алгоритма. В каком случае его удастся достичь?
Оцените коэффициент сжатия с помощью RLE-алгоритма в худшем случае. Опишите этот худший случай.
Сравнение алгоритмов сжатия
Запустите программу Huffman.exe и закодируйте строку «ЕНОТ НЕ ТОНЕТ», используя методы Шеннона-Фано и Хаффмана. Запишите результаты в таблицу:
| Шеннон и Фано | Хаффман |
|
| Длина основного кода | ||
| | ||
| | ||
| |
Сделайте выводы.
Ответ :
Как, по вашему мнению, будет изменяться коэффициент сжатия при увеличении длины текста, при условии, что набор символов и частота их встречаемости останутся неизменной? Проверьте ваш вывод с помощью программы (например, можно несколько раз скопировать ту же фразу).
Ответ :
Повторите эксперимент с фразой «НОВОЕ ЕНОТОВО».
| Шеннон и Фано | Хаффман |
|
| Длина основного кода | ||
| Длина кодовой таблицы (дерева) | ||
| Коэффициент сжатия (по основным кодам) | ||
| Коэффициент сжатия (с учетом дерева кодов) |
Сделайте выводы.
Ответ :
Нарисуйте в тетради кодовые деревья, которые были построены программой при использовании обоих методов.
Используя кнопку Анализ файла в программе Huffman a.txt 1 при побайтном кодировании.
С помощью программ RLE и Huffman выполните сжатие файла a . txt разными способами. Запишите результаты в таблицу:
Объясните результат, полученный с помощью алгоритма RLE.
Ответ :
Используя кнопку Анализ файла в программе Huffman , определите предельный теоретический коэффициент сжатия для файла a.txt.huf при побайтном кодировании. Объясните результат.
Примените несколько раз повторное сжатие этого файла с помощью алгоритма Хаффмана (новые файлы получат имена a.txt.huf2 , a.txt.huf3 и т.д.) и заполните таблицу, каждый раз выполняя анализ полученного файла.
| Размер файла | |
|
| a.txt | ||
| a.txt.huf | ||
| a.txt.huf2 | ||
| a.txt.huf3 | ||
| a.txt.huf4 | ||
| a.txt.huf5 |
Ответ :
Выполните те же действия, используя метод Шеннона-Фано.
| Размер файла | Предельный коэффициент сжатия |
|
| a.txt | ||
| a.txt.shf | ||
| a.txt.shf2 | ||
| a.txt.shf3 | ||
| a.txt.shf4 | ||
| a.txt.shf5 |
Объясните, почему с некоторого момента при повторном сжатии файла его размер увеличивается.
Ответ :
Сравните результаты сжатия этого файла с помощью алгоритма RLE, лучшие результаты, полученные методами Шеннона-Фано и Хаффмана, а также результат сжатия этого файла каким-нибудь архиватором.
| Размер файла | Предельный коэффициент сжатия |
|
| RLE | ||
| Хаффман | ||
| Шеннон и Фано | ||
| ZIP | ||
| RAR | ||
| 7Z |
Объясните результаты и сделайте выводы.
Ответ :
Использование архиватора
Изучите возможности архиватора, который установлен на вашем компьютере (Ark , 7- Zip , WinRAR или др.).
Откройте каталог, указанный учителем. Он должен содержать все файлы, которые используются далее.
Распакуйте архив secret. zip , который упакован с паролем secretLatin . В подкаталогах, получившихся после распаковки, вы должны найти 3 файла, содержащие части высказывания на латинском языке, которое означает «договоры следует выполнять».
Создайте новый текстовый файл latin.txt и запишите в него это высказывание на латыни. После этого удалите архив secret.zip .
Выполните сжатие отдельно для каждого из перечисленных в таблице файлов, используя формат архива, указанный учителем. Вычислите коэффициент сжатия (для этого удобно использовать табличный процессор):
| Имя файла | Описание | Объем до сжатия, Кб | Объем после сжатия, Кб | Коэффициент сжатия |
| random.dat | случайные данные | 391 | ||
| morning.zip | сжатый файл | 244 | ||
| sunset.jpg | рисунок в формате JPEG | 730 | ||
| prog.exe | программа для Windows | 163 | ||
| signal.mp3 | звук в формате MP3 | 137 | ||
| forest.wav | звук в формате WAV | 609 | ||
| ladoga.bmp | рисунок в формате BMP | 9217 | ||
| tolstoy.txt | текст | 5379 |
Запишите в тетради выводы о том, какие файлы обычно сжимаются лучше, а какие – хуже.
Если ваш архиватор позволяет создавать самораспаковывающиеся архивы, сравните размеры обычного архива и SFX-архива для файла tolstoy . txt :
Объясните, почему размеры двух архивов получились разные. После этого удалите оба созданных архива.
Переместите рисунки в отдельный каталог Pictures , а звуковые файлы – в каталог Sounds.
Упакуйте рисунки и звуки в архив Media с паролем media123 .
Упакуйте все остальные файлы и папки в архив Data (без пароля).
Удалите все файлы, кроме архивов Media и Data , и покажите работу учителю.
Сжатие с потерями
Скопируйте в свою папку файл valaam.jpg .
Используя растровый графический редактор (GIMP , Photoshop ), сохраните несколько копий этого рисунка с разным качеством, от 0% до 100%.
| Качество, % | 0 | 10 | 20 | 30 | 40 | 50 | 60 | 70 | 80 | 90 | 100 |
| Объем файла, Кбайт |
С помощью табличного процессора постройте график по этим данным. Сделайте выводы.
Просмотрите файлы, полученные при разных степенях сжатия. Выберите оптимальный на ваш взгляд вариант, когда при небольшом размере файла сохраняется приемлемое качество рисунка.
Скопируйте в свою папку звуковой файл bears . mp 3 .
Используя звуковой редактор (например, Audacity ), сохраните несколько копий этого звукового файла с разным качеством. Для формата Ogg Vorbis используйте качество от 0% до 100%, для формата MP3 – битрейт от 16 до 128 Кбит/с.
В табличном процессоре заполните таблицу
Постройте график по этим данным. Объясните, почему получилась именно такая зависимость.
Прослушайте файлы, полученные при разных степенях сжатия. Выберите оптимальный на ваш взгляд вариант, когда при небольшом размере файла сохраняется приемлемое качество звука.
