Архивация, компрессия, сжатие

(С) Сергей Симонович, 1994.

"...B пятом выпуске "ZX-РЕВЮ" в рассказе о фирме Level 9 Вы упомянули, что программисты придумали специальную систему, которая позволяет сжимать и уплотнять тексты. Скажите, не пробовали ли Вы разобраться, как работает эта система. Может быть, были попытки удачного "взлома" словарей в играх фирмы L9?" - спрашивает нас Илья Ползунов из Казани.

Нет, Илья, как-то руки не дошли до "раскрутки" этих программ в такой постановке вопроса, но вот о том, каким образом производится компрессия данных в общем случае, у нас есть, что рассказать, тем более, что эти вопросы достаточно актуальны для программистов.

Во-первых, удачные алгоритмы компрессии и декомпрессии данных позволяют значительно увеличить размеры программы, которую можно за один прием загрузить в компьютер и запустить. Это ведь только в пословице говорится, что краткость - сестра таланта. А куда деваться обычным людям, то есть таким бесталанным, как большинство из нас? Нам приходится брать не талантом, а усердием, то есть объемом. Вот и получается, что чем больший объем мы "втолкнем" в компьютерную программу за один раз, тем выше наши шансы приблизиться к лучшим образцам, исходящим от одаренных корифеев. Тем лучше будет наша графика, интереснее текст, богаче музыка.

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

В третьих, вопросы коммуникации. Через модем просто не принято работать с неархивированными данными. Это расточительство и времени и денег и рабочего пространства .

А на повестке дня сегодня работа мультимедийных систем. H$i одном лазерном диске записывают и программу и двадцатидвухканальную стереомузыку и видеоряд и все это надо мгновенно считывать в компьютер, преобразовывать и выдавать в РЕАЛЬНОМ ВРЕМЕНИ, т.е. так, чтобы пользователь не замечал задержек в видеофрагментах из-за того, что дисковод медленно передает информацию в компьютер. Здесь без очень "крутых" методов сжатия просто нечего делать. Не хватает никакой скорости передачи .

Вот так и получается, что вопросы компрессии информации, с которыми каждый "синклерист" сталкивается уже на первых шагах жизни, нарисовав первые картинки в ARTSTUDIO и вставив их в свою БЕЙСИК-программу, оказываются очень важными, интересными и до сих пор до конца нерешенными.

Два подхода.

Конечно существует множество разных методов компрессии данных. Но если взглянуть в их суть, то можно выделить два основных направления . Первое направление представляют разнообразные методы, основанные на использовании длин последовательностей повторяющихся данных (метод RLE - Run Length Encoding). Второе направление связано с использованием не длины повторяющихся данных, а частоты их повторения и эти методы строятся на алгоритме, носящем имя Хафмана (Huffman).

1. Классический подход.

Классический, давно известный подход основан на том, что если некоторый символ "X" повторяется подряд "N" раз, то вместо того, чтобы расходовать на него N байтов, лучше сначала дать сам символ X, а потом дать его число повторов N. Это, конечно, самый простой прием и он может давать как очень хорошие, так и очень плохие результаты. Рассмотрим таблицу 1 (на след.странице).

QQQQQQQQQQQQQQQQQQQQ AAAAAAAAAAQQQQQQQBBB ABBCCCDDDDEEEEEFFFFF QAQAQAQAQAQAQAQAQAQA

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

Кстати, здесь возникает и еще один интересный смежный вопрос, а сколько разрядов (байтов) отдавать числу повторов?

Простейшее решение - сделать так, чтобы максимальным числом повторов было 255 и тогда на этот параметр уйдет один байт. Но как быть с тем, что нередко количество повторов бывает и больше? Тогда придется записывать число дважды. Например, пусть у нас буква Q повторяется подряд 300 раз. В этом случае результат работы архиватора будет таким:

255,"Q",45,"Q"

Представим себе, что нам надо заархивировать весь экран (6 3/4 килобайтов). Тогда даже при том, что он весь будет чистым, нам все равно придется израсходовать 54 байта

255,0,255,0,255,0...и так 27 раз

А вот если бы мы счетчик повторов выражали бы не одноразрядным числом, а двуразрядным, то в нем можно было бы разместить от 0 до 65535 целых чисел и тогда результат компрессии чистого экрана укладывался бы всего в три байта:

27,0,0

