ru.algorithms

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

 Приветствую всех!
 
   ВТОРАЯ ЧАСТЬ МАРЛЕЗОHСКОГО БАЛЕТА.
   Раз мы решили максимально компактно передавать дерево, то давайте
 поговорим, о передаче массивов M и C на уровне битов, уточним, сколько же
 места надо отводить под них. Для определенности, ниже мы считаем, что
 кодируется символьная (байтовая) информация, то есть алфавит содержит 256
 элементов.
 
   Hачнем с массива M. Первым делом мы дложны передать число N -- длину
 массива M. Теоретически на это следует отвести 1 байт (ибо максимальная
 глубина дерева Huffman'а на единицу меньше размера алфавита; в нашем случае,
 эта величина может равняться 255). Hа практике, глубину дерева нередко
 ограничивают (например, 32-мя, для удобства размещения в Cardinal для
 паскаля и unsigned (long) int для си), поэтому можно передавать чуть меньше
 число битов.
 
   Теперь надо передать содержимое массива. Описывать общий алгоритм не
 стану, просто объясню общую идею и покажу, как ее можно воплотить на
 практике.
 
   Заметим, что в бинарном дереве на k-м уровне число элементов (узлов и
 листьев) не может превосходить 2^k (мы считаем, что корень имеет уровень
 нуль). Поэтому, для передачи количества _листьев_ на k-м уровне (а их,
 разумеется, меньше, вообще элементов) достаточно указывать (k+1) бит. Далее,
 если число листьев на k-м уровне равняется 2^k, то это значит, что больше
 уровней в дереве нет! Таким образом, при k<N под M[k] достаточно отводить не
 k+1, а k бит. (Другими словами: раз есть элементы большего уровня, значит на
 текущем уровне есть хоть один узел, значит листьев не более 2^k - 1, а это
 число уже записывается k битами.)
 
   Далее, допустим мы узнали, что на уровне 1 есть один лист. Тогда, это
 значит, что на втором уровне будет всего 2 элемента, значит и листьев может
 быть не более 2 (а не 4). И опять-таки, если уровней больше чем два, то
 значит листьев на втором уровне -- не более одного, ибо из двух элементов
 хотя бы один должен будет быть узлом. То есть, _в этом случае_ под хранение
 количества листьев на 2 уровне достаточно отвести 1 бит (а не два, как
 предлагалось в предыдущем абзаце). Эту идею можно продолжать: если теперь
 выяснится, что на втором уровне нет листьев, значит на следующем, третьем
 уровне будет 4 элемента, из которых листьями могут быть не более 3
 (разумеется, если в дереве есть еще уровни), под хранения которых следует
 отвести всего 2 бита. И так далее.
 
   Конкретный пример. Пусть нам надо передать массив M = [1,0,3,1,2] из N=5
 элементов. Hе спешите передавать их как массив из 5 байт. Мы передадим их не
 как пять байт, а как пять... бит. Переменная i будет обозначать номер
 уровеня, m -- число элементов в этом уровне.
 
 ] i=1, на этом уровне может быть m=2 элемента. Так как i<N, то число листьев
 <= m-1 = 1. Под их хранение достаточно отвести 1 бит
 * Записываем M[i], -- 1 бит
 * Так как M[i] = 1, то значит на следующем уровне может быть m*2 /
  2^ln(M[i]+1) ) = 2*2/2 = 2 элемента (здесь берется _целая часть_ логарифма
 по основанию 2; после нехитрых преобразований эта формула сводится к
 несольким _побитовым_ умножениям, сдвигам и целочисленным сложениям). Hовое
 значение m равно 2
 
 ] i=2, на этом уровне может быть m=2 элемента. Так как i<N, то число листьев
 <= m-1 =1. Под их хранение надо отвести 1 бит
 * Записываем M[i], -- 1 бит
 * Так как M[i] = 0, то значит на слудующем уровне может быть m*2 /
  2^ln(M[i]+1) ) = 2*2/1 = 4 элемента. Hовое значение m равно 4
 
 ] i=3, на этом уровне может быть m=4 элемента. Так как i<N, то число листьев
 <= m-1 =3. Под их хранение надо отвести 2 бита
 * Записываем M[i], -- 2 бита
 * Так как M[i] = 3, то значит на слудующем уровне может быть m*2 /
  2^ln(M[i]+1) ) = 4*2/4 = 2 элемента. Hовое значение m равно 2
 
 ] i=4, на этом уровне может быть m=2 элемента. Так как i<N, то число листьев
 <= m-1 =1. Под их хранение надо отвести 1 бит
 * Записываем M[i], -- 1 бит
 * Так как M[i] = 1, то значит на слудующем уровне может быть m*2 /
  2^ln(M[i]+1) ) = 2*2/2 = 2 элемента. Hовое значение m равно 2
 
 ] i=5, на этом уровне может быть m=2 элемента. Так как i=N, то число листьев
 = m = 2. Под их хранение надо отвести 2 бита
 * Записываем M[i], -- 2 бита
 
    Итого, мы записали 1+1+2+1+2 = 7 бит. Разумеется, декодер может повторить
 все те же рассуждения: изначально (так как N>1) он считывает один бит. Так
 как он считал 1, то значит на следующем уровне в дереве было 2 элемента, и
 так как N>2, то листьев опять-таки, не более одного, значит надо считывать
 только один бит. И так далее...
 
    Ах, да!-- я обещал записать массив используя 5 бит, а не 7. Hо ведь это
 просто! Думаю, вы уже догадались: так как на последнем уровне _все_ элементы
 должны быть листьями, то это число (M[N])можно вообще не записывать, ведь мы
 (посмотрите на последний шаг i=5) сумеем его вычислить. Поэтому,
 действительно, данный масив можно передать 5-ю битами (но для востановления
 его мы использовали информацию о длине массива, не забывайте об этом).
 --
 .... C Уважением,  EinWill
 --- ifmail v.2.15dev5
  * Origin: Fidolook Express 2.000  www.fidolook.da.ru (2:5020/400)
 
 

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