Сравнение затрат памяти для метода деревьев цифрового поиска и его усовершенствования
В статье выполнен сравнительный анализ затрат памяти для организации поиска строковых величин
 методом деревьев цифрового поиска и его усовершенствования. Разработана методика теоретической
 оценки затрат памяти для обоих методов. Выполнено сравнение реальных данных с расчетными&...
Збережено в:
| Дата: | 2009 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут проблем штучного інтелекту МОН України та НАН України
2009
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/8193 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Сравнение затрат памяти для метода деревьев цифрового поиска и его усовершенствования / Г.В. Дорохина // Штучний інтелект. — 2009. — № 4. — С. 338-343. — Бібліогр.: 1 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860087795986464768 |
|---|---|
| author | Дорохина, Г.В. |
| author_facet | Дорохина, Г.В. |
| citation_txt | Сравнение затрат памяти для метода деревьев цифрового поиска и его усовершенствования / Г.В. Дорохина // Штучний інтелект. — 2009. — № 4. — С. 338-343. — Бібліогр.: 1 назв. — рос. |
| collection | DSpace DC |
| description | В статье выполнен сравнительный анализ затрат памяти для организации поиска строковых величин
методом деревьев цифрового поиска и его усовершенствования. Разработана методика теоретической
оценки затрат памяти для обоих методов. Выполнено сравнение реальных данных с расчетными
оценками при заданном количестве узлов древовидной структуры.
У статті проведено порівняльний аналіз витрат пам’яті для організації пошуку рядкових величин методом
дерев цифрового пошуку та його удосконалення. Розроблено методику теоретичної оцінки витрат пам’яті
для обох методів. Порівняно реальні дані з оцінками, що обчислено при заданій кількості вузлів деревоподібної
структури.
The paper is devoted to the problem of memory expenses for the method of digital search tree and its improvement.
The method for theoretical estimation of memory expenses of these structures is proposed. Comparison of the real
memory expenses and calculated estimations are made.
|
| first_indexed | 2025-12-07T17:21:02Z |
| format | Article |
| fulltext |
«Искусственный интеллект» 4’2009 338
7Д
УДК 004.62
Г.В. Дорохина
Институт проблем искусственного интеллекта МОН Украины и НАН Украины
г. Донецк, Украина
sgv@iai.donetsk.ua
Сравнение затрат памяти для метода деревьев
цифрового поиска и его усовершенствования
В статье выполнен сравнительный анализ затрат памяти для организации поиска строковых величин
методом деревьев цифрового поиска и его усовершенствования. Разработана методика теоретической
оценки затрат памяти для обоих методов. Выполнено сравнение реальных данных с расчетными
оценками при заданном количестве узлов древовидной структуры.
Введение
Одну из наиболее высоких скоростей поиска обеспечивают деревья цифрового
поиска (ЦП). Данный метод используется редко ввиду больших затрат памяти, т.к.
он предполагает хранение древовидной структуры и самих данных в специально
выделенной области памяти. В связи с этим актуальным является анализ способов
организации данных, позволяющих выполнять поиск данных с той же скоростью,
что и деревья ЦП, и сократить затраты памяти по сравнению с этим методом.
В работе [1] предложено усовершенствование метода деревьев ЦП, обеспечи-
вающее хранение строковых величин в древовидной структуре и скоростной поиск
данных в ней. Оно характеризуется такой же скоростью поиска данных, как у метода
деревьев ЦП, и за счет хранения данных в древовидной структуре может давать зна-
чительный выигрыш в затратах памяти.
Целью данной работы является сравнительный анализ затрат памяти при исполь-
зовании деревьев ЦП и усовершенствованных деревьев ЦП. Поставленная цель мо-
жет быть достигнута путём решения следующих задач: формальное описание затрат
памяти на хранение данных и деревьев ЦП; формальное описание затрат памяти на
хранение данных методом усовершенствованных деревьев ЦП; сравнительный ана-
лиз затрат памяти.
Затраты памяти при поиске строковых величин
методом деревьев цифрового поиска
Как отмечено ранее, метод деревьев ЦП предполагает хранение данных, а также
древовидной структуры, обеспечивающей их скоростной поиск. Рассмотрим задачу
использования деревьев цифрового поиска для задачи поиска элементов словаря
строк – множества строк без повторений. Для хранения самих данных можем исполь-
зовать массив строк фиксированной длины или строк переменной длины.
Пусть максимальная длина строки в словаре равна h, а словарь содержит z
строк. При его хранении с помощью строк фиксированной длины необходимо
P (G) = (h + 1) z Sс (1)
байт. Здесь Sс – количество байт, отводимых под хранение одного символа.
Сравнение затрат памяти для метода деревьев цифрового поиска…
«Штучний інтелект» 4’2009 339
7Д
Затраты памяти массива строк переменной длины для хранения того же словаря
при известных величинах zi – количество в словаре G строк длины i вычислим со-
гласно:
h
k
i SckzGP
1
)42()( . (2)
При этом 2 байта отводится для хранения реальной длины строки, а 4 байта – для
указания ссылки на строку.
Быстрый поиск данных методом деревьев ЦП обеспечивает древовидная струк-
тура. От содержимого словаря зависит
h
i
ivv
1
– количество узлов в ней. Здесь vi –
количество в древовидной структуре узлов высоты i. Определим границы данной
величины, исходя из данных: t – размер алфавита символов, составляющих строки
словаря; z – количество строк в словаре G; zi – количество в словаре G строк длины i;
l = [logt z] – целая часть от logt z.
liz
lit
v h
ij
j
i
i |
|
)sup( , (3)
t
vzv i
ii
1,max)inf( . (4)
Здесь
t
vi 1 – операция округления вверх результатов деления
t
vi 1 .
Исходя из верхней, нижней границ vi и вышевведенного значения l, величина v
удовлетворяет:
hi
i
ivv
1
)inf()inf( ,
h
li
i
l
i
i zlitv
11
)()sup( . (5)
Здесь l = [logt z].
Каждый из множества узлов O дерева цифрового поиска может быть описан
вектором oj = (oj1, oj2, oj3), где oj1 – символ алфавита; oj2 – целое число, oj2 = 0 для узла,
в котором не оканчивается ни одна строка, и oj2[1; z] для узла, в котором окан-
чивается строка с номером oj2 в словаре G; oj3 – множество номеров узлов, дочерних
по отношению к j-му узлу.
Объем памяти, необходимый для хранения узлов высоты i представим в виде
суммы объема памяти, необходимого для хранения элементов oj1, oj2 этих узлов, и
суммарного объема памяти, необходимого для хранения
j
jo 3 , где j принадлежит
множеству узлов высоты i. Причем
13 i
j
j vo . (6)
Обозначив количество байт, отводимое для хранения целого числа, через Si, полу-
чим выражение для оценки затрат памяти для хранения множества узлов высоты i:
vi (Si + Sc) + vi+1 Si. (7)
Тогда затраты памяти для хранения всех узлов дерева ЦП:
h
i
ii SivSiScvOP
0
1)()( .
Дорохина Г.В.
«Искусственный интеллект» 4’2009 340
7Д
Разбив эту сумму на две, получим
h
i
i
h
i
i
h
i
i
h
i
i vSivSiScvSivSiScOP
0
1
00
1
0
)()()( .
Для любого непустого словаря v0 = 1, а vh+1 = 0. Перепишем выражения
h
i
i
h
i
i vv
10
1 ,
h
i
i
h
i
i
h
i
i
h
i
i vrvv
11
1
10
1 0 .
Получим
h
i
ivSiScSiScOP
1
)2()( . (8)
Подставив в (8) выражения (3) и (4), получим оценку затрат памяти для хране-
ния дерева ЦП:
h
li
i
l
i
i zlitSiScSiScOP
11
)()2())(sup( , (9)
h
i
i
i t
rzSiScSiScOP
1
1,max)2())(inf( , (10)
где l = [logt z], где rh+1 = 0, ] [в – операция округления до большего целого числа.
Использование деревьев ЦП предполагает хранение древовидной структуры и
самих данных. Поэтому совокупные затраты памяти при использовании метода де-
ревьев ЦП ),( OGP определяются суммой
)()(),( OPGPOGP . (11)
Затраты памяти при поиске строковых величин методом
усовершенствованных деревьев цифрового поиска
Усовершенствование [1] метода деревьев ЦП состоит во введении в узел древо-
видной структуры дополнительного элемента данных – номера родительской вер-
шины, а также в использовании ссылок (массива номеров узлов) на узлы-окончания
строк. Это усовершенствование позволяет хранить данные в самой древовидной
структуре. То есть, с одной стороны, увеличивается размер узла и появляется массив
ссылок на узлы-окончания строк, с другой стороны, исчезает необходимость в хране-
нии массива данных наряду с древовидной структурой.
Каждый из множества узлов O′ дерева цифрового поиска может быть описан
вектором o′j =(oj1, oj2, oj3, oj4), где элемент oj4 – номер родительского узла по отно-
шению к данному. Массив ссылок (номеров) на узлы-окончания строк обозначим
через X. Его размер равен количеству строк в словаре z. Причём
ioxkoXx kiki 4,: .
Количество узлов в древовидной структуре, построенной по одному словарю,
совпадает для дерева ЦП и для усовершенствованного дерева ЦП.
Обозначим через P(O′, X) затраты памяти для хранения усовершенствованного
дерева ЦП.
)()(),( XPOPXOP . (12)
SizXP )(
Найдем объем памяти, необходимый для хранения множества O. В каждый эле-
мент oj множества O в сравнении с элементом oj множества O дополнительно введен
Сравнение затрат памяти для метода деревьев цифрового поиска…
«Штучний інтелект» 4’2009 341
7Д
элемент oj4, являющийся целым числом. Значит, размер каждого элемента oj превышает
размер oj на размер целого числа Si. По аналогии с деревом ЦП:
h
i
ivSiScSiScOP
1
)3(2)( , (13)
h
li
i
l
i
i zlitSiScSiScOP
11
)()3(2))(sup( , (14)
h
i
i
i t
rzSiScSiScOP
1
1,max)3(2))(inf( . (15)
Сравнение затрат памяти метода деревьев цифрового
поиска и метода усовершенствованных деревьев
цифрового поиска
Проанализируем изменение затрат памяти при фиксированных размере алфави-
та и объеме словаря, но различных значениях h. Пусть z = 1000000, t = 33. В формулах
определения затрат памяти фигурирует величина zi. Допустим, эта величина определя-
ется по формуле
1,1,
1
,min
1
1
hi
ih
zz
tz
i
j
i
i
i ,
1
1
h
j
ih zzz , (16)
что соответствует наиболее равномерному распределению величин zi.
Вычислим выигрыш в затратах памяти метода усовершенствованных деревьев
ЦП по формуле
%100
),(
),(),(
OGP
XOPOGPf . (17)
При оценке затрат памяти будем рассматривать три случая:
количество узлов в древовидной структуре максимально v = sup(v);
количество узлов в древовидной структуре минимально v = inf(v);
количество узлов в древовидной структуре является средним между минимальным
и максимальным
2
)sup()inf( vvv
.
На рис. 1 отражены зависимости относительного выигрыша в затратах памяти (17)
метода усовершенствованных деревьев ЦП от максимальной длины строки словаря
(h по оси аргумента), количестве в словаре слов длины i, определяемом по (16) для ми-
нимального, максимального и среднего количества узлов.
Приведенные данные относительно выигрыша (проигрыша) в затратах памяти
усовершенствованного метода деревьев ЦП имеют слишком большой разброс. Это
делает затруднительным его оценку. Кроме того, выбранное распределение длин
строк в словаре не соответствует реальному распределению строк в словарях, эле-
ментами которых являются слова языка.
Приведем пример расчетных и реальных относительных затрат памяти для строк
фиксированной и переменной длины. В качестве словарей были использованы база сло-
воформ русского языка, содержащая 1 779 843 уникальных строк, и база начальных форм
слов русского языка, содержащая 110 746 уникальных строк. База словоформ в отличие
от базы начальных форм содержит большее количество уникальных строк. В то же время
она содержит большее количество строк, начальные символы которых совпадают и отлич-
Дорохина Г.В.
«Искусственный интеллект» 4’2009 342
7Д
ны только несколько последних символов. То есть одна и та же ветвь древовидной струк-
туры позволяет хранить начальные символы большего количества слов. Распределение
длин уникальных строк в этих базах приведено на рис. 2. Видим кардинальное отличие
распределений длин слов реальных словарей от равномерного распределения (16), ко-
торое мы использовали при подсчете затрат памяти для хранения различных представле-
ний словарей. Поскольку рассмотренные реальные словари содержат меньше слов большей
длины, то затраты на их хранение должны быть меньше приведенных ранее расчетных.
Сравнение со строками фиксированной длины
Сравнение со строками переменной длины
Рисунок 1 – Относительный выигрыш в затратах памяти
метода усовершенствованных деревьев ЦП
а) б)
Рисунок 2 – Распределение длин строк в реальных словарях: а) в базе словоформ
русского языка; б) в базе начальных форм слов русского языка
Сопоставим полученные нами реальные данные выигрыша в затратах памяти раз-
работанного метода с расчетными данными при минимальном, максимальном и сред-
нем числе узлов в древовидной структуре (табл. 1).
Видим, что при хранении базы словоформ – словаря большего размера с большим
количеством строк, отличающихся друг от друга несколькими последними символами, –
выигрыш от использования разработанного метода приближается к расчетному выигры-
шу при минимальном количестве вершин древовидной структуры. При хранении же базы
начальных форм оцениваемый выигрыш приближается к расчетному выигрышу при сред-
нем количестве вершин. Отметим также, что метод усовершенствованных деревьев
ЦП может проигрывать в затратах памяти базовому методу, если словарь строк базового
метода хранится в виде строк переменной длины.
вы
иг
ры
ш
, %
вы
иг
ры
ш
, %
Сравнение затрат памяти для метода деревьев цифрового поиска…
«Штучний інтелект» 4’2009 343
7Д
Таблица 1 – Выигрыш в затратах памяти на словарях слов русского языка
Расчетные данные при заданном коли-
честве узлов древовидной структуры Словарь Длина
строк
Реальные
данные Max Min Ave
фиксир. 43,10 -6,86 54,05 15,94 База
словоформ перемен. 22,60 -20,57 34,55 -7,77
фиксир. 17,30 -4,80 54,05 18,29 База начальных
форм перемен. -4,32 -20,89 31,36 -8,50
Заметим также, что мы оценили выигрыш разработанного метода при хранении
словарей, состоящих из уникальных строк. В базе начальных форм общее число строк –
111 133, а мы рассматривали словарь из 110 746 уникальных строк этой базы. По базе
словоформ мы сформировали словарь, содержащий 1 779 843 уникальных строк, тогда
как общее число строк в этой базе – 3 167 168.
Выводы
В работе рассмотрена проблема оценки затрат памяти усовершенствованных де-
ревьев ЦП. Предложена методика теоретической оценки относительного выигрыша в
затратах памяти этого метода в сравнении с базовым при известных характеристиках
словаря: размер алфавита символов, образующих строки словаря; максимальная длина
строки словаря; количество в словаре строк заданной длины. Полученная методика
позволяет определить целесообразность использования для словаря с заданными пара-
метрами метода усовершенствованных деревьев ЦП. Сравнение реальных данных со-
гласуется с теоретическими оценками при заданном количестве узлов древовидной
структуры. Анализ показывает эффективность применения усовершенствованного ме-
тода деревьев ЦП для хранения и поиска строковых величин, различающихся послед-
ними символами.
Литература
1. Патент України № 78806. Пристрій для збереження і пошуку рядкових величин та спосіб збереження
і пошуку рядкових величин / Дорохіна Г.В.; патентовласник: Інститут проблем штучного інтелекту
МОН України і НАН України // Промислова власність ; опубл. 25.04.2007, Бюл. № 5.
Г.В. Дорохіна
Порівняння витрат пам’яті для методу дерев цифрового пошуку та його удосконалення
У статті проведено порівняльний аналіз витрат пам’яті для організації пошуку рядкових величин методом
дерев цифрового пошуку та його удосконалення. Розроблено методику теоретичної оцінки витрат пам’яті
для обох методів. Порівняно реальні дані з оцінками, що обчислено при заданій кількості вузлів деревоподібної
структури.
G.V. Dorokhina
Memory Expenses Comparison for the Method of Digital Search Tree and Its Improvement
The paper is devoted to the problem of memory expenses for the method of digital search tree and its improvement.
The method for theoretical estimation of memory expenses of these structures is proposed. Comparison of the real
memory expenses and calculated estimations are made.
Статья поступила в редакцию 24.06.2009.
|
| id | nasplib_isofts_kiev_ua-123456789-8193 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1561-5359 |
| language | Russian |
| last_indexed | 2025-12-07T17:21:02Z |
| publishDate | 2009 |
| publisher | Інститут проблем штучного інтелекту МОН України та НАН України |
| record_format | dspace |
| spelling | Дорохина, Г.В. 2010-05-14T09:43:25Z 2010-05-14T09:43:25Z 2009 Сравнение затрат памяти для метода деревьев цифрового поиска и его усовершенствования / Г.В. Дорохина // Штучний інтелект. — 2009. — № 4. — С. 338-343. — Бібліогр.: 1 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/8193 004.62 В статье выполнен сравнительный анализ затрат памяти для организации поиска строковых величин
 методом деревьев цифрового поиска и его усовершенствования. Разработана методика теоретической
 оценки затрат памяти для обоих методов. Выполнено сравнение реальных данных с расчетными
 оценками при заданном количестве узлов древовидной структуры. У статті проведено порівняльний аналіз витрат пам’яті для організації пошуку рядкових величин методом
 дерев цифрового пошуку та його удосконалення. Розроблено методику теоретичної оцінки витрат пам’яті
 для обох методів. Порівняно реальні дані з оцінками, що обчислено при заданій кількості вузлів деревоподібної
 структури. The paper is devoted to the problem of memory expenses for the method of digital search tree and its improvement.
 The method for theoretical estimation of memory expenses of these structures is proposed. Comparison of the real
 memory expenses and calculated estimations are made. ru Інститут проблем штучного інтелекту МОН України та НАН України Обучающие и экспертные системы Сравнение затрат памяти для метода деревьев цифрового поиска и его усовершенствования Порівняння витрат пам’яті для методу дерев цифрового пошуку та його удосконалення Memory Expenses Comparison for the Method of Digital Search Tree and Its Improvement Article published earlier |
| spellingShingle | Сравнение затрат памяти для метода деревьев цифрового поиска и его усовершенствования Дорохина, Г.В. Обучающие и экспертные системы |
| title | Сравнение затрат памяти для метода деревьев цифрового поиска и его усовершенствования |
| title_alt | Порівняння витрат пам’яті для методу дерев цифрового пошуку та його удосконалення Memory Expenses Comparison for the Method of Digital Search Tree and Its Improvement |
| title_full | Сравнение затрат памяти для метода деревьев цифрового поиска и его усовершенствования |
| title_fullStr | Сравнение затрат памяти для метода деревьев цифрового поиска и его усовершенствования |
| title_full_unstemmed | Сравнение затрат памяти для метода деревьев цифрового поиска и его усовершенствования |
| title_short | Сравнение затрат памяти для метода деревьев цифрового поиска и его усовершенствования |
| title_sort | сравнение затрат памяти для метода деревьев цифрового поиска и его усовершенствования |
| topic | Обучающие и экспертные системы |
| topic_facet | Обучающие и экспертные системы |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/8193 |
| work_keys_str_mv | AT dorohinagv sravneniezatratpamâtidlâmetodaderevʹevcifrovogopoiskaiegousoveršenstvovaniâ AT dorohinagv porívnânnâvitratpamâtídlâmetoduderevcifrovogopošukutaiogoudoskonalennâ AT dorohinagv memoryexpensescomparisonforthemethodofdigitalsearchtreeanditsimprovement |