Зато с другой стороны, если бы Вы "нарвались" при таком методе компрессии на последовательность QAQAQAQA.. (таб.1), то получили бы в результате не 20, а 60 байтов - катастрофа!

Можно сколь угодно спорить о том, какой коэффициент повтора лучше. Мы, например считаем, что учитывая особенность "синклеровс-кого" экрана совсем неплох коэффициент повтора 31. Конечно, внимательный читатель может спросить, а какой смысл в таком коэффициенте, если 255 занимает ту же длину, что и 31? Но у числа 31 есть еще в запасе три старших бита и, если крепко подумать и суметь их мудро применить, например в работе со спрайтами или "окнами" , то у коэффициента 31 есть определенное право на жизнь.

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

Но из этой теоремы можно вывести два следствия, одну гипотезу и один вывод.

Следствие 1 (олряшр™*). Всегда можно найти такой файл, на котором Ваш алгоритм будет самым наилучшим .

Следствие 2. Если файл "прогнать" через алгоритм несколько раз, то результат каждого следующего "прогона" после первого будет все хуже и хуже. Проверьте это сами с помощью карандаша и бумаги

Гипотеза. Если Вы прогоняете свой файл через некий компрессор несколько раз и с каждым прогоном результат все хуже и хуже, значит есть вероятность, что компрессор построен на методе RLE.

Вывод. Если Вы разработали метод типа RLE и доказываете своим друзьям, что он лучше, чем чей-то другой, то это говорит о недостаточной математической воспитанности. Нет здесь лучших или худших методов. Есть методы, лучше или хуже приспособленные к конкретным условиям. Один лучше работает с текстами, другой с рыхлой графикой, третий - с плотной графикой , а четвертый - еще с чем-то.

2. Метод Хафмана.

Алгоритм Хафмана основан на том наблюдении, что в большинстве файлов разные символы встречаются с разной частотой и поэтому расходовать на каждый из них по равному количеству памяти (то есть по восемь битов) былб бы расточительностью. Алгоритм так изменяет систему кодирования, что для часто повторяющихся символов можно обойтись одним-двумя битами, правда в качестве расплаты за это приходится отдавать редко встречающимся символам по 10, а то и по 15 и даже по двадцать битов. Поскольку редко встречающиеся символы встречаются по определению редко, то их увеличенная длина оказывает небольшое влияние на размеры файла, зато укороченные часто встречающиеся символы солидно уменьшают его размер.

Проще всего рассмотреть алгоритм Хафмана на простейшем примере, представленном на рис. 1. Предположим, что нам надо заархивировать следующую символьную последовательность: "AAABCCD". Без архивации эта последовательность заняла бы 7 байтов. С архивацией по методу RLE она выглядела бы, как:

3,^иАМ₁"В^и,2,"СМ/0"

то есть возросла бы до 8-ми байтов, а алгоритм Хафмана может сократить ее почти до двух байтов, и вот как это происходит.

Прежде всего, отметим, что разные символы встречаются в нашем тексте по-разному. Чаще всего присутствует буква "А". Можно составить таблицу частот:

А-3 В-1 С-2 D-3

Затем эта таблица используется для создания так называемого двоичного дерева. (Двоичное дерево -это ветвящаяся структура, у которой из каждого узла исходят только две ветви). Это дерево используется для генерации нового сжатого кода:

0 / 1 / А 0 / 1 / С 0 / 1

/ О В

Рис. 1

Левые ветви дерева помечены кодом 0, а правые - 1. Имея такое дерево, легко найти код для любого символа, если идти от вершины к нужному символу. Итак, в нашем случае алгоритм выглядит так:

Если символ равен "А", то ему присваивается двоичный ноль, в противном случае - единица и рассматривается следующий бит. Если символ - "С", то он получит код 10, в противном случае - 11. Если символ равен "О", то его код - 110, в противном случае - 111.

Обратите внимание на то, что хотя в алгоритме Хафмана разные символы будут иметь разную битовую длину, не надо иметь никакого разделителя между символами. Вы можете сами это увидеть, если возьмете любую последовательность нулей и единиц и попробуете декодировать ее с помощью дерева, представленного на рис. 1. Например , последовательность

0001111111010110

даст Вам текст "AAABBCCD".

0 0 0 111 111 10 10 110 AAA В В CCD

а рассмотренный нами выше текст "AAABCCD" займет всего лишь 13 битов (а это меньше двух байтов)

