Курсовий проект
Суффіксние дерева пошуку
1. Постановка завдання
програміст користувач системний
Реалізувати алгоритм побудови суффіксного пошукового дерева для організації ефективного пошуку строкових даних. Повинні бути реалізовані такі функції як додавання елемента, друк дерева, пошук елементів в дереві.
2. Опис алгоритму
Суффіксное дерево - спосіб організації даних (рядків), дозволяє з'ясовувати, чи міститься шукана стрічка в даній структурі чи ні. Використовується в пошукових системах, електронних словниках і довідниках. Основна особливість такого дерева - відсутність функції видалення елементів (вузлів), так як ця операція вельми трудомістка і практично не використовується в цих структурах.
. Алгоритм додавання нового елементу в дерево
У кожному вузлі дерева є покажчик на свого предка (* parent) і динамічний список покажчиків на вузли-нащадки (list lt; node * gt; lstNode). У кореневого вузла покажчик на батька вказує на нульове значення (NULL).
При додаванні нового значення спочатку перевіряється наявність самого дерева. Якщо його немає, то викликається функція для створення кореня, результатом якої будуть три вузли - корінь, перша буква введеного слова й саме слово без першої літери. Якщо додається нове значення у вже існуюче дерево, то спочатку йде перевірка на наявність цього слова в дереві. Якщо слово вже міститься, то програма виводить повідомлення про те, що слово вже є. В іншому випадку, програма додасть елемент в дерево.
Процес додавання відбувається наступним чином: програма спочатку відокремлює першу букву, порівнює її з наявними, якщо таких немає, то програма ставить покажчик на вузол з буквою в кінець списку кореня (root - gt; lstNode.push_back ( tn), tn- gt; parent=root, де root - покажчик на корінь, а tn - покажчик на вузол з буквою). Потім програма ставить в кінець списку вузла з буквою покажчик на вузол з зі словом без першої літери (tn- gt; lstNode.push_back (tn1), tn1- gt; parent=tn, де tn - покажчик на вузол з буквою, tn1 - покажчик на вузол із залишком слова). Якщо збіглася перша буква, то програма переходить на наступний рівень подстрок, вона бере значення з вузлів цього рівня, спочатку порівнює з кожним довжину залишку слова і довжину значення у вузлах.
Далі алгоритм розгалужується: якщо залишок слова менше значення у вузлі, то в даний вузол записується вхідне значення, а та частина слова, яка не збігається, записується в новий вузол, який полагоджений даному.
Інший випадок: коли довжина значення вузла менше вхідного значення. Тут вже інакше, якщо частина вхідного слова збігається, то програма пересувається по слову на довжину значення у вузлі і йде на рекурсію, далі операція повторюється, якщо цей вузол є листом, то ми створюємо новий вузол з незбіжних частиною слова, який полагоджений даному вузлу.
Якщо жодне з даних умов не співпало, то підпрограма створює новий вузол на тому рівні, де не було співпадаючих значень.
. Алгоритм пошуку по дереву
Цей алгоритм схожий на алгоритм додавання нового слова. Вводиться слово, яке необхідно знайти. Програма спочатку відокремлює перший букву і шукає її, якщо її немає, то підпрограма завершує роботу, так як далі немає сенсу шукати. Якщо літера знайшлася, то програма відокремлює її і переходить на наступний рівень. Далі підпрограма шукає вузли, які мають спільні букви з введенням словом, якщо їх немає, то вона завершує свою роботу, інакше вона їх відділяє співпадаючі букви і переходить на наступний рівень. І так далі поки підпрограма не дійде до листа, або знайде відмінності.
. Керівництво користувача
Робота з екранним меню
Після запуску програми з'являється просте екранне меню, де потрібно ввести номер бажаної команди. Після виконання команди на консолі з'явиться результат дії, і програма знову вимагатиме введення номера команди. Для виходу з програми потрібно ввести команду під номером «0».
Додавання елемента
Для операції додавання введіть «1», далі слово, як показано на рис. 1. У даному випадку перше доданий слово - «accelerated».
Рис. 1
Таким же чином введемо такі слова: avaivable_page_quene, avaivable_unit, avaivable_unit_quene, backup, backward, back, backbon...
