Метод сжатия хаффмана


Содержание

Всё о сжатии данных, изображений и видео

Сравнения кодеков

Проекты

Разделы

Сайт подключен к Orphus. Если вы заметили опечатку, выделите слово и нажмите Ctrl+Enter. Спасибо!

Динамическое сжатие методом Хаффмана

Данная статья предполагает, что читатель знаком с принципами сжатия данных при помощи алгоритма Хаффмана. Суть алгоритма заключается в том, что символы почти любого алфавита имеют разную вероятность появления в тексте. Для примера — в русском языке буква «А» встречается намного чаще, чем «Ъ». А у Александра Сергеевича Пушкина — «Ф» — встречается всего три раза: дважды в «Сказке о царе Салтане» и один раз в «Медном всаднике». Итак, раз разные символы имеют разные вероятности появления, следовательно, если кодировать их не все по 8 бит, как они хранятся в ASCII формате, а длину кода наиболее часто встречаемых уменьшить за счёт увеличения длины кода редких символов — можно довольно неплохо сжать исходный текст. Документации по этому алгоритму в Интернете целое море и ещё небольшая лужица размером с океанчик.

Различия статической и динамической моделей

Практически все существующие алгоритмы сжатия данных можно реализовать в двух вариантах — статическом и динамическом. Каждый из них имеет своё право на жизнь и, соответственно, занимает определённую нишу, используясь в тех случаях, когда он наиболее удобен. Алгоритм Хаффмана не является исключением — применяясь во многих и многих архиваторах и форматах он используется иногда в статическом (JPEG, ARJ) или в динамическом (утилита compact для UNIX, ICE) вариантах.

В чём же заключается различие между этими двумя типами реализаций? Так как алгоритм Хаффмана сжимает данные за счёт вероятностей появления символов в источнике, следовательно для того чтоб успешно что-то сжать и разжать нам потребуется знать эти самые вероятности для каждого символа. Статические алгоритмы справляются с этим делом не мудрствуя лукаво — перед тем как начать сжатие файла программа быстренько пробегается по самому файлу и подсчитывает какой символ сколько раз встречается. Затем, в соответствии с вероятностями появлений символов, строится двоичное дерево Хаффмана — откуда извлекаются соответствующие каждому символу коды разной длины. И на третьем этапе снова осуществляется проход по исходному файлу, когда каждый символ заменяется на свой древесный код. Таким образом статическому алгоритму требуется два прохода по файлу источнику, чтоб закодировать данные.

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

Ниже представлены алгоритмы работы статического и динамического архиваторов кодами Хаффмана.

Статический алгоритм:
InitTree ‘ Инициализируем двоичное дерево
For i=0 to Ubound(CharCount)
CharCount(i)=0 ‘ Инициализируем массив частот элементов алфавита
Next
Do While not EOF( Файл источник ) ‘ Запускаем первый проход файла
Get Файл источник , C ‘ Читаем текущий символ
CharCount(C)= CharCount(C)+1 ‘ Увеличиваем на один частоту его встречаемости
Loop
ReBuildTree ‘ По полученным частотам строим двоичное дерево
WriteTree ( Файл приёмник ) ‘ Записываем в файл двоичное дерево
Do While not EOF( Файл источник ) ‘ Запускаем второй проход файла
Get Файл источник , C ‘ Читаем текущий символ
code=FindCodeInTree(C) ‘ Находим соответствующий ему код в дереве
Put Файл приёмник , code ‘ Записываем последовательность бит в файл
Loop

Процедура InitTree инициализирует двоичное дерево, обнуляя значения, веса, и указатели на родителя и потомков текущего листа. Далее выполняется первый проход по источнику данных с целью проверки частотности символов — результаты которого запоминаются в массив CharCount. Размерность этого массива должна равняться количеству элементов алфавита источника. В общем случае, для сжатия произвольного компьютерного файла, его длина должна составлять 256 элементов. Затем, в соответствии с полученным набором частот строим двоичное дерево ReBuildTree. Во время второго прохода, перекодируем источник в соответствии с деревом и записываем получаемые последовательности бит в сжатый файл. Для того, чтоб потом возможно было восстановить сжатые данные — необходимо, также, в полученный файл, сохранить копию двоичного дерева WriteTree.

Динамический алгоритм:
InitTree ‘ Инициализируем двоичное дерево
For i=0 to Ubound(CharCount)
CharCount(i)=0 ‘ Инициализируем массив частот элементов алфавита
Next
Do While not EOF( Файл источник ) ‘ Запускаем проход файла
Get Файл источник , C ‘ Читаем текущий символ
If C нет в дереве then ‘ Проверяем встречался ли текущий символ раньше
code= Код «пустого» символа & Asc(C) ‘ Если нет, то запоминаем код пустого листа и ASCII код текущего символа
else
code= Код C ‘ Иначе запоминаем код текущего символа
End if
Put Файл приёмник , code ‘ Записываем последовательность бит в файл
ReBuildTree(С) ‘ Обновляем двоичное дерево символом
Loop

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

Динамический алгоритм сжатия Хаффмана

Динамическое сжатие методом Хаффмана было предложено независимо Фоллером [1973] и Галлагером [1978]. В 1985 Дональд Кнут разработал окончательный усовершенствованный вариант алгоритма — вследствие чего алгоритм получил название FGK (Faller, Gallager, Knuth) алгоритма. Основным принципом FGK алгоритма — является свойство «братства». Двоичное дерево обладает данным свойством, если каждый его узел (за исключением корневого) имеет в дереве узла «брата» и, при расположении всех узлов в списке, в порядке неувеличения их весов, узлы «братья» находятся по соседству. «Братьями» назовём два узла, которые имеют общего родителя.

Например, для указанного дерева, при выписывании узлов в требуемый список — получаем:

Уз3 Уз2 Уз1 Г В Б А
9 5 4 3 2 2 2

Где верхний ряд означает узел дерева, а нижний его вес. Таким образом выясняем, что данное дерево обладает свойством «братства», так как каждый, кроме корневого, узел имеет «брата» и все узлы «братья» находятся в списке по соседству < А - Б >, < В - Г >, . Листья такого дерева представляют собой символы извлекаемые из исходного файла, а веса листьев — количество появлений этих символов в исходном файле. По мере прохождения алгоритма через файл веса листьев могут либо увеличиваться, либо оставаться без изменений.

Первоначально дерево состоит из одного «пустого» узла. Этот узел является единственным листом, который не содержит никакого символа и имеет нулевой вес. Он предназначается для кодирования тех символов, которые ранее не попадали во входной поток. Далее, по мере поступления на вход программы архиватора символов из исходного файла, проверяется, есть ли уже такой символ в дереве или нет. Если символ присутствует — его код передаётся сжатому файлу, затем его (и всех его родителей) вес инкрементируется и дерево пересчитывается по новой. При отсутствии символа в дереве — в сжатый файл передаётся код «пустого» символа, следующие за которым биты содержат информацию однозначно определяющий новый символ (чаще всего это ASCII код). После чего в дерево добавляется ещё один лист, который содержит новый символ и имеет вес 1. Инкрементируются веса всех родителей новоиспечённого узла. Снова пересчитываем дерево.

Так как «пустой» узел имеет вес 0, то при пересчёте дерева он всегда будет иметь самый длинный код. Следовательно, каждый появившийся новый символ будет иметь код равный по длине коду «пустого» узла или меньший его на 1 бит. Благодаря чему самые редковстречаемые символы, которые будут, соответственно, позже появляться — будут иметь самые длинные коды — что полностью соответствует принципам алгоритма сжатия Хаффмана.

Принципы построения основных процедур

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

От процедуры ReBuildTree во многом зависит быстродействие программы архиватора, так как именно она должна после каждого поступившего символа заново перестраивать двоичное дерево кодов. Самый простой и надёжный способ — конечно же полное построение дерева — однако в этом случае алгоритм будет настолько медленным, что при архивации даже самого маленького файла можно будет успеть выпить пару чашек кофе и немножко вздремнуть. Полное построение двоичного дерева — довольно большая и нелёгкая работа даже для современных компьютеров. Но выход всё-таки есть! Вспомним, что мы пользуемся для сжатия данных FGK алгоритмом, который обладает свойством «братства». Согласно правилам, при расположении всех узлов в списке, в порядке неувеличения их весов, узлы «братья» находятся по соседству. Откуда следует, что вместо того, чтоб постоянно полностью модифицировать всё дерево можно хранить его в виде упорядоченного списка и изменять только те элементы списка, которые требуют изменения.

Для рассмотренного выше дерева упорядоченный список представлял собой:

Уз3 Уз2 Уз1 Г В Б А
9 5 4 3 2 2 2

Теперь, если очередным символом во входящем потоке будет символ «Г«, тогда увеличиваем его вес на 1. Очевидно, что вес родителя Уз2 теперь не соответствует сумме весов потомков, поэтому его тоже следует инкрементировать. Увеличив вес узла Уз2 — переходим к его родителю — корню дерева Уз3, вес которого так же увеличивается на 1. Новый список теперь будет иметь вид:

Уз3 Уз2 Уз1 Г В Б А
10 6 4 4 2 2 2

А дерево соответственно станет:

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

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

Уз3 Уз2 Уз1 Г В Б А
11 7 4 5 2 2 2

Как видно свойство упорядоченности нарушено. Символ «Г» вес которого больше чем вес Уз1 стоит раньше него в списке. В таком случае необходимо произвести операцию упорядочивания списка. Для этого после инкрементации веса символа начинаем двигаться по списку, в сторону увеличения веса, до тех пор пока не найдем последний узел с меньшим весом чем текущий. Затем переставляем текущий и найденный узлы восстанавливая таким образом порядок в списке. При этом родители обоих узлов тоже изменяются. Родителем текущего узла становится родитель найденного и наоборот. Дальше увеличивается вес нового родителя и так далее, до самого корня дерева. Новый список уже будет выглядеть следующим образом:

Уз3 Уз2 Г Уз1 В Б А
10 6 5 4 2 2 2

А дерево соответственно:

Из приведённого примера видно, что чем чаще встречается тот либо иной символ, тем ближе он находится к началу списка и короче код имеет. В последнем двоичном дереве самый часто встречаемый символ «Г» имеет самый короткий код — 1 бит.

В общем виде алгоритм модификации дерева можно записать так:

Public Sub ReBuildTree ( Символ as Byte)
ТекущийУзел = ЛистСоответствующий ( Символ ) ‘ Находим в дереве лист соответствующий символу
Do While True
ТекущийУзел.Вес = ТекущийУзел.Вес + 1 ‘ Увеличиваем его вес на 1
If ТекущийУзел = КореньДерева then ‘ Является ли текущий узел корнем дерева
Exit Do ‘ Если да, то заканчиваем процедуру обновления
else
if ТекущийУзел.Вес > ( ТекущийУзел +1) .Вес ‘ Проверяем не нарушена ли упорядоченность
i=1
Do While ТекущийУзел.Вес > ( ТекущийУзел +i) .Вес
i=i+1
Loop
Перестановка ТекущийУзел , ТекущийУзел +i ‘ Если упорядоченность нарушена, то восстанавливаем её путём обмена узлов
End if
ТекущийУзел = ТекущийУзел.Родитель ‘ Переходим к родителю текущего узла
End if
Loop
End sub

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

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

Уз1 А
1 1 0

Например, при имеющемся двоичном дереве с одним символом «А» и нулевым узлом, если следующим символом поступающим из файла источника является «Б» необходимо добавить его в список.

Уз1 А Уз2 Б
2 1 1 1 0

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

Public Sub AddNode ( Символ as Byte)
Создать( НовыйУзел ) ‘ Создаём новый узел дерева
Создать( НовыйЛист ) ‘ Создаём новый лист дерева (для символа)
НовыйУзел.Родитель = ПустойЛист.Родитель ‘ Родителем нового узла делаем родителя пустого символа
ПустойЛист.Родитель = НовыйУзел ‘ Делаем новый узел родителем пустого
НовыйЛист.Родитель = НовыйУзел ‘ Делаем новый узел родителем нового листа
НовыйУзел.Вес =0 ‘ Присваиваем новому узлу нулевой вес
НовыйЛист.Вес =0 ‘ Присваиваем новому листу нулевой вес
НовыйЛист.Символ = Символ ‘ Запоминаем в листе символ, ради которого его создавали
ReBuildTree( Символ ) ‘ Обновляем двоичное дерево
End Sub

Инициализация дерева, процедура InitTree, представляет собой ни что иное, как просто создание «пустого» символа. В самом начале упорядоченного списка. Так как при начале кодирования дерево не содержит ни одного символа, то «пустой» символ не смотря на свой нулевой вес будет первым и единственным и при обращении к нему выдаст в поток однобитный код 0.

Заключение

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

Сайт подключен к Orphus. Если вы заметили опечатку, выделите слово и нажмите Ctrl+Enter. Спасибо!

АЛГОРИТМЫ СЖАТИЯ

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

Адаптивное сжатие Хаффмана

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

Декодер в адаптивной схеме работает аналогичным образом:

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

Адаптивное кодирование Хаффмана

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

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

Здесь W – вес узла, N – порядковый номер в списке узлов.

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

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

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

Если и дальше продолжать обрабатывать увеличение веса, двигаясь к корню дерева, то наше дерево перестанет быть деревом Хаффмана. Чтобы сохранить упорядоченность дерева кодирования, алгоритм работает следующим образом. Пусть новый увеличенный вес узла равен W+1. Тогда начинаем двигаться по списку в сторону увеличения веса, пока не найдем последний узел с весом W. Переставим текущий и найденный узлы между собой в списке, восстанавливая таким образом порядок в дереве.

При этом родители каждого из узлов тоже изменяются. На этом операция перестановки заканчивается. После перестановки операция увеличения веса узлов продолжается дальше.

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

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

Проблемы адаптивного кодирования

Хорошо было бы, чтобы кодер не тратил зря кодовое пространство на символы, которые не встречаются в сообщении. Если речь идет о классическом алгоритме Хаффмана, то те символы, которые не встречаются в сообщении, уже известны до начала кодирования, так как известна таблица частот и символы, у которых частота встречаемости равна 0. В адаптивной версии алгоритма мы не можем знать заранее, какие символы появятся в сообщении. Можно проинициализировать дерево Хаффмана так, чтобы оно имело все 256 символов алфавита (для 8-и битовых кодов) с частотой, равной 1. В начале кодирования каждый код будет иметь длину 8 битов. По мере адаптации модели наиболее часто встречающиеся символы будут кодироваться все меньшим и меньшим количеством битов. Такой подход работоспособен, но он значительно снижает степень сжатия, особенно на коротких сообщениях.

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

Чтобы разрешить это противоречие, введем специальный ESCAPE код, который будет означать, что следующий символ закодирован вне контекста модели сообщения. Например, его можно передать в поток сжатой информации как есть, не кодируя вообще. Метод «ЗакодироватьСимвол» в алгоритме адаптивного кодирования Хаффмана можно записать следующим образом:

Использование специального символа ESC подразумевает определенную инициализацию дерева до начала кодирования и декодирования: в него помещаются 2 специальных символа: ESC и EOF (конец файла), с весом, равным 1.

Поскольку процесс обновления не коснется их веса, то по ходу кодирования они будут перемещаться на самые удаленные ветви дерева и иметь самые длинные коды.

Код Хаффмана

В этой статье мы рассмотрим один из самых распространенных методов сжатия данных. Речь пойдет о коде Хаффмана (Huffman code) или минимально-избыточном префиксном коде (minimum-redundancy prefix code). Мы начнем с основных идей кода Хаффмана, исследуем ряд важных свойств и затем приведем полную реализацию кодера и декодера, построенных на идеях, изложенных в этой статье.

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

Первым такой алгоритм опубликовал Дэвид Хаффман (David Huffman) [1] в 1952 году. Алгоритм Хаффмана двухпроходный. На первом проходе строится частотный словарь и генерируются коды. На втором проходе происходит непосредственно кодирование.

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

Код Хаффмана

Определение 1: Пусть A=1,a2,. ,an> — алфавит из n различных символов, W=1,w2,. ,wn> — соответствующий ему набор положительных целых весов. Тогда набор бинарных кодов C=1,c2,. ,cn>, такой что:

(1) ci не является префиксом для cj, при i!=j
(2) минимальна (|ci| длина кода ci)

называется минимально-избыточным префиксным кодом или иначе кодом Хаффмана.

Замечания:

Известно, что любому бинарному префиксному коду соответствует определенное бинарное дерево.

Определение 2: Бинарное дерево, соответствующее коду Хаффмана, будем называть деревом Хаффмана.

Задача построения кода Хаффмана равносильна задаче построения соответствующего ему дерева. Приведем общую схему построения дерева Хаффмана:

Приведем пример: построим дерево Хаффмана для сообщения S=»A H F B H C E H E H C E A H D C E E H H H C H H H D E G H G G E H C H H».

Для начала введем несколько обозначений:

В списке, как и требовалось, остался всего один узел. Дерево Хаффмана построено. Теперь запишем его в более привычном для нас виде.

