Оптимальное хранение словаря в алгоритме Хаффмана
При сжатии данных алгоритмом Хаффмана появляется проблема передачи оптимального кода зашифрованного сообщения, который поможет получателю расшифровать его. Рассмотрим некоторые варианты решения этой задачи.
Задача: |
Пусть у нас есть алфавит | , , и код , сопоставляющий каждому символу его код . Нужно придумать эффективное представление кода в памяти.
Содержание
Простое решение[править]
Заметим, что
. Дополним все коды до длины нулями с конца и запишем их друг за другом. Также необходимо передать . При условии, что не превышает получаем дополнительных бит на передачу префиксного кода.Чтобы декодировать полученную информацию о коде, достаточно сначала узнать
и записать в префиксное дерево коды всех символов. Построив соответствующее дерево, можно заметить, что некоторые вершины являются единственным ребенком — такие вершины получены в результате дополнения нашего оптимального кода до бит нулями. Все такие вершины можно просто удалить из дерева, и мы получим оптимальный префиксный код, который мы передавали.Докажем, что код который мы получили совпадает с изначальным. В результате дополнения всех кодов до длины
мы, очевидно, ничего не потеряли в структуре дерева, ведь дополнение кода нулями фактически равносильно добавлению к дереву пустых (не несущих информации) листьев и вершин. В результате удаления вершин, являющихся единственным ребенком, мы также не удалим лишние: предположим мы удалили вершину, в которой содержался какой-то код, тогда она не могла быть единственным ребенком ввиду самого алгоритма Хаффмана, ведь мы выбираем два узла с наименьшим весом и добавляем их к вновь сформированному узлу.Пример[править]
Для примера возьмем слово "миссисипи". Тогда код
будет выглядеть следующим образом:Символ | и | м | п | с |
---|---|---|---|---|
Код | 0 | 100 | 101 | 11 |
При помощи нашего алгоритма
будет закодирован как:
Построим префиксное дерево по полученному коду:
Удалив вершины, являющиеся единственными детьми у других вершин, получим зашифрованное префиксное дерево:
Эффективное решение[править]
Построим префиксное дерево, соответствующее нашему коду
. Наша задача состоит из двух подзадач: передача структуры этого дерева и передача информации, по которой впоследствии можно будет понять, где какой лист находится.Передача структуры дерева[править]
Обойдем дерево, используя обход в глубину, причем будем сначала всегда спускаться в левого ребенка, а только потом — в правого. Каждый раз, проходя по ребру запишем одну из букв , или , в зависимости от того, куда по ребру мы прошли ( — в левого ребенка, — в правого ребенка, — в родителя). Эта информация поможет нам восстановить дерево.
Построим обход дерева Хаффмана для слова "миссисипи":
Первая модификация[править]
Заметим, что на самом деле мы можем объединить ребра типа
и в ребро типа , которое значит, что мы спускаемся вниз, а в которого ребенка — в левого или в правого, можно определить на месте.Модифицируем наш обход:
Вторая модификация[править]
Модифицируем значение команды
. Пусть теперь символ значит, что мы поднимаемся к предку текущей вершины, пока мы — правый ребенок или пока не достигли корня, и если мы, остановившись, пришли из левого сына вершины, перейдем по ребру в правого ребенка. После такой модификации записывая каждый символ мы ровно по одному ребру проходим в первый раз. Конечный вариант кодировки дерева: Распишем подробнее:Спускаемся влево | |
Поднимаемся и спускаемся вправо | |
Спускаемся влево | |
Спускаемся влево | |
Поднимаемся и спускаемся вправо | |
Поднимаемся, поднимаемся и спускаемся вправо | |
Поднимаемся до корня |
Оценим используемое количество памяти. Так как в нашем дереве
листьев, то в нем ребер (это легко показать из алгоритма Хаффмана, в нем итерация и на каждой в дерево добавляется по два ребра), а символов в нашей записи будет , так как на каждое ребро приходится по символу плюс последний, терминальный, . Заметим, что терминальный нам вообще говоря не нужен: мы всегда в конце поднимаемся в корень дерева, а значит, если все символы прочитаны — то обход закончен. Итоговая оценка памяти: .Передача информации для восстановления листьев[править]
Алфавит нам будет дан изначально, не будет лишь кодов каждого символа, следовательно нам нужно просто указать, какой лист в дереве соответствует каждому символу. Занумеруем подряд все символы алфавита. Сопоставим каждому символу алфавита код фиксированной
длины — его порядковый номер в алфавите, записанный в двоичной системе счисления. Все коды имеют фиксированную длину, а значит легко понять где заканчивается один, и начинается другой код. Тогда, если выписать подряд коды для всех символов в том порядке, в котором обход в глубину посещает соответствующие им листы, несложно восстановить, какому символу какой код соответствует. Когда мы, в результате обхода в глубину, пришли в вершину, у которой нет детей, мы возьмем следующий переданный нам номер, посмотрим в нашем алфавите что это за символ, и присвоим текущей вершине этот символ.Отсутствие некоторых символов в тексте[править]
Предположим теперь, что не все символы из алфавита были использованы в тексте, тогда возникает вопрос: получив очередной код, как узнать какому символу он принадлежит? Для решения этой проблемы поступим следующим образом: выпишем подряд коды
в том порядке, в котором обход в глубину посещает соответствующие им листы, лишь для тех символов, что были использованы в нашем сообщении. Тогда встретив очередной символ, мы гарантированно будем знать, что он встречался в нашем сообщении.Используемая память[править]
В этом решении нам также придется передавать размер алфавита (
бита).Итого, задача решена с использованием
бит.Если же были использованы не все символы, то будет использовано
бит, где — количество использованных символов.Реализация[править]
// s — наша строка обхода, tree[] — дерево вершин, code — текущий код, alphabet[] — массив кодов символов, // c'[] — номера символов в порядке обхода function huffman(): //текущая вершина — корень дерева curV = root for i = 0..n - 2 if s[i] == 'D' curV = tree[curV].leftChild code += '0' if curV не имеет детей alphabet[следующий номер c'].push(code) else while curV является правым ребенком и curV не корень curV = tree[curV].parent удалить из code последний символ curV = tree[curV].rightChild code += '1' if curV не имеет детей alphabet[следующий номер c'].push(code)