Метод Шеннона-Фано (Shannon-Fano method)

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

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

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

а б в г

Рис. 4. Префиксный код Хаффмана.

Хаффман предложил очень простой алгоритм определения того, какой символ необходимо кодировать каким кодом для получения файла с длиной, очень близкой к его энтропии (то есть информационной насыщенности). Пусть у нас имеется список всех символов, встречающихся в исходном тексте, причем известно количество появлений каждого символа в нем. Выпишем их вертикально в ряд в виде ячеек будущего графа по правому краю листа (рис. 4а). Выберем два символа с наименьшим количеством повторений в тексте (если три или большее число символов имеют одинаковые значения, выбираем любые два из них). Проведем от них линии влево к новой вершине графа и запишем в нее значение, равное сумме частот повторения каждого из объединяемых символов (рис. 4б). Отныне не будем принимать во внимание при поиске наименьших частот повторения два объединенных узла (для этого сотрем числа в этих двух вершинах), но будем рассматривать новую вершину как полноценную ячейку с частотой появления, равной сумме частот появления двух соединившихся вершин. Будем повторять операцию объединения вершин до тех пор, пока не придем к одной вершине с числом (рис. 4в и 4г). Для проверки: очевидно, что в ней будет записана длина кодируемого файла (текста). Теперь расставим на двух ребрах графа, исходящих из каждой вершины, биты 0 и 1 произвольно – например, на каждом верхнем ребре 0, а на каждом нижнем – 1. Теперь для определения кода каждой конкретной буквы необходимо просто пройти от вершины дерева до нее, выписывая нули и единицы по маршруту следования. Для рисунка символ "А" получает код "000", символ "Б" – код "01", символ "К" – код "001", а символ "О" – код "1".

В теории кодирования информации показывается, что код Хаффмана является префиксным, то есть код никакого символа не является началом кода какого-либо другого символа. Проверьте это на нашем примере. А из этого следует, что код Хаффмана однозначно восстановим получателем, даже если не сообщается длина кода каждого переданного символа. Получателю пересылают только дерево Хаффмана в компактном виде, а затем входная последовательность кодов символов декодируется им самостоятельно без какой-либо дополнительной информации. Например, при приеме "0100010100001" им сначала отделяется первый символ "Б": "01-00010100001", затем снова начиная с вершины дерева – "А" "01-000-10100001", затем аналогично декодируется вся запись "01-000-1-01-000-01" "БАОБАБ".

 

Работа алгоритма с файлами

 

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

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

--------

 

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

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

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

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

 

Программная реализация алгоритма Huffman

 

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

Например: строка "Business information systems"

 

Первое дерево: ("sp" - space)

s[6] i[3] n[3] t[2] o[2] e[2] sp[2] m[2] B[1] u[1] f[1] r[1] a[1] y[1]

│ │ │ │ │ │ │ │ │┌──┐│ │┌──┐│ │┌──┐│

│ │ │ │ │ │ │ │ 0└┤ 2├┘1 0└┤ 2├┘1 0└┤ 2├┘

│ 0│┌──┐│1 0│┌──┐│1 │ 0┌──┐1│ 0│┌───┐└─┬┘ └─┬┘ ┌───┐└─┬┘1

│ └┤ 6├┘ └┤ 4├┘ └──┤ 4├─┘ └┤ 4 ├──┘ └──┤ 4 ├──┘

│ └─┬┘ └─┬┘ └┬─┘ └─┬─┘1 0 └─┬─┘ 1

│0┌───┐1│ │ 0┌───┐1 │ │ 0┌────┐1 │

└─┤ 12├─┘ └──┤ 8 ├───┘ └──────┤ 8 ├───────┘

└─┬─┘ └─┬─┘ 0┌────┐1 └──┬─┘

│ └─────────┤ 16 ├────────────┘

│ 0┌──────────┐1 └──┬─┘

└───────────┤ Root ├────────┘

└──────────┘

Второе дерево:

s[6] i[3] n[3] t[2] o[2] e[2] sp[2] m[2] B[1] u[1] f[1] r[1] a[1] y[1]

│ │ │ │ │ │ │ │ │ │ │ │ │┌──┐│

│ │ │ │ │ 0│┌───┐1 │ ┌┘ └─┐ │ │ │ 0└┤ 2├┘1

│ │ │ │ │ └┤ 12├┐ │ 0│┌───┐1 │ │ │ 0│┌──┐ └─┬┘

│ │ │ │ 0│┌───┐└─┬─┘│ │ └┤ 8 ├┐ │ │ │ └┤ 3├───┘

