11 / 14
Алгоритм кодирования бинарного дерева с минимальной избыточностью
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2017. № 3
43
Окончание таблицы
N
1
2
L N
=
2
2
log
N
L
C
=
1
R
2
R
4
8
4
0,524
0,048
5
10
6
0,461
0,101
6
12
8
0,413
0,119
7
14
9
0,375
0,028
8
16
11
0,345
0,047
9
18
13
0,32
0,058
10
20
15
0,298
0,064
20
40
33
0,185
0,012
30
60
52
0,137
0,005
40
80
72
0,111
0,012
50
100
91
0,093
0,004
60
120
111
0,081
0,006
70
140
130
0,072
0,0003
80
160
150
0,065
0,002
90
180
170
0,059
0,003
100
200
190
0,054
0,004
200
400
388
0,031
0,0008
300
600
587
0,022
0,0003
400
800
787
0,017
0,001
500
1000
986
0,014
0,0003
600
1200
1186
0,012
0,0006
700
1400
1385
0,011
0,000004
800
1600
1585
0,01
0,0002
900
1800
1785
0,009
0,0003
1000
2000
1985
0,008
0,0004
Заключение.
Разработан алгоритм, позволяющий кодировать структуры
бинарных деревьев с помощью битовых последовательностей минимальной
длины. Длина битовой последовательности разработанного кода близка к ми-
нимальному теоретически возможному значению:
(
)
2
2 Θ log
n
n
−
бит. Недо-
статком разработанного метода является невозможность эффективного выпол-
нения операций с закодированным представлением дерева без его предвари-
тельного декодирования и преобразования в более удобное представление. Тем
не менее это кодирование было применено автором в хромосоме генетического
алгоритма, оптимизирующего графический пользовательский интерфейс. Кро-
ме того, алгоритм может быть использован в системах связи или сжатия ин-
формации. Известные методы однозначного преобразования бинарных деревь-
ев в обычные деревья и другие смежные объекты [2, 12] позволяют кодировать
любые древовидные структуры и леса с использованием разработанного алго-
ритма.