О сжатии информации

Что такое информация? Как сжимают информацию? На compression-pointers.com — сотни ссылок, а на act.by.net — сотни программ-компрессоров. Что в них, о чем они — все эти стандарты, методы, алгоритмы, программы?

Все достаточно просто. Но сначала — несколько определений. Бит — это «атом» цифровой информации: представим себе небольшой «ящик» где-то в пространстве-времени (в микросхеме, на магнитном/оптическом диске, линии связи) со всего лишь двумя возможными состояниями: полный (1, единица, да, истина, существует) и пустой (0, ноль, нет, ложь, не существует). Конечную последовательность битов назовем кодом. Байт (традиционный) — это последовательность восьми битов. N-битный (обобщенный) байт — последовательность N битов — имеет 2^N (два в степени N) возможных значений-состояний (таким образом, традиционный 8-битный байт может принимать 256 разных значений: 0, 1, ..., 255). Конечную последовательность байтов назовем словом, а количество байт в слове — длиной слова. В общем случае слово построено из N-битных, а не из 8-битных байтов (таким образом, код — это слово из 1-битных байтов).

Что же такое «символ» в данном случае? Ведь именно это слово фигурирует в многочисленных международных патентах о методах и устройствах для сжатия информации. Символ — это «атом» некоторого языка (например, буква, цифра, нота). ASCII (американский стандарт) ставит символ в соответствие каждому значению 8-битного байта. Но чтобы построить соответствие для всех символов из множества национальных алфавитов народов мира, необходимо больше: 16 бит на символ (стандарт UNICODE).

И последнее определение: сжатием конечного объема цифровой информации (блока) называется такое его описание, при котором создаваемый сжатый блок содержит меньше битов, чем исходный, но по нему однозначно восстановим каждый бит исходного блока. Так называемое сжатие с потерями (lossy compression) — это два разных процесса: выделение сохраняемой части из блоков информации — создание модели, зависящей от цели сжатия и по возможности улучшающей степень последующего сжатия, — и собственно сжатие (lossless compression).

Чем отличаются эти определения от ныне существующих? С незапамятных времен, когда 8-битных процессоров было больше, чем 16-битных, а в UNICODE не было необходимости, символом чаще всего стали называть байт, а байтом — последовательность восьми битов. Последовательность двух байтов компьютерный мир называет словом (Word), а четырех — двойным словом (Dword). Однако очень многие процессоры (остальные, x86-несовместимые) устроены так, что в каждой адресуемой ячейке памяти лежит 16- , 24- или 32-битный байт, а вовсе не 8-битный, как во всех IBM-совместимых ПК. Если «сжатый» файл длиннее исходного — то это перекодирование, но не сжатие по определению, вопреки «мнению» многих сжимающих программ (паковщики, компрессоры, архиваторы), в том числе RAR32 для DOS и OS/2. Если сжатие с потерями не содержит функций истинного сжатия, то это удаление информации, несущественной для заданной цели, в рамках принятой модели. Впрочем, определений понятий «сжатие», а особенно «код» существует столько, что недоразумений возникает куда больше, чем хотелось бы.

Теперь, с такими четкими определениями, кажется достаточно очевидным следующее:

1. Каждый из методов сжатия создан или для сжатия блоков битов, или блоков байтов, или блоков слов — потому что это очень разные объекты. Можно создать четкие математические определения для этих трех базовых видов цифровой информации, но ясно и без формул: сжимая заданный блок, метод сжатия «думает» о нем одно из трех: а) вероятности битов различны и зависят от их значения; б) вероятности появления байтов различны; в) вероятности разных слов неодинаковы.

2. Заданный блок сожмется лучше, если известна его структура:

а) это блок слов из N-битных байтов;

б) это блок N-битных байтов;

в) это блок битов.

А также, разумеется, если известен «ответ»: как, по каким закономерностям блок был создан, какой длины были записи-байты, как они формировались. Иначе говоря, чем точнее процесс сжатия учитывает процесс создания блока, тем лучше сжатие. А создаваемые блоки принадлежат, как правило, одному из этих трех базовых видов: биты, байты, слова. Можно добавить и еще два «граничных» вида: нулевой — «хаос» (невозможно обнаружить никаких закономерностей — ни для битов, ни для байтов, ни для слов) и четвертый — «тексты» (последовательности слов) появляются по некоторому правилу. Например, блок содержит русские предложения, английские и тексты функций на языке C. Другие виды (например, смесь хаоса и байтов или битов и слов) встречаются существенно реже.

3. В каждом из трех случаев возможны два варианта:

а) вероятности элементов (битов, байтов, слов) различны и не зависят от непосредственно предшествующих («контекста»);

б) вероятности элементов (битов, байтов, слов) различны и сильно зависят от непосредственно предшествующих.

Промежуточные случаи столь редки, что ими можно пренебречь. Видно, что случай, когда вероятности байтов различны и зависят от контекста, идентичен случаю, когда вероятности слов различны и не зависят от контекста, а вот другие — не идентичны. Связано это с тем, что по определению конечная последовательность байтов — это слово, а битов — код, а не байт. Иначе говоря, байт — это запись фиксированной длины, а слово — произвольной.

4. Для упрощения структуры данных:

1) сжимая блоки слов, лучше создавать блоки байтов и/или битов;

2) сжимая блоки байтов — создавать блоки битов, и только;

3) сжимая блоки битов — конечный сжатый блок, несжимаемый «хаос».

По некоторым причинам большинство современных программ-компрессоров просто пропускает третий этап (сжатие блоков битов), или «склеивают» его со вторым (сжатие блоков байтов), начиная процесс с предположения: задан блок слов. И только архиваторы с опциями для мультимедийного сжатия проверяют, не блок ли это байтов. Поэтому принято говорить в терминах «первичного» и «вторичного» сжатия: сначала — моделирование или сортировка (тасование байтов), затем — encoding (дожатие) байтов в коды. Например, как справедливо пишут в учебниках для школьников, все первые архиваторы (ARC, ARJ, LHA, PAK, ZIP и т.д.) использовали LZ77 или LZ78 с последующим дожатием методом Хаффмена или Шеннона.

Что же это за причины? Во-первых, большинство «природных» данных, появляющихся в компьютерах с устройств ввода (клавиатура, сканер, микрофон, видеокамера), — это действительно блоки слов (в общем случае не 8-битных байтов: современные графические устройства оперируют 24- или 32-битными байтами — «пикселами», а аудио — 8- , 16- или 32-битными «сэмплами»). Также и исполнимый код для процессора (файлы .exe, .dll и т.д.) — блоки слов. Блоки байтов и битов появляются, как правило, лишь при компьютерной обработке этих «природных» данных. Таким образом, основная задача сжимающего алгоритма — выяснить, как были построены слова блока, по каким правилам-закономерностям. Именно «первичный» алгоритм играет решающую роль в достижении приемлемого качества сжатия, близкого к мировому рекорду (на заданных файлах, act.by.net).

Во-вторых, компьютерам гораздо легче оперировать с байтами, чем с битами. Каждый байт имеет свой адрес в памяти, каждый адрес указывает на один байт (8-битный, если это обычный IBM-совместимый компьютер). Всего лишь 20 лет назад появились первые 16-битные процессоры, способные обрабатывать больше чем 8 бит одной инструкцией. В-третьих, известных алгоритмов для сжатия блоков битов практически нет (по первым двум причинам). Прекрасные результаты дают правильные первичные и вторичные алгоритмы сжатия, а третий шаг занимает много времени, но мало улучшает качество сжатия.

Около 10 лет назад, когда разрабатывался «универсальный» формат .zip, почти все тексты были блоками 8-битных ASCII-символов, исполнимые модули — для 16- или 8-битных процессоров, а большинство мультимедийных файлов — графических и звуковых — блоки 8- или 4-битных байтов. Поэтому вполне достаточно было иметь один алгоритм для всех данных: и слов, и 8-битных байтов. С тех пор было создано много специальных алгоритмов для конкретных типов данных, но мало универсальных программ, дающих результаты, близкие к мировым рекордам, на всех типах данных.

