Сжатие данных без потерь. Алгоритм Хаффмана

60.Алгоритмы сжатия данных. Сжатие с потерями и без потерь. Метод Хаффмана. Сжатие заголовков. Алгоритм Лемпеля-Зива

Сжатие данных без потерь. Алгоритм Хаффмана

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

Все методы сжатия данных делятся на дваосновных класса:

  • Сжатие без потерь
  • Сжатие с потерями

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

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

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

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

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

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

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

В дальнейшем ( в дереве )мы будем размещать указатели которыебудут указывать на этот «узел». Дляясности давайте рассмотрим пример:

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

|——————|——|——|——|——|——|——|

| cимвол | A | B | C | D | E | F |

|——————|——|——|——|——|——|——|

| число вхождений| 10 | 20 | 30 | 5 | 25 | 10 |

|——————|——|——|——|——|——|——|

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

|——————|——|——|——|——|——|——|

| cимвол | C | E | B | F | A | D |

|——————|——|——|——|——|——|——|

| число вхождений| 30 | 25 | 20 | 10 | 10 | 5 |

|——————|——|——|——|——|——|——|

Мы возьмем из последней таблицы символыс наименьшей частотой. В нашем случаеэто D (5) и какой либо символ из F или A(10), можно взять любой из них, напримерA.

Сформируем из «узлов» D и A новый»узел», частота вхождения длякоторого будет равна сумме частот D иA:

Частота 30 10 5 10 20 25

Символа C A D F B E

| |

|—|—|

||-|

|15| = 5 + 10

|—|

Номер в рамке — сумма частот символов Dи A. Теперь мы снова ищем два символа ссамыми низкими частотами вхождения,исключаяиз просмотра D и A и рассматриваявместо них новый «узел» с суммарнойчастотой вхождения. Самая низкая частотатеперь у F и нового «узла». Сновасделаем операцию слияния узлов :

Частота 30 10 5 10 20 25

Символа C A D F B E

| | |

| | |

| |—|| |

|-|15|| |

||-| |

| |

| |—| |

|—-|25|-|= 10 + 15

|—|

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

Частота 30 10 5 10 20 25

Символа C A D F B E

| | | | | |

| | | | | |

| | |—|| | | |

| |-|15|| | | |

| ||-| | | |

| | | | |

| | |—| | | |—| |

| |—-|25|-| |-|45|-|

| ||-| ||-|

| |—| | |

|—-|55|——| |

|-|| |

| |————| |

|—|Root (100) |—-|

|————|

Теперь когда наше дерево создано, мыможем кодировать файл. Мы должнывсегданачинать из корня ( Root ). Кодируяпервый символ (лист дерева С) Мыпрослеживаем вверх по дереву все поворотыветвей и если мы делаем левый поворот,то запоминаем 0-й бит, и аналогично 1-йбит для правого поворота.

Так для C, мыбудем идти влево к 55 ( и запомним 0 ), затемснова влево (0) к самому символу. КодХаффмана для нашего символа C — 00. Дляследующего символа ( А ) у нас получается- лево,право,лево,лево , что создаетпоследовательность 0100.

Выполнив вышесказанное для всех символов получим

C = 00 ( 2 бита )

A = 0100 ( 4 бита )

D = 0101 ( 4 бита )

F = 011 ( 3 бита )

B = 10 ( 2 бита )

E = 11 ( 2 бита )

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

|———-|—————-|——————-|—————|

|Частота | первоначально | уплотненныебиты | уменьшено на |

|———-|—————-|——————-|—————|

| C 30 | 30 x 8 = 240 | 30 x 2 = 60 | 180 |

| A 10 | 10 x 8 = 80 | 10 x 3 = 30 | 50 |

| D 5 | 5 x 8 = 40 | 5 x 4 = 20 | 20 |

| F 10 | 10 x 8 = 80 | 10 x 4 = 40 | 40 |

| B 20 | 20 x 8 = 160 | 20 x 2 = 40 | 120 |

| E 25 | 25 x 8 = 200 | 25 x 2 = 50 | 150 |

|———-|—————-|——————-|—————|

Первоначальныйразмер файла : 100 байт — 800 бит;

Размерсжатого файла : 30 байт — 240 бит;

240- 30% из 800 , так что мы сжали этот файл на70%.

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

В нашей методике сжатия и каждом узленаходятся 4 байта указателя, по этому,полная таблица для 256 байт будетприблизительно 1 Кбайт длинной.

Таблица в нашем примере имеет 5 узловплюс 6 вершин ( где и находятся нашисимволы ), всего 11. 4 байта 11 раз — 44. Еслимы добавим после небольшое количествобайтов для сохранения места узла инекоторую другую статистику — нашатаблица будет приблизительно 50 байтовдлинны.

Добавив к 30 байтам сжатой информации,50 байтов таблицы получаем, что общаядлина архивного файла вырастет до 80байт. Учитывая , что первоначальнаядлинна файла в рассматриваемом примеребыла 100 байт — мы получили 20% сжатиеинформации.

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

Что мы можем получить на этом пути?

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

Мы получим что можно иметь только :

4 — 2 разрядных кода;

8 — 3 разрядных кодов;

16 — 4 разрядных кодов;

32 — 5 разрядных кодов;

64 — 6 разрядных кодов;

128 — 7 разрядных кодов;

Необходимо еще два 8 разрядных кода.

4 — 2 разрядных кода;

8 — 3 разрядных кодов;

16 — 4 разрядных кодов;

32 — 5 разрядных кодов;

64 — 6 разрядных кодов;

128 — 7 разрядных кодов;

———

254

Итак, мы имеем итог из 256 различныхкомбинаций, которыми можно кодироватьбайт. Из этих комбинаций лишь 2 подлинеравны 8 битам. Если мы сложим числобитов, которые это представляет, то витоге получим 1554 бит или 195 байтов. Такв максимуме, мы сжали 256 байт к 195 или33%, таким образом,максимальноидеализированный Huffman может достигатьсжатия в 33%, когда используется на уровнебайта.

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

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

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

Источник: https://studfile.net/preview/2044043/page:26/

Сжатие данных без потерь. Алгоритм Хаффмана

Сжатие данных без потерь. Алгоритм Хаффмана

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

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

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

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

Подобные устройства, как правило, оснащаются высокоскоростными каналами для транслирования информации. Однако, стоит отметить, что с каждым годом объем необходимой пользователям информации становится все больше и больше. Всего $10$ лет назад объем стандартного видеофильма не превышал $700$ Мб.

В настоящее время объем фильмов в HD-качестве может достигать нескольких десятков гигабайт.

Ничего непонятно?

Попробуй обратиться за помощью к преподавателям

Когда необходимо сжатие данных?

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

  1. Передача по электронной почте.

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

  2. Публикация данных на интернет-сайтах и порталах.

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

  3. Экономия свободного места на диске.

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

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

Способы сжатия информации

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

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

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

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

Сжатие без потери информации

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

Пример 1

Приведем простой пример. Русский язык включает в себя $33$ буквы, $10$ цифр и еще примерно $15$ знаков препинания и других специальных символов.

Для текста, записанного только прописными русскими буквами (например как в телеграммах) вполне хватило бы $60$ разных значений. Тем не менее, каждый символ обычно кодируется байтом, содержащим, как нам известно, 8 битов, и может выражаться $256$ различными кодами.

Это один из первых факторов, характеризующих избыточность. Для телеграфного текста вполне хватило бы и $6$ битов на символ.

Пример 2

Рассмотрим другой пример.

В международной кодировке символов ASCII для кодирования любого символа выделяется одинаковое количество битов ($8$), в то время, как всем давно и хорошо известно, что наиболее часто встречающиеся символы имеет смысл кодировать меньшим количеством знаков.

Так, к примеру, в азбуке Морзе буквы «Е» и «Т», которые встречаются очень часто, кодируются $1$ знаком (соответственно это точка и тире). А такие редкие буквы, как «Ю» ($• • — -$) и «Ц» ($- • — •$), кодируются $4$ знаками.

Замечание 1

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

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

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

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

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

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

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

Рисунок 1. Распределение английских букв по их частоте использования

Величина сжатия определяется избыточностью обрабатываемого массива бит. Каждый из естественных языков обладает определенной избыточностью.

Среди европейских языков русский имеет самый высокий уровней избыточности. Об этом можно судить по размерам русского перевода английского текста. Обычно он примерно на $30\%$ больше.

Если речь идет о стихотворном тексте, избыточность может быть до $2$ раз выше.

Замечание 2

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

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

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

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

Еще одним недостатком кодов является то, что минимальная длина кодового слова для них не может быть меньше единицы, тогда как энтропия сообщения вполне может составлять и $0,1$, и $0,01$ бит/букву.

В этом случае код становится существенно избыточным.

Проблема решается применением алгоритма к блокам символов, но тогда усложняется процедура кодирования/декодирования и значительно расширяется кодовое дерево, которое нужно в конечном итоге сохранять вместе с кодом.

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

Замечание 3

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

Источник: https://spravochnick.ru/informatika/kodirovanie_informacii/szhatie_dannyh_bez_poter_algoritm_haffmana/

«Алгоритм Хаффмана (Huffman) — сжатие данных без потерь»C++ Visual Studio 2012

Сжатие данных без потерь. Алгоритм Хаффмана

Учебная программа сжатия информации (данных) без потерь.

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

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

  • создание очереди символов (сортированного списка)
  • создание очереди узлов дерева (каждый символ — это листок, т.е. конечный узел)
  • создание дерева Хаффмана
  • создание таблицы Хаффмана

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

Задание:

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

Решение:

По органам управления на форме все понятно. Одна кнопка вызывает «метод сжатия» Encode , а вторая обратный метод Decode (восстановление первоначального текста из архива).

Вот так выглядит обработчик события нажатия кнопки «Создание таблицы»:

Void Form1::button1_Click(System::Object sender, System::EventArgs e)    {     if (textBox1->Text!=»») {       //Строим дерево по строке для кодирования       codeTree = buildTree(textBox1->Text);       //Строим таблицу Хаффмана по этому дереву       codeTable = buildTable(codeTree);       //заполнение textBox4 для наглядности       textBox4->Text=»»;       hlNode *cur=codeTable->first;       while (cur!=NULL)  {         String sym = ((wchar_t)(cur->symbol)).ToString();         String cod = gcnew String(cur->code);         textBox4->Text=» '»+sym+»' — «+cod+»\r»+textBox4->Text;         cur=cur->next;       }     }     else { MessageBox::Show( «Отсутствует строка для кодирования», «Внимание!!!»,    System::Windows::Forms::MessageBoxButtons::OK,System::Windows::Forms::MessageBoxIcon::Error );     textBox4->Text=»»;     } }

В файлах Huffman.h, Huffman.cpp, pQueue.h, pQueue.cpp содержатся все необходимые функции для обеспечения работы алгоритма.

htTree * buildTree(System::String inputString);   //построение дерева по строке символов
hlTable * buildTable(htTree *huffmanTree);   //построение таблицы по дереву
System::String Encode(hlTable *table, System::String stringToEncode);   //кодирование по таблице и строке символов
System::String Decode(htTree *tree, System::String stringToDecode);   //декодирование по дереву и строке кода
и другие…

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

скачать exe-файл для тестирования

Имеется проект с точно таким же интерфейсом, но на C# Visual Studio 2012 .

Условия получения кода?    Показать?

А это еще одна версия программы, демонстрирующая алгоритм Хаффмана, но написанная на С++ Borland Builder 6.0

Изменяя текст в первом окне и щелкнув кнопку «Сжатие», Вы увидите произошедшие изменения в частотах символов (окно 5… можете пересчитать, если не верите…), в Таблице Хаффмана (окно2), сжатом тексте (окно 3), последовательности битов сжатого текста (окно 4).

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

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

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

, но если вы хоть один раз ошибётесь… (в разряде или цифре), получите значительные искажения…

скачать exe-файл для тестирования

Другие примеры на тему «Шифрование, Кодирование и/или Сжатие Информации»

Другие примеры на языках «C»,«C++»,«C#»

Если на этой странице не нашлось того, что Вы так искали…

         Не расстраивайтесь, не все потеряно… Смело щелкайте…

       телефон:
+7(919) 572-59-92 +7(987) 848-79-61

460040, г.Оренбург       © 2010    Учебные программы и сайты для студентов  

Источник: https://orenstudent.ru/Huffman.htm

Алгоритмы сжатия: описание, основные приемы, характеристики

Сжатие данных без потерь. Алгоритм Хаффмана

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

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

Таким образом, например, если последовательность появляется в файле, как «AAAAAA», занимая 6 байтов, он будет сохранен, как «6A», который занимает только 2 байта, в алгоритме сжатия RLE.

История возникновения процесса

Азбука Морзе, изобретенная в 1838 году — первый известный случай сжатия данных. Позже, когда в 1949 году мейнфрейм-компьютеры начали завоевывать популярность, Клод Шеннон и Роберт Фано изобрели кодирование, названного в честь авторов — Шеннона-Фано. Это шифрование присваивает коды символам в массиве данных по теории вероятности.

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

В 1977 году, Авраам Лемпель и Джейкоб Зив издали свой инновационный метод LZ77, использующий более модернизированный словарь. В 1978 году, та же команда авторов, издала усовершенствованный алгоритм сжатия LZ78. Который использует новый словарь, анализирующий входные данные и генерирующий статический словарь, а не динамический, как у 77 версии.

Формы исполнения компрессии

Компрессия выполняется программой, которая использует формулу или алгоритм, определяющих, как уменьшить размер данных. Например, представить строку битов с меньшей строкой 0 и 1, используя словарь для преобразований или формулу.

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

Для передачи процесс выполняют в блоке передачи, включая данные заголовка. Когда информация отправляется или принимается через интернет, заархивированные по отдельности или вместе с другими большими файлами, могут передаваться в ZIP, GZIP или другом «уменьшенном» формате.

Преимущество алгоритмов сжатия:

  1. Значительно уменьшает объем памяти. При степени сжатия 2:1 файл в 20 мегабайт (МБ) займет 10 МБ пространства. В результате администраторы сети тратят меньше денег и времени на хранение баз данных.
  2. Оптимизирует производительность резервного копирования.
  3. Важный метод сокращения данных.
  4. Практически любой файл может быть сжат, но важно выбрать нужную технологию под конкретный тип файла. Иначе файлы могут быть «уменьшены», но при этом общий размер не изменится.

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

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

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

Этот процесс, который можно использовать для «уменьшения» или шифрования.

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

Порядок создания алгоритмы сжатия данных:

  1. Просчитывают, сколько раз каждый символ повторяется в файле для «уменьшения».
  2. Создают связанный список с информацией о символах и частотах.
  3. Выполняют сортировку списка от наименьшего к наибольшему в зависимости от частоты.
  4. Преобразуют каждый элемент в списке в дерево.
  5. Объединяют деревья в одно, при этом первые два образуют новое.
  6. Добавляют частоты каждой ветви в новый элемент дерева.
  7. Вставляют новое в нужное место в списке, в соответствии с суммой полученных частот.
  8. Назначают новый двоичный код каждого символа. Если берется нулевая ветвь, к коду добавляется ноль, а если первая ветвь, добавляется единица.
  9. Файл перекодируется в соответствии с новыми кодами.
  10. Например характеристики алгоритмов сжатия для короткого текста:»ata la jaca a la estaca»
  11. Подсчитывают, сколько раз появляется каждый символ и составляют связанный список:'' (5), a (9), c (2), e (1), j (1), l (2), s (1), t (2)
  12. Заказывают по частоте от низшей к высшей: e (1), j (1), s (1), c (2), l (2), t (2), '' (5), a (9)

Как видно, корневой узел дерева создан, далее назначаются коды.

И осталось только упаковать биты в группы по восемь, то есть в байты:

0111001011010101111110110001001011010101111101111011100110000000
0x720xd50x0x120xd50xF70xB90x80

Всего восемь байтов, а исходный текст был 23.

Демонстрация библиотеки LZ77

Алгоритм LZ77 рассмотрим на примере текста«howtogeek». Если повторить его три раза, то он изменит его следующим образом.

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

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

С повторяющимися словами можно получить огромные коэффициенты сжатия.

Например, текст со словом «howtogeek», повторенным 100 раз имеет размер три килобайта, при компрессии займет всего 158 байт, то есть с 95% «уменьшением».

Это, конечно, довольно экстремальный пример, но наглядно демонстрирует свойства алгоритмов сжатия. В общей практике он составляет 30-40% с текстовым форматом ZIP. Алгоритм LZ77, применяется ко всем двоичным данным, а не только к тексту, хотя последний легче сжать из-за повторяющихся слов.

Дискретное косинусное преобразование изображений

Сжатие видео и аудио работает совсем по-другому. В отличие от текста, где выполняют алгоритмы сжатия без потерь, и данные не будут потеряны, с изображениями выполняют «уменьшение» с потерями, и чем больше %, тем больше потерь. Это приводит к тем ужасно выглядящим JPEG-файлам, которые люди загружали, обменивали и делали скриншоты по несколько раз.

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

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

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

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

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

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

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

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

MP3 использует битрейт, в диапазоне от нижнего уровня 48 и 96 кбит/с (нижний предел) до 128 и 240 кбит/с (довольно хороший) до 320 кбит/с (высококачественный звук), и услышать разницу можно только с исключительно хорошими наушниками.

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

Форматы «уменьшения» текста

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

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

Источник: https://FB.ru/article/457728/algoritmyi-sjatiya-opisanie-osnovnyie-priemyi-harakteristiki

Сжатие данных алгоритмом Хаффмана

Сжатие данных без потерь. Алгоритм Хаффмана

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

В результате напишем простенький архиватор. Об этом уже была статья на Хабре, но без практической реализации. Теоретический материал текущего поста взят из школьных уроков информатики и книги Роберта Лафоре «Data Structures and Algorithms in Java». Итак, все под кат!

Немного размышлений

В обычном текстовом файле один символ кодируется 8 битами(кодировка ASCII) или 16(кодировка Unicode). Далее будем рассматривать кодировку ASCII. Для примера возьмем строку s1 = «SUSIE SAYS IT IS EASY».

Всего в строке 22 символа, естественно, включая пробелы и символ перехода на новую строку — ''. Файл, содержащий данную строку будет весить 22*8 = 176 бит. Сразу же встает вопрос: рационально ли использовать все 8 бит для кодировки 1 символа? Мы ведь используем не все символы кодировки ASCII.

Даже если бы и использовали, рациональней было бы самой частой букве — S — дать самый короткий возможный код, а для самой редкой букве — T (или U, или '') — дать код подлиннее.

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

Кодирование

Почему бы символу 'S' не дать код, например, длиной в 1 бит: 0 или 1. Пусть это будет 1. Тогда второму наиболее встречающемуся символу — ' '(пробел) — дадим 0.

Представьте себе, вы начали декодировать свое сообщение — закодированную строку s1 — и видите, что код начинается с 1.

Итак, что же делать: это символ S, или же это какой-то другой символ, например A? Поэтому возникает важное правило:

Ни один код не должен быть префиксом другого

Это правило является ключевым в алгоритме. Поэтому создание кода начинается с частотной таблицы, в которой указана частота (количество вхождений) каждого символа: Символы с наибольшим количеством вхождений должны кодироваться наименьшим возможным количеством битов. Приведу пример одной из возможных таблиц кодов: Таким образом, закодированное сообщение будет выглядеть так: 10 01111 10 110 1111 00 10 010 1110 10 00 110 0110 00 110 10 00 1111 010 10 1110 01110 Код каждого символа я разделил пробелом. По-настоящему в сжатом файле такого не будет!

Вытекает вопрос: как этот салага придумал код как создать таблицу кодов? Об этом пойдет речь ниже.

Построение дерева Хаффмана

Здесь приходят на выручку бинарные деревья поиска. Не волнуйтесь, здесь методы поиска, вставки и удаления не потребуются. Вот структура дерева на java: public class Node { private int frequence; private char letter; private Node leftChild; private Node rightChild; …

}
class BinaryTree { private Node root; public BinaryTree() { root = new Node(); } public BinaryTree(Node root) { this.root = root; } …} Это не полный код, полный код будет ниже. Вот сам алгоритм построения дерева:

  1. Создать объект Node для каждого символа из сообщения(строка s1).

    В нашем случае будет 9 узлов(объектов Node). Каждый узел состоит из двух полей данных: символ и частота

  2. Создать объект Дерева(BinaryTree) для кажлого из узлов Node. Узел становится корнем дерева.
  3. Вставить эти деревья в приоритетную очередь. Чем меньше частота, тем больше приоритет.

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

Далее нужно циклически делать следующее:

  1. Извлечь два дерева из приоритетной очереди и сделать их потомками нового узла (только что созданного узла без буквы). Частота нового узла равна сумме частот двух деревьев-потомков.
  2. Для этого узла создать дерево с корнем в данном узле. Вставить это дерево обратно в приоритетную очередь.

    (Так как у дерева новая частота, то скорее всего она встанет на новое место в очереди)

  3. Продолжать выполнение шагов 1 и 2, пока в очереди не останется одно дерево — дерево Хаффмана

Рассмотрим данный алгоритм на строке s1: Здесь символ «lf»(linefeed) обозначает переход на новую строку, «sp» (space) — это пробел.

А что дальше?

Мы получили дерево Хаффмана. Ну окей. И что с ним делать? Его и за бесплатно не возьмут А далее, нужно отследить все возможные пути от корня до листов дерева. Условимся обозначить ребро 0, если оно ведет к левому потомку и 1 — если к правому.

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

Тогда в сжатом виде исходный файл будет весить: 2 * 3 + 2*4 + 3 * 3 + 6 * 2 + 1 * 4 + 1 * 5 + 2 * 4 + 4 * 2 + 1 * 5 = 65 бит. Вначале он весил 176 бит. Следовательно, мы уменьшили его аж в 176/65 = 2.7 раза! Но это утопия. Такой коэффициент вряд ли будет получен.

Почему? Об этом пойдет речь чуть позже.

Booksm
Добавить комментарий