Статья 'Эффективная структура данных' - журнал 'Кибернетика и программирование' - NotaBene.ru
по
Journal Menu
> Issues > Rubrics > About journal > Authors > About the Journal > Requirements for publication > Council of Editors > Peer-review process > Policy of publication. Aims & Scope. > Article retraction > Ethics > Online First Pre-Publication > Copyright & Licensing Policy > Digital archiving policy > Open Access Policy > Article Processing Charge > Article Identification Policy > Plagiarism check policy
Journals in science databases
About the Journal

MAIN PAGE > Back to contents
Cybernetics and programming
Reference:

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

Received:

20-11-2014


Published:

04-12-2014


Abstract: The efficiency of information retrieval systems depends significantly on the structure of the data. The selected data structure determines the speed of data operations (search, insert, delete), and the necessary cost of memory. Due to the importance of the problem of optimizing the structure of data in modern scientific and technical literature are well represented implement a variety of data structures and analysis of their effectiveness. A wide range of known effective data structures uses the properties of linear arrays of data, and binary trees. The article deals with one of the special data structure known as a digital trie (Trie unlike Tree). Search speed in the proposed structure is the statistical value and the worst value is characterized by O (log (N / 2)) and the average value of O (log (N / 2) / 2) operations. It also has the best memory cost in comparison with the traditional characteristics of a digital tree. Thus the aturhos propose and implemented an efficient data structure - "vertical" digital tree, which is characterized by high-speed data retrieval and low memory consumption.


Keywords:

data structure, tree structure, digital tree, array of pointers, red-black trees, feathered trees, key, node, memory costs, search

This article written in Russian. You can find original text of the article here .

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

m1

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

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

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

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

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

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

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

m2

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

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

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

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

Таблица 1.

Структура Затраты памяти (Overhead)
Линейный массив 256
Бинарное дерево 1024
Цифровое дерево m=2, k=8 510
m=4, k=4 340
m=16, k=2 272

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

m3

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

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

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

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

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

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

m_4

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

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

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

m_5

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

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

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

References
1.
2.
3.
Link to this article

You can simply select and copy link from below text field.


Other our sites:
Official Website of NOTA BENE / Aurora Group s.r.o.