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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «== Способ хранения информации об оптимальном префиксном коде == При передаче информации ...»)
 
(Используемая память)
 
(не показана 31 промежуточная версия 5 участников)
Строка 1: Строка 1:
== Способ хранения информации об оптимальном префиксном коде ==
+
При сжатии данных [[Алгоритм Хаффмана|алгоритмом Хаффмана]] появляется проблема передачи оптимального кода зашифрованного сообщения, который поможет получателю расшифровать его. Рассмотрим некоторые варианты решения этой задачи.
  
При передаче информации кроме проблемы сжатия данных появляется проблема необходимости передачи дополнительных данных, которые помогут получателю расшифровать полученное сообщение. Существует несколько способов решения этой задачи. Рассмотрим варианты, как можно передать информацию об оптимальном префиксном коде.
+
{{Задача
 +
|definition =
 +
Пусть у нас есть алфавит <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| \leqslant 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>n</tex> мы, очевидно, ничего не потеряли в структуре дерева, ведь дополнение кода нулями фактически равносильно добавлению к дереву пустых (не несущих информации) листьев и вершин. В результате удаления вершин, являющихся единственным ребенком, мы также не удалим лишние: предположим мы удалили вершину, в которой содержался какой-то код, тогда она не могла быть единственным ребенком ввиду самого алгоритма Хаффмана, ведь мы выбираем два узла с наименьшим весом и добавляем их к вновь сформированному узлу.
 +
 
 +
=== Пример ===
 +
 
 +
Для примера возьмем слово "миссисипи". Тогда код <tex> c </tex> будет выглядеть следующим образом:
 +
 
 +
{| class="wikitable"
 +
! Символ || и || м || п || с
 +
|-
 +
| Код || 0 || 100 || 101 || 11
 +
|}
 +
 
 +
При помощи нашего алгоритма <tex> c </tex> будет закодирован как:
 +
 
 +
<tex>0000\ 1000\ 1010\ 1100</tex>
 +
 
 +
Построим префиксное дерево по полученному коду:
 +
 
 +
[[Файл:Missisipi2.png|600px|Дерево Хаффмана для слова ''"миссисипи"'']]
 +
 
 +
Удалив вершины, являющиеся единственными детьми у других вершин, получим зашифрованное префиксное дерево:
 +
 
 +
[[Файл:Mississippi.png|400px|Дерево Хаффмана для слова ''"миссисипи"'']]
 +
 
 +
== Эффективное решение ==
 +
 
 +
Построим префиксное дерево, соответствующее нашему коду <tex>c</tex>. Наша задача состоит из двух подзадач: передача структуры этого дерева и передача информации, по которой впоследствии можно будет понять, где какой лист находится.
  
Пусть у нас есть алфавит <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> L </tex>, <tex> R </tex> или <tex> U </tex>, в зависимости от того, куда по ребру мы прошли (<tex>L</tex> — в левого ребенка, <tex>R</tex> — в правого ребенка, <tex>U</tex> — в родителя). Эта информация поможет нам восстановить дерево.
 +
 
 +
Построим обход дерева Хаффмана для слова "миссисипи":
 +
 
 +
<tex>LURLLURUURUU</tex>
 +
 
 +
==== Первая модификация ====
 +
 
 +
Заметим, что на самом деле мы можем объединить ребра типа <tex>L</tex> и <tex>R</tex> в ребро типа <tex>D</tex>, которое значит, что мы спускаемся вниз, а в которого ребенка — в левого или в правого, можно определить на месте.
 +
 
 +
Модифицируем наш обход:
 +
 
 +
<tex>DUDDDUDUUDUU</tex>
 +
 
 +
==== Вторая модификация ====
 +
Модифицируем значение команды <tex>U</tex>. Пусть теперь символ <tex>U</tex> значит, что мы поднимаемся к предку текущей вершины, пока мы — правый ребенок или пока не достигли корня, и если мы, остановившись, пришли из левого сына вершины, перейдем по ребру в правого ребенка. После такой модификации записывая каждый символ мы ровно по одному ребру проходим в первый раз.
 +
Конечный вариант кодировки дерева:
 +
<tex>DUDDUUU</tex>
 +
Распишем подробнее:
 +
{| class=wikitable
 +
| <tex>D</tex> || Спускаемся влево
 +
|-
 +
| <tex>U</tex> || Поднимаемся и спускаемся вправо
 +
|-
 +
| <tex>D</tex> || Спускаемся влево
 +
|-
 +
| <tex>D</tex> || Спускаемся влево
 +
|-
 +
| <tex>U</tex> || Поднимаемся и спускаемся вправо
 +
|-
 +
| <tex>U</tex> || Поднимаемся, поднимаемся и спускаемся вправо
 +
|-
 +
| <tex>U</tex> || Поднимаемся до корня
 +
|}
 +
Оценим используемое количество памяти. Так как в нашем дереве <tex> n </tex> листьев, то в нем <tex> 2 \cdot n - 2 </tex> ребер (это легко показать из алгоритма Хаффмана, в нем <tex> n - 1 </tex> итерация и на каждой в дерево добавляется по два ребра), а символов в нашей записи будет <tex> 2 \cdot n - 1 </tex>, так как на каждое ребро приходится по символу плюс последний, терминальный, <tex> U </tex>.
 +
Заметим, что терминальный <tex>U</tex> нам вообще говоря не нужен: мы всегда в конце поднимаемся в корень дерева, а значит, если все символы прочитаны — то обход закончен. Итоговая оценка памяти: <tex> 2 \cdot n - 2 </tex>.
 +
 
 +
=== Передача информации для восстановления листьев ===
 +
Алфавит нам будет дан изначально, не будет лишь кодов каждого символа, следовательно нам нужно просто указать, какой лист в дереве соответствует каждому символу. Занумеруем подряд все символы алфавита. Сопоставим каждому символу алфавита код фиксированной <tex>c'</tex> длины <tex> \lceil \log _2 \rceil n</tex> — его порядковый номер в алфавите, записанный в двоичной системе счисления. Все коды имеют фиксированную длину, а значит легко понять где заканчивается один, и начинается другой код. Тогда, если выписать подряд коды <tex>c'</tex> для всех символов в том порядке, в котором обход в глубину посещает соответствующие им листы, несложно восстановить, какому символу какой код <tex>c</tex> соответствует. Когда мы, в результате обхода в глубину, пришли в вершину, у которой нет детей, мы возьмем следующий переданный нам номер, посмотрим в нашем алфавите что это за символ, и присвоим текущей вершине этот символ.
  
Первое решение:
+
=== Отсутствие некоторых символов в тексте ===
Заметим, что <tex>\forall i: |c_i| \le n</tex>, поэтому мы можем, используя <tex>32 + n^2</tex> бит передать всю необходимую информацию: сначала передадим число <tex>n</tex> - размер алфавита (для этого можно использовать, к примеру, <tex>32</tex> бита, предполагая, что размер алфавита не превышает <tex>2^{32} - 1</tex>), а потом <tex>n</tex> блоков по <tex>n</tex> бит: для каждого символа в алфавите (в отсортированном порядке) передадим его код, дополненный до <tex>n</tex> бит нулями в конце записи.
+
Предположим теперь, что не все символы из алфавита были использованы в тексте, тогда возникает вопрос: получив очередной код, как узнать какому символу он принадлежит? Для решения этой проблемы поступим следующим образом: выпишем подряд коды <tex>c'</tex> в том порядке, в котором обход в глубину посещает соответствующие им листы, лишь для тех символов, что были использованы в нашем сообщении. Тогда встретив очередной символ, мы гарантированно будем знать, что он встречался в нашем сообщении.
  
Чтобы декодировать полученную информацию о коде, достаточно сначала узнать <tex>n</tex> — размер алфавита, а записать в дерево коды всех символов. Построив соответствующее дерево, можно заметить, что некоторые вершины имеют одного ребенка — все такие вершины получены в результате дополнения нашего оптимального кода до <tex>n</tex> бит нулями. Все такие вершины можно просто удалить из дерева, и мы получим оптимальный префиксный код, который мы передавали.
+
=== Используемая память ===
  
 +
В этом решении нам также придется передавать размер алфавита (<tex>32</tex> бита).
  
Второе решение:
+
Итого, задача решена с использованием <tex>n \lceil \log_2 \rceil n + 2n - 1 + 32 = n \lceil \log_2 \rceil n + 2n + 31 </tex> бит.
Построим префиксное дерево, соответствующее нашему коду <tex>c</tex>. Наша задача состоит в передаче структуры этого дерева и информации для различения листьев.
 
  
Будем решать подзадачу о передаче структуры дерева последовательными оптимизациями.
+
Если же были использованы не все символы, то будет использовано <tex>k \lceil \log_2 \rceil n + 2k - 1 + 32 = k \lceil \log_2 \rceil n + 2k + 31 </tex> бит, где <tex>k</tex> — количество использованных символов.
  
Для начала заметим, что в дереве <tex>n</tex> листьев, откуда следует, что в нем <tex>2n - 2</tex> ребра. Доказать это просто из самого алгоритма Хаффмана: в нем <tex>n - 1</tex> фаза, и на каждой фазе удаляются ровно два ребра.
+
=== Реализация ===
 +
  <span style="color:Green">// s — наша строка обхода, tree[] — дерево вершин, code — текущий код, alphabet[] — массив кодов символов, </span>
 +
  <span style="color:Green">// c'[] — номера символов в порядке обхода</span>
 +
'''function''' huffman():
 +
  <span style="color:Green">//текущая вершина — корень дерева</span>
 +
  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)
  
Первый способ: обойдем дерево, используя dfs — алгоритм поиска в глубину. Каждый раз, проходя по ребру, запишем в ответ одну из букв <tex>L, R</tex> или <tex>U</tex>, в зависимости от того, куда по ребру мы прошли (<tex>L</tex> — в левого ребенка, <tex>R</tex> — в правого ребенка, <tex>U</tex> — в родителя). Эта информация поможет нам восстановить дерево.
+
== См. также ==
 +
*[[Алгоритм_Хаффмана_за_O(n) | Алгоритм Хаффмана за O(n)]]
  
Затратим мы <tex>2\cdot(2n - 2) \cdot 2</tex> бита — <tex>2\cdot(2n - 2)</tex> раз мы пройдем по ребрам, <tex>2</tex> бита — на хранение информации о типе ребра.
+
== Источники информации ==
  
Второй способ: заметим, что на самом деле мы можем объединить ребра типа <tex>L</tex> и <tex>R</tex> в ребро типа <tex>D</tex>, которое значит, что мы спускаемся вниз, а в которого ребенка в левого или в правого, можно определить на месте. Таким образом требуемый объем памяти снижается до <tex>2\cdot(2n - 2)</tex>, так как мы до сих пор по каждому ребру проходим дважды, но уже на хранение информации о ребре требуется лишь один бит.
+
*[http://answerstop.org/question/127217/efficient-way-of-storing-huffman-tree Answerstop.org Efficient way of storing Huffman tree]
 +
*[http://hashcode.ru/questions/283569/алгоритм-как-хранить-дерево-хаффмана Hashcode.ru — Как хранить дерево Хаффмана?]
  
Третий способ: модифицируем значение команды <tex>U</tex>. Пусть теперь символ <tex>U</tex> значит, что мы поднимаемся к предку текущей вершины, пока мы — правый ребенок или пока не достигли корня, и если мы, остановившись, пришли из левого сына вершины, перейдем по ребру в правого ребенка. Несложно заметить, что мы корректно обойдем все дерево, а так же при обработке каждого символа (как <tex>U</tex>, так и <tex>D</tex>) мы ровно по одному ребру проходим в первый раз. Значит, длина строки — <tex>2n - 2 + 1 = 2n - 1</tex> (по каждому ребру проходим один раз, а так же последний <tex>U</tex> дает возможность понять, что мы обошли все дерево, и служит терминальным символом).
 
  
Вторая подзадача, передача информации о соответствии листов в дереве и символов алфавита.
+
[[Категория: Дискретная математика и алгоритмы]]
Сопоставим каждому символу алфавита равномерный код <tex>c'</tex> длины <tex>n \lceil log_{2} \rceil n</tex> - его порядковый номер в алфавите, записанный в двоичной системе счисления. Тогда, если выписать подряд коды <tex>c'</tex> для всех символов в том порядке, в котором dfs посещает соответствующие им листы, несложно восстановить, какому символу какой код <tex>c</tex> соответствует.
 
  
Итого, задача решена с использованием <tex>n \lceil log_{2} \rceil n + 2n - 1</tex> бит.
+
[[Категория: Алгоритмы сжатия ]]

Текущая версия на 16:25, 15 января 2015

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


Задача:
Пусть у нас есть алфавит [math]\Sigma = \{a_1, a_2, \cdots, a_n\}[/math], [math]|\Sigma| = n[/math], и код [math]c[/math], сопоставляющий каждому символу [math]a_i[/math] его код [math]c_i[/math]. Нужно придумать эффективное представление кода [math] c [/math] в памяти.


Простое решение[править]

Заметим, что [math]\forall i: |c_i| \leqslant n[/math]. Дополним все коды до длины [math] n [/math] нулями с конца и запишем их друг за другом. Также необходимо передать [math] n [/math]. При условии, что [math] n [/math] не превышает [math] 2^{32} - 1 [/math] получаем [math] 32 + n^2 [/math] дополнительных бит на передачу префиксного кода.

Чтобы декодировать полученную информацию о коде, достаточно сначала узнать [math]n[/math] и записать в префиксное дерево коды всех символов. Построив соответствующее дерево, можно заметить, что некоторые вершины являются единственным ребенком — такие вершины получены в результате дополнения нашего оптимального кода до [math]n[/math] бит нулями. Все такие вершины можно просто удалить из дерева, и мы получим оптимальный префиксный код, который мы передавали.

Докажем, что код который мы получили совпадает с изначальным. В результате дополнения всех кодов до длины [math]n[/math] мы, очевидно, ничего не потеряли в структуре дерева, ведь дополнение кода нулями фактически равносильно добавлению к дереву пустых (не несущих информации) листьев и вершин. В результате удаления вершин, являющихся единственным ребенком, мы также не удалим лишние: предположим мы удалили вершину, в которой содержался какой-то код, тогда она не могла быть единственным ребенком ввиду самого алгоритма Хаффмана, ведь мы выбираем два узла с наименьшим весом и добавляем их к вновь сформированному узлу.

Пример[править]

Для примера возьмем слово "миссисипи". Тогда код [math] c [/math] будет выглядеть следующим образом:

Символ и м п с
Код 0 100 101 11

При помощи нашего алгоритма [math] c [/math] будет закодирован как:

[math]0000\ 1000\ 1010\ 1100[/math]

Построим префиксное дерево по полученному коду:

Дерево Хаффмана для слова "миссисипи"

Удалив вершины, являющиеся единственными детьми у других вершин, получим зашифрованное префиксное дерево:

Дерево Хаффмана для слова "миссисипи"

Эффективное решение[править]

Построим префиксное дерево, соответствующее нашему коду [math]c[/math]. Наша задача состоит из двух подзадач: передача структуры этого дерева и передача информации, по которой впоследствии можно будет понять, где какой лист находится.

Передача структуры дерева[править]

Обойдем дерево, используя обход в глубину, причем будем сначала всегда спускаться в левого ребенка, а только потом — в правого. Каждый раз, проходя по ребру запишем одну из букв [math] L [/math], [math] R [/math] или [math] U [/math], в зависимости от того, куда по ребру мы прошли ([math]L[/math] — в левого ребенка, [math]R[/math] — в правого ребенка, [math]U[/math] — в родителя). Эта информация поможет нам восстановить дерево.

Построим обход дерева Хаффмана для слова "миссисипи":

[math]LURLLURUURUU[/math]

Первая модификация[править]

Заметим, что на самом деле мы можем объединить ребра типа [math]L[/math] и [math]R[/math] в ребро типа [math]D[/math], которое значит, что мы спускаемся вниз, а в которого ребенка — в левого или в правого, можно определить на месте.

Модифицируем наш обход:

[math]DUDDDUDUUDUU[/math]

Вторая модификация[править]

Модифицируем значение команды [math]U[/math]. Пусть теперь символ [math]U[/math] значит, что мы поднимаемся к предку текущей вершины, пока мы — правый ребенок или пока не достигли корня, и если мы, остановившись, пришли из левого сына вершины, перейдем по ребру в правого ребенка. После такой модификации записывая каждый символ мы ровно по одному ребру проходим в первый раз. Конечный вариант кодировки дерева: [math]DUDDUUU[/math] Распишем подробнее:

[math]D[/math] Спускаемся влево
[math]U[/math] Поднимаемся и спускаемся вправо
[math]D[/math] Спускаемся влево
[math]D[/math] Спускаемся влево
[math]U[/math] Поднимаемся и спускаемся вправо
[math]U[/math] Поднимаемся, поднимаемся и спускаемся вправо
[math]U[/math] Поднимаемся до корня

Оценим используемое количество памяти. Так как в нашем дереве [math] n [/math] листьев, то в нем [math] 2 \cdot n - 2 [/math] ребер (это легко показать из алгоритма Хаффмана, в нем [math] n - 1 [/math] итерация и на каждой в дерево добавляется по два ребра), а символов в нашей записи будет [math] 2 \cdot n - 1 [/math], так как на каждое ребро приходится по символу плюс последний, терминальный, [math] U [/math]. Заметим, что терминальный [math]U[/math] нам вообще говоря не нужен: мы всегда в конце поднимаемся в корень дерева, а значит, если все символы прочитаны — то обход закончен. Итоговая оценка памяти: [math] 2 \cdot n - 2 [/math].

Передача информации для восстановления листьев[править]

Алфавит нам будет дан изначально, не будет лишь кодов каждого символа, следовательно нам нужно просто указать, какой лист в дереве соответствует каждому символу. Занумеруем подряд все символы алфавита. Сопоставим каждому символу алфавита код фиксированной [math]c'[/math] длины [math] \lceil \log _2 \rceil n[/math] — его порядковый номер в алфавите, записанный в двоичной системе счисления. Все коды имеют фиксированную длину, а значит легко понять где заканчивается один, и начинается другой код. Тогда, если выписать подряд коды [math]c'[/math] для всех символов в том порядке, в котором обход в глубину посещает соответствующие им листы, несложно восстановить, какому символу какой код [math]c[/math] соответствует. Когда мы, в результате обхода в глубину, пришли в вершину, у которой нет детей, мы возьмем следующий переданный нам номер, посмотрим в нашем алфавите что это за символ, и присвоим текущей вершине этот символ.

Отсутствие некоторых символов в тексте[править]

Предположим теперь, что не все символы из алфавита были использованы в тексте, тогда возникает вопрос: получив очередной код, как узнать какому символу он принадлежит? Для решения этой проблемы поступим следующим образом: выпишем подряд коды [math]c'[/math] в том порядке, в котором обход в глубину посещает соответствующие им листы, лишь для тех символов, что были использованы в нашем сообщении. Тогда встретив очередной символ, мы гарантированно будем знать, что он встречался в нашем сообщении.

Используемая память[править]

В этом решении нам также придется передавать размер алфавита ([math]32[/math] бита).

Итого, задача решена с использованием [math]n \lceil \log_2 \rceil n + 2n - 1 + 32 = n \lceil \log_2 \rceil n + 2n + 31 [/math] бит.

Если же были использованы не все символы, то будет использовано [math]k \lceil \log_2 \rceil n + 2k - 1 + 32 = k \lceil \log_2 \rceil n + 2k + 31 [/math] бит, где [math]k[/math] — количество использованных символов.

Реализация[править]

 // 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)

См. также[править]

Источники информации[править]