Суффиксные деревья поиска

 














Курсовой проект

Суффиксные деревья поиска



1. Постановка задачи

программист пользователь системный

Реализовать алгоритм построения суффиксного поискового дерева для организации эффективного поиска строковых данных. Должны быть реализованы такие функции как добавление элемента, печать дерева, поиск элементов в дереве.


2. Описание алгоритма


Суффиксное дерево - способ организации данных (строк), позволяющий выяснять, содержится ли искомая строка в данной структуре или нет. Используется в поисковых системах, электронных словарях и справочниках. Основная особенность такого дерева - отсутствие функции удаления элементов (узлов), так как эта операция весьма трудоемка и практически не используется в этих структурах.


. Алгоритм добавления нового элемента в дерево


В каждом узле дерева имеется указатель на своего предка (*parent) и динамический список указателей на узлы-потомки (list<node*> lstNode). У корневого узла указатель на родителя указывает на нулевое значение (NULL).

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

Процесс добавления происходит следующим образом: программа сначала отделяет первую букву, сравнивает её с имеющимися, если таких нет, то программа ставит указатель на узел с буквой в конец списка корня (root ->lstNode.push_back(tn), tn->parent=root, где root - указатель на корень, а tn - указатель на узел с буквой). Потом программа ставит в конец списка узла с буквой указатель на узел с со словом без первой буквы (tn->lstNode.push_back(tn1), tn1->parent=tn, где tn - указатель на узел с буквой, tn1 - указатель на узел с остатком слова). Если совпала первая буква, то программа переходит на следующий уровень подстрок, она берет значения из узлов этого уровня, сначала сравнивает с каждым длину остатка слова и длину значения в узлах.

Далее алгоритм разветвляется: если остаток слова меньше значения в узле, то в данный узел записывается входящее значение, а та часть слова, которая не совпадает, записывается в новый узел, который починен данному.

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

Если ни одно из данных условий не совпало, то подпрограмма создает новый узел на том уровне, где не было совпадающих значений.


. Алгоритм поиска по дереву


Этот алгоритм похож на алгоритм добавления нового слова. Вводится слово, которое необходимо найти. Программа сначала отделяет первую букву и ищет её, если её нет, то подпрограмма завершает работу, так как дальше нет смысла искать. Если буква нашлась, то программа отделяет её и переходит на следующий уровень. Далее подпрограмма ищет узлы, которые имеют общие буквы с введенным словом, если их нет, то она завершает свою работу, иначе она их отделяет совпадающие буквы и переходит на следующий уровень. И так далее пока подпрограмма не дойдет до листа, или найдет различия.


. Руководство пользователя


Работа с экранным меню

После запуска программы появляется простое экранное меню, где требуется ввести номер желаемой команды. После выполнения команды на консоли появится результат действия, и программа снова потребует ввода номера команды. Для выхода из программы нужно ввести команду под номером «0».

Добавление элемента

Для операции добавления введите «1», далее слово, как показано на рис. 1. В данном случае первое добавленное слово - «accelerated».


Рис. 1


Таким же образом введем следующие слова: avaivable_page_quene, avaivable_unit, avaivable_unit_quene, backup, backward, back, backbone_cabling, backward_brunch, backward_drive.


6. Печать дерева


Для печати дерева введите «2», как показано на рис. 2:


Рис. 2


Заметим, что слово «backward» (подчеркнуто желтым) добавлено до слова «back» (подчеркнуто голубым) и поэтому оно не разбито как следующие слова (подчеркнуто красным). Это следствие того, что слова добавлялись не в алфавитном порядке.


7. Поиск элемента

Для поиска требуемого слова необходимо ввести «3» и само значения, как показано на рис. 3:



Рис. 3


В данном случае введено слово «back_transfer», которого нет в дереве. Программа вывела сообщение, что слово «back_transfer» не найдено. Если ввести для поиска слово «backup», то программа выведет сообщение, что слово «backup» найдено (рис. 4):


Рис. 4


9. Руководство системного программиста


Для запуска программы необходимо зайти в папку tree/Debug и запустить файл «tree.exe». Программа будет работать на версиях ОС Windows XP и выше.

Приложение


Программный код с комментариями:

/**

\file MyClass.h (MyClass.cpp)

\brief Класс cписок с модулями

\ Бригаденко

\date 13,02,2014

*/

#include <list>

#include <iterator>

namespace std;

int MAX_STR = 256; // размер для буферной переменной


// узел дереваnode

{:val [MAX_STR]; // переменная для записи суффикса в узел

// конструктор списока указателей на возможные узлы<node*> lstNode;

// указатель на родителя*parent;

// конструктор с парметром(char* node_val);

// конструктор для корня без параметра();

// деструктор

~node();

/// Печать данный в виде дерева «на боку»

/// Рекурсивный обход дерева справа налевоprint (int level = 0);

// функция поиска узла

// Рекурсивный обход дерева справа налево

};


// деревоtree

