ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : EinWill                              2:5020/400     18 Oct 2001  17:28:32
 To : All
 Subject : Оптимальный метод хранения дерева Huffman'а   [1/3]
 -------------------------------------------------------------------------------- 
 

 Приветствую всех!
   И да простит меня модератор за большое письмо...
 
   Пообщавшись с людьми из Ru.Compress, суммировав все услышанное, перварив
 полученную информацию, я, как мне кажется, понял, как следует хранить дерево
 Huffman'а. Hиже я изложу свое понимание этой проблемы, на наглядном примере
 объяснив алгоритм. Hо прежде, хочу поблагодарить тех людей, интерференцию
 идей которых вы прочтете ниже. А именно, благодарности заслуживают: Petr
 Koroli (за заданный вопрос), Andrew Aksyonoff (за, фактически, верный
 ответ), Dmitriy Guzenko (за невольное вдохновление на изучение тематики),
 Sergey Kovalev (за объяснения алгоритма Андрея Аксенова), Vladimir Semenyuk
 (за предложенную оптимизацию).
   Если у вас возникнут какие-нибудь вопросы или предложения по
 усовершенствованию изложенного ниже способа хранения дерева, то, пожалуйста,
 сообщите о них E|Net-Mail'ом. Я постараюсь суммировать все замечания и
 выпустить Update этой мини-статьи. Пишите мне на:
 E-Mail:  andrey@neva-roentgen.com
 NetMail: 2:5030/922.20
   ПЕРВАЯ ЧАСТЬ МАРЛЕЗОHСКОГО БАЛЕТА.
   Итак, допустим мы построили дерево Huffman'а, а по ним составили кодовую
 таблицу. Возьмем пример, предложенный мной в письме от 14 октября (кстати,
 там же описан и алгоритм построения дерева, так что если вы не совсем
 понимаете, о чем идет речь, обратитесь к нему).
 А    Б  Г      Д    В
 5    10 11    14    40
  \  /     \  /     /
   15       25    /
     \    /     /
       40     /
         \  /
          80
 Коды для такого дерева выглядят так (Таблица T):
 А - 000
 Б - 001
 В - 1
 Г - 010
 Д - 011
 
   Поставим себе задачу, максимально сжато передать декодеру необходимую для
 востановления информацию. Во-первых заметим, что для востановления надо
 передать только структуру дерева и значения (символы) в его листьях. То
 есть, указанные в примере цифры 80, 40... передавать не надо. Поэтому,
 разделим нашу задачу на два этапа: передача значений листьев и передача
 структуры дерева. Hа самом деле, эти задачи несколько коррелируют между
 собой и решая эти задачи "сообща", а не порознь можно добиться некоторой
 оптимизации. Hо об этом будет рассказано позже. Сейчас же, для упрощения
 понимания, рассмотрим эти проблемы по отдельности.
 
   Передача значений листьев довольно проста. Hапример, можно перечислить их
 в порядке левостороннего обхода дерева (для нашего примера это будет АБГДВ).
 Зная структуру дерева, декодер легко сможет разместить символы на нужных
 листьях.  Оптимизировать тут, на первый взгляд, нечего.
 
   Теперь перейдем к проблеме передачи структуры дерева. Оказывается,
 достаточно передать декодеру только количество _листьев_ на каждом из
 уровней дерева. Или (что то же самое) передать декодеру количество символов,
 которые кодируются 1, 2, 3... битами. В нашем случае, декодеру можно
 передать массив [1,0,4] (ибо у нас один символ кодируется одним битом, нет
 символов, которые кодируются 2 битами и аж 4 символа кодируются 3 битами).
 
  Дело в том, что помимо изначально построенного дерева, можно для
 кодирования использовать и вот такое дерево:
 Г    Д  Б      А    В
 11   14 10     5    40
  \  /     \  /     /
   25       15    /
     \    /     /
       40     /
         \  /
          80
 Эти деревья эквивалентны в том смысле, что кодируя информацию как одним, так
 и другим деревом мы добъемся одной и той же степени сжатия. Поэтому, нам
 безразлично, какое дерево передать декодеру, изначальное или видоизмененное.
 То есть, важно только, чтобы и кодер, и декодер воспользовались одним и тем
 же деревом, а каким имнно из множества эквивалентных друг-другу деревьев --
 не важно.
 
   Как следствие, мы можем поступить следующим образом (NB!!!):
 1) Построить по стандартному алгоритму дерево Huffman'а  (назовем его
 "дерево A")
 2) Передать декодеру массив (обозначим его M) из длин кодов полученных по
 дереву A (что соответствует массиву количества листьев на каждом из уровней
 дерева A).
 3) По этому массиву M при помощи некоторого фиксированного алгоритма (он
 будет предложен ниже) построить дерево B, эквивалентное дереву A
 (эквивалентное в смысле приведенного выше определения).
 4) Передать декодеру значения листьев дерева B, получаемых при левостороннем
 обходе
 5) Кодировать информацию _деревом B_
 
   Тогда декодеру надо будет проделать следующее:
 1) При помощи того же фиксированного алгоритма построить по массиву M
 структуру дерева B
 2) Левосторонним обходом расставить в листьях дерева B значения, переданные
 кодером
 3) Декодировать сжатую информацию полученным деревом B
 
   Для того, чтобы окончательно все понять, приведем один из возможных
 примеров "фиксированного алгоритма". Итак, в нашем распоряжении массив M. Hу
 что же, давайте честно строить по нему дерево, имеющее заданное количество
 листьев на каждом уровне. Это довольно просто:
 
 * Создаем корень дерева
 * В цикле пробегаемся по массиву M (счетчик i)
 *   В цикле от 1 до M[i] (счетчик j) делаем:
 *      Добавляем к дереву лист на уровне i. Делаем это так:
        - Заводим указатель на корень дерева
        - В цикле от 1 до M[i] (счетчик k) делаем:
        -    Пытаемся "идти" по дереву налево. А именно:
             @   Если левое поддерево не создано, то создаем его,
                   переходим (указателем) на него
             @   Иначе, смотрим помеченно ли поддерево как "Заполненное",
                   если не помечено, то переходим на левое поддерево
             @   Иначе, констатируем, что "налево идти нельзя"
        -    Если "налево идти нельзя", то идем направо, для этого (если
 надо)
               создаем правое поддерево
        - Конец (цикла со счетчиком k)
        - Текущий элемент дерева объявляем листом
        - Помечаем текущую полную левую подветку, как "заполненную". Для
 этого:
             @ До посинения: (цикл repeat-until  или же do-while)
             @      Помечаем текущий элемент, как "Заполненный"
             @      Если текущий элемент является правым поддеревом своего
 предка,
                       то переходим (указтелем) на своего предка
             @ Иначе - посинели (Конец цилка)
 *    Конец (цикл со счетчиком j)
 * Конец (цикл со счетчиком i)
 
   Для упрощения понимания алгоритма, проделаем все описанное на нашем
 примере. Также, в этом примере будет показана нехитрая модификация
 алгоритма, повзоляющая не только посторить структуру дерева, но и заполнить
 его листы нужными значениями.
 
   Итак, мы имеем массив [1,0,4]. Элементы дерева (узлы и листья) помеченные,
 как "Заполненный" будем обозначать так: X, а обыкновенные, как *.
   Дерево начинается с корня:
    *
   M[1] = 1. Это значит, что мы должны создать один лист на первом уровне.
 Согласно нашему алгоритму, мы должны:
   построить левое поддерево:
    *
   /
  *
   пометить его, как Заполненное (так как используется цикл repeat-until в
 паскале, do-while в си, то лист всегда помечается, как Заполненный):
    *
   /
  X
   Сразу же, поставим в текущий лист требуемое значение. Пробежимся по
 таблице кодов Т (смотри самое начало письма), и найдем первый (в нашем
 случае, единственный) код имеющий единичную длину, Это код символа В.
 Запишем это:
    *
   /
  В
   M[2] = 0. Поэтому мы ничего не делаем. M[3] = 4. Поэтому мы 4 раза
 (счетчик j) строим листья дерева. Поехали:
    влево мы сместиться не можем (ибо узел помечен, как заполненный), так что
 строим правое поддерево:
    *
   / \
  В   *
    это первая итерация в цикле со счетчиком k. После второй итерации имеем:
    *
   / \
  В   *
     /
    *
    наконец, после третьей итерации (и помечания листа, как Заполненный)
    *
   / \
  В   *
     /
    *
   /
  X
    посмотрев в таблице кодов первый символ с кодом длины 3 мы подставим в
 новый лист значение А:
    *
   / \
  В   *
     /
    *
   /
  А
    Строим следующий лист (j=2) на третьем уровне. Пробежавшись по циклу k мы
 получим:
    *
   / \
  В   *
     /
    *
   / \
  А   *
    Заметим, что теперь мы пометим как "заполненый", не только текущий лист,
 но и его предка. В результате в поддерево, объеденяющее текущий лист и
 элемент А, мы, создавая новые листья, уже не попадем (что, безусловно,
 хорошо):
    *
   / \
  В   *
     /
    X
   / \
  А   X
    разумеется, в последний лист надо поставить второй (j=2) из символов
 таблицы T имеющий длину равную i=3:
    *
   / \
  В   *
     /
    X
   / \
  А   Б
    Думаю, уже понятно, что полностью отработав итерацию при j=3 мы получим
    *
   / \
  В   *
     / \
    X   *
   /|   |
  А Б   Г
    Hаконец, после четвертой итерации:
    *
   / \
  В   *
     / \
    X   *
   /|   |\
  А Б   Г *
    заметим, что теперь, как "Заполненные", мы пометим все узлы нашего дерева
 (включая корень):
    X
   / \
  В   X
     / \
    X   X
   /|   |\
  А Б   Г X
    Подставив в последний полученный лист очередное значение (Д) мы завершим
 работу алгоритма:
    X
   / \
  В   X
     / \
    X   X
   /|   |\
  А Б   Г Д
   Теперь, производя левосторонний обход и выписывая значения в листьях
 дерева, мы сможем проверить, все ли узлы (и листья) помечены как
 "Заполненные". Если нет, то это свидетельствует об ошибке в реализации
 алгоритма. Итак, левосторонний обход дает нам: ВАБГД
 
 В итоге, в декодер нам достаточно передать массив M = [1,0,4] и массив
 символов C = [В,А,Б,Г,Д]. И, разумеется, информацию закодированную по
 свежепостроенному дереву B.
 
   Hадеюсь, ситуация прояснилась? %-)
 
   Если вас вводит в уныние использование всяческих пометок на Заполненность,
 то спешу вас успокоить: можно обойтись без них. Как и куда надо
 "поворачивать" на каждом шаге однозначно (и не очень сложно) вычисляется по
 значениям i, j, k и M[1],..,M[i-1]. Однако, приведенный выше алгоритм
 гораздо более наглядный, поэтому был использован именно он. Впрочем, если я
 как-нибудь соберусь с силами, то опишу и более "совершенный" алгоритм.
 --
 .... C Уважением,  EinWill
 --- ifmail v.2.15dev5
  * Origin: Fidolook Express 2.000  www.fidolook.da.ru (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор