Huffman

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 , так как следующий бит может быть как началом следующего кода, так и продолжением предыдущего.Необходимо добавить, что ключем к построению префиксных кодов служит обычное бинарное дерево и если внимательно рассмотреть предыдущий пример с построением дерева, можно убедится, что все получаемые коды там префиксные.Одно последнее примечание - алгоритм Хаффмана требует читать входной файл дважды , один раз считая частоты вхождения символов, другой раз производя непосредственно кодирование.---В примере сжатия по алгоритму Хаффмана автору для сохранения таблицы (или же просто дерева) потребовалось около 50 байт. Но я хочу вам рассказать о методе кодирования деревьев, известного из дискретной математики. При использовании этого метода для сохранения полной структуры дерева из примера потребуется всего 2.5 байта + 6 байт для алфавита. Для описания метода кодирования надо принять несколько обозначений и соглашений. Движением вперед будем называть продвижение по дереву от корня к листьям. По одному ребру дерева можно проходить только два раза - вперед и назад, после этого ребро должно удаляться из рассмотрения. Для сохранения пути движения за "1" обозначим движение вперед, за "0" - движение назад. Для кодирования используется обход дерева. Давайте начнем обход дерева. Условимся двигаться слева направо. Таким образом первым нашим движением будет - из "ROOT" в "C". Здесь мы двигались вперед значит запоминаем "1" в нашей закодированной последовательности. Теперь мы находимся в "C" и дальше двигаться вперед уже не можем, значит двигаемся назад и запоминаем "0". Мы находимся снова в "ROOT", но идти снова в "С" мы не можем, так как мы прошли по нему уже два раза, т.е. мы убираем его из рассмотрения. Таким образом мы можем идти только в узел "3", сохраняем "1". Узел "3" не является вершиной дерева, и кроме того у него есть ребра по которым мы еще не проходили. Так как мы идем слева на право, то сдедующим движением будет из "3" в "2", запоминаем "1". После того как мы окажемся в "А" движение вперед будет невозможным, и начнется движение назад. Т.е. из "А" в "1" с сохранением "0". Находясь в узле "1" снова двигаться в "А" мы уже не можем и будем двигаться в "D". И так далее пока мы не пройдем по всем ребрам по 2 раза. В результате у нас получится закодированная последовательность: 10111101001001101000 Ее длина 20 бит, что составляет всего 2.5 байта. Таким образом с сжатом файле полнотью сохраненное дерево будет занимать 2.5+6 байт, т.е. 9 полных байт. Теперь длина сжатого файла уже будет не 80 байт, а всего 9+30=39 байт, что само по себе просто замечательно, ведь закодировав просто дерево нам удалось достичь большего сжатия, чем прежде. Конечно при сжатии файлов в мегабайты, экономия в данном алгоритме не имеет никакого значения, но при маленьких размерах файла позволяет съэкономить несколько десятков байт.