3 / 14
Алгоритм кодирования бинарного дерева с минимальной избыточностью
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2017. № 3
35
Откуда следует, что число битов, необходимое для кодирования структуры би-
нарного дерева с
N
узлами, равно
2
log ,
N
C
где скобки обозначают округление
до ближайшего целого в большую сторону. Например, хранение бинарного де-
рева с девятью узлами потребует
2 9
2
log
log 4862 13
C
=
=
бит. Последова-
тельность длиной
2
log
N
C
вследствие округления в большую сторону облада-
ет некоторой избыточностью информации по отношению к исходному сообще-
нию. Величина абсолютной избыточности равна
2
2
lo
.
g
log
a
N
N
R
C
C
=
−
Относительная избыточность составляет
2
2
2
log
log
.
log
N
N
N
C
C
R
C
−
=
На практике это будет выражаться в том, что последние
2
log
2
N
C
N
C
−
со-
общений не будут соответствовать никакой структуре. Для того чтобы получить
из исходного сообщения
2
log
0; 2
1
N
C
I
∈
−
валидный индекс бинарного дере-
ва, необходимо вычислить его как остаток от деления
I
на
.
N
C
Здесь и далее би-
товая последовательность длиной
L
будет отождествляться с соответствующим
ей целым числом
0; 2 1 .
L
I
∈ −
Кроме того, будем использовать индексацию,
начинающуюся с нуля.
Следует отметить, что существуют различные методы кодирования бинар-
ных деревьев. Этой задаче посвящена, например, работа [4]. Предложенный в
этой работе метод требует строго
2
N
бит данных для кодирования бинарных
деревьев с
N
узлами. Это основано на аппроксимации чисел Каталана [5]:
4 ;
N
N
C
N N
≈
π
2
2
2
2
3
1
log
log 4 log
log 2 .
2
2
N
N
C
N
N
≈
−
−
π <
Другой метод кодирования деревьев, позволяющий кодировать деревья с
N
узлами последовательностью
( )
2
N o N
+
бит, представлен в работе [6]. Достоин-
ство этого метода состоит в том, что он позволяет выполнять операции с закоди-
рованным деревом за время
( )
1
O
. Еще более компактное представление, требу-
ющее
(
)
( )
1
2
2
/ log
O
N N N
+
бит данных, описано в работе [7]. Достаточно полный
обзор методов кодирования приведен в работе [8]. Основной вывод указанной
работы заключается в том, что универсального способа кодирования деревьев не
существует, и для конкретных задач необходимо выбирать наиболее подходящие
методы кодирования. Тем не менее до сих пор вопрос кодирования с минимально
теоретически возможной избыточностью не был достаточно хорошо проработан.