Порівняльний аналіз та класифікація існуючих методів інформаційного пошуку що ґрунтуються на застосуванні цифрових дерев. Дослідження локалізації просторово-часових характеристик, що можуть бути досягнуті цифровими деревами з адаптивним гілкуванням.
Аннотация к работе
За таких умов особливого значення набуває задача розробки алгоритмів, що забезпечують пошук за лог-логарифмічною (або навіть константною) кількістю звернень до памяті. Відомим класом алгоритмів з константною швидкістю є хешування, однак цей метод мало пристосований до пошуку за шаблонами, або у випадках, коли пошук здійснюють за частковими чи ранговими ознаками. Основні результати по (не адаптивним) цифровим деревам були одержані вітчизняними вченими: А. В. Роботу виконано в межах наукових тем кафедри математичної інформатики Київського національного університету імені Тараса Шевченка: “Розробка систем інтелектуалізації інформаційних технологій та дистанційного навчання” (державний реєстраційний номер 0101U002170) та “Дослідження та розробка технологій захисту інформації в коммунікаційно-інформаціийних системах, що динамично змінюються” (державний реєстраційний номер 01032U006601), а також ряду інших проектів систем пошуку та стиснення інформації, виконаних за участю автора у США. · дослідження локалізації просторово-часових характеристик, що можуть бути досягнуті цифровими деревами з адаптивним гілкуванням;Перший розділ дисертаційної роботи присвячений аналізу відомих типів цифрових дерев (trie-дерева, дерева Коффмана і Еве, Patricia, b-дерева, багаторозрядні дерева, LC-дерева та N-дерева). Запис. означає суффікс рядка, що починається з k-ї позиції цього рядка (тобто існує рядок, такий, що.). Запис. означає k молодших значущих цифр в бінарному представленні числа i. (тобто S містить лише один рядок), дерево є зовнішнім вузлом, що містить указник на цей рядок в S. При. дерево є внутрішнім вузлом, що містить указники на 2 дочірні дерева:. та, побудовані з суффіксів рядків з S, які починаються відповідно з символів 0 та 1. Якщо, дерево є зовнішнім вузлом, що містить указник на єдиний рядок в S. При, дерево є r-розрядным внутрішнім вузлом, що містить указники на. дочірні дерева, побудовані з суффіксів рядків з S, які починаються з відповідних r-розрядних послідовностей.Основним результатом дисертаційної роботи є теоретичне вивчення класу цифрових дерев з адаптивним гілкуванням, розробка та експериментальне дослідження алгоритмів динамічної побудови таких дерев та створення прикладних систем на їх основі.
План
Основний зміст роботи
Вывод
Основним результатом дисертаційної роботи є теоретичне вивчення класу цифрових дерев з адаптивним гілкуванням, розробка та експериментальне дослідження алгоритмів динамічної побудови таких дерев та створення прикладних систем на їх основі.
В дисертаційній роботі поставлено та вирішено такі задачі: · порівняльний аналіз та класифікація існуючих методів інформаційного пошуку, що грунтуються на застосуванні цифрових дерев;
· створення узагальненої аналітичної моделі для класу цифрових дерев з адаптивним гілкуванням;
· дослідження локалізації просторово-часових характеристик, які можуть бути досягнуті цифровими деревами з адаптивним гілкуванням;
· розробка та експериментальне порівняльне дослідження ефективності прикладних алгоритмів інформаційного пошуку на основі цифрових дерев з адаптивним гілкуванням;
· розробка методики збільшення продуктивності дерев шляхом симетруючого перетворення рядків вхідних даних.
Найбільш перспективними для застосування результатів даної роботи є: · інформаційно-пошукові системи;
· програми та системи критично залежні від ефективності пошукових операцій: web-сервери, IP-роутери, сервери систем мобільного звязку;
· програми та системи, що використовують цифрові дерева для внутрішнього представлення даних: CAD-системи, системи обробки зображень, геоінформаційні системи, системи мовного перекладу, алгоритми стиснення даних.