Листовые узлы дерева Хаффмана соответствуют символам кодируемого алфавита. Глубина листовых узлов равна длине кода соответствующих символов.

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

A=0010bin C=000bin E=011bin G=0101bin
B=01001bin D=0011bin F=01000bin H=1bin

Теперь у нас есть все необходимое для того чтобы закодировать сообщение S. Достаточно просто заменить каждый символ соответствующим ему кодом:

S / =»0010 1 01000 01001 1 000 011 1 011 1 000 011 0010 1 0011 000 011 011 1 1 1 000 1 1 1 0011 011 0101 1 0101 0101 011 1 000 1 1″.

Оценим теперь степень сжатия. В исходном сообщении S было 36 символов, на каждый из которых отводилось по [log2|A|]=3 бита (здесь и далее будем понимать квадратные скобки [] как целую часть, округленную в положительную сторону, т.е. [3,018]=4). Таким образом, размер S равен 36*3=108 бит

Размер закодированного сообщения S / можно получить воспользовавшись замечанием 2 к определению 1, или непосредственно, подсчитав количество бит в S / . И в том и другом случае мы получим 89 бит.

Итак, нам удалось сжать 108 в 89 бит.

Теперь декодируем сообщение S / . Начиная с корня дерева будем двигаться вниз, выбирая левое поддерево, если очередной бит в потоке равен «0», и правое — если «1». Дойдя до листового узла мы декодируем соответствующий ему символ.

Ясно, что следуя этому алгоритму мы в точности получим исходное сообщение S.

Канонический код Хаффмана

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

Определение 3: Код Хаффмана D=1,d2,. ,dn> называется каноническим [2], если:
(1) Короткие коды (если их дополнить нулями справа) численно больше длинных,
(2) Коды одинаковой длины численно возрастают вместе с алфавитом.

Далее, для краткости, будем называть канонический код Хаффмана просто каноническим кодом.

Определение 4: Бинарное дерево, соответствующее каноническому коду Хаффмана, будем называть каноническим деревом Хаффмана.

В качестве примера приведем каноническое дерево Хаффмана для сообщения S, и сравним его с обычным деревом Хаффмана.

Выпишем теперь канонические коды для всех символов нашего алфавита в двоичной и десятичной форме. При этом сгруппируем символы по длине кода.

B=00000bin=0dec A=0001bin=1dec C=010bin=2dec H=1bin=1dec
F=00001bin=1dec D=0010bin=2dec E=011bin=3dec
G=0011bin=3dec

Убедимся в том, что свойства (1) и (2) из определения 3 выполняются:

Рассмотрим, к примеру, два символа: E и G. Дополним код символа E=011bin=3dec (максимальная_длина_кода-длина_кода)=5-3=2 нулями справа: E / =011 00bin=12dec, аналогично получим G / =0011 0bin=6dec. Видно что E / >G / .

Рассмотрим теперь три символа: A, D, G. Все они имеют код одной длины. Лексикографически A м уровне (имеет длину кода 3). Его порядковый номер на этом уровне равен 2 (учитывая два нелистовых узла слева), т.е. численно равен коду символа C. Теперь запишем этот номер в двоичной форме и дополним его нулевым битом слева (т.к. 2 представляется двумя битами, а код символа C тремя): 2dec=10bin=>0 10bin. Мы получили в точности код символа C.

Таким образом, мы пришли к очень важному выводу: канонические коды вполне определяются своими длинами. Это свойство канонических кодов очень широко используется на практике. Мы к нему еще вернемся.

Теперь вновь закодируем сообщение S, но уже при помощи канонических кодов:

Z / =»0001 1 00001 00000 1 010 011 1 011 1 010 011 0001 1 0010 010 011 011 1 1 1 010 1 1 1 0010 011 0011 1 0011 0011 011 1 010 1 1″

Т.к. мы не изменили длин кодов, размер закодированного сообщения не изменился: |S / |=|Z / |=89 бит.

Теперь декодируем сообщение Z / , используя свойства канонических кодов.

Построим три массива: base[], symb[], offs[]. Где base[i] — количество нелистовых узлов на уровне i; symb[] — перестановка символов алфавита, отсортированная по двум ключам: первичный — длина кода, вторичный — лексикографическое значение; offs[i] — индекс массива symb[], такой что symb[offs[i]] первый листовой узел (символ) на уровне i.

Приведем несколько пояснений. base[0]=? и offs[0]=? не используются, т.к. нет кодов длины 0, а offs[2]=? — т.к. на втором уровне нет листовых узлов.

Теперь приведем алгоритм декодирования (CANONICAL_DECODE) [5]:

  1. code = следующий бит из потока, length = 1
  2. Пока code / .

Z / =»0001 1 00001 00000 1 010 011 1 011 1 010 011 0001 1 0010 010 011 011 1 1 1 010 1 1 1 0010 011 0011 1 0011 0011 011 1 010 1 1″

  1. code = 0, length = 1
  2. code = 0 base[length] = 0
  3. symbol = symb[offs[length] = 0 + code = 1 — base[length] = 0] = symb[1] = F

Итак, мы декодировали 3 первых символа: A, H, F. Ясно, что следуя этому алгоритму мы получим в точности сообщение S.

Это, пожалуй, самый простой алгоритм для декодирования канонических кодов. К нему можно придумать массу усовершенствований. Подробнее о них можно прочитать в [5] и [9].

Вычисление длин кодов

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

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

На сегодняшний день существует множество эффективных алгоритмов вычисления длин кодов ([3], [4]). Мы ограничимся рассмотрением лишь одного из них. Этот алгоритм достаточно прост, но несмотря на это очень популярен. Он используется в таких программах как zip, gzip, pkzip, bzip2 и многих других.

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

Будем считать, что для каждого узла сохранен указатель на его родителя. У корня дерева этот указатель положим равным NULL. Выберем теперь листовой узел (символ) и следуя сохраненным указателям будем подниматься вверх по дереву до тех пор, пока очередной указатель не станет равен NULL. Последнее условие означает, что мы добрались до корня дерева. Ясно, что число переходов с уровня на уровень равно глубине листового узла (символа), а следовательно и длине его кода. Обойдя таким образом все узлы (символы), мы получим длины их кодов.

Максимальная длина кода

Как правило, при кодировании используется так называемая кодовая книга (CodeBook), простая структура данных, по сути два массива: один с длинами, другой с кодами. Другими словами, код (как битовая строка) хранится в ячейке памяти или регистре фиксированного размера (чаще 16, 32 или 64). Для того чтобы не произошло переполнение, мы должны быть уверены в том, что код поместится в регистр.

Оказывается, что на N-символьном алфавите максимальный размер кода может достигать (N-1) бит в длину. Иначе говоря, при N=256 (распространенный вариант) мы можем получить код в 255 бит длиной (правда для этого файл должен быть очень велик: 2.292654130570773*10^53

=2^177.259)! Ясно, что такой код в регистр не поместится и с ним нужно что-то делать.

Для начала выясним при каких условиях возникает переполнение. Пусть частота i-го символа равна i-му числу Фибоначчи. Например: A-1, B-1, C-2, D-3, E-5, F-8, G-13, H-21. Построим соответствующее дерево Хаффмана.

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

Эту проблему можно решить двумя приемлемыми способами. Первый из них опирается на одно из свойств канонических кодов. Дело в том, что в каноническом коде (битовой строке) не более [log2N] младших бит могут быть ненулями. Другими словами, все остальные биты можно вообще не сохранять, т.к. они всегда равны нулю. В случае N=256 нам достаточно от каждого кода сохранять лишь младшие 8 битов, подразумевая все остальные биты равными нулю. Это решает проблему, но лишь отчасти. Это значительно усложнит и замедлит как кодирование, так и декодирование. Поэтому этот способ редко применяется на практике.

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

Существует два типа алгоритмов ограничивающих длины кодов. Эвристические (приблизительные) и оптимальные. Алгоритмы второго типа достаточно сложны в реализации и как правило требуют больших затрат времени и памяти, чем первые. Эффективность эвристически-ограниченного кода определяется его отклонением от оптимально-ограниченного. Чем меньше эта разница, тем лучше. Стоит отметить, что для некоторых эвристических алгоритмов эта разница очень мала ([6], [7], [8]), к тому же они очень часто генерируют оптимальный код (хотя и не гарантируют, что так будет всегда). Более того, т.к. на практике переполнение случается крайне редко (если только не поставлено очень жесткое ограничение на максимальную длину кода), при небольшом размере алфавита целесообразнее применять простые и быстрые эвристические методы.