А А А В С С D 0 0 0 111 10 10 110

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

2.1. Замечание-1.

Первая проблема состоит в том, что на разных файлах метод может генерировать разные двоичные деревья. И действительно, Вы понимаете, например, что в русских текстах самая высокая частота повтора у буквы "а" и она будет стоять у вершины дерева и ей будет присвоен код, равный двоичному нулю. А вот в англоязычных текстах, например, самая частая буква - это "е" и этот код будет присвоен ей. А если Ваш файл - не текст, а какая-нибудь арифметическая таблица, то там чаще встречается цифра "ноль", а в файлах графики чаще встречаются коды "О" и "255". Представляете, что будет, если программа-декомп-рессор не будет знать ничего о том, каким двоичным деревом кодировался Ваш файл? Ничего она не разархивирует, так как понятия не имеет каким символам (кодам) соответствуют О, 10, 110, 111 и т.д.

Первое решение приходит в голову просто: в самом начале архивированного файла надо записывать само дерево, с помощью которого проходила архивация. Но здесь сидит ловушка. Ведь если мы архивировали файл длиной 8 байтов и сжали его до 2-х байтов, а теперь к нему приложим справочную таблицу длиной еще байтов 8-10, то ценность от нашей архивации будет отрицательной. Таким образом, на коротких файлах такой метод Хаф-мана ничего не даст и чем длиннее файл, тем лучше будет эффект.

Второе решение может быть, например, таким. Мы можем иметь несколько "стандартных" деревьев. Первое, например, для файлов -экранов. Второе - для англоязычных текстов. Третье - для русскоязычных текстов. Четвертое - для блоков машинного кода и т.д. и т.п. Если эти деревья (таблицы соответствия) достаточно стандартны, то можно таблицу к файлу не прикладывать, а перед сжатым файлом давать один байт, в котором цифра указывает на то, каким методом (по какому дереву архивировался файл).

В этом случае компрессирующая программа может проверить на Вашем файле несколько разных методов, посмотреть, какой будет эффективнее (скорость от компрессора не требуется), припишет к выходному файлу префиксный байт и потом осуществит саму архивацию. Декомпрессирующая программа по первому байту определит каким методом была произведена компрессия и, поскольку таблицы стандартны, произведет декодирование. Этот прием всем хорош, но только сами понимаете, сколько лет может пройти, пока то или иное предложение оформится в качестве общепризнанного стандарта. Хотя в рамках программ одного автора или одной фирмы этим пользовался вполне можно.

2.2. Замечание-2.

В описанном нами алгоритме очень большая проблема связана с определением конца файла. Как декомпрессирующая программа поймет, что файл закончен? Какой маркер поставить в финале?

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

Второй вариант - изящнее. В качестве маркера используется символ, который не может встречаться в файле. Так, например, в текстовых файлах не может быть символов больше 127, поэтому любой такой символ будет маркером конца файла. Но, к сожалению, очень редко можно заранее знать точно, что таких-то или таких-то символов не может быть в файле. Напрймер, если Вы делаете компрессор общего назначения, то он должен работать с чем угодно, а не только с текстами. Как же быть, например, с графикой, в которой возможны любые коды от 0 до 255? В этом случае вводят дополнительный фальшсимвол - 256-ой. Он будет самым редковстречающимся в файле и может быть в нем встречен только один раз. В силу своей редкости, он будет самым длинным и для его записи будет использована весьма длинная битовая последовательность , но поскольку это происходит только один раз, то в этом и нет ничего страшного. Хотя старый принцип остается в действии: "На коротких файлах алгоритм теряет эффективность".

2.3. Замечание-3.

Внимательный читатель мог бы поймать нас и еще на одной нелепице. Рассмотрим наше дерево на рис. 1. В соответствии с ним, мы можем получить таблицу соответствия :

А - О С - 10 D - 110

И если бы мы не закончили с символом "В" (111), а работали бы с набором из многих символов, то получили бы чепуху примерно такую:

4-ый символ - 1110

5-ый символ - 11110

6-ой символ - 111110

Нетрудно догадаться, что 255-й символ имел бы у нас длину в 255 битов (32 байта!!!!), а это свело бы на "нет" все преимущества компрессии.

С этой проблемой нужно расправляться применением какой-то иной системы двоичного кодирования. Оговоримся сразу, что их может быть немало. Вы можете и сами поломать голову, может быть придумаете что-либо интересное. А мы Вам дадим здесь пару вариантов. Один простой и один сложный.

2.3.1. Вариант N1 (простой).

Договоримся, что мы как бы ра-зобъем все символы нашего файла на группы по числу битов в номере символа. И будем строить новое представление двоичного числа из двух половинок. Левая половинка указывает на номер группы Вашего числа - сколько единичек слева, таков и номер группы. Правая половина - указывает на место числа в этой группе. Обратимся к конкретным примерам.

Припер 1. Символ N5. В двоичной форме 5=101. Длина - три бита. Это число из третьей группы, в которую входят числа 4... 7. Порядковый номер числа в группе 001 (номер 000 - у числа 4). В итоге мы имеем следующее новое представление:

5 = 111 001

/ номер группы номер в группе

Пример 2. Символ N10. В двоичной форме 10=1010. Длина - четыре бита. Число из четвертой группы, в которую входят числа 8...15. Порядковый номер в группе - 0010. В итоге имеем следующее представление :

10 » 1111 0010

Пример 3. Символ N44. В двоичной форме 44 ■ 101100 - число из 6-ой группы (от 32 до 63). Порядковый номер в группе - 12-ый, т.е. в двоичной форме - 001100. В итоге получаем следующее представление :

44 » 111111 001100

На запись символа ушло 12 битов. Это и есть наша "расплата" за то, что мы самые частые символы кодировали всего лишь одним битом.

Если Вы внимательно рассмотрели наши примеры, то легко можете сформулировать правило, по которому производится перекодирование из обычной двоичной системы в рассмотренную нами:

1) Берется двоичное число.

2) Первая единица в нем заменяется на "О".

3) Слева к числу приписывается столько единиц, сколько битов в исходном числе.

Теперь посмотрим, как работает декомпрессирующая программа.

Пусть на нее поступила произвольная последовательность битов, например:

110101010001110011111010101010 - всего 30 битов

Количество ведущих единиц указывает на длину двоичного кода. Режем текст по ведущим единицам.

1101,0,10,10,0,0,111001, 11110101,10,10

А теперь вместо двоичных значений поставим порядковые номера символов:

3,0,1,1,0,0,5,12,1,1 - всего 10 символов

Как видите, декодирование происходит вполне однозначно и несложно. Можно и оценить эффективность компрессии - 10 символов у нас хранились в 30 битах (примерно в 4-х байтах). Это очень хорошая эффективность.

Что можно сказать об этой системе?

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

Во-вторых, можно отметить еще одну интересную деталь. Мы теперь можем иметь дело и с 256-ым и с 500-ым и с любым другим символом. Наши коды не ограничены стандартной длиной одного байта и потому мы можем иметь в нашем символьном наборе хоть миллион символов. Поскольку один миллион - это 2 в двадцатой степени, то для записи миллионного символа нам потребуется 2*20=40 битов, то есть всего пять байтов. Может быть, это и расточительно, но ведь на этот "символ" можно подвешивать совсем не только один символ, а целую группу символов. Так, например. Вы можете считать, что часто встречающаяся последовательность "ZX-Spectrum" - это как бы 256-ой символ. Слово "компьютер" 257-ой символ и т.д. и т.п. Вот так и составляются словари в компьютерных играх.

2.3.2. Вариант N2 (рекуррентная система).

Этот вариант модернизации двоичной системы несколько посложнее, чем предыдущий, но у него есть свои преимущества. Так, на больших символьных наборах (от 512 разных символов и выше) этот вариант более эффективен.

Номер символа Представление

Рассмотрим, например, как в этой системе образуется двоичное представление для числа 5.

Все начинается с обычной двоичной формы 5«101. Далее берется первый бит (1), а последние 2 бита (01) откладываются в остаток г [5*] Измеряется длина этого остатка 1(г[5]). Она равна 2 битам. Между первой единицей и остатком записывается рекуррентное представление числа 2 - р{2}.

р(5) = 1 + р{1(г[5])) + г[5] =

= 1 + р(2) + 01