│ │ │ │ └┤ 14├──┘ │ │┌──┐└─┬─┘│┌┘ │ 0│┌──┐1└─┬┘1

│ │ │ 0│┌───┐└─┬─┘1 │ └┤10├──┘ ││ │ └┤ 4├───┘

│ │ │ └┤ 16├──┘ │ 0└─┬┘1 ││ 0│┌──┐ └─┬┘

│ │ 0│┌───┐└─┬─┘1 └────┘ ││0 └┤ 5├───┘

│ │ └┤ 19├──┘ ││┌──┐└─┬┘1

│ 0 │┌───┐└─┬─┘1 │└┤ 6├──┘

│ └┤ 22├──┘ │ └─┬┘1

│ └─┬─┘1 └───┘

│ └───────────┐

│0┌─────────────┐1 │

└─┤ Root (28) ├───┘

└─────────────┘

 

 

Распишем коды полученные по различным деревьям:

 

по первому : по второму :

s[6] - 00 - 6*2=12 s[6] - 0 - 6*1 =6

i[3] - 010 - 3*3= 9 i[3] - 10 - 3*2 =6

n[3] - 011 - 3*3= 9 n[3] - 110 - 3*3 =9

t[2] - 1000 - 2*4= 8 t[2] - 1110 - 2*4 =8

o[2] - 1001 - 2*4= 8 o[2] - 11110 - 2*5 =10

e[2] - 1010 - 2*4= 8 e[2] - 111110 - 2*6 =12

sp[2] - 1011 - 2*4= 8 sp[2] - 1111110 - 2*7 =14

m[2] - 1100 - 2*4= 8 m[2] - 11111110 - 2*8 =16

B[1] - 11010 - 1*5= 5 B[1] - 111111110 - 1*9 =9

u[1] - 11011 - 1*5= 5 u[1] - 1111111110 - 1*10=10

f[1] - 11100 - 1*5= 5 f[1] - 11111111110 - 1*11=11

r[1] - 11101 - 1*5= 5 r[1] - 111111111110 - 1*12=12

a[1] - 11110 - 1*5= 5 a[1] - 1111111111110 - 1*13=13

y[1] - 11111 - 1*5= 5 y[1] - 1111111111111 - 1*13=14

─────────────────────── ────────────────────────────────

всего бит 100 байт 13 всего бит 150 байт 19

 

Из первоначальных 304 бит в первом случае осталось всего 100 бит, а во втором 150 бит. Из этого можно сделать вывод, что первое дерево является оптимальным (оно строится именно по алгоритму Huffman). Но не во всех приложениях возможно применение алгоритма построения дерева, поэтому нельзя сбрасывать со счета и использования "усредненного" дерева для многих, близких по статистической таблице, блоков данных.

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

 

Метод Шеннона-Фано (Shannon-Fano method)

Родственным методом для кодирования Хаффмана является кодирование Шеннона-Фано, которое осуществляется следующим образом:

  1. Делим множество символов на два подмножества так, чтобы сумма вероятностей появления символов одного подмножества была примерно равна сумме вероятностей появления символов другого. Для левого подмножества каждому символу приписываем "0", для правого - "1".
  2. Повторяем шаг (1) до тех пор, пока все подмножества не будут состоять из одного элемента.

Алгоритм создания кода Хаффмана называется снизу-вверх, а Шеннона-Фано - сверху вниз. Кодирование по Хаффману всегда дает оптимальные коды, по Шеннону-Фано иногда используется немного больше бит.

Алгоритмы Хаффмана и Шеннона-Фано являются одними из классических, поэтому они часто используются в графических форматах. Они берут только частоту появления одинаковых байт в изображении и сопоставляют символам входного потока, которые встречаются большее число раз, цепочку бит меньшей длины. И напротив - встречающимся редко - цепочку большей длины. Для сбора статистики требуют двух проходов по изображению. Коэффициенты сжатия алгоритмов : 1/8, 2/3, 1. Требуют записи в файл таблицы соответствия кодируемых символов и кодирующих цепочек. На практике используются их разновидности. Так, в некоторых случаях резонно либо использовать постоянную таблицу, либо строить ее адаптивно, т.е. в процессе архивации/разархивации. Эти приемы избавляют от двух проходов по изображению и необходимости хранения таблицы вместе с файлом. Кодирование с фиксированной таблицей применяется в качестве последнего этапа архивации в JPEG.

<== предыдущая лекция | следующая лекция ==>
 | Понятие о силе и системе сил

Дата добавления: 2019-02-08; просмотров: 792;


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.032 сек.