Рус Eng Cn Перевести страницу на:  
Please select your language to translate the article


You can just close the window to don't translate
Библиотека
ваш профиль

Вернуться к содержанию

Кибернетика и программирование
Правильная ссылка на статью:

Эффективная структура данных

Малашкевич Василий Борисович

кандидат технических наук

доцент, кафедра Информационно-вычислительных систем, Поволжский государственный технологический университет

424000, Россия, Марий Эл область, г. Йошкар-Ола, ул. Пл. Ленина, 3

Malashkevich Vasilii Borisovich

PhD in Technical Science

424000, Russia, Marii El oblast', g. Ioshkar-Ola, ul. Pl. Lenina, 3

MalashkevichVB@volgatech.net
Малашкевич Ирина Ардалионовна

доцент, кафедра ИВС, Поволжский государственный технологический университет

424000, Россия, Марий Эл область, г. Йошкар-Ола, пл. Ленина, 3

Malashkevich Irina Ardalionovna

424000, Russia, Marii El oblast', g. Ioshkar-Ola, pl. Lenina, 3

MalashkevichIA@volgatech.net

Дата направления статьи в редакцию:

20-11-2014


Дата публикации:

04-12-2014


Аннотация: Эффективность работы информационно-поисковых систем существенно зависит от структуры данных. Выбранная структура данных определяет как скорость операций с данными (поиск, вставка, удаление) , так и необходимые затраты памяти. В связи с важностью проблемы оптимизации структуры данных в современной научно-технической литературе широко представлены реализации разнообразных структур данных и результаты анализа их эффективности . Широкий спектр известных эффективных структур данных использует свойства линейных массивов данных и бинарных деревьев. Работа посвящена исследованию одной из специальных структур данных, известной как цифровое дерево (Trie в отличие от Tree). Скорость поиска данных в предложенной структуре – величина статистическая и характеризуется наихудшим значением О(log(N/2)) и средним значением О(log(N/2)/2) операций. Она также имеет лучшие в сравнении с традиционным цифровым деревом характеристики по затратам памяти. Таким образом предложена и реализована эффективная структура данных - «вертикальное » цифровое дерево, которая характеризуется высокой скоростью поиска данных и малыми затратами памяти.


Ключевые слова:

структура данных, древовидная структура, цифровое дерево, массив указателей, красно-черные деревья, скошенные деревья, ключ, узел, затраты памяти, поиск

УДК:

004.415.2.043

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

Работа посвящена исследованию одной из специальных структур данных, известной как цифровое дерево. (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 Затраты памяти «вертикального»цифрового дерева

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

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

Библиография
1. ru.wikipedia.org/wiki/Список структур данных
2. en.wikipedia.org/wiki/Trie
3. Кнут Д. Э. Искусство программирования. Том 3. Сортировка и поиск.: М., Диалектика/Вильямс, 2009
References
1. ru.wikipedia.org/wiki/Spisok struktur dannykh
2. en.wikipedia.org/wiki/Trie
3. Knut D. E. Iskusstvo programmirovaniya. Tom 3. Sortirovka i poisk.: M., Dialektika/Vil'yams, 2009