Архиватор собственными руками! (Часть I)


Устинов Петр Сергеевич (Настройка домашней сети)

Содержание:

Часть первая (текущая страница)

Часть вторая

Исходный текст архиватора (алгоритм Хаффмана)


ПК соткан из нулей и единиц!? Он спрессован из архивов!

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

Когда у меня был компьютер на базе процессора i386 с жестким диском Maxtor объемом в 270 Mbyte, я очень активно пользовался архиваторами, более того, они не всегда помогали и, подчас, приходилось вместо MS Word ставить Lexicon. Это были тяжелые времена. Но и сейчас я не перестаю пользоваться архиватором, хотя проблемы с дисковым пространством навсегда канули в лету. Почему?

Для этого есть целый ряд причин. Перечислю некоторые из них:

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

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

Сейчас, когда производительность CPU увеличилась кардинальным образом, использование сжатия на уровне файловой системы не только не тормозит систему, но и наоборот, ускоряет ее. Если есть объективные причины, тормозящие увеличение пропускной способности дисковой подсистемы, то почему бы не использовать сжатие (возможно, на АППАРАТНОМ уровне)? Объем передаваемых потоков уменьшится, а скорость их передачи по тракту HDD-->IDE Controller-->Шина PCI-->RAM увеличится. С памятью та же ситуация, с той лишь разницей, что увеличение реальной производительности возможно только за счет реализации алгоритмов сжатия на аппаратном уровне (без модификации контроллера памяти здесь не обойтись).

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

Архиватор - от идеи до реализации

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

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

Приведу примеры наиболее интересных в контексте рассматриваемого вопроса ресурсов. Сайт, полностью посвященный технологии сжатия данных: http://escoman.chat.ru. Здесь вы найдете статьи по теории кодирования, описания различных алгоритмов, форматов архивов и исходники с примерами реализаций. Перейдя по ссылке http://books.org.ua/soft/arhvator, можно обнаружить описание большинства алгоритмов и примеры их реализации. Здесь http://www.codenet.ru вы можете почитать статьи по истории и теории кодирования и описание различных алгоритмов сжатия, как с потерей, так и без потери качества. Здесь же вы обнаружите тематическую конференцию и сможете задать вопросы по реализации того или иного алгоритма. Интересен сайт Андрея Зайчикова http://andrey.nnov.ru, целью которого является помощь студентам и начинающим программистам. Здесь вы найдете много интересных статей по технологии программирования. А если вы обладаете писательским даром, то сможете заслужить признание посетителей сайта, опубликовав один из ваших трудов. Наиболее интересна статья Михаила Сваричевского "Сжатие данных".

Если вы посетили все эти ресурсы, но так и не вдохновились идеей написания собственного архиватора, то я предприму еще одну попытку :).

Способ представления информации в ПК

Для начала следует уяснить, что в памяти машины (на диске или в ОЗУ) данные хранятся в виде последовательности нулей и единиц. Каждая минимальная ячейка файла содержит нуль или единицу. Разберемся, что нам, пользователям, может говорить эта бесконечная череда циферок?

Изначально вся пользовательская информация ограничивалась только текстами. Тексты состоят из символов. Посчитаем количество символов, необходимых для того, чтобы писать разнообразные тексты. Прежде всего, наш национальный алфавит (кириллица). Добавим латиницу, знаки пунктуации, цифры, знаки математических операций, символы №, #, @, % и пр. Плюс ко всему символы псевдографики, предназначенные для рисования таблиц в тексте и некоторые другие. В итоге мы получили "виртуальный алфавит", содержащий немногим более двухсот элементов.

Но как сохранить текст, написанный в таком большом алфавите, если компьютер может "запоминать" только нули и единицы? Минимальная ячейка (бит) может принимать два значения - 0 и 1. Если взять две такие, идущие друг за другом, ячейки, то эта пара может принимать 4 значения: "00", "01", "10", "11". Возможно, вы уже догадались, что если брать наборы из n минимальных ячеек (бит), то число всевозможных значений такого набора увеличивается и будет равно степени двойки с показателем n. Т.е. если группируем два бита, то число возможных вариантов 2^2=4; если три бита, то вариантов значений этой группы восемь (2^3): "000", "001", "010", "011", "100", "101", "110", "111" и так для любого количества бит в группе.

Мы хотим подобрать такое число бит, группа из которых может принимать как минимум около двухсот значений (каждое из значений мы отождествим с символом нашего алфавита). Минимальная степень двойки, превосходящая количество элементов "виртуального алфавита" - восьмая (2^8=256). Иными словами, сгруппировав биты по восемь штук, мы сможем каждому значению такого набора бит (всего таких значений 256) сопоставить свою букву, как, впрочем, и было сделано в стандарте ASCII. Именно поэтому вся память ПК разделена на байты - группы по восемь бит. Кстати, именно поэтому первые массовые процессоры были восьмиразрядными (карьера Билла Гейтса началась с внедрения интерпретатора языка Basic для систем, построенных на базе восьмиразрядного процессора 8080).

Идея кодирования со сжатием

Теперь давайте подумаем как же и на чем можно экономить место при сжатии файлов. В некоторых файлах встречаются довольно длинные подцепочки одинаковых байтов. Представьте себе такой файл:

aaaaabbbccccccccccccccadddddddddddddddd{end of file}.

Файл занимает на диске 39 Byte. Очевидно, что информация в файле несколько избыточна и хранение файла в таком виде не оправдано. Совсем другое дело, если файл будет выглядеть так:

5a3b14ca16d{end of file}.

В таком случае файл будет занимать всего 11 byte. В итоге файл можно записать экономичнее в 39/11=3,5 раза. На этом же примере можно описать еще один способ экономии дискового пространства. Как видно файл состоит всего из четырех символов. Если сопоставить каждому из них пару битов, то получим:

a - "00",
b - "01",
c - "10",
d - "11".

Иными словами файл можно закодировать таким образом, что каждый из символов будет кодироваться не восемью, а двумя битами. И тогда экономия будет четырехкратной (8/2=4). Следует заметить, что этот вариант алгоритма более общий и одинаково эффективен даже если в файле нет ни одной однородной подцепочки. Заметьте, что для применения такого алгоритма качественный состав представленных в файле байт должен быть неполным. Например, если в файле представлены 200 разных символов, то для однозначной идентификации каждого из них придется использовать все восемь бит (семи не хватит, так как комбинации из семи бит могут принимать 2^7=128 значений), что не позволит достичь никаких результатов при применении этого способа сжатия.

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

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

Алгоритм Хаффмана

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

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

Можно представить, что все файлы - это тексты, написанные в алфавите, состоящем из 256 букв (так оно на самом деле и есть). Рассмотрим все множество файлов, размер которых не превышает n byte (где n произвольное число). И допустим, что существует некий алгоритм кодирования, который любой из этих файлов сжимает с "положительной" эффективностью. Тогда множество всех их архивов содержится во множестве всех файлов, размер которых МЕНЬШЕ n byte. Согласно нашему предположению существует взаимно-однозначное (биективное, как сказали бы математики) соответствие между двумя конечными множествами, число элементов в которых не совпадает. Чего быть не может (так называемый принцип Дирихле; да, сказывается математическое образование). Отсюда можно сделать довольно значимые выводы: 1) не существует архиватора, который бы одинаково хорошо паковал любые файлы, 2) для любого архиватора найдутся файлы, в результате сжатия которых будут получаться архивы в лучшем случае не меньшего размера, чем исходные файлы.

Теперь приступим к описанию алгоритма Хаффмана. Рассмотрим его на примере следующего файла:

cccacbcdaaabdcdcddcddccccccccccc{End of file}

Распишем частоты каждого из символов:

a - 4,
b - 2,
c - 19,
d - 7.

Весь файл занимает 32 byte. Каждый из символов в исходном файле кодируется согласно таблице ASCII восемью битами:

a - 01100001,
b - 01100010,
c - 01100011,
d - 01100100.

Шаг №1. Расположим эти четыре символа в порядке убывания их частот:
{(c,19), (d,7), (a,4), (b,2)}

Шаг №2. На следующей строке запишем набор, полученный из предыдущего следующим образом:

Шаг №3. Переходим на шаг №2 до тех пор, пока набор не будет состоять только из одного элемента: ("вершина #last_number", summa_vseh_chastot):
{(c, 19), ("вершина #2", 13)}
{("вершина #3", 32)}

Что же в итоге? Посмотрите на рисунок. Вы видите дерево, растущее с листьев! Если соединять чертой каждый из элементов "вершина #x" с теми элементами предшествующих наборов, сумма частот которых хранится во второй части элемента "вершина #x", то мы получим своего рода дерево (в программировании подобные структуры называются бинарными деревьями).

Смысл этой древесной структуры состоит в том, чтобы каждому из символов сопоставить различное число бит в зависимости от его частоты (как мы уже говорили, в несжатом файле символы хранятся в виде групп по восемь бит). Если внимательно всмотреться в следующий рисунок, вы увидите, что каждая из ветвей помечена либо нулем, либо единицей. Таким образом, если мысленно пройтись по дереву от корня до какой-либо вершины, содержащей символ, то последовательность нулей и единиц, встречающихся у вас на пути, и будет новой комбинацией бит для этого символа. Например, символ "c" как наиболее часто встречающийся будет кодироваться одним битом "0", символ "d" двумя битами "10" и т.д.

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

ddddddaaaaaabbbbbbccccdffffffffffdddd{37 byte, end of file}

В двоичном виде файл будет выглядеть так:

01100100 01100100 01100100 01100100 01100100 01100100 01100001 01100001 01100001 01100001 01100001 01100001 01100010 01100010 01100010 01100010 01100010 01100010 01100011 01100011 01100011 01100011 01100100 01100110 01100110 01100110 01100110 01100110 01100110 01100110 01100110 01100110 01100110 01100100 01100100 01100100 01100100{296 bit, end of file}

Распишем частоты каждого из символов:

a - 6
b - 6
c - 4
d - 11
f - 10

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

1. {(d,11), (f,10), (a,6), (b,6), (c,4)};
2. {(d,11), (f,10), (вершина #1, 10), (a,6)} (заметьте, сортировка по убыванию частот обязательна!);
3. {(вершина #2, 16), (d,11), (f,10)};
4. {(вершина #3, 21), (вершина #2, 16)};
5. {(вершина #4, 37)}

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

a - "11"
b - "100"
c - "101"
d - "00"
f - "01".

В двоичном виде файл будет выглядеть так:

00000000 00001111 11111111 10010010 01001001 00101101 10110100 01010101 01010101 01010000 0000хххх{88 bit, end of file}

Сжатый файл занял 11 байт (последние четыре бита xxxx записываются произвольно, ведь весь файл на самом деле умещается в 84 бита, что не кратно восьми). Коэффициент сжатия при таком кодировании равен 3,5.

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

Метод арифметического кодирования

Если метод Хаффмана состоит в представлении символов в виде целого числа бит, то метод арифметического кодирования позволяет максимально эффективно использовать частотные характеристики символов за счет замены исходных байтов рациональным (дробным) числом бит. Рассмотрение данного алгоритма выходит за рамки данной статьи. Однако в качестве домашнего задания я могу сформулировать для вас следующую задачу: попробуйте реализовать метод арифметического кодирования, основываясь на материалах из internet. Редакция журнала "Магия ПК" и автор настоящей статьи будут рады рассмотреть любое решение этой задачи, и, возможно, статью по данной тематике.

Продолжение статьи


Главная страница.

Hosted by uCoz