Efficient data structure

Malashkevich Vasilii Borisovich PhD in Technical Science 424000, Russia, Marii El oblast', g. Ioshkar-Ola, ul. Pl. Lenina, 3 MalashkevichVB@volgatech.net

Malashkevich Irina Ardalionovna 424000, Russia, Marii El oblast', g. Ioshkar-Ola, pl. Lenina, 3 MalashkevichIA@volgatech.net

Работа посвящена исследованию одной из специальных структур данных, известной как цифровое дерево. (Trie в отличие от Tree) ^[1,2,3]. Цифровое дерево – иерархическая структура, организация данных в которой представлена на Рис.1

Рис.1. Структура цифрового дерева Trie.

Цифровое дерево состоит их иерархии массивов указателей, нижний уровень которой обеспечивает ссылки на данные D. Поиск данных основан на ключе, характеризующем искомые данные (обычно это хэш-функция данных). Значение ключа искомых данных определяет выбор последовательности указателей на разных уровнях дерева, обеспечивающей доступ к данным. Несложно заметить, что доступ к данным требует О(k) операций, где k – количество уровней дерева, а избыточные затраты памяти составляют

`M = (m(m^k - 1))/(m - 1)`

где m – размерность массива указателей.

Общее количество различных наборов данных в цифровом дереве составляет `N = m^k` .

Важными свойствами цифрового дерева являются отсутствие необходимости выполнения операций переконфигурации дерева при внесении новых данных для сохранения эффективности поиска данных (например операций «вращения» в красно-черных деревьях (RB-Tree) и скошенных деревьях (Splay Tree) ^[3]), а также небольшие дополнительные затраты памяти для хранения массивов ссылок.

Для сравнительной оценки избыточных затрат памяти (overhead) рассмотрим линейный массив и узел бинарного дерева (Рис.2)

Рис.2. Линейный массив и бинарное дерево.

OverHead для этих структур составляет:

`M_(Arr) = N; M_(RBT) = 4N`

Данные по затратам памяти для рассмотренных структур при N=256 (Ключ Key - 8-битное число) представлены в таблице 1

Таблица 1.

Несложно заметить, что увеличение размерности массива узла цифрового дерева ведет как к снижению затрат памяти, так и к сокращению времени доступа к данным. К сожалению, также как и для обычного линейного массива этот выигрыш достигается только для плотно заполненных структур, в которых реальное количество данных `N_(d)` близко к максимально возможному `N` . Для пояснения этого факта на Рис.3 приведены графики затрат памяти, полученные при статистическом моделировании цифрового дерева.

Рис.3. Статистическая оценка затрат памяти Trie.

Анализ графиков на Рис .3 позволяет утверждать, что с точки зрения затрат памяти цифровое дерево становится эффективнее , чем бинарное дерево, при заполнении 25-35% данных.

Для снижения затрат памяти, необходимой для цифрового дерева, в работе предложена новая организация этой структуры цифрового дерева.

Анализ поведения цифрового дерева при вставке первых данных с равномерным распределением значений ключа показывает, что каждая вставка сопровождается выделением памяти под новый массив практически на всех нижних уровнях и только при достижения 25%-ой заполненности интенсивный рост запросов на выделение памяти прекращается – используются ранее созданные массивы.

Основная идея новой структуры – ограничение потребностей в выделении памяти на начальных этапах заполнения цифрового дерева. Этого можно достичь с помощью «вертикальной» организации массивов указателей в отличие от традиционной «горизонтальной» структуры, представленной на Рис.1.

Новая оптимизированная структура содержит узлы подобные «башне» и имеет вид, представленный на Рис.4.

Рис.4 «Вертикальное» цифровое дерево

В поле Skey каждой «башни» содержатся старшие биты ключей данных, на которые указывают ссылки в основании «башни». Биты Skey определяют также условия, при которых должен выполняться переход по горизонтальной ссылке и номер ссылки в вертикальном массиве «башни». Выбор ссылки выполняется с помощью простых и быстрых битовых операций над значениями искомого ключа и поля Skey.

Скорость поиска данных в предложенной структуре – величина статистическая и характеризуется наихудшим значением О(log(N/2)) и средним значением О(log(N/2)/2)операций. Она также имеет лучшие в сравнении с традиционным цифровым деревом характеристики по затратам памяти. Их можно оценить по Рис.5

Рис.5 Затраты памяти «вертикального»цифрового дерева

Предложенная структура реализована в форме программного компонента, интерфейс которого реализует все типовые операции – вставки, удаления , поиска.

Таким образом предложена и реализована эффективная структура данных - «вертикальное » цифровое дерево, которая характеризуется высокой скоростью поиска данных и малыми затратами памяти.