admin / 15.05.2018

Кодирование по хаффману

.

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

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

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

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

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

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

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

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

Итак, после всего этого таблицы Huffman в формате JPEG являются просто таблицами, которые позволяют распаковать поток в полезную информацию.

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


(a) Вероятно, наилучшим примером минимального хранения этой таблицы было бы что-то вроде:

Для текста выше, это будет:

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

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

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

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

Затем, после того, как каждый байт будет выведен и обновленные подсчеты, таблица/дерево перебалансируется на основе новых счетчиков, чтобы быть наиболее экономичной по площади (хотя перебалансировка может быть отложена для повышения скорости, вам просто нужно обеспечить такая же отсрочка происходит во время декомпрессии, примером является каждый раз, когда вы добавляете байт для первого 1K ввода, затем каждые 10K ввода после этого, предполагая, что вы добавили новые байты с момента последнего перебалансирования).

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

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

Таким образом, вам не нужно иметь таблицу с сжатым файлом.

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

ответ дан paxdiablo 10 февр. '11 в 9:39

источникподелиться

Алгоритм построения дерева

  1. Символы исходного алфавита образуют список свободных узлов. Каждый узел имеет вес, равный количеству вхождений символа в исходное сообщение.
  2. В списке выбираются два свободных узла с наименьшими весами.
  3. Создается их узел «родитель» с весом, равным сумме их весов, он соединяется с «детьми» дугами.
  4. Одной дуге, выходящей из «родителя» ставится в соответствии «1» бит, другой – «0».
  5. «Родитель» добавляется в список свободных узлов, а двое «детей» удаляются из списка.
  6. Шаги 2-6 повторяются до тех пор, пока в списке свободных узлов не останется.

Пример: построить дерево Хаффмана и найти префиксные коды для сообщения: «КОЛ_ОКОЛО_КОЛОКОЛА»

Решение:

· Составим таблицу частот вхождения символов

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

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

Буквосочетания можно рассматривать как новый, расширенный алфавит объемом

K=Nm , где

N – объем исходного алфавита;

M – число символов в буквосочетании.

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

 

Рассчитаем коэффициент сжатия сообщения.

Пример 3. Вычислили объем сообщения «КОЛ ОКОЛО КОЛОКОЛА» при использовании кодировок ASCII (Vascii =144 бита) и Unicode (Vunicode = 288 бит). Выше построили код Хаффмана для этой же фразы, на основании которого оценили объем сообщения Vхаффмана=39 бит.

В результате мы получаем коэффициент сжатия равный 144/39 = 3,7 для кодировки ASCII и 288/39 =7,4 для кодировки Unicode.

Метод RLE

В основу алгоритмов RLE (Run-Length Encoding – кодирование путем учета числа повторений) положен принцип выявления повторяющихся последовательностей данных и замены их простой структурой: повторяющийся фрагмент и коэффициент повторения.

Рассмотрим идею сжатия методом RLE. Во входной последовательности:

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

2. все неповторяющиеся цепочки байтов заменяются на фрагменты {управляющий байт, цепочка неповторяющихся байтов}, причем управляющий в десятичной системе счисления должен иметь значение 0+ длина цепочки.

Код Хаффмана

Это означат, что старший бит управляющего байта для цепочки неповторяющихся байтов всегда равен 0.

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

 

Пример 4. Упакуем методом RLE следующую последовательность из 14-ти байтов:

11111111 11111111 11111111 11111111 11111111 11110000 00001111 11000011 10101010 10101010 10101010 10101010 10101010 10101010

В начале последовательности 5 раз повторяется байт 11111111. Чтобы закодировать эти 5-ть байтов, запишем вначале управляющий байт 10000101, а затем сам повторяющийся байт 11111111. Рассмотрим как получился управляющийся байт: к значению 128 мы прибавили число повторений байта 5, получили 13310=100001012.

Далее идут 3 разных байта. Чтобы их закодировать, мы записываем управляющий байт 00000011 (112=310), а затем эти неповторяющиеся байты.

Далее в последовательности 7 раз идет байт 10101010. Чтобы закодировать эти 7 байтов, мы записываем управляющий байт 10000111 (128+7=13510=10001112), а затем повторяющийся байт 10101010.

В результате применения метода RLE мы получаем последовательность из 8-ми байтов: 10000101 11111111 00000011 11110000 00001111 11000011 10000111 10101010.

Таким образом, коэффициент сжатия 14/8=1,75.

Схема распаковки:

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

2. Если во входной (сжатой) последовательности управляющий байт с нулем в старшем бите, то в выходную последовательность нужно поместить столько следующих за управляющим байтов входной последовательности, сколько указано в оставшихся 7-ми битах управляющего байта.

Пример 5. Распакуем сжатую последовательность данных методом RLE:

00000010 00001111 11110000 10000110 11000011 00000011 00001111 00111100 01010101.

Первый байт данной последовательности управляющий 000000010, начинается с 0. Следовательно, следующие за ним 102=210 байта помещаются в выходную последовательность.

Замечание. Будем зачеркивать обработанные байты.

00000010 00001111 11110000 10000110 11000011 00000011 00001111 00111100 01010101

Следующий управляющий байт 10000110 начинается с 1. Следовательно, следующий за ним байт нужно поместить в выходную последовательность 1102=610 раз.

00000010 00001111 11110000 10000110 11000011 00000011 00001111 00111100 01010101

Следующий управляющий байт 00000011 начинается с 0. Следовательно, следующие за ним 112=310 байта нужно поместить в выходную последовательность.

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

00001111 11110000 11000011 11000011 11000011 11000011 11000011 11000011 00001111 00111100 01010101

 

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

 

 

Предыдущая891011121314151617181920212223Следующая


Дата добавления: 2015-11-10; просмотров: 787;


ПОСМОТРЕТЬ ЕЩЕ:

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

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

Сжимая файл по алгоритму Хаффмана первое что мы должны сделать — это необходимо прочитать файл полностью и подсчитать сколько раз встречается каждый символ из расширенного набора 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 , так как следующий бит может быть как началом следующего кода, так и продолжением предыдущего.

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

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

А здесь — реализация на Паскалe.

FILED UNDER : IT

Submit a Comment

Must be required * marked fields.

:*
:*