{:*root; // указатель на корень*zero_node; // указатель на пустой узел

// Запрещаем копирование и присвоение(const tree &);

tree & operator=(const tree &);


// закрытые внутренние фунции


// Сделать кореньmake_root (char* root_val)

{b [MAX_STR]=»»;

// создаем корень и в него записываем указатель

// на узел с началом слова= new node();(b, root_val, 1);*tn = new node(b); // конструируем узел с одной буквой>parent = root; // регистрация редителя у потомка>lstNode.push_back(tn); // регистрация потомка у родителя

// создаем первое слово в этой букве

// копируем слово без первой буквы*tn1 = new node (root_val+1);

// рестрация->parent = tn;>lstNode.push_back(tn1);

}


// Вставка узла* insert_node (char* insert_value, node *start_node = 0)

{b [MAX_STR]=»»; // буфер обмена

if(! root) // если дерево пустое создаем корень

{

// при создании создаеися 3 узла: пустая строка - общий корень - точка входа в дерево

// узел по первой букве слова, узел со словом без первой буквы

make_root (insert_value);root;

}

// перводим указатель в исходное положение на корне

if (! start_node) start_node = root;*tn = start_node;*tnl = zero_node;

if (fd_nd (insert_value)==true) // проверяем есть ли слово в деревеNULL; // если есть, то выходим и говорим, что слово уже добавлено

// пока не перебрали все возможные узлы и если новое значение узла уникальное(tn)

{

// на первом уровне все где есть хотябы 1 указатель на подчиненный уровень букв

// 1-й шаг - прохожд. по начальным буквам

for each (node* tn1 in tn->lstNode)

{

// найденная 1-я буква(tn1->val[0] == insert_value[0])

{= tn1;;

}

}

// найденная 1-я буква

if (tnl!= zero_node /*1->val[0] == insert_value[0]*/)

{

// проход на уровни ниже* tn3 = left_tree_raise (tnl, insert_value+1);

//cout<<«tn3->val: «<<tn3->val<<endl;tn3;

}// буквы нет

{

// создаем новую букву(b, insert_value, 1); *tn4 = new node(b); // конструируем узел с одной буквой->parent = root; // регистрация редителя у потомка>lstNode.push_back(tn4); // регистрация потомка у родителя

// создаем первое слово в этой букве*tn5 = new node (insert_value+1); // копируем слово без первой буквы

tn5->parent = tn4;->lstNode.push_back(tn5);tn5;

}


}


// если tn не NULL - ошибка(tn)

{<< «The global algorithm error, tree node can't be not NULL!!!» << tn->val << endl;

}NULL;

}


// обход след. уровня (исп. в добавления узла)* left_tree_raise (node *tn, char* insert_val)

{ // создаем указатель на пустой узел*tnl = zero_node;b [MAX_STR]=»»; // буферная переменнаяeach (node* tn1 in tn->lstNode) // цикл по элементам списка в узле

{ // проверяем совпадает ли часть слова с значением в узле

if((! strcmp (tn1->val, insert_val))||(! strncmp (tn1->val, insert_val, strlen (insert_val)))||(! strncmp (tn1->val, insert_val, strlen (tn1->val))))

{

//cout<< «system A\n»;= tn1;;

}

}

// если указатель не на пустой узел, то смотрим как

// значение в узле совпадает со входящим значением

if (tnl!= zero_node)

{ //cout<< «system B\n»;(strlen(insert_val)<strlen (tnl->val)) // если остаток слова меньше длины cтроки в узле

{ //cout<< «system C\n»;(! strncmp(tnl->val, insert_val, strlen (insert_val))) // если совпадает часть строки

{ //cout<< «system D\n»;*tn3 = new node (tnl->val+strlen (insert_val)); //cоздаем новый узел с остатком значения из старого узла->parent=tnl;>lstNode.push_back(tn3);(tnl->val, insert_val);

return tn3;

}// создаем новый узел

{ //cout<< «system F\n»;*tn4 = new node (insert_val);->parent=tnl;>lstNode.push_back(tn4);tn4;

}

}(! strncmp(tnl->val, insert_val, strlen (tnl->val))) // если совпадает часть строки, но длина строки в узле меньше длины входящей строки

{ //cout<< «system E\n»;

// если конечный узел или нет совпадений

// создаем новый узел(tnl->lstNode.empty()) // если список в узле пуст

{ //cout<< «system I\n»;*tn2 = new node (insert_val+strlen (tnl->val)); // передвигаемся по слову на длину значения в узле и создаем узел

tn2->parent=tnl; // регистрируемся>lstNode.push_back(tn2);tn2;

}

{ //cout<< «system L\n»;

left_tree_raise (tnl, insert_val+strlen (tnl->val)); // передвигаемся по слову на длину значения в узле, рекурсия

}

}

}// если на данном уровне нет совпадений, то просто создаем новый узел

{ //cout<< «system N\n»;

*tn6 = new node (insert_val); // создаем узел->parent=tn; // регистрируемся>lstNode.push_back(tn6);

return tn6;


}tn; // все сделали, возвращаем указатель предыдущего узла


}* find_node (char* find_value, node * tn)

{each (node* tn1 in tn->lstNode) // цикл по элементам списка

{

if (strlen(find_value)>strlen (tn1->val)) // если длина искомого значения больше длины значения в узле

{ //cout<< «system A\n»;(! strncmp(find_value, tn1->val, strlen (tn1->val))) // если какая-то часть слова совпадает со значением в узле

{ //cout<< «system B\n»;

//cout<<find_value<<endl;

//cout<<«tn1->val «<<tn1->val<<endl;

return find_node (find_value+strlen (tn1->val), tn1); // если да, то вызываем рекусивно функцию, для средующего уровня узлов

}

} // если длина искомого значения меньше или совпадаетif (strlen(find_value) == strlen (tn1->val)) // если длина искомого значения совпадает с длиной узла

{ //cout<< «system C\n»;(! strncmp(find_value, tn1->val, strlen (tn1->val))) // если значение в узле совпадает,

{

//cout<< «system D\n»;tn1; // то возвращаем указатель

}


}

}zero_node; // если совпадений нет, то возвращаем пустое значение

}

:

// Конструктор без параметра();

// Конструктор с параметром(char root_val);

// деструктор

~tree() {}

// функции открытой области

// Добавление узла

bool add (char* insert_value);


// поиск в дереве по значениюfd_nd (char *find_value);


// печать дереваprint();


};


/**

\file MyClass.h (MyClass.cpp)

\brief описание модулей

\ Бригаденко

\date 13,02,2014

*/

#include «stdafx.h»

#include <iostream>

#include «class.h»

namespace std;


// конструктор для корня:node()

{=NULL; // указатель на родителя нулевой(val, «ROOT»); // присвайиваем символьное значение, указывающ, что это корень

}

// констуктор для узла

node:node (char* node_val)

{(val, node_val); // записываем значение в узел

}

// деструктор:~node() {}


// обход дерева в глубину

void node:print (int level)

{node *tn = this; // создаем указатель на данный узел(tn) // если узел не конечный

{each (node* tn1 in tn->lstNode) // цикл по элементам списка в узле->print (level + 1); // рекурсивный вызов функции самой себя

}(int spaces = 0; spaces < level; spaces++) // выводим нужное количество пробелов<<»»;

if(tn) // выводим само значение узла

{<< tn->val << endl;

}

}


// конструктор дерева

tree:tree()

{= NULL;_node=NULL;

}

// добавление суффикса в деревоtree:add (char* insert_value)

{*ret = insert_node (insert_value); // вызываем конструктор(ret) return true; // если все хорошо, то вовращаем true

else return false; // иначе false

}


// ищем суффикс с заданным значениемtree: fd_nd (char *find_value)

{(! root)false;*find_nd=find_node (find_value, root);(find_nd!=zero_node)true;

}


tree:print() // печатаем дерево

{(! root) // защита от ошибок - если вообще нет дерева, то просто выходим

return false;<< «================================\n\n»;

root->print(); // вызываем функцию печати<< «================================\n\n»;

}

// tree.cpp: определяет точку входа для консольного приложения.

//


/**

\brief работа со случайным деревом поиска

\author Бригаденко

\date 28/03/2011

*/

#include «stdafx.h»

#include <iostream>

#include «class.h»

using namespace std;



// основная программа консольного приложения

int _tmain (int argc, _TCHAR* argv[])

{m = 0;


// создаем дерево*ptree = new tree();


// организуем простое экранное меню

do {


cout << «________________________________\n\n»;<< «0 - Exit\n»;<< «1 - Add word\n»;<< «2 - Print tree\n»;<< «3 - Find the word\n»;<< «________________________________\n\n»;<< «\tInput the command number:\n»;>> m;<< «________________________________\n\n»;d [MAX_STR]=»», d1 [MAX_STR]=»»;


// выполняем действия в зависимости от выбранного пункта меню

switch(m)

{

1: // добавим элемент<< «\tEnter the word to add: \n»;>> d;(ptree->add(d)==true)<<»\tValue is added\n»;<<»\tERROR: word is not added or already has added\n»;;2: // напечатать список(ptree->print()==false)<<» \t!!! THE TREE IS EMPTY!!!\n»;;3: // поиск<<»\tEnter the word to search:\n»;>>d;

{

// если нашли(ptree->fd_nd(d)==true)<< «\tThe word < «<<d<<» > is in tree!\n»;<< «\t Word < «<<d<<» > not found… \n»;

};0: // выход из программы

std:cout << «\tGOOD LUCK!» <<endl;

break;: // пустое условие для остальных действий

cout << «\t!!! Input the command number from menu!!!\n»;

break;

}


} while (m!=0); // условие выхода


// удаляем список(ptree)

{ptree;

}


// выход из программы0;

}


Курсовой проект Суффиксные деревья поиска 1. Постановка задачи программист пользователь сис

Больше работ по теме:

КОНТАКТНЫЙ EMAIL: [email protected]

Скачать реферат © 2017 | Пользовательское соглашение

Скачать      Реферат

ПРОФЕССИОНАЛЬНАЯ ПОМОЩЬ СТУДЕНТАМ