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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Пример)
(Используемая память)
 
(не показано 25 промежуточных версий 2 участников)
Строка 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>\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> 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>\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>n</tex> бит нулями. Все такие вершины можно просто удалить из дерева, и мы получим оптимальный префиксный код, который мы передавали.
+
Докажем, что код который мы получили совпадает с изначальным. В результате дополнения всех кодов до длины <tex>n</tex> мы, очевидно, ничего не потеряли в структуре дерева, ведь дополнение кода нулями фактически равносильно добавлению к дереву пустых (не несущих информации) листьев и вершин. В результате удаления вершин, являющихся единственным ребенком, мы также не удалим лишние: предположим мы удалили вершину, в которой содержался какой-то код, тогда она не могла быть единственным ребенком ввиду самого алгоритма Хаффмана, ведь мы выбираем два узла с наименьшим весом и добавляем их к вновь сформированному узлу.  
  
 
=== Пример ===
 
=== Пример ===
Строка 37: Строка 39:
 
== Эффективное решение ==
 
== Эффективное решение ==
  
Построим префиксное дерево, соответствующее нашему коду <tex>c</tex>. Наша задача состоит из двух подзадач: передача структуры этого дерева и передача информации для различения листьев.
+
Построим префиксное дерево, соответствующее нашему коду <tex>c</tex>. Наша задача состоит из двух подзадач: передача структуры этого дерева и передача информации, по которой впоследствии можно будет понять, где какой лист находится.
  
 
=== Передача структуры дерева ===
 
=== Передача структуры дерева ===
  
Обойдем дерево, используя [[Обход в глубину, цвета вершин|обход в глубину]]. Каждый раз, проходя по ребру запишем одну из букв <tex> L </tex>, <tex> R </tex> или <tex> U </tex>, в зависимости от того, куда по ребру мы прошли (<tex>L</tex> - в левого ребенка, <tex>R</tex> - в правого ребенка, <tex>U</tex> - в родителя). Эта информация поможет нам восстановить дерево.
+
Обойдем дерево, используя [[Обход в глубину, цвета вершин|обход в глубину]], причем будем сначала всегда спускаться в левого ребенка, а только потом — в правого. Каждый раз, проходя по ребру запишем одну из букв <tex> L </tex>, <tex> R </tex> или <tex> U </tex>, в зависимости от того, куда по ребру мы прошли (<tex>L</tex> в левого ребенка, <tex>R</tex> в правого ребенка, <tex>U</tex> в родителя). Эта информация поможет нам восстановить дерево.
  
 
Построим обход дерева Хаффмана для слова "миссисипи":
 
Построим обход дерева Хаффмана для слова "миссисипи":
  
LURLLURUURUU
+
<tex>LURLLURUURUU</tex>
  
 
==== Первая модификация ====
 
==== Первая модификация ====
Строка 53: Строка 55:
 
Модифицируем наш обход:
 
Модифицируем наш обход:
  
DUDDDUDUUDUU
+
<tex>DUDDDUDUUDUU</tex>
  
 
==== Вторая модификация ====
 
==== Вторая модификация ====
 
 
Модифицируем значение команды <tex>U</tex>. Пусть теперь символ <tex>U</tex> значит, что мы поднимаемся к предку текущей вершины, пока мы — правый ребенок или пока не достигли корня, и если мы, остановившись, пришли из левого сына вершины, перейдем по ребру в правого ребенка. После такой модификации записывая каждый символ мы ровно по одному ребру проходим в первый раз.
 
Модифицируем значение команды <tex>U</tex>. Пусть теперь символ <tex>U</tex> значит, что мы поднимаемся к предку текущей вершины, пока мы — правый ребенок или пока не достигли корня, и если мы, остановившись, пришли из левого сына вершины, перейдем по ребру в правого ребенка. После такой модификации записывая каждый символ мы ровно по одному ребру проходим в первый раз.
 
 
Конечный вариант кодировки дерева:
 
Конечный вариант кодировки дерева:
 
+
<tex>DUDDUUU</tex>
DUDDUUU
 
 
 
 
Распишем подробнее:
 
Распишем подробнее:
 
+
{| class=wikitable
{| class="wikitable"
+
| <tex>D</tex> || Спускаемся влево
| D || Спускаемся влево
 
 
|-
 
|-
| U || Поднимаемся и спускаемся вправо
+
| <tex>U</tex> || Поднимаемся и спускаемся вправо
 
|-
 
|-
| D || Спускаемся влево
+
| <tex>D</tex> || Спускаемся влево
 
|-
 
|-
| D || Спускаемся влево
+
| <tex>D</tex> || Спускаемся влево
 
|-
 
|-
| U || Поднимаемся и спускаемся вправо
+
| <tex>U</tex> || Поднимаемся и спускаемся вправо
 
|-
 
|-
| U || Поднимаемся, поднимаемся и спускаемся вправо
+
| <tex>U</tex> || Поднимаемся, поднимаемся и спускаемся вправо
 
|-
 
|-
| U || Поднимаемся до корня
+
| <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> n </tex> листьев, то в нем <tex> 2 \cdot n - 2 </tex> ребер (это легко показать из алгоритма Хаффмана, в нем <tex> n - 1 </tex> итерация и на каждой в дерево добавляется по 2 ребра), а символов в нашей записи будет <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>c'</tex> длины <tex> \lceil \log _2 \rceil n</tex> - его порядковый номер в алфавите, записанный в двоичной системе счисления. Тогда, если выписать подряд коды <tex>c'</tex> для всех символов в том порядке, в котором обход в глубину посещает соответствующие им листы, несложно восстановить, какому символу какой код <tex>c</tex> соответствует.
+
=== Отсутствие некоторых символов в тексте ===
 +
Предположим теперь, что не все символы из алфавита были использованы в тексте, тогда возникает вопрос: получив очередной код, как узнать какому символу он принадлежит? Для решения этой проблемы поступим следующим образом: выпишем подряд коды <tex>c'</tex> в том порядке, в котором обход в глубину посещает соответствующие им листы, лишь для тех символов, что были использованы в нашем сообщении. Тогда встретив очередной символ, мы гарантированно будем знать, что он встречался в нашем сообщении.
  
 
=== Используемая память ===
 
=== Используемая память ===
  
В этом решении нам также придется передавать размер алфавита (32 бита).
+
В этом решении нам также придется передавать размер алфавита (<tex>32</tex> бита).
  
 
Итого, задача решена с использованием <tex>n \lceil \log_2 \rceil n + 2n - 1 + 32 = n \lceil \log_2 \rceil n + 2n + 31 </tex> бит.
 
Итого, задача решена с использованием <tex>n \lceil \log_2 \rceil n + 2n - 1 + 32 = n \lceil \log_2 \rceil n + 2n + 31 </tex> бит.
  
== Ссылки ==
+
Если же были использованы не все символы, то будет использовано <tex>k \lceil \log_2 \rceil n + 2k - 1 + 32 = k \lceil \log_2 \rceil n + 2k + 31 </tex> бит, где <tex>k</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)
 +
 
 +
== См. также ==
 +
*[[Алгоритм_Хаффмана_за_O(n) | Алгоритм Хаффмана за O(n)]]
 +
 
 +
== Источники информации ==
 +
 
 +
*[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 — Как хранить дерево Хаффмана?]
  
*[[Алгоритм Хаффмана]]
 
*[[Обход в глубину, цвета вершин|Обход в глубину]]
 
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
  
 
[[Категория: Алгоритмы сжатия ]]
 
[[Категория: Алгоритмы сжатия ]]

Текущая версия на 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)

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

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