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

Размещено на http://www.allbest.ru/

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

УДК 681.51:519.713.2

Автореферат

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

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

Спеціальність 01.05.03 - математичне та програмне забезпечення обчислювальних машин і систем

Резнік Юрій Олександрович

Київ 2005

Загальна характеристика роботи

цифрове дерево адаптивне гілкування

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Апробація результатів дисертації. Основні наукові результати дисертаційної роботы доповідались та обговорювались на міжнародних конференціях: 2^nd ACM / SIAM Workshop on Analytic Algorithmics and Combinatorics (ANALCO'05) (Vancouver, Canada, 22 Січня 2005), 3^rd 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), 8^th 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), 6^th International Seminar on the Analysis of Algorithms (AofA'00) (Krynica Morska, Poland, 3-7 липня 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 березня - 1 квітня 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. Адаптивне багаторозрядне дерево є багаторозрядным цифровим деревом, у якого параметри.що визначають число оброблюваних вузлами розрядів, визначаються адаптивно від одного вузла до іншого.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Висновки

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

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

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

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

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

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

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

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

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

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

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

Список опублікованих праць за темою дисертації

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

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

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

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

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

6. 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.

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

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

9. 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 2-4, 2002.- P. 253-262.

10. 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.

11. 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/

12. 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.

13. 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

14. 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.

15. 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/

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

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

Анотація

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

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

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

Аннотация

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

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

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

Summary

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 2. 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. The problem of 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;

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

Размещено на Allbest.ru