Мы рассмотрим один достаточно простой и очень популярный эвристический алгоритм. Он нашел свое применение в таких программах как zip, gzip, pkzip, bzip2 и многих других.

Задача ограничения максимальной длины кода эквивалентна задаче ограничения высоты дерева Хаффмана. Заметим, что по построению любой нелистовой узел дерева Хаффмана имеет ровно два потомка. На каждой итерации нашего алгоритма будем уменьшать высоту дерева на 1. Итак, пусть L — максимальная длина кода (высота дерева) и требуется ограничить ее до L / &lt L. Пусть далее RNi самый правый листовой узел на уровне i, а LNi — самый левый.

Начнем работу с уровня L. Переместим узел RNL на место своего родителя. Т.к. узлы идут парами нам необходимо найти место и для соседного с RNL узла. Для этого найдем ближайший к L уровень j, содержащий листовые узлы, такой, что j &lt (L-1). На месте LNj сформируем нелистовой узел и присоединим к нему в качестве дочерних узел LNj и оставшийся без пары узел с уровня L. Ко всем оставшимся парам узлов на уровне L применим такую же операцию. Ясно, что перераспределив таким образом узлы, мы уменьшили высоту нашего дерева на 1. Теперь она равна (L-1). Если теперь L / &lt (L-1), то проделаем то же самое с уровнем (L-1) и т.д. до тех пор, пока требуемое ограничение не будет достигнуто.

Вернемся к нашему примеру, где L=5. Ограничим максимальную длину кода до L / =4.

Видно, что в нашем случае RNL=F, j=3, LNj=C. Сначала переместим узел RNL=F на место своего родителя.

Теперь на месте LNj=C сформируем нелистовой узел.

Присоединим к сформированному узлу два непарных: B и C.

Таким образом, мы ограничили максимальную длину кода до 4. Ясно, что изменив длины кодов, мы немного потеряли в эффективности. Так сообщение S, закодированное при помощи такого кода, будет иметь размер 92 бита, т.е. на 3 бита больше по сравнению с минимально-избыточным кодом.

Ясно, что чем сильнее мы ограничим максимальную длину кода, тем менее эффективен будет код. Выясним насколько можно ограничивать максимальную длину кода. Очевидно что не короче [log2N] бит.

Вычисление канонических кодов

Как мы уже неоднократно отмечали, длин кодов достаточно для того чтобы сгенерировать сами коды. Покажем как это можно сделать. Предположим, что мы уже вычислили длины кодов и подсчитали сколько кодов каждой длины у нас есть. Пусть L — максимальная длина кода, а Ti — количество кодов длины i.

Вычислим Si — начальное значение кода длины i, для всех i из [1..L]

Для нашего примера L = 5, T1 .. 5 = <1, 0, 2 ,3, 2>.

Видно, что S5, S4, S3, S1 — в точности коды символов B, A, C, H. Эти символы объединяет то, что все они стоят на первом месте, каждый на своем уровне. Другими словами, мы нашли начальное значение кода для каждой длины (или уровня).

Теперь присвоим коды остальным символам. Код первого символа на уровне i равен Si, второго Si + 1, третьего Si + 2 и т.д.

Выпишем оставшиеся коды для нашего примера:

B = S5 = 00000bin A = S4 = 0001bin C = S3 = 010bin H = S1 = 1bin
F = S5 + 1 = 00001bin D = S4 + 1 = 0010bin E = S3 + 1 = 011bin
G = S4 + 2 = 0011bin

Видно, что мы получили точно такие же коды, как если бы мы явно построили каноническое дерево Хаффмана.

Передача кодового дерева

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

Решить эту задачу можно несколькими способами. Самое очевидное решение — сохранить дерево в явном виде (т.е. как упорядоченное множество узлов и указателей того или иного вида). Это пожалуй самый расточительный и неэффективный способ. На практике он не используется.

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

Наконец, можно использовать одно из свойств канонических кодов. Как уже было отмечено ранее, канонические коды вполне определяются своими длинами. Другими словами, все что необходимо декодеру — это список длин кодов символов. Учитывая, что в среднем длину одного кода для N-символьного алфавита можно закодировать [(log2(log2N))] битами, получим очень эффективный алгоритм. На нем мы остановимся подробнее.

Предположим, что размер алфавита N=256, и мы сжимаем обыкновенный текстовый файл (ASCII). Скорее всего мы не встретим все N символов нашего алфавита в таком файле. Положим тогда длину кода отсутвующих символов равной нулю. В этом случае сохраняемый список длин кодов будет содержать достаточно большое число нулей (длин кодов отсутствующих символов) сгруппированных вместе. Каждую такую группу можно сжать при помощи так называемого группового кодирования — RLE (Run — Length — Encoding). Этот алгоритм чрезвычайно прост. Вместо последовательности из M одинаковых элементов идущих подряд, будем сохранять первый элемент этой последовательности и число его повторений, т.е. (M-1). Пример: RLE(«AAAABBBCDDDDDDD»)=A3 B2 C0 D6.

Более того, этот метод можно несколько расширить. Мы можем применить алгоритм RLE не только к группам нулевых длин, но и ко всем остальным. Такой способ передачи кодового дерева является общепринятым и применяется в большинстве современных реализаций.

Реализация: SHCODEC

Большинство идей, изложенных в этой статье, легли в основу программы SHCODEC (Static Huffman COder / DECoder). SHCODEC — является свободно-распространяемой программой (freeware). Программу, исходный код, документацию, а так же результаты испытаний можно найти тут: http://www.webcenter.ru/

Приложение: биография Д. Хаффмана

Список литературы

[1] D.A. Huffman, «A method for the construction of minimum-redundancy codes», Proc. Inst. Radio Engineers, vol. 40, no. 9, pp. 1098-1101, Sep. 1952. [Скачать]

[2] E.S. Schwartz, B. Kallick, «Generating a canonical prefix encoding», Communications of the ACM, vol. 7, no. 3, pp. 166-169, Mar. 1964.

[3] J.V. Leeuwen, «On the construction of Huffman trees», Proc. 3rd International Colloquium on Automata, Languages, and Programming, Edinburgh University, pp. 382-410 July 1976.

[4] J. Katajainen, A. Moffat, «In-place calculation of minimum-redundancy codes», Proc. Workshop on Algorithms and Data Structures, pp. 393-402, Aug. 1995. [Скачать]

[5] A. Moffat, A. Turpin, «On the implementation of minimum-redundancy prefix codes», IEEE Transactions on Communications, vol. 45, no. 10, pp. 1200-1207, June 1997. [Скачать]

Адаптивный алгоритм Хаффмана сжатия информации Текст научной статьи по специальности « Общие и комплексные проблемы естественных и точных наук»

Похожие темы научных работ по общим и комплексным проблемам естественных и точных наук , автор научной работы — Кудрина М.А., Кудрин К.А., Дегтярева О.А., Сопченко Е.В.,

Текст научной работы на тему «Адаптивный алгоритм Хаффмана сжатия информации»

Кудрина М.А., Кудрин К.А., Дегтярева О.А., Сопченко Е.В.

ФГАОУ ВО «Самарский государственный аэрокосмический университет им. академика С.П. Королева (Национальный исследовательский университет)», Самара, Россия

АДАПТИВНЫЙ АЛГОРИТМ ХАФФМАНА СЖАТИЯ ИНФОРМАЦИИ

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

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

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

На рис. 1 приведен пример упорядоченного дерева Хаффмана. Рядом с узлами дерева на данном рисунке приведены их веса, а в квадратных скобках приведены порядковые номера узлов дерева при перечислении.

№ узла ] 2 Í 4 5 6 7 К у

] -.i r v t I i 0 I 1 1 1 2 2 3 5

Пример упорядоченного дереЕ Хаффмана

Правила построения и упорядочивания бинарного дерева Хаффмана

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

Левые ветви дерева помечаются 0, а правые —

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

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

Рассмотрим пример упорядочивания дерева Хаффмана. Возьмем в качестве исходного дерева дерево, представленное на рис.1. Пусть на вход поступил очередной символ Б. Вес листа Б увеличился и стал равен 2. На рис. 2а приведен порядок перечисления узлов и последовательность весов, которая не является неубывающей. Следовательно, двоичное дерево не упорядочено. Для упорядочивания необходимо поменять местами лист Б (нарушивший упорядоченность) и лист В (последний из меньших по весу узлов при перечислении). Результат упорядочивания приведен на рис. 2б.

1. Элементы входного сообщения считываются побайтно.

2. Если входной символ присутствует в дереве, в выходной поток записывается код, соответствующий последовательности нулей и единиц, которыми помечены ветки дерева, при проходе от корня дерева к данному листу. Вес данного листа увеличивается на 1. Веса узлов-предков коррек-

тируются. Если дерево становится неупорядоченным — упорядочивается. з) л* р]

] 2 3 4 5 6 7 S 9

Вес .fia II 2 2 ] 1 .1 2 4 Г>

№ ■ та 1 2 3 4 5 6 7 Я 9

Вес гым II 1 1 1 2 2 2 4 Ь

Рисунок 2 — Пример упорядочивания дерева Хаффмана

3. Если очередной символ, считанный из входного сообщения при сжатии, отсутствует в дереве, е выходной поток записывается набор нулей и единиц, которыми помечены ветки бинарного дерева при движении от корня к escape-символу, а затем 8 бит ASCII-кода нового символа. В дерево вместо escape-символа добавляется ветка: родитель, два потомка. Левый потомок становится escape-символом, правый — новым добавленным в дерево символом. Веса узлов-предков корректируются, а дерево при необходимости упорядочивается.

Например, если мы имеем дерево Хаффмана как на рис. 3а, и очередной символ на входе C, которого еще нет в дереве, то выходной код нового символа будет 00’C’, где ‘C’ — ASCII-код символа С. В дерево добавляется ветка с новым символом (см. рис. 3б) и дерево упорядочивается (см. рис. Зв) .

Рисунок 3 — Пример) добавления нового символа в дерево Хаффмана

Рассмотрим пример работы алгоритма архивации на следующей входной последовательности символов: ABCCDDDDBB.

/щннме ДЗЕЕаЫС дерева : mít

Пример работы алгоритма сжатия из 10 символов

занимает 80 бит.

сообщение занимает 55 бит.

Для сравнения подсчитаем, сколько бит займет данное сообщение, закодированное обычным методом Хаффмана. Таблица кодировки и кодовое дерево приведены на рис. 5.

Символ Вероятность Код

1001110110100001111 (всего 19 бит). Кроме того, следует учесть, что вместе с закодированным сообщением передается и таблица кодировки. В данном случае это как минимум еще 4 байта АБС11-кодов символов плюс соответствующие им коды Хаффмана. Всего 68 бит.

1. Элементы входного сообщения считываются побитно.

2. Каждый раз при считывании 0 или 1 происходит перемещение от корня вниз по соответствующей ветке бинарного дерева Хаффмана, до тех пор, пока не будет достигнут какой-либо лист дерева.

3. Если достигнут лист, соответствующий символу, в выходное сообщение записывается АБС11-код данного символа. Вес листа увеличивается на

Пр о г р а мма д е мо н с тр> а ции

1, веса узлов-предков корректируются, дерево при необходимости упорядочивается.

4. Если же достигнут евоаре-символ, из входного сообщения считываются 8 следующих бит, соответствующих АБС11-коду нового символа. В выходное сообщение записывается АБСИ-код данного символа. В дерево добавляется новый символ, веса узлов-предков корректируются, затем при необходимости производится его упорядочивание.

Рассмотрим процесс декодирования сообщения ‘А’0’В’0100’С’11. В начале декодирования дерево Хаффмана содержит только евоаре-символ с частотой 0. С раскодированием каждого нового символа дерево перестраивается (см. рис. 6). На выходе получим последовательность АВВСВВ.

данные данные дерева

— Пример) работы алгоритма декомпрессии

работы алгоритмов сжатия

J Программа демонстрации работы алгоритмов

Сжатие по Хаффману ] 12-алгоритмы

О Блочный алгоритм Адаптивный алгоритм

‘А’ 0’В’ 00’С 101 ÍOÜ’O’ 1101 10 о 1101 111

Предыдущий 11 Сохранить ЕСледующий

| Сжать 11 Просмотр деревьев |

Рисунок 7 — Программа-визуализатор алгоритмов сжатия

Адаптивное кодирование Хаффмана имеет ряд особенностей при своей работе [2, 3]. Одна из них связана с хранением значений кодов символов, при кодировании длинных последовательностей. Дело в том, что языки высокого уровня, обычно, оперируют с числами максимум в 32 бит, в которых можно записывать числа от 0 до 4294967296, т.е. можно работать с файлами размером 4Гб. Но иногда этих значений недостаточно и приходится вырабатывать дополнительные меры по предотвращению переполнения счетчиков символов. Правильное решение может заключаться в накоплении битов кода в связанном списке, к которому можно добавлять новые узлы. Следующая

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

Но, несмотря на указанные сложности, он часто применяется на практике, например, в протоколе У.32 передачи данных по модему со скоро-

стью 14400 бод или в программе compact операционной системы UNIX. Этот алгоритм наиболее эффективен для сжатия текстов или программных файлов. Изображения лучше сжимаются другими алгоритмами сжатия.

На кафедре информационных систем и технологий Самарского государственного аэрокосмического университета им. академика С.П. Королева разработана программа-визуализатор алгоритмов сжатия информации. Данная программа используется в учебном процессе в курсе «Теория информации» [4] при проведении лабораторных работ, а

также для создания аттестационных педагогических измерительных материалов. Программа позволяет автоматизировать процесс составления тестовых задач. Также визуализатор демонстрирует студентам работу следующих алгоритмов сжатия: алгоритм Хаффмана с блокированием и без, адаптивный алгоритм Хаффмана, алгоритмы семейства (Ь277, Ь17в, Ь1ББ). В будущем планируется расширить возможности программы путем добавления в нее других алгоритмов сжатия данных.


На рис. 7 приведен скриншот работы адаптивного алгоритма Хаффмана

1. Лидовский В.В. Теория информации. — М.:Наука, 2003. — 112 с.

2. http://old.reslib.com/book/Teoriya_informacii_^ЬоУБк^ V V

3. http://rain.ifmo.ru/cat/view.php/theory/data-compression/adaptive-huffman-2 0 0 6

4. http://sernam.ru/cod 2.php

5. Горячев Н.В. К вопросу реализации метода автоматизированного выбора системы охлаждения / Горячев Н.В., Кочегаров И.И., Юрков Н.К. // Алгоритмы, методы и системы обработки данных. 2013. № 3 (25). С. 16-20.

6. Трусов В.А. Однопозиционный модуль управления шаговым двигателем / Трусов В.А., Кочегаров И.И., Горячев Н.В., Юрков Н.К. // Теоретические и прикладные аспекты современной науки. 2015. № 7-3. С. 131-133.

7. Кудрина М.А., Кудрин К.А., Попова-Коварцева Д.А. Учебно-методический комплекс дисциплины «Теория информации» // Надежность и качество — 2012: труды Межд. симпозиума: в 2 т./ под ред. Н.К. Юркова. — Пенза: Изд-во ПГУ, 2012. — 1 т. С. 376-377.

Макаров В.Ф., Никитин С.П.

ФГБОУ ВПО «Пермский национальный исследовательский политехнический университет», Пермь, Россия ОБЕСПЕЧЕНИЕ КАЧЕСТВА И УСТАЛОСТНОЙ ПРОЧНОСТИ ЛОПАТОК ТУРБИН НА ОСНОВЕ МОДЕЛИРОВАНИЯ ДИНАМИЧЕСКОЙ СИСТЕМЫ СТАНКА И ПРОЦЕССА ГЛУБИННОГО ШЛИФОВАНИЯ

Для изготовления рабочих и сопловых лопаток турбины газотурбинных двигателей (ГТД) используют жаропрочные литейные никелевые сплавы. Одним из основных методов обработки базовых поверхностей лопаток ГТД является глубинное профильное шлифование на многокоординатных станках.

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

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

Процесс прогноза можно представить в виде трех этапов.

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

в = / (у, г, К 0, аз. ), Р = / (у, 5,1, К 0, аз. ), (1)

Ка = / (у, 5, г, К 0, аз. )

Далее необходимо выявить влияние температур в зоне резания и нагрузок на наклеп и остаточные напряжения в обрабатываемом материале [2, 3].

к, = / (в,Р,Яа ) , и = / (в, Р, яа)

Затем следует определить влияние параметров поверхностного слоя на предел выносливости ст-1 лопаток.

0-.1 = / Кст ,Т, Rа ) (3)

Такие математические зависимости, связывающие предел выносливости ст-1 с шероховатостью, наклепом и остаточными напряжениями были получены Т.В. Серенсеном, В.П. Когаевым, Р.Б. Шней-деровичем [2].

Значительное внимание на первом этапе должно быть уделено исследованию динамики и устойчивости процесса, термодинамическим явлениям при профильном глубинном шлифовании [3,4]. Качество поверхностного слоя заготовки определяется одновременным воздействием геометрического, силового и теплового факторов, являющихся функциями процесса шлифования и имеющих непосредственную связь с относительными колебаниями формообразующих узлов станка [4]. Колебания при шлифовании являются вынужденными, но их уровень зависит от степени устойчивости динамической системы. Колебания динамической системы станка при шлифовании вызывает изменение фактического срезаемого слоя, фактической силы резания, а в силу взаимосвязанности процессов вызывают изменения в тепловой системе станка при шлифовании. Это приводит к колебаниям температур в зоне шлифования.

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

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

Сжатие данных. Метод Хаффмана

Федеральное агентство по образованию РФ

ГОУ ВПО «Уральский государственный технический университет — УПИ»

Факультет дистанционного образования

Лабораторная работа № 2

по дисциплине: Теория информации

на тему: Сжатие данных. Метод Хаффмана

Студент гр. № ИТЗ–26010ДТ

Номер зачётной книжки

Лабораторная работа № 2 по Теории информации

№ записи в книге регистрации____________ дата регистрации _______________2008 г.

Студент группа № ИТЗ-26010ДТ

алгоритмы сжатия без потерь. 7

Метод повторяющихся символов (Running) 7

Зива – Лемпеля — Велча (LZW) 7

Хаффмана (Huffman) 8

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

Руководство к программе. 14

Сравнение сжатия файлов.. 17

Код программы.. 18

ВВЕДЕНИЕ

Проблема сжатия информации была актуальна всегда, т. к. объем носителей, хоть и неуклонно растёт, но всё же ограничен.

Стоит ли в таких условиях задумываться о сути архиваторов и следует ли вообще их использовать? Для этого есть целый ряд причин:

· при передаче файлов по почте или с помощью терминальных программ критичным является каждый килобайт, да и, кроме того, при пересылке большого числа файлов (особенно со сложной структурой каталогов) проще в письмо вложить всего один файл — архив;

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

· пишущий CD-ROM стал стандартом для ПК среднего класса, многие из нас сталкиваются с проблемой, когда на компакт диск необходимо перенести очень сложную структуру каталогов, тогда как файловая система компакт-диска не допускает более чем восьмикратный уровень вложенности папок. Это было бы очень серьезной проблемой, если бы не архиваторы, позволяющие упаковывать всю структуру в один файл;

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

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

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

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

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

Все приведенные выше выкладки имеют целью показать актуальность рассмотрения алгоритмов сжатия.

Мультимедиа-сжатие

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

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

Так вот, соседние пиксели, отличающиеся друг от друга по цвету незначительно, отождествляются (коэффициент «похожести» соседних пикселей определяет баланс качества изображения и степени сжатия, см. рис.). Одинаковые группы пикселей объединяются в блоки и, далее, применяется один из методов сжатия без потери качества. Например, в формате JPEG сначала производится разбиение изображения на блоки 8×8. Затем данные блоки изображения подвергаются так называемому дискретному косинус-преобразованию (ДКП, на данном этапе происходит потеря качества) и, на заключительном этапе, применяется метод Хаффмана. Данный формат очень эффективен при хранении фотографий и прочей полноцветной графики.

Кроме того, ключевым моментом является количество бит, выделяемых для хранения цвета одного пикселя. Чем больше бит выделено под хранение одного пикселя, тем реалистичнее картинка и тем больше объем графического файла. Так, в большинстве случаев мы имеем дело с графикой, цветовая палитра которой — 16 или 24 бит (Hi и True color соответственно). Всем известный формат графических файлов GIF ограничивает цветовую палитру одним байтом (всего 256 цветов для каждого пикселя), тем самым, достигая значительной экономии в объеме файла. Следует учесть, что фотографии в данном формате хранить не следует. Приличное качество недостижимо, а объем уменьшается незначительно. Преимуществом данного формата является возможность хранения простейшей анимации.

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

Основные параметры, определяющие качество сжатого файла — это битрейт и частота дискретизации. Битрейт (bit rate, битовая частота) определяет количество передаваемой за единицу времени информации; чем больше битрейт, тем выше реалистичность и соответствие исходному звуковому потоку (оптимальное значение, обеспечивающее качество компакт-диска — 128 kBit/s).

Убедиться в обоснованности этого числа можно так: для прослушивания обычного, несжатого потока аудио (записанного на Audio CD) требуется привод CD-ROM с формулой 1x. Скорость линейного чтения у такого привода равна 150 kByte/s (т. е. 1200 kBit/s). Разделим это число на отношение объемов несжатого и сжатого аудио-потоков. Как мы уже говорили, коэффициент сжатия в формате mp3 примерно равен десяти. Получаем 120 kBit/s (что и требовалось доказать).

Частота дискретизации — еще один очень важный параметр, определяющий максимальную частоту выходного сигнала (и, соответственно, чем он больше, тем ближе звучание mp3 файла к оригиналу). Общепринята точка зрения, согласно которой восприятие человеком звука ограничено частотным диапазоном от 20Hz до 20kHz. Чаще всего значение частоты дискретизации устанавливается в два раза большее, чем верхний порог восприятия (44.1 или 48 kHz).

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

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

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

Существует несколько видео-форматов. MPEG1 — первый и довольно эффективный формат. Этот формат сделал возможным просмотр видео фильмов даже на самых скромных ПК на базе процессоров Pentium (без поддержки мультимедиа-инструкций MMX). Основным недостатком этого формата являлся недостаточный коэффициент сжатия. Например, полуторачасовой фильм в таком формате занимал два компакт диска. Пользователи, смотревшие мелодраму, очень сильно переживали необходимость смены компакт-дисков в моменты развязки сюжета :).

Формат видео MPEG2 (и его VBR-реализация) используется в рамках технологии DVD и обеспечивает высокое качество выходного видео. Особой степенью сжатия не характеризуется, в силу того, что носители, используемые в технологии DVD, обладают достаточной емкостью (DVD-Disk имеет емкость от 4,7 GByte). Соответственно процесс декодирования не особенно требователен к аппаратным ресурсам ПК.

Формат MPEG4 обладает очень высокой степенью сжатия при довольно приличном качестве. Основным недостатком этого формата являются довольно высокие требования к вычислительной мощности ПК. Так, при просмотре фильмов в этом формате на системе с процессором ниже Pentium III с частотой 600 MHz, иногда, можно наблюдать слайд-шоу. Удивляет тот факт, что аудио поток в таком случае будет воспроизводиться без искажений. Таким образом, при выборе ПК, одной из задач которого будет воспроизведение видео в данном формате, следует ориентироваться на систему на базе процессоров класса Pentium III или Athlon с частотой от 1GHz (или их дешевые аналоги Celeron и Duron). Особое внимание следует уделить производительности дисковой подсистемы (в силу того, что «картинка» и «звук» хранятся в видео-файле отдельно и требуется высокая скорость произвольного доступа к диску).

алгоритмы сжатия без потерь

Метод повторяющихся символов (Running)

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

· «флаг», показывающий, что данный участок сжат

· кол-во повторений первого байта

Допустим, что есть строка, содержащая 10 подряд идущих пробелов. Данная последовательность из 10 одинаковых байт кодируется в 3.

· Первый байт — собственно сам пробел (кодируемый байт).

· Второй байт — «флаг», который указывает, что мы должны развернуть предыдущий в строке байт в последовательность при восстановлении строки.

· Третий байт — байт счетчик. Будет равен 10, т. к. мы кодируем 10 пробелов.

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

Плюс: простота реализации

Минус: малая степень сжатия (не так часто встречаются непрерывные серии одинаковых символов).

Зива – Лемпеля — Велча (LZW)

История этого алгоритма начинается с опубликования в мае 1977 г. Дж. Зивом и А. Лемпелем статьи в журнале «Информационные теории». В последствии этот алгоритм был доработан А. Велчем, и в окончательном варианте отражен в статье «IEEE Computer» в июне 1984 . В этой статье описывались подробности алгоритма и некоторые общие проблемы, с которыми можно столкнуться при его реализации. Позже этот алгоритм получил название — LZW (Lempel — Ziv — Welch) .

Алгоритм LZW представляет собой алгоритм кодирования последовательностей неодинаковых символов. Возьмем для примера строку: «Объект TSortedCollection порожден от TCollection.».В данной строке слово «Collection» повторяется дважды. В этом слове 10 символов = 80 бит. Если мы заменим это слово, в выходном файле, во втором его включении, на ссылку на первое включение, то получим сжатие информации. Если рассматривать входной блок информации размером не более 64К и ограничить длину кодируемой строки в 256 символов, то, учитывая байт «флаг» получим, что строка из 80 бит, заменяется 8+16+8 = 32 бита. (1 байт – флаг, 2 байта – ссылка, 1 байт – длинна кодируемой последовательности). Если существуют повторяющиеся строки в файле, то они будут закодированы в таблицу. Очевидным преимуществом алгоритма является то, что нет необходимости включать таблицу кодировки в сжатый файл. Другой важной особенностью является то, что сжатие по алгоритму LZW является однопроходной операцией в противоположность алгоритму Хаффмана, которому требуется два прохода.

