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

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

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

Алгоритм: история

Первым алгоритмом, предназначенным для проведения эффективного кодирования электронной информации, стал код, предложенный Хаффманом в 1952 году. Именно этот код на сегодняшний день можно считать базовым элементом большинства программ, разработанных для сжатия информации. Одними из наиболее популярных источников, которые используют данный код, на сегодняшний день являются архивы RAR, ARJ, ZIP. Данный алгоритм также используется для сжатия изображений JPEG и графических объектов. Также во всех современных факсах используется алгоритм кодирования, который был изобретен еще в 1952 году. Несмотря на то, что со времени создания данного кода прошло достаточно много времени, его эффективно используют в оборудовании старого типа, а также в новом оборудовании и оболочках.

Принцип эффективного кодирования

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

Код Хаффмана: пример

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

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

Дерево Хаффмана: алгоритм построения

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

Как повысить эффективность сжатия

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

Как ускорить процесс сжатия

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

Вывод

Коды Хаффмана представляют собой простой и давно разработанный алгоритм, который по сей день используется во многих популярных программах. Простота и понятность данного кода позволяет добиться эффективного сжатия файлов любых объемов.