Изменения

Перейти к: навигация, поиск
Нет описания правки
При сжатии данных [[Алгоритм Хаффмана|алгоритмом Хаффмана ]] появляется проблема передачи дополнительной информации об оптимальном префиксном коде оптимального кода зашифрованного сообщения, который поможет получателю расшифровать его. Рассмотрим некоторые варианты решения этой задачи. == Постановка задачи == Пусть у нас есть алфавит <tex>\Sigma = \{a_1, a_2, \cdots, a_n\}</tex>, <tex>|\Sigma| = n</tex>, и код <tex>c</tex>, сопоставляющий каждому символу <tex>a_i</tex> его код <tex>c_i</tex>. Нужно придумать эффективное представление кода <tex> c </tex> в памяти. == Простое решение == Заметим, что <tex>\forall i: |c_i| \le n</tex>. Дополним все коды до длины <tex> n </tex> нулями и запишем их друг за другом. Также необходимо передать <tex> n </tex>. При условии, что <tex> n </tex> не превышает <tex> 2^{32} - 1 </tex> получаем <tex> 32 + n^2 </tex> дополнительных бит на передачу префиксного кода. Чтобы декодировать полученную информацию о коде, достаточно сначала узнать <tex>n</tex> и записать в префиксное дерево коды всех символов. Построив соответствующее дерево, можно заметить, что некоторые вершины имеют одного ребенка — такие вершины получены в результате дополнения нашего оптимального кода до <tex>n</tex> бит нулями. Все такие вершины можно просто удалить из дерева, и мы получим оптимальный префиксный код, который мы передавали. === Пример === Для примера возьмем слово "миссисипи". Тогда код <tex> c </tex> будет выглядеть следующим образом: {| class="wikitable"! Символ || и || м || п || с|-| Код || 0 || 100 || 101 || 11|} При помощи нашего алгоритма <tex> c </tex> будет закодирован как: 0000 1000 1010 1100 Построим префиксное дерево по полученному коду: [[Файл:Missisipi2.png|600px|Дерево Хаффмана для слова ''"миссисипи"'']] Удалив вершины, являющиеся единственными детьми у других вершин, получим зашифрованное префиксное дерево: [[Файл:Mississippi.png|400px|Дерево Хаффмана для слова ''"миссисипи"'']] == Эффективное решение == Построим префиксное дерево, соответствующее нашему коду <tex>c</tex>. Наша задача состоит из двух подзадач: передача структуры этого дерева и передача информации для различения листьев. === Передача структуры дерева === Обойдем дерево, используя [[Обход в глубину, цвета вершин|обход в глубину]]. Каждый раз, проходя по ребру запишем одну из букв <tex> L </tex>, <tex> R </tex> или <tex> U </tex>, в зависимости от того, куда по ребру мы прошли (<tex>L</tex> - в левого ребенка, <tex>R</tex> - в левого ребенка, <tex>U</tex> - в родителя). Эта информация поможет нам восстановить дерево. Построим обход дерева Хаффмана для слова "миссисипи": LURLLURUURUU ==== Первая модификация ==== Заметим, что на самом деле мы можем объединить ребра типа <tex>L</tex> и <tex>R</tex> в ребро типа <tex>D</tex>, которое значит, что мы спускаемся вниз, а в которого ребенка — в левого или в правого, можно определить на месте. Модифицируем наш обход: DUDDDUDUUDUU ==== Вторая модификация ==== Модифицируем значение команды <tex>U</tex>. Пусть теперь символ <tex>U</tex> значит, что мы поднимаемся к предку текущей вершины, пока мы — правый ребенок или пока не достигли корня, и если мы, остановившись, пришли из левого сына вершины, перейдем по ребру в правого ребенка. После такой модификации записывая каждый символ мы ровно по одному ребру проходим в первый раз. Конечный вариант кодировки дерева: DUDDUUU Распишем подробнее: {| class="wikitable"| D || Спускаемся влево|-| U || Поднимаемся и спускаемся вправо|-| D || Спускаемся влево|-| D || Спускаемся влево|-| U || Поднимаемся и спускаемся вправо|-| U || Поднимаемся, поднимаемся и спускаемся вправо|-| U || Поднимаемся до корня|} Оценим используемое количество памяти. Так как в нашем дереве <tex> n </tex> листьев, то в нем <tex> 2 \cdot n - 2 </tex> (это легко показать из алгоритма Хаффмана, в нем <tex> n - 1 </tex> итерация и на каждой в дерево добавляется по 2 ребра), а символов в нашей записи будет <tex> 2 \cdot n - 1 </tex>, так как на каждое ребро приходится по символу плюс последний, терминальный, <tex> U </tex>. === Передача информации для восстановления листьев === Сопоставим каждому символу алфавита равномерный код <tex>c'</tex> длины <tex> \lceil log_{2} \rceil n</tex> - его порядковый номер в алфавите, записанный в двоичной системе счисления. Тогда, если выписать подряд коды <tex>c'</tex> для всех символов в том порядке, в котором обход в глубину посещает соответствующие им листы, несложно восстановить, какому символу какой код <tex>c</tex> соответствует. === Используемая память === Итого, задача решена с использованием <tex>n \lceil log_{2} \rceil n + 2n - 1</tex> бит. == Ссылки == *[[Алгоритм Хаффмана]]*[[Обход в глубину, цвета вершин|Обход в глубину]] [[Категория: Дискретная математика и алгоритмы]] [[Категория: Алгоритмы сжатия ]]
7
правок

Навигация