Плюс: высокая степень сжатия

Минус: сложность в реализации.

Хаффмана (Huffman)

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

Пусть есть файл длинной в 100 байт и состоящий из 6 различных символов. Мы подсчитали вхождение каждого из символов в файл и получили следующее:

Информатика.Сжатие данных.Код Хаффмана.

Дубликаты не найдены

Хочу отнести в школу, где пикабу низзя. Дайте сcылку на скачивание видео, пожалуйста.

Перед youtube сделай ss -> ssyoutube

Код Хаффмана — он же про оптимальное кодирование, а не про сжатие данных.

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

А что там про разделители говорилось? Как они реализуются?

Они не нужны в принципе, смотри. Предположим у тебя источник с алфавитом из трех элементарных сообщений. (1,2,3). P(1)=0.5 P(2)=0.25 P(3)=0.25 (Вероятности появления соответствующих сообщений.). Таким образом, они будут закодированы как-то так 1=0; 2=10; 3=11. И закодировав поток сообщений ты сможешь однозначно его декодировать. к примеру
111223 = 000101011. Там иначе и не получится декодировать.

Ты просто привел пример, в котором невозможно по-иному декодировать. А в видео наглядно показано, что такое возможно

Смотри внимательнее видео. Кодирование Хаффмана подразумевает однозначное декодирование без всяких разделителей. В этом суть оптимального кодирования

да, извиняюсь, ошибься

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

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

а вот почему 1750 бит? а как же разделители?

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

В этом то вся фишка

я восхищен умом некоторых

На 11 секунде мои глаза тайно изнасиловали.

Да блядь! Зачем картавые люди делают переводы к видео?! Зачееем.

Имеешь дефект речи ? Тогда вперёд, ОЗВУЧИВАТЬ видосы )

Это по Фрейду) Погуглите «оральный характер».

О сообществе

Мы любим науку и популяризируем её! Мы — лига науки Пикабу!

Основные условия публикации

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

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

— Научные статьи должны сопровождаться описанием исследования, доступным на популярном уровне. Слишком профессиональный материал может быть отклонён.

— Видеоматериалы должны иметь описание.

— Названия должны отражать суть исследования.

— Если пост содержит материал, оригинал которого написан или снят на иностранном языке, русская версия должна содержать все основные положения.

Не принимаются к публикации

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

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

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

— Оскорбления, выраженные лично пользователю или категории пользователей.

— Попытки использовать сообщество для рекламы.

— Многократные попытки публикации материалов, не удовлетворяющих правилам.

— Нарушение правил сайта в целом.

Окончательное решение по соответствию поста или комментария правилам принимается модерацией сообщества. Просьбы о разбане и жалобы на модерацию принимает администратор сообщества. Жалобы на администратора принимает @SupportComunity и общество пикабу.

Кодирование, классификация, методы сжатия (RLE, Хаффман, JPEG).

Алгоритмы сжатия выбираются исходя из класса изображения.

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

Классы изображений:

1) изображения с небольшим количеством цветов (4-16) и большими областями, заполненными одним цветом

2) изображения, с использованием плавных переходов, построенные на компьютере(САПР,презентации)

3) фотореалистичные изображения(скан)

4) фотореалистичные изображения с наложением деловой графики

5) некачественно отсканированные в 256 градаций серого цвета страницы журналов или растровые изображения топографических карт

Критерии оценки алгоритмов

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

2) Симметричность(ресурсоемкость процессов кодирования и декодирования. Для нас наиболее важными являются два коэффициента: отношение времени кодирования ко времени декодирования и требования на память.)

3) Качество разжатия:Оч. Хороший(разницу между исходным и разжатым не отличить на глаз)

Хороший(исходное и разжатое можно отличить совместив их)

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

Групповое кодирование— RunLengthEncoding (RLE). Алгоритм сжатия без потерь.Сжатие в RLE происходит за счет того, что в исходном изображении встречаются цепочки одинаковых байт.Замена их на пары «счетчик, значение» уменьшает избыточность данных. Лучший, средний и худший коэффициенты сжатия — 1/32, 1/2, 2/1.Он не требует дополнительной памяти при работе, и быстро выполняется. Ориентирован алгоритм на изображения с небольшим количеством цветов: деловую и научную графику. Применяется в форматах РСХ, TIFF, ВМР.

LZW(Lempel-Ziv&Welch). Один из самых распространенных кодов сжатия без потерь. Используется в TIFF и GIF. Коэффициенты сжатия: 1/1000, 1/4, 7/5. Работа алгоритма основана на поиске во входном файле повторяющихся последовательностей символов, которые кодируются комбинациями длиной от 8 до 12 бит. Таким образом, наибольшую эффективность данный алгоритм имеет на текстовых файлах и на графических файлах, в которых имеются большие одноцветные участки или повторяющиеся последовательности пикселей.

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

Используется на последнем этапе сжатия JPEG. Коэффициенты сжатия: 1/8, 2/3, 1.

Кодирование Хаффмана работает на предпосылке, что некоторые символы используются в представлении данных чаще, чем другие. Наиболее общее представление — алфавит ASCII — использует 8 бит для каждого символа. В английском языке буква e явно будет чаще встречаться, чем буква q, хотя мы используем для их представления одинаковое количество бит. Если мы используем только 4 бита для e и 12 бит для q, мы могли бы выиграть несколько бит, сохраняя английский текст.

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

JPEG.

1) Прежде всего, программа делит изображение на блоки — матрицы размером 8х8 пикселей.

2) Схема YUV использует три компоненты, Y – яркость (может быть использована как чёрно – белое изображение), U – голубизна, V – краснота. Перевод из RGB осуществляется по схеме:

Y = 0.299R + 0.587G + 0.114B

U = 0.1687R — 0.3313G + 0.5B

V = 0.5R — 0.1187G + 0.0813B

Это преобразование, в принципе, не имеет потерь, но на практике вводится ошибка округления, обусловленная необходимостью округления результата до целого. Так как глаз человека более чувствителен к первой компоненте, чем к двум другим, то в JPEG допускает дискретизацию различных компонент с различной частотой. Наиболее общий случай – использование одной выборки U и V для четырёх выборок Y. Это позволяет сохранять лишь 50% используемого объёма при практически неизменном качестве изображения. Технология дискретизации, при которой некоторые компоненты оцифровываются с меньшей частотой, чем другие, называется поддескритизацией.

3) К значениям пикселей применяется формула, названная дискретным косинусоидальным преобразованием (DiscreteCosineTransform — DCT). DCT переводит матрицу значений пикселей 8х8 в матрицу значений амплитуд такой же размерности, соответствующую определенным частотам синусоидальных колебаний. Левый верхний угол матрицы соответствует низким частотам, а правый нижний — высоким.

Дискретное косинусоидальное преобразование (DCT) превращает массив данных интенсивности в массив данных частоты, который содержит информацию о том, как быстро изменяется интенсивность. В JPEG применяется DCT для квадратов 8*8 данных о пикселях для каждого компонента цвета. Точки в каждом блоке нумеруются от (0,0) в верхнем левом до (7,7) в нижнем правом углах. F(x,y) есть значение данных в точке (x,y). Создаётся новый блок по формуле:

Обратное преобразование имеет вид:

По физическому смыслу преобразование сводится к представлению изображения в виде суммы (ко)синусоидальных гармоник (волн). Значения F определяют амплитуды гармоник, u,v – их частоты. F(u,v) указывает на степень изменения величин для каждой из множества частот. Значение F(0,0) указывает что уровень значения не изменился, F(7,7) определяет наиболее быстрое изменение величины в обоих направлениях. Более высокие частоты “отвечают” за передачу более “тонких” деталей изображения.

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

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

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

Дата добавления: 2020-05-12 ; просмотров: 632 ; ЗАКАЗАТЬ РАБОТУ

Сжатие методом Хаффмана

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

Я хочу написать это в виде дерева но не могу понять как сохранять новые узлы полученные сложением минимальных частот символов

К примеру у нас такая последовательность: TAATTAGAAATTCTATTATA
Частота символа
A = 0.45 = 45%,
C = 0.05 = 5%,
G = 0.05 = 5%,
T = 0.45 = 45%.

В начале у нас будут 4 узла в которых в качестве значения будут храниться частоты символов. Ищем среди них минимальные значения, минимальными значениями будут здесь 0.05(символа C) и 0.05(символа G), суммируем их 0.1 получаем новый узел который будет связан с узлами 0.05(символа C) и 0.05(символа G). Вопрос, как сохранить этот новый узел чтобы при следующей итерации к нему можно было сразу обращаться?

15.03.2020, 22:07

Сжатие Хаффмана
Как изменить данный алгоритм, чтобы ограничить длину кода символа заданным числом Nmax? Спасибо! .

Сжатие Хаффмана
Есть прога, реализующая сжатие Хаффмана: #include «stdafx.h» #include #include.

Кодирование текста методом Хаффмана
Вроде бы всё правильно , НО : 1)вылезает «ё» в самом начале , хотя сортируется map по умолчанию по.

Сжатие методом Шеннона-Фано (Pascal -> C++)
Есть код на pascal может кто-нибудь помочь перевести на с++ ? uses crt; var c:char; .

Сжатие данных методом Лемпеля-Зива-Велча. Почему некоторые файлы увеличиваются в размере?
Здравствуйте. Подскажите, пожалуйста, почему файлы с расширениями (mp3, djvu, pdf, avi) при.

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

Читайте также:

  1. III группа. Свойства, характеризующие методологию целеполагания системы
  2. III. Методы отдельных навесок и пипетирования.
  3. IV. Методи аналізу травматизму
  4. V. Методические рекомендации по организации изучения дисциплины
  5. VI. Понятие и виды методов управленческих действий.
  6. VIIІ. МЕТОДИЧНІ РЕКОМЕНДАЦІЇ ДО САМОСТІЙНОЇ РОБОТИ
  7. W. Stern (1980) предложил метод определения жировой прослойки у спортсменов.
  8. А в 2008 году по результатам такого анализа среди 50 стран мира по этой же методике МЭФ Россия была «перемещена – на 38 место.
  9. Або певні психологічні феномени: методи релаксопедії, гіпнопедії, сугестопедії, активізації резервних можливостей особистості.
  10. Адміністративний та навчальний методи супервізії в менеджменті соціальної роботи.
  11. Активні методи
  12. Алгебраический метод построения матрицы ориентации

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

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

Префиксный код – это код, в котором никакое кодовое слово не является префиксом любого другого кодового слова. Эти коды имеют переменную длину.

Оптимальный префиксный код – это префиксный код, имеющий минимальную среднюю длину.

Алгоритм Хаффмана можно разделить на два этапа.

1) Определение вероятности появления символов в исходном тексте.

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

2) Нахождение оптимального префиксного кода.

Далее находятся два символа a и b с наименьшими вероятностями появления и заменяются одним фиктивным символом x, который имеет вероятность появления, равную сумме вероятностей появления символов a и b. Затем, используя эту процедуру рекурсивно, находится оптимальный префиксный код для меньшего множества символов (где символы a и b заменены одним символом x). Код для исходного множества символов получается из кодов замещающих символов путем добавления 0 или 1 перед кодом замещающего символа, и эти два новых кода принимаются как коды заменяемых символов. Например, код символа a будет соответствовать коду x с добавленным нулем перед этим кодом, а для символа b перед кодом символа x будет добавлена единица.

Коды Хаффмана имеют уникальный префикс, что и позволяет однозначно их декодировать, несмотря на их переменную длину.

Пример 1. Программная реализация метода Хаффмана.

Кодирование, классификация, методы сжатия (RLE, Хаффман, JPEG).

Алгоритмы сжатия выбираются исходя из класса изображения.

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

Классы изображений:

1) изображения с небольшим количеством цветов (4-16) и большими областями, заполненными одним цветом

2) изображения, с использованием плавных переходов, построенные на компьютере(САПР,презентации)

3) фотореалистичные изображения(скан)

4) фотореалистичные изображения с наложением деловой графики

5) некачественно отсканированные в 256 градаций серого цвета страницы журналов или растровые изображения топографических карт

Критерии оценки алгоритмов

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

2) Симметричность(ресурсоемкость процессов кодирования и декодирования. Для нас наиболее важными являются два коэффициента: отношение времени кодирования ко времени декодирования и требования на память.)

3) Качество разжатия:Оч. Хороший(разницу между исходным и разжатым не отличить на глаз)

Хороший(исходное и разжатое можно отличить совместив их)

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

Групповое кодирование— RunLengthEncoding (RLE). Алгоритм сжатия без потерь.Сжатие в RLE происходит за счет того, что в исходном изображении встречаются цепочки одинаковых байт.Замена их на пары «счетчик, значение» уменьшает избыточность данных. Лучший, средний и худший коэффициенты сжатия — 1/32, 1/2, 2/1.Он не требует дополнительной памяти при работе, и быстро выполняется. Ориентирован алгоритм на изображения с небольшим количеством цветов: деловую и научную графику. Применяется в форматах РСХ, TIFF, ВМР.

LZW(Lempel-Ziv&Welch). Один из самых распространенных кодов сжатия без потерь. Используется в TIFF и GIF. Коэффициенты сжатия: 1/1000, 1/4, 7/5. Работа алгоритма основана на поиске во входном файле повторяющихся последовательностей символов, которые кодируются комбинациями длиной от 8 до 12 бит. Таким образом, наибольшую эффективность данный алгоритм имеет на текстовых файлах и на графических файлах, в которых имеются большие одноцветные участки или повторяющиеся последовательности пикселей.

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

Используется на последнем этапе сжатия JPEG. Коэффициенты сжатия: 1/8, 2/3, 1.

Кодирование Хаффмана работает на предпосылке, что некоторые символы используются в представлении данных чаще, чем другие. Наиболее общее представление — алфавит ASCII — использует 8 бит для каждого символа. В английском языке буква e явно будет чаще встречаться, чем буква q, хотя мы используем для их представления одинаковое количество бит. Если мы используем только 4 бита для e и 12 бит для q, мы могли бы выиграть несколько бит, сохраняя английский текст.

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

JPEG.

1) Прежде всего, программа делит изображение на блоки — матрицы размером 8х8 пикселей.

2) Схема YUV использует три компоненты, Y – яркость (может быть использована как чёрно – белое изображение), U – голубизна, V – краснота. Перевод из RGB осуществляется по схеме:

Y = 0.299R + 0.587G + 0.114B

U = 0.1687R — 0.3313G + 0.5B

V = 0.5R — 0.1187G + 0.0813B

Это преобразование, в принципе, не имеет потерь, но на практике вводится ошибка округления, обусловленная необходимостью округления результата до целого. Так как глаз человека более чувствителен к первой компоненте, чем к двум другим, то в JPEG допускает дискретизацию различных компонент с различной частотой. Наиболее общий случай – использование одной выборки U и V для четырёх выборок Y. Это позволяет сохранять лишь 50% используемого объёма при практически неизменном качестве изображения. Технология дискретизации, при которой некоторые компоненты оцифровываются с меньшей частотой, чем другие, называется поддескритизацией.

3) К значениям пикселей применяется формула, названная дискретным косинусоидальным преобразованием (DiscreteCosineTransform — DCT). DCT переводит матрицу значений пикселей 8х8 в матрицу значений амплитуд такой же размерности, соответствующую определенным частотам синусоидальных колебаний. Левый верхний угол матрицы соответствует низким частотам, а правый нижний — высоким.

Дискретное косинусоидальное преобразование (DCT) превращает массив данных интенсивности в массив данных частоты, который содержит информацию о том, как быстро изменяется интенсивность. В JPEG применяется DCT для квадратов 8*8 данных о пикселях для каждого компонента цвета. Точки в каждом блоке нумеруются от (0,0) в верхнем левом до (7,7) в нижнем правом углах. F(x,y) есть значение данных в точке (x,y). Создаётся новый блок по формуле:

Обратное преобразование имеет вид:

По физическому смыслу преобразование сводится к представлению изображения в виде суммы (ко)синусоидальных гармоник (волн). Значения F определяют амплитуды гармоник, u,v – их частоты. F(u,v) указывает на степень изменения величин для каждой из множества частот. Значение F(0,0) указывает что уровень значения не изменился, F(7,7) определяет наиболее быстрое изменение величины в обоих направлениях. Более высокие частоты “отвечают” за передачу более “тонких” деталей изображения.

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

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

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

Дата добавления: 2020-05-12 ; просмотров: 633 ; ЗАКАЗАТЬ РАБОТУ

Илон Маск рекомендует:  strlen - Возвращает длину строки
Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL