КИЇВСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ

ІМЕНІ ТАРАСА ШЕВЧЕНКА

РЕЗНІК ЮРІЙ ОЛЕКСАНДРОВИЧ

УДК 681.51:519.713.2

ДОСЛІДЖЕННЯ ВЛАСТИВОСТЕЙ ЦИФРОВИХ ДЕРЕВ

З АДАПТИВНИМ ГІЛКУВАННЯМ

Спеціальність 01.05.03 – математичне та програмне забезпечення

обчислювальних машин і систем

АВТОРЕФЕРАТ

дисертації на здобуття наукового ступеня

кандидата фізико-математичних наук

Київ – 2005

Дисертацією є рукопис.

Работа виконана в інституті проблем математичних машин

і систем НАН України і на кафедрі математичної інформатики

Київького національного університету імені Тараса Шевченка.

Науковий керівник доктор фізіко-математичних наук, професор

Анісімов Анатолій Васильович,

Київський національний університет імені Тараса Шевченка,

завідувач кафедри математичної інформатики

Офіційні опоненти: доктор фізіко-математичних наук, професор

Асельдеров Зайнутдін Макашаріпович

Національний технічний університет України „КПІ”

професор кафедри автоматизованих систем обробки

інформації та управління

Кандидат фізико-математичних наук, доцент

Гороховський Семен Самуїлович

Національний університет “Києво-Могилянська академія”

доцент кафедри інформатики

Провідна установа Інститут кібернетики ім. В. М. Глушкова

НАН України, м. Київ.

Захист відбудеться 16 червня 2005 р. о 14 годині на засіданні

спеціалізованої вченої ради Д 26.001.09 Київського національного

університету імені Тараса Шевченка, за адресою 03127 м. Київ, просп.

Академіка Глушкова, 2. корп. 6., ф-т кібернетики.

З дисертацією можна ознайомиться у бібліотеці Київського

національного університету імені Тараса Шевченка, за адресою

03127 м.Київ, просп. Академіка Глушкова, 2. корп. 6., ф-т кібернетики.

Автореферат розісланий 14 травня 2005 р.

Вчений секретар спеціалізованої вченої ради,

кандидат фізико-математичних наук, доцент В.П.Шевченко

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми зумовлена постійним збільшенням обсягів інформації в сучасних комп’ютерних мережах і системах та викликаних цим проблемах ефективного її представлення та швидкого здійснення операцій пошуку й сортування. За таких умов особливого значення набуває задача розробки алгоритмів, що забезпечують пошук за лог-логарифмічною (або навіть константною) кількістю звернень до пам’яті. Відомим класом алгоритмів з константною швидкістю є хешування, однак цей метод мало пристосований до пошуку за шаблонами, або у випадках, коли пошук здійснюють за частковими чи ранговими ознаками. Вирішенню цієї задачі на основі використання цифрових дерев з адаптивним гілкуванням присвячена пропонована дисертаційна робота.

Основні результати по (не адаптивним) цифровим деревам були одержані вітчизняними вченими: А. В. Анісімовим, С. Я. Берковичем, Р. Е. Кричевським, О. Б. Лупановим, Б. Піттелем, Б. Я. Рябко, а також Д. Кнутом, Р. Седжевіком, В. Шпанковським та ін. у США, Л. Девроєм у Канаді, Ф.Флажоле, Б.Валі та ін. у Франції.

Попередні результати по адаптивним цифровим деревам було одержано А. Андерсоном та С. Нільсеном (1993-1998) у Швеції, В. Шпанковським (2001-2005) у США, та Л. Девроєм (2002-2005) у Канаді.

Зв’язок роботи с науковими програмами, планами та темами. Роботу виконано в межах наукових тем кафедри математичної інформатики Київського національного університету імені Тараса Шевченка: “Розробка систем інтелектуалізації інформаційних технологій та дистанційного навчання” (державний реєстраційний номер 0101U002170) та “Дослідження та розробка технологій захисту інформації в коммунікаційно-інформаціийних системах, що динамично змінюються” (державний реєстраційний номер 01032U006601), а також ряду інших проектів систем пошуку та стиснення інформації, виконаних за участю автора у США.

Мета диссертаційної роботи – удосконалення методів та розробка більш ефективних алгоритмів пошуку інформації на основі використання властивостей цифрових дерев з адаптивним гілкуванням.

Задачі досліждження. Для досягнення вказаної мети в дисертаційній роботі здійснено розв’язання таких задач:

порівняльний аналіз та класифікація існуючих методів інформаційного пошуку що грунтуються на застосуванні цифрових дерев;

розробка узагальненої аналітичної моделі для класу цифрових дерев з адаптивним гілкуванням;

дослідження локалізації просторово-часових характеристик, що можуть бути досягнуті цифровими деревами з адаптивним гілкуванням;