Какие методы сжатия общеизвестны сейчас? Для блоков слов или байтов — LZ77, LZ78, LZW и другие варианты «скользящего окна», полная (BWT) и частичная сортировка (по последним P-символам), PPM, Марковы и другие моделирования. Для байтов — MTF, методы Хаффмена, Шеннона-Фэно, для байтов или битов — RLE и арифметическое кодирование со всеми модификациями.

Что можно сказать о статическом и динамическом кодировании? В те «доисторические» времена, когда компьютеры были большими, а файлы — маленькими, проблемы выделения в заданном файле логически разных фрагментов не возникало. Во-первых, относительно меньше было файлов с разнородными данными, да и самих типов данных было поменьше: размерность байтов редко достигала даже 24 и тем более 32 или 64 (4-канальный звук с 16-битным качеством). Во-вторых, сами логически разные подфрагменты были столь малы, что издержки на описание границ подфрагментов были сравнимы с выигрышем в случае их использования. На запись нового бинарного дерева (методы Хаффмена или Шеннона-Фэно; 8-битные байты) требуется порядка 100 байтов, к тому же сложность и время работы метода могут увеличиться почти вдвое — поэтому обращать внимание на фрагменты короче килобайта не имеет смысла. Тем более если средний размер файла — 100 Кбайт, а вероятность того, что записи в нем совершенно разные, — менее процента. Сейчас с этим иначе: и средний размер в десяток раз больше, и вероятность разнородности фрагментов файла — примерно во столько же. Теоретически любой алгоритм сжатия можно сделать как «совсем статическим» (все параметры жестко заданы изначально), так и «совсем динамическим» (все параметры периодически перевычисляются). Но практически, произнося слова «статический» или «динамический», имеют в виду самый первый алгоритм, описанный Хаффменом в 1952 году.

Как выяснить, что содержит заданный файл: блок битов, байтов или слов? В основном в файлах лежат блоки слов, 8- или 16-битных, а мультимедийные, аудио- , видео-, графические файлы — блоки 8-, 16-, 24- или 32-битных байтов. Поэтому самый простой способ — посмотреть расширение файла, или заголовок, или, протестировав несколько килобайт, выбрать метод, лучший на этом фрагменте. Незачем применять алгоритмы, хорошие для блоков слов, к байтам или битам, а созданные для сжатия байтов — к битам или словам.

Кроме этого, простейшего, существуют ли и другие методы? Следующий способ сложнее и занимает больше времени.

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

Тогда, предположив, что заданный блок — слова, применим к нему первый алгоритм и вычислим первую величину — W, затем предположим, что в блоке — байты, и получим второе значение — Y; наконец, вычислим третью меру — B, применив третий алгоритм. Сравнивая полученные три числа — W, Y, B (их значения лежат в интервале от нуля до единицы), легко видим, чему больше соответствует изучаемый блок. Если же допустить, что байт может быть еще и 16- или 32-битным, необходимо вычислять три величины для байтов и три — для слов, то есть всего — семь.

Похоже, все три алгоритма действуют примерно одинаково, но с разными элементами — битами, байтами и словами? Именно так. В простейшем случае, если элементы — биты и если алгоритм предварительно разбивает заданный блок битов на логически разные фрагменты (то есть, к примеру, случай «сто нулей, затем сто единиц», рассматривается как два «хороших», а не как один «плохой»):

B = ( |n1 — N/2| + |n0 — N/2| ) / N,

где N — число битов в блоке, n1 — число единиц, n0 — число нулей.

Легко видеть, что B = 0, если n1 = n0 = N/2 ; B = 1, если n1 = N или n0 = N.

Аналогичный тривиальный пример для случая 8-битных байтов:

Y = ( |n255–N/256| + ... + |n0–N/256| ) x 128 / (N x 255)

Y = 0, если n255 = ... = n0 = N/256; Y = 1, если n255 = N или n254 = N ... или n0 = N.

Довольно просто для битов и байтов, но как быть со словами, если их длина 3, 4, ..., L, а L — порядка десяти, сами же слова могут быть составлены из 16- , 24- или 32-битных байтов? Как в любом исследовании: идеи, допущения, моделирование, тестирование, оптимизация... Поиск более эффективного алгоритма — процесс очень увлекательный и даже азартный.