ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2017. № 3
33
УДК 519.171.2
DOI: 10.18698/0236-3933-2017-3-33-46
АЛГОРИТМ КОДИРОВАНИЯ БИНАРНОГО ДЕРЕВА
С МИНИМАЛЬНОЙ ИЗБЫТОЧНОСТЬЮ
В.П. Корвяков
vladimir.korviakov@gmail.comПАО «Ракетно-космическая корпорация «Энергия» им. С.П. Королёва»,
Королёв, Московская обл., Российская Федерация
Аннотация
Ключевые слова
Предложен алгоритм кодирования и декодирования
бинарных деревьев с минимальной избыточностью, т. е.
использующий битовые последовательности минималь-
но возможной длины. Рекурсивное вычисление индек-
сов деревьев выполнено с использованием чисел Ката-
лана. Приведены оценки сложности алгоритма. Разра-
ботанный метод позволяет построить бинарное дерево
на основе уникального индекса его структуры и числа
узлов без необходимости явного перечисления всех
возможных структур деревьев. Минимальная длина
битовой последовательности дает возможность оптими-
зировать деревья с заданным числом узлов с помощью
генетических алгоритмов
Бинарное дерево, числа Каталана,
алгоритм кодирования, мини-
мальная избыточность
Поступила в редакцию 30.09.2016
©МГТУ им. Н.Э. Баумана, 2017
Введение.
В процессе работы над методами оптимизации и автоматической ге-
нерации графических пользовательских интерфейсов автор настоящей статьи
столкнулся с проблемой кодирования структуры данных, представляющей ком-
поновку элементов графического интерфейса с помощью бинарного дерева.
В принятой модели интерфейс представлен набором виджетов (элементов ин-
терфейса), положение и размеры которых определены рекурсивным раздвоени-
ем прямоугольных областей в вертикальном или горизонтальном направлении.
При такой компоновке виджеты ассоциируются с листовыми узлами строго би-
нарного дерева.
Задача осложняется тем, что рассматриваемая структура данных должна
быть закодирована в битовую последовательность фиксированной (для задан-
ного числа виджетов) длины так, чтобы изменение любого ее бита преобразо-
вывало последовательность в непротиворечивую битовую последовательность,
также кодирующую интерфейс с таким же числом виджетов. Не должно возни-
кать противоречий в битовой последовательности при скрещивании двух раз-
личных битовых последовательностей (рис. 1). Это ограничение связано с тем,
что битовая последовательность должна быть использована в качестве хромо-
сомы генетического алгоритма, который оптимизирует интерфейс с позиции
заданного критерия [1]. Для ускорения работы генетического алгоритма длина
хромосомы должна быть минимальной, а ее содержание — непротиворечивым.