розробка та експериментальне дослідження ефективності прикладних алгоритмів інформаційного пошуку.

Об’єктами дослідження є структури даних та методи пошуку інформації, що грунтуються на застосуванні цифрових дерев з адаптивним гілкуванням.

Предметом дослідження є аналітичні властивості класу цифрових дерев з адаптивним гілкуванням, методи динамічної побудови цифрових дерев з адаптивним гілкуванням, основані на них нові алгоритми та прикладні програми пошуку та стиснення інформації.

Методи дослідження. В роботі використовуються математичні методи аналізу очікуваної поведінки алгоритмів: рекурентне представлення необхідних статистик, твірні функції, перетворення Мелліна та інтегральний метод Райса для знакозмінних сум. Для одержання асимптотичних оцінок застосовуються методи інтегрування в комплексній області: теорема Коші, метод Лапласа, метод сідлової точки (метод переходу), а також метод Ван дер Вардена для сідлових точок, що збігаються з полюсами в підінтегральних виразах.

Наукова новизна одержаних результатів.

Основні положення, що виносяться до захисту:

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

розроблено узагальнену аналітичну модель для класу дерев з адаптивним гілкуванням;

вперше проаналізовано класи дерев з лог-логарифмічною та константною середньою довжиною шляху і з лінійною залежністью розміру від кількості ключів;

вперше розроблено алгоритми побудови дерев с константним середнім часом доступу;

розроблено та програмно реалізовано високоефективні алгоритми пошуку та стиснення даних на основі використання цифрових дерев з адаптивним гілкуванням.

Практичне значення одержаних результатів полягає у створенні нових методів пошуку та стиснення даних, що забезпечують оптимальне використання ресурсів ПВМ. Ці методи реалізовано в таких програмних продуктах:

RealPlayer, RealProducer, RealServer 8-10 – Internet streaming media software

RealNetworks, Inc. Seattle, Wa,

http://www.realnetworks.com/products

DTFS Desktop Filesystem – Unix filesystem; bundled in Unixware, SCO OpenServer, etc.

CrosStor, Inc. (form. Programmed Logic Corp), NJ

http://www.sco.com/products/unix/

JAM Disk Compression Software

shareware, Kiev, Ukraine

Особистий внесок здобувача. Всі основні результати дисертаційної роботи одержані здобувачем особисто. В опублікованих роботах, виконаних зі співавторами, здобувачеві належать: в роботах [6,8,14] – реалізація методів розв’язання задачі, в роботі [9] – ідея вживання VB-кода для симетруючого перетворення рядків вхідних даних і постановка задачі побудови такого коду з метою підвищення продуктивності алгоритмів цифрового пошуку.

Апробація результатів дисертації. Основні наукові результати дисертаційної роботы доповідались та обговорювались на міжнародних конференціях: 2ndWorkshop on Analytic Algorithmics and Combinatorics (ANALCO’05) (Vancouver, Canada, 22 Січня 2005), 3rd Intl. Colloquium on Mathematics and Computer Science (MathInfo’04) (Vienna, Austria, 13-17 Вересня 2004), IEEE International Symposium on Information Theory (ISIT’02) (Lausanne, Switzerland, 1-5 липня 2002), 8th International Seminar on the Analysis of Algorithms (AofA’02) (Strobl, Austria, 23 – 29 червня 2002), IEEE Data Compression Conference (DCC’02) (Snowbird, Utah, USA, 28-30 березня 2002), 6th Annual International Computing and Combinatorics Conference (COCOON'00) (Bondi Beach, Sydney, Australia, 26-28 липня 2000), 6th International Seminar on the Analysis of Algorithms (AofA’00) (Krynica Morska, Poland, липня 2000), IEEE Data Compression Conference (DCC'00) (Snowbird, Utah, USA, 28-30 березня 2000), DIMACS Workshop on Codes and Trees (DIMACS Center, Rutgers University, Piscataway, NJ, USA, 5-7 жовтня 1998), IEEE Data Compression Conference (DCC'98) (Snowbird, Utah, USA, 30 березня –  квітня 1998), а також доповідались на семінарах із проблем теорії обчислень у Київському національному університеті ім. Тараса Шевченка (Київ, 28 квітня 2001), University of Washington (Seattle, WA, USA, 11 травня 2001) и Purdue University (West Lafayette, IN, USA, 1 листопада 2004).

Публикації. Результати дисертаційного дослідження опубліковано в 17 наукових роботах, з яких 4 - у фахових виданнях, затверджених ВАК України, 2 - у міжнародних наукових журналах, 10 - в тезах доповідей міжнародних конференцій та 1 стаття в науково-популярному журналі.

Структура и обсяг роботи. Дисертація складається з переліку умовних позначень, вступу, 5 основних розділів, висновків, переліку використаних джерел та 2 додатків. Робота містить 20 рисунків. Перелік використаних джерел включає 134 найменувань. Загальний обсяг роботи - 150 сторінок, обсяг основного тексту – 117 сторінок.

ОСНОВНИЙ ЗМІСТ РОБОТИ

У вступі обґрунтовується актуальність теми, окреслюється зв’язок дисертаційної роботи з планами наукових досліджень, виконуваних в Інституті математичних машин і систем НАН України та на кафедрі математичної інформатики Київського національного університету імені Тараса Шевченко за національними програмами інформатизації.

Перший розділ дисертаційної роботи присвячений аналізу відомих типів цифрових дерев (trie-дерева, дерева Коффмана і Еве, Patricia, b-дерева, багаторозрядні дерева, LC-дерева та N-дерева). На підставі проведеного аналізу визначено можливість побудови нового класу цифрових дерев з адаптивним вибором розрядності складових вузлів та обґрунтовано доцільність детального їх вивчення.

Наведемо найважливіші визначення для цього класу дерев. Нехай .- набір з n рядків, кажен з яких складається з символів бінарного алфавіту .. Запис . означає суффікс рядка ., що починається з k-ї позиції цього рядка (тобто існує рядок ., ., такий, що .). Запис . означає k молодших значущих цифр в бінарному представленні числа i.

Визначення 1.1. Бінарне цифрове дерево . над набором рядків S будується рекурсивно за допомогою таких правил. Якщо ., дерево пусте. Якщо . (тобто S містить лише один рядок), дерево є зовнішнім вузлом, що містить указник на цей рядок в S. При . дерево є внутрішнім вузлом, що містить указники на 2 дочірні дерева: . та ., побудовані з суффіксів рядків з S, які починаються відповідно з символів 0 та 1: ..

Визначення 1.2. Багаторозрядне цифрове дерево . над набором рядків S будується рекурсивно за допомогою таких правил. Якщо ., дерево пусте. Якщо ., дерево є зовнішнім вузлом, що містить указник на єдиний рядок в S. При ., дерево є r-розрядным внутрішнім вузлом (.), що містить указники на . дочірні дерева .,. ..,., побудовані з суффіксів рядків з S, які починаються з відповідних r_розрядних послідовностей: . ..

Визначення 1.3. Адаптивне багаторозрядне дерево є багаторозрядным цифровим деревом, у якого параметри .що визначають число оброблюваних вузлами розрядів, визначаються адаптивно від одного вузла до іншого.

Приклади цифрових дерев, що відповідають визначенням 1.1 – 1.3 подано на рис.1.1.

З точки зору програмування, стандартними операціями над цифровими деревами є такі:

вставка нового рядка .: .,

видалення рядка .: .,

пошук рядка .: ..

Якщо операція пошуку знаходить відповідний рядок в S, пошук вважається успішним, а якщо такого рядка не існує - неуспішним. Цифрові дерева можуть також застосовуватись для пошуку інтервалу, що містить рядок .: ., а також для виконання інших (більш спеціалізованих) операцій.

Рис. 1.1. Приклади дерев, що відповідають 7 бінарним рядкам: s1=0000..., s2=0001...,=0010...,=0100...,=0110...,=100...,=110....

В другому розділі дисертації розглянуто основні параметри цифрових дерев, подано огляд існуючих методів аналізу їхніх властивостей, та поставлено задачу вивчення класу дерев з адаптивним багаторозрядним гілкуванням.

Для цифрових дерев над набором з n (бінарних) рядків стандартними є такі параметри:

. - число внутрішніх вузлів;

. - число зовнішніх вузлів (.);

. - число указників на пусті під-дерева;

.- загальна кількість указників;

. - довжина зовнішнього шляху (сумма довжин шляхів від кореня до зовнішніх вузлів);

. - глибина дерева.

Глибина дерева . дозволяє оцінювати час успішного пошуку в дереві. Загальна кількість указників в дереві . визначає обсяг простору, потрібного для розміщення дерева в основній пам’яті комп’ютера.

Для одержання середніх (очікуваних) значень цих парамерів застосовують стохастичну модель породження вхідних рядків .. В роботі використано модель процесу Бернуллі, в якому символи алфавіту . з’являються незалежно. Якщо . i-й символ, то  для будь-якого i: ., а .. При . процес є симетричним, інакше – асиметричним.

Оцінка середніх значень часу пошуку та розміру дерев базується на знаходженні величин

.,

.,

де математичні очікування беруться по всім можливим деревам над n рядками при заданих значеннях параметрів процесу (p, q).

Задача аналізу очікуваної продуктивності класу дерев полягає у виявленні локалізації пар величин ., що є досяжними для дерев даного класу при заданій моделі процесу.

Третій розділ роботи присвячений аналізу класу адаптивних багаторозрядних цифрових дерев. Припускається що вибір розрядності вузлів (параметрів .) здійснюється деяким (детермінованим) алгоритмом. Зазначено, що в моделі процесу Бернуллі результати роботи такого алгоритму залежать тільки від (1) кількості рядків . що проходять через даний вузол, та (2) параметрів самого процесу (p, q). Таким чином, розрядності вузлів можуть бути визначені як числа . породжені стохастичним процесом, які сходяться (принаймні по імовірності при .) до деякої функції від . та.:

.. (3.1)

На основі даного представлення одержано рекурентні співвідношення для основних параметрів адаптивних цифрових дерев.

Лема 3.1. В моделі Бернуллі справедливі такі рекурентні співвідношення для середньої довжини зовнішніх шляхів . та середньої кількості гілок . багаторозрядних дерев:

.(3.2)

.(3.3)

де n – загальна кількість рядків, використаних для побудови дерева.

Аналіз цих співвідношень у загальній формі є досить складним і застосування стандартних методів приводу (використання твірних функцій, перетворення Бернуллі, та ін.) виявляється в данному випадку недостатнім. Тому в роботі розглянуто часткові рішення рівнянь (2.2 - 2.3), що грунтуються на припущенні линійності (або лог-логарифмічності) . и . як функцій n.

Встановлено, що для класу дерев з линійним середнім обсягом має місце

Теорема 3.1. Середній обсяг адаптивних дерев з розрядностями

. (3.4)

(. – деяка константа) є обмежений лінійною залежністю від числа рядків n, що в них містяться: ., якщо

., (3.5)

де

.(3.6)

- константа, що залежить лише від параметрівв процессу..

Мінімальну середню глибину серед них мають дерева з .. Такі дерева в роботі названо FLS-деревами (FLS = Fastest in Linear Space). Асимптотичну залежність між розрядністю вузлів адаптивних дерев данного класу та їхнім обсягом встановлює

Теорема 3.2. Середній обсяг адаптивних дерев з розрядностями

., (3.7)

де .– константа визначена в (3.6),

., (3.8)

., (3.9)

і ., задовольняє (при .,.)

.(3.10)

де

., (3.11)

є функція нормального розподілу.

При вивченні дерев з лінійним обсягом встановлено такий факт.

Теорема 3.3. Існують адаптивні багаторозрядні дерева мінімального обсягу. Розрядності вузлів у таких деревах задовольняють

., (3.12)

де константа .залежить лише від параметрів процессу і знаходиться в межах

., (3.13)

де

.. (3.14)

В роботі цей тип дерев названо MS-деревами (MS = Minimum Space).

Наступна теорема встановлює існування класу дерев з константною середньою глибиною.

Теорема 3.4. Середня глибина адаптивних дерев з розрядностями

. (3.15)

(. – деяка константа) є константною ., якщо

., (3.16)

де

.(3.17)

- константа, що залежить лише від параметрів процессу . (ентропія процесу).

Найкомпактнішими в цьому класі виявляються дерева з .. Асимптотичну оцінку средньої глибини для цього класу дерев, названих SCT-деревами (SCT = Smallest in Constant Time) визначає наступна теорема.

Теорема 3.5. Середня глибина адаптивних дерев з розрядностями

.(3.18)

де

., (3.19)

., (3.20)

і ., відповідає (при .,.)

., (3.21)

де . – функція нормального розподілу.

Порівняння умов лінійності середнього обсягу (3.5) та константності середньої глибини (3.16) дозволяє одержати наступний висновок.

Наслідок 3.1 Лінійний середній обсяг та константна середня глибина досягаються одночасно при симметричному процесі ..

При асиметричному процесі обсяг дерев з константною середньою глибиною зростає як .,  де показник ступеню . може бути як завгодно великим.

Наступна теорема встановлює асимптотичну залежність між параметрами класу дерев з лог-логарифмічною глибиною .:

Теорема 3.6. Середня глибина адаптивних дерев з розрядностями

. (3.22)

(. – деяка константа) задовольняє (при .,.)

., (3.23)

де .– ентропія процесу (3.17).

Зокрема, для LC-дерев (LC = Level Compression) Андерсона та Нільсона доведено наступне твердження (що підсилює їхню оцінку .).

Наслідок 3.2. Середня глибина LC-дерев задовольняє (при .,.)

.. (3.24)

Для введених нами FLS- дерев (3.7) має місце наступне твердження.

Наслідок 3.3. Середня глибина FLS-дерев задовольняє (при .,.)

.. (3.25)

Ще одним важливим представником класу дерев з лог-логарифмічною глибиною є дерева з .- розрядними вузлами (названі як логарифмічні дерева, або Lg-дерева). Властивості цього класу визначає наступне твердження.

Наслідок 3.4. Середня глибина . і середній обсяг . адаптивних дерев з розрядностями

. (3.26)

(. – константа) задовольняють (при .,.)

., (3.27)

та

.. (3.28)

Як бачимо, обсяг логарифмічнмих дерев зростає як ., що може бути прийнятним для низки практичних застосувань.

Графіки залежності глибини від параметрів процесу для дерев з лог-логарифмічною глибиною подано на рис. 3.1.

.

Рис. 3.1. Залежності глибини для .- дерев від параметра процесу.

Найбільшу глибину мають LC-дерева, дещо меншу - FLS-дерева. Найменьшу глибину мають логарифмічні дерева. Для всіх розглянутих дерев глибина стрімко падає при .. В точці . , що відповідає симметричному процессу має місце розрив, що свідчить про перехід . в асимптотичний режим . для LC-дерев, або. для FLS- та Lg-дерев.

На рис.3.2 показано відносне прискорення пошуку, що досягається в FLS- та Lg-деревах порівняно з LC-деревами. При асиметричному процесі, FLS-дерева переважають за швидкістю пошуку LC-дерева лише в 2 - 2.16587… рази, тоді як для логарифмичних дерев цей виграш необмежено зростає зі збільшенням асиметрії процесу.

.

Рис. 3.2. Прискорення пошуку, що досягається FLS- деревами (суцільна лінія) та

.-розрядними деревами (пунктир) відносно LC-дерев.

На рис.3.3 представлено зони локалізації пар ., що є досяжними для різних класів цифрових дерев з адаптивним гілкуванням. Позначено класи LC-, MS-, FLS-, SCT-, и Lg-дерев, які мають теоретичне та практичне значення.

Рис. 3.3. Класи дерев з адаптивним багаторозрядним гілкуванням та локалізація їх просторово-часових характеристик для моделі процесу Бернуллі.

Четвертий розділ присвячений алгоритмам побудови дерев з адаптивним багаторозрядним гілкуванням та експериментальному дослідженню їхніх властивостей. Головна проблема побудови таких дерев полягає у виборі розрядності вузлів. Застосування асимптотичних режимів, розглянутих в розділі 3, дозволяє значно спростити побудову алгоритмів, що відповідають заданим вимогам до таких дерев.

Рис. 4.1. Параметри r -розрядного вузла з n вхідними рядками.

На рис. 4.1 представлено такі параметри багаторозрядних вузлів адаптивних дерев:

. - число указників на приєднані внутрішні вузли;

.- число указників на зовнішні вузли (рядки);

. - число указників на пусті дочірні дерева.

Загальна кількість указників в такому r -розрядному вузлі становить

.(4.1)

Визначення 4.1. Щільністю r-розрядного вузла, що обробляє n рядків ., назвемо відношення кількості указників на непусті вузли до загальної кількості указників в цьому вузлі

.. (4.2)

Визначення 4.2. Модифікованою щільністю r-розрядного вузла, що обробляє n рядків ., назвемо відношення кількості указників на непусті вузли мінус 1 до загального числа указників в цьому вузлі

.. (4.3)

Визначення 4.3. Вибірковістю r-розрядного вузла, що обробляє n рядків ., назвемо відношення числа рядків, ідентифікованих цим вузлом (число приєднаних зовнішніх вузлів), до загального числа оброблюваних ним рядків

.. (4.4)

Визначення 4.4. Эфективністю r-розрядного вузла з n вхідними рядками ., назвемо відношення числа указників на зовнішні вузли (що містять однозначно розділені рядки), до загального числа указників у цьому вузлі

.. (4.5)

Зв’язок між параметрами вузлів та параметрами цілого дерева встановлюється за допомогою наступних нерівностей.

Лема 4.1. Нехай

., ., (4.7)

де j пробігає всі номери внутрішніх вузлів дерева. Тоді щільність цього дерева задовольняє

.. (4.8)

Лема 4.2. Нехай

., ., (4.10)

де j пробігає всі номери внутрішніх вузлів дерева. Тоді обсяг . цього дерева задовольняє

.. (4.11)

Лема 4.3. Нехай

., ., (4.13)

де j пробігає всі номери внутрішніх вузлів дерева. Тоді глибина . цього дерева задовольняє

.. (4.14)

Нижче наведено низку прикладів алгоритмів, що використовують параметри щільності ., . та вибірковості . вузлів для побудови багаторозрядних дерев.

Перший алгоритм – добре відоме LC-дерево Андерсена - Нільсона (1993).

Визначення 4.5. LC-дерево це адаптивне багаторозрядне цифрове дерево, в якому число розрядів r, оброблюваних в його вузлах над n рядками задовольняє умові

.. (4.15)

Другий алгоритм – це модифікація LC –дерева, запропонована Нільсоном та Тікканеном (1998), що використовує обмеження на щільність вузлів.

Визначення 4.6. Багаторозрядне дерево з обмеженою щільністю - це адаптивне багаторозрядне дерево, в якому число розрядів r, оброблюваних у його вузлах, над n рядками задовольняє умові

.. (4.16)

де . - деякі позитивні константи.

Для побудови дерев мінімального обсягу пропонується користуватись модифікованим критерієм щільності вузлів (4.3).

Визначення 4.7. Багаторозрядне дерево з максимальною щільністю - це адаптивне багаторозрядне дерево, в якому число розрядів r, оброблюваних в його вузлах над n рядками відповідає

.. (4.16)

Для побудови дерев з константною глибиною пропонується використовувати вибірковість багаторозрядних вузлів (4.4).

Визначення 4.8. Багаторозрядне дерево з обмеженою вибірковістю - це адаптивне багаторозрядне дерево, в якому число розрядів r, оброблюваних в його вузлах над n рядками задовольняє умові

.. (4.17)

де . - деякі позитивні константи.

Для побудови логарифмічних дерев необхідно знати лише число рядків у піддереві.

Визначення 4.9. Логарифмічне багаторозрядне дерево - це адаптивне багаторозрядне дерево, в якому число розрядів r оброблюванихв його вузлах над n рядками обчислюється як

.. (4.18)

На Рис.4.2. и Рис.4.3. представлено результати экспериментальної оцінки очікуваної тривалості успішного пошуку та очікуваного обсягу пам’яті для реализації розглянутих типів дерев.

При побудові дерев було використано створені комп’ютером послідовності бінарних цифр для симетричного (p=0.5) та несиметричного (p=0.25) випадків. Діапазон зміни числа рядків у дереві становив від 2 до 105. Для кожного значення n і кожної моделі процессу було створено 103 різних дерева, і оцінено відносні розміри та очікувані значення висоти.

Рис. 4.2. Залежність середньої висоти . від загального числа рядків . в багато-розрядних деревах: (а) симетричний процесс ., (b) несимметричний

Зазначимо, що для симметричного випадку (рис.4.2,a), LC-дерево є єдиною структурою, для якої висота зростає разом з с n (приблизно як . [12]). Висота інших дерев не виходить за межі (1.5_.5), тобто швидкість зростання для них становить .. У несимметричному випадку обидва LC- та 50% щільні дерева ростуть із швидкісті приблизно як .). Логарифмічне дерево також зростає, але дещо повільніше. Висота дерев з 50%- вибірковістю коливається в межах (1.8 -2.8), тобто швидкість зростання наближається до до ..

Одержані результати дозволяють висловити припущення, що під впливом симметричного процесу відносні розміри для всіх модифікацій дерев мають порядок .. У випадку несиметричних процессів дерева з 50%-вибірковістю зростають досить швидко (не менш, як .). Однак для LC- дерев з 50% щільністю відносні розміри змінюються в межах констант, звідки випливає, що їхні розміри мають порядок ..

Одержані експериментальні дані добре узгоджуються з результатами аналізу в розділі 3, що підтверджує існування дерев з визначеними типами просторово-часових характеристик.

Рис. 4..3. Залежність середніх відносних розмірів . від загальної кількості рядків в дереві: (a) –симетричний процес ., (b) несиметричний процес..

П’ятий розділ дисертаційної роботи присвячений вирішенню задачі покращення продуктивності дерев шляхом застосування “симетруючого” перетворення над рядками перед їх вставкою в дерева. Показано, що задача побудови такого перетворення є еквівалентною побудові неблокових кодів, що мінімізують надлишковість кодування. У випадку невідомих параметрів процесу її рішенням є застосування рівномірного по виходу коду Ходака, а у випадку невідомих параметрів – коду Кричевського-Трофімова.

Висновки

Основним результатом дисертаційної роботи є теоретичне вивчення класу цифрових дерев з адаптивним гілкуванням, розробка та експериментальне дослідження алгоритмів динамічної побудови таких дерев та створення прикладних систем на їх основі.

В дисертаційній роботі поставлено та вирішено такі задачі:

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

створення узагальненої аналітичної моделі для класу цифрових дерев з адаптивним гілкуванням;

дослідження локалізації просторово-часових характеристик, які можуть бути досягнуті цифровими деревами з адаптивним гілкуванням;

розробка та експериментальне порівняльне дослідження ефективності прикладних алгоритмів інформаційного пошуку на основі цифрових дерев з адаптивним гілкуванням;

розробка методики збільшення продуктивності дерев шляхом симетруючого перетворення рядків вхідних даних.

Найбільш перспективними для застосування результатів даної роботи є:

інформаційно-пошукові системи;

програми та системи критично залежні від ефективності пошукових операцій: web-сервери, IP-роутери, сервери систем мобільного зв’язку;

програми та системи, що використовують цифрові дерева для внутрішнього представлен-ня даних: CAD-системи, системи обробки зображень, геоінформаційні системи, системи мовного перекладу, алгоритми стиснення даних.

СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

Резник Ю.А. О пространственно-временной эффективности цифровых деревьев с адаптивным многоразрядным ветвлением // Кибернетика и системный анализ. –2003.- № .- С.152-162.

Резник Ю. А. О средней плотности и избирательности узлов в многоразрядных цифровых деревьях // Математические машины и системы. –2002.- № 1.- С.70-83.

Резник Ю.А. Некоторые результаты касающиеся деревьев с адаптивным ветвлением // Математические машины и системы. –2001.- № 1-2.- С.55-65.

Резник Ю.А. On compact level partitioning of digital trees // Математические машины и системы. –1998.- № 1.- С. 38-45. 

Reznik Yu. A. Some Results on Tries with Adaptive Branching // Theoretical Computer Science. - 2002. – Vol. 289, № 2. - P.1009-1026.

Reznik Yu. A., Szpankowski W. On the Average Redundancy Rate of the Lempel-Ziv Code with the K-Error Protocol // Information Sciences.-2001.- Vol. 135.- P. 57--70.

Reznik Yu. A., On the Average Density and Selectivity of Nodes in Multi-Digit Tries // Proc. 2nd ACM/SIAM Workshop on Analytic Algorithmics and Combinatorics (ANALCO’05).- Vancouver, BC, Canada, January 22, 2005. – P.58-69.

Reznik Yu. A., Anisimov A.Using Tries for Universal Data Compression // Proc. 3rd Intl. Colloquium on Mathematics and Computer Science (MathInfo’04).- Vienna, Austria, September 13-17, 2004.- P. .

Reznik Yu. A., Szpankowski W. Improved behaviour of tries by the symmetrization of the source // Proc. IEEE Data Compression Conference (DCC’02).- Snowbird, Utah, USA, April , 2002.- P. 253-262.

Reznik Yu. A. On Tries, Suffix Trees, and Universal Variable-Length-to-Block Codes // Proc. IEEE International Symposium on Information Theory (ISIT’02).- Lausanne, Switzerland, June 30 - July 5, 2002.- P. 287.

Reznik Yu. A. On Time/Space Performance of Tries with Adaptive Branching // The Eighth International Seminar on the Analysis of Algorithms (AofA’02), Strobl, Austria, June 23-29, 2002. Online: http://www.geometrie.tuwien.ac.at/AofA2002/

Reznik Yu. A. Some Results on Tries with Adaptive Branching // Proc. 6th Annual International Computing and Combinatorics Conference (COCOON'00), Bondi Beach, Sydney, Australia, July 26-28, 2000 / Lecture Notes in Computer Science, Vol. 1858.- Springer-Verlag, New York, 2000.- P. 148-158.

Reznik Yu. A. On Three Classes of Tries with Adaptive Multi-Digit Branching // The Sixth Inter-national Seminar on the Analysis of Algorithms (AofA’00), Krynica Morska, Poland, July 3-7, 2000. Online: http://www.cs.purdue.edu/homes/spa/gdansk/aofa.html

Reznik Yu. A., Szpankowski W. On the Average Redundancy Rate of the Lempel-Ziv Code with K-Error Protocol // Proc. IEEE Data Compression Conference (DCC'00), Snowbird, Utah, USA, March 28-30, 2000.- P. 373-382.

Reznik Yu. A. On Compact Level Partitioning of Digital Trees // DIMACS Workshop on Codes and Trees: Algorithmic and Information Theoretic Approaches, DIMACS Center, Rutgers University, Piscataway, NJ, USA, October 5-7, 1998. Online: http://dimacs.rutgers.edu/Workshops/Codes/

Reznik Yu. A. LZRW1 Without Hashing // Proc. IEEE Data Compression Conference (DCC'98), Snowbird, Utah, USA, March 30 – April 1, 1998.- P.569.

Резник Ю.А. Алгоритмы в системах сжатия реального времени // IndexPro.-1994.- № 1.-P.22--_.

АНОТАЦІЇ

Резнік Ю.А. Дослідження властивостей цифрових дерев з адаптивним гілкуванням.– Рукопис. Дисертації на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.05.03 – математичне та програмне забезпечення обчислювальних машин і систем. – Київський національний університет імені Тараса Шевченка. Київ, 2005.

Дисертацію присвячено дослідженню властивостей цифрових дерев з адаптивним гілкуванням та розробці ефективних алгортмів пошуку інформації що грунтуються на застосуванні таких дерев. У роботі створено узагальнену аналітичну модель для класу цифрових дерев з адаптивним гілкуванням і проведено аналіз локалізації їх досяжних просторово-часових характеристик. На основі цього аналізу виявлено режими маючі найбільш практичний інтерес і розроблено алгортми побудови такіх дерев. Зокрема, у роботі створено нові алгоритми побудови дерев з лог-логаріфмічним та з константним середнім часом доступу.

Ключові слова: алгортми пошуку інформації, цифрові дерева, LC-дерева, адаптивне гілкування, аналіз очікуваної поведінки алгоритмів.

Резник Ю.А. Исследование свойств цифровых деревьев с адаптивным ветвлением.– Рукопись. Диссертация на соискание научной степени кандидата физико-математических наук по специальности 01.05.03 – математическое и програмное обеспечение вычислительних машин и систем. – Киевский национальний университет имени Тараса Шевченко. Киев, 2005.

Диссертация посвящена исследованию свойств цифровых деревьев с адаптивным ветвлением и разработке эффективных алгоритмов поиска информации основанных на их использовании. В работе разрабатывается обобщенная аналитическая модель для класса таких деревьев и производиться анализ локализации достижимых ими пространственно-временных характеристик. На основании этого анализа определены режимы представляющие наибольший практический интерес и разработаны алгоритмы построения таких деревьев. В частности, в работе получены новые алгоритмы построения деревьев с лог-логарифмической и с константной средней скоростью доступа к данным.

Ключевые слова: алгоритмы поиска информации, цифровые деревья, LC-деревья, адаптивное ветвление, анализ ожидаемого поведения алгоритмов.

Reznik Yu. A. Analysis of properties of digital trees with adaptive branching. –Manuscript. Dissertation submitted in partial fulfillment of the requirements for the degree of Candidate of Science (Physics and Mathematics) in the speciality 01.05.03 – Mathematical and Software Foundation of Computing Devices and Systems. Kiyv National Taras Schevchenko University. – Kiyv, Ukraine, 2005.

The dissertation is dedicated to the problem of analysis of a class of digital trees (tries) with adaptive multi-digit branching, and development of efficient algorithms for information retrieval, employing such data structures.

The first chapter contains a detailed survey of the existing techniques for information retrieval employing digital trees and their variants, such as tries (Fredkin, 1960), digital search trees (Coffman and Eve, 1970), Patricia tries (Morrison, 1968), N-trees (Dobosiewitz 1968, Ehrlich 1970), LC-tries (Andersson and Nilsson, 1993), and others. It is shown, that tries employing adaptive multi-digit branching represent a promising new class of data structures, deserving further analytical and experimental study.

The setting of a problem of the average case analysis of a class of tries with adaptive multi-digit branching is given in chapter . It is assumed that n input strings (keys) used for construction of tries are generated by a memoryless process. The average space-complexity of a trie over n strings is estimated by counting the total number of pointers (branches) in such a trie ., and the average time-complexity of such a trie is estimated by counting its average depth .. Theof analysis of the average case behavior of a class of tries with adaptive branching consists in finding localizations of pairs . which are asymptotically attainable by such tries when ..

The third chapter contains detailed analysis of this problem. Main results of this analysis are schematically depicted on the following diagram.

It is shown, that LC-tries belong to a region of tries with linear average size and log-logarithmic depth. Two extreme points in this region represent

MS-tries – tries that attain minimum possible average size; and

FLS-tries – tries with smallest average depth while having asymptotically linear average size.

The best time complexity on this diagram is attained by tries with constant average depth. The extreme point in this (lower right) region represents

SCT-tries – tries with smallest average size while having asymptotically constant average depth.

The main disadvantage of constant depth tries is that their average size is growing as ., where the constant . depends on the parameters on the process, and can be arbitrarily large. Finally, the region in the middle represents tries, whose degrees of nodes are produced by simply taking logarithms on the remaining number of strings. It is shown, that the size of such tries is bounded by . and that their average depth is log-logarithmic. The final results of the analysis of the above-described types of tries are formulated in the form of first-term accurate asymptotic expressions for their average sizes and depths.

Chapter 4 of the thesis is dedicated to the development of practical algorithms for construction of adaptive multi-digit tries, and experimental verification of their efficiency. It is shown, that the observed behavior of practically constructed algorithms is in a good agreement with their theoretically predicted properties.

The last chapter develops complimentary technique for improving performance of trie-based search algorithms by using “symmetrization” transform of input data. It is shown that such a transform can be implemented by using standard variable-length-to-block codes, such as Tunstall, Khodak, or Krichevsky-Trofimov codes, and that such techniques are very efficient in minimizing the sensitivity of search algorithms to the varying statistics of input data.

Key words: searching algorithms, digital trees, tries, LC-tries, adaptive branching, average case analysis of algorithms