р(2) = 1 + р{1(г[1})> + 0 =

» 1 + р(1) + 0

Р(1) - ю

Итого: р(5)»1 1 10 0 01 * 1110001

Еще один пример рассмотрим для числа 10.

10 DEC - 1010 BIN

р(10) = 1 +p<l(r[10j)> + r[10] -- 1 + р(3) + 010

р(3) - 1 + p{l(r[l])> + 1 =

- 1 + р(1) + 1

р(1) * 10

Итого:р(10)=1 1 10 1 010-11101010

Теперь для числа 17.

17 DEC - 10001 BIN

р(17) - 1 + р(4) + 0001 р(4) ■ 1 + р(2) + 00 р(2) - 1 + р(1) + 0 р(1) - 10

Итого: р(17) = 111100000001

Подведем первые итоги:

Выводы: Вы видите на конкретных примерах (и, кстати, это подтверждается исследованиями математиков), что при малом количестве символов в наборе вариант N1 является более эффективным. Для наборов 128...512 символов эти системы примерно равны и здесь трудно что-то улучшить. Но для очень больших наборов, в которых тысячи кодируемых элементов, по-видимому нет более эффективных систем, чем предложенная здесь рекуррентная система.

3. А что же дальше?

На том, о чем мы рассказали, исследования, конечно, не останавливаются и сейчас в основном исследования идут по двум направлениям. Первое направление - это интеллектуализация архиваторов. Делая несколько проходов по компрессируемому файлу, они выбирают наиболее эффективный алгоритм, пригодный именно для этого файла.

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

Все методы, о которых мы говорили в этой статье выше, дают 100%-ную надежность воспроизведения исходного текста при разархи-вации. Да ведь иначе и нельзя, если имеешь дело с текстом, документом, программой, таблицей и т.п. Но, как оказывается, далеко не все файлы требуют безусловно 100%-ной точности воспроизведения. Так, например, графика во многих случаях может иметь погрешности (шумы), особенно если она взята со сканера или видеокамеры . Звук, музыка тоже могут иметь незначительные погрешности, которые не сильно ухудшают качество материала и не портят впечатления от программы, но позволяют значительно поднять плотность архивации. Обычно в JPEG и MPEG - методах пользователю предоставляется право выбрать, что ему дороже - качество и надежность или объем. Выигрывая в одном, пользователь проигрывает в другом, а оптимум выбирает в соответствии с тем, какая перед ним стоит задача.

Все это сейчас только начинает развиваться и Вы можете сами попробовать придумать что-либо интересное и испытать свои идеи на

"ZX-CneKTpyMe".

* * *

1. К нашим читателям - "Инфорком" поздравляет своих читателей с Новым, 1995 годом.
2. Спектрум в школе - Сегодня мы предлагаем материал, который может пригодиться на уроках информатики. Он поможет при изучении операторов Бейсика PLOT и DRAW.
3. Профессиональный подход - Определение базового адреса релоцируемой программы.
4. Профессиональный подход - Автоматизация создания релоцируемых программ.
5. Профессиональный подход - Архивация, компрессия, сжатие.
6. Профессиональный подход - О введении стардарта на программы для ZX-Spectrum.
7. Возвращаясь к напечатанному - загрузчик для часов.
8. Читатель-читателю - нестандартный загрузчик со счётчиком.
9. Читатель-читателю - Полезные советы.
10. Читатель-читателю - Kempston mouse.
11. Читатель-читателю - несколько устройств для вашего "Спектрума".
12. Читатель-читателю - Опыт работы с "BLAST"
13. Этюды - несколько слов по поводу запуска прерываний 2 рода.
14. Маленькие хитрости - Нюанс в использовании команд переброски.
15. Форум - Сегодняшний ФОРУМ мы начинаем с аппаратного обеспечения.
16. Перекрёсток - Adventure games. Обзоры игр.
17. Ролевые игры - Система правил AD*D (продолжение).
18. Ролевые игры - Проект RPG (продолжение).
19. Советы эксперта - описание игры SHADOWFIRE.
20. Советы эксперта - описание игры DEFENDERS OF THE CROWN.
21. Советы эксперта - описание игры MULTI-PLAYER SOCCER MANAGER.
22. Советы эксперта - описание игры SORCERER LORD.
23. Советы эксперта - описание игры SOLDIER OF FORTUNE.
24. Компьютерная новелла - Мечи и магия (HERO QUEST).
25. Компьютерная новелла - по игре "ZOMBI".
26. Авторская программа. - заявки авторских системных и игровых программ.
27. Реклама. - К нам подключилась большая группа "синклеристов", подписавшихся на первое полугодие ZX РЕВЮ'95 через систему "КНИГА-СЕРВИС".