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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

После запуска программы появляется простое экранное меню, где требуется ввести номер желаемой команды. После выполнения команды на консоли появится результат действия, и программа снова потребует ввода номера команды. Для выхода из программы нужно ввести команду под номером «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

#include

using namespace std;

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

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

class node

{

public:

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

// конструктор списока указателей на возможные узлы

list lstNode;

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

node *parent;

// конструктор с парметром

node (char* node_val);

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

node ();

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

~node ();

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

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

void print (int level = 0);

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

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

};

// дерево

class tree

{

private:

node *root; // указатель на корень

node *zero_node; // указатель на пустой узел

// Запрещаем копирование и присвоение

tree (const tree &);

tree & operator=(const tree &);

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

// Сделать корень

void make_root (char* root_val)

{

char b [MAX_STR]="";

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

// на узел с началом слова

root = new node ();

strncpy (b, root_val, 1);

node *tn = new node (b); // конструируем узел с одной буквой

tn->parent = root; // регистрация редителя у потомка

root->lstNode.push_back (tn); // регистрация потомка у родителя

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

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

node *tn1 = new node (root_val+1);

// рестрация

tn1->parent = tn;

tn->lstNode.push_back (tn1);

}

// Вставка узла

node * insert_node (char* insert_value, node *start_node = 0)

{

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

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

{

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

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

make_root (insert_value);

return root;

}

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

if (! start_node) start_node = root;

node *tn = start_node;

node *tnl = zero_node;

if (fd_nd (insert_value)==true) // проверяем есть ли слово в дереве

return NULL; // если есть, то выходим и говорим, что слово уже добавлено

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

if (tn)

{

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

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

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

{

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

if (tn1->val[0] == insert_value[0])

{

tnl = tn1;

break;

}

}

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

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

{

// проход на уровни ниже

node * tn3 = left_tree_raise (tnl, insert_value+1);

//cout<<�"tn3->val: «<val<

return tn3;

}

else // буквы нет

{

// создаем новую букву

strncpy (b, insert_value, 1);

node *tn4 = new node (b); // конструируем узел с одной буквой

tn4->parent = root; // регистрация редителя у потомка

root->lstNode.push_back (tn4); // регистрация потомка у родителя

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

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

tn5->parent = tn4;

tn4->lstNode.push_back (tn5);

return tn5;

}

}

// если tn не NULL — ошибка

if (tn)

{

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

}

return NULL;

}

// обход след. уровня (исп. в добавления узла)

node * left_tree_raise (node *tn, char* insert_val)

{ // создаем указатель на пустой узел

node *tnl = zero_node;

char b [MAX_STR]=""; // буферная переменная

for 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 An»;

tnl = tn1;

break;

}

}

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

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

if (tnl≠ zero_node)

{ //cout<< «system Bn»;

if (strlen (insert_val)val)) // если остаток слова меньше длины cтроки в узле

{ //cout<< «system Cn»;

if (! strncmp (tnl->val, insert_val, strlen (insert_val))) // если совпадает часть строки

{ //cout<< «system Dn»;

node *tn3 = new node (tnl->val+strlen (insert_val)); //cоздаем новый узел с остатком значения из старого узла

tn3->parent=tnl;

tnl->lstNode.push_back (tn3);

strcpy (tnl->val, insert_val);

return tn3;

}

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

{ //cout<< «system Fn»;

node *tn4 = new node (insert_val);

tn4->parent=tnl;

tnl->lstNode.push_back (tn4);

return tn4;

}

}

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

{ //cout<< «system En»;

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

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

if (tnl->lstNode.empty ()) // если список в узле пуст

{ //cout<< «system In»;

node *tn2 = new node (insert_val+strlen (tnl->val)); // передвигаемся по слову на длину значения в узле и создаем узел

tn2->parent=tnl; // регистрируемся

tnl->lstNode.push_back (tn2);

return tn2;

}

else

{ //cout<< «system Ln»;

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

}

}

}

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

{ //cout<< «system Nn»;

node *tn6 = new node (insert_val); // создаем узел

tn6->parent=tn; // регистрируемся

tn->lstNode.push_back (tn6);

return tn6;

}

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

}

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

{

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

{

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

{ //cout<< «system An»;

if (! strncmp (find_value, tn1->val, strlen (tn1->val))) // если какая-то часть слова совпадает со значением в узле

{ //cout<< «system Bn»;

//cout<

//cout<<�"tn1->val «<val<

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

}

} // если длина искомого значения меньше или совпадает

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

{ //cout<< «system Cn»;

if (! strncmp (find_value, tn1->val, strlen (tn1->val))) // если значение в узле совпадает,

{

//cout<< «system Dn»;

return tn1; // то возвращаем указатель

}

}

}

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

}

public:

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

tree ();

// Конструктор с параметром

tree (char root_val);

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

~tree () {}

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

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

bool add (char* insert_value);

// поиск в дереве по значению

bool fd_nd (char *find_value);

// печать дерева

bool print ();

};

/**

file MyClass. h (MyClass.cpp)

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

Бригаденко

date 13,02,2014

*/

#include «stdafx.h»

#include

#include «class.h»

using namespace std;

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

node:node ()

{

parent=NULL; // указатель на родителя нулевой

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

}

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

node:node (char* node_val)

{

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

}

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

node:~node () {}

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

void node: print (int level)

{

const node *tn = this; // создаем указатель на данный узел

if (tn) // если узел не конечный

{

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

tn1->print (level + 1); // рекурсивный вызов функции самой себя

}

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

cout <<�"";

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

{

cout << tn->val << endl;

}

}

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

tree:tree ()

{

root = NULL;

zero_node=NULL;

}

// добавление суффикса в дерево

bool tree: add (char* insert_value)

{

node *ret = insert_node (insert_value); // вызываем конструктор

if (ret) return true; // если все хорошо, то вовращаем true

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

}

// ищем суффикс с заданным значением

bool tree: fd_nd (char *find_value)

{

if (! root)

return false;

node *find_nd=find_node (find_value, root);

if (find_nd≠zero_node)

return true;

}

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

{

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

return false;

cout << «================================nn»;

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

cout << «================================nn»;

}

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

//

/**

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

author Бригаденко

date 28/03/2011

*/

#include «stdafx.h»

#include

#include «class.h»

using namespace std;

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

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

{

int m = 0;

// создаем дерево

tree *ptree = new tree ();

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

do {

cout << «________________________________nn»;

cout << «0 — Exitn»;

cout << «1 — Add wordn»;

cout << «2 — Print treen»;

cout << «3 — Find the wordn»;

cout << «________________________________nn»;

cout << «tInput the command number: n»;

cin >> m;

cout << «________________________________nn»;

char d [MAX_STR]="", d1 [MAX_STR]="";

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

switch (m)

{

case 1: // добавим элемент

cout << «tEnter the word to add: n»;

cin >> d;

if (ptree->add (d)==true)

cout<<�"tValue is addedn";

else

cout<<�"tERROR: word is not added or already has addedn";

break;

case 2: // напечатать список

if (ptree->print ()==false)

cout<<�" t!!! THE TREE IS EMPTY!!! n";

break;

case 3: // поиск

cout <<�"tEnter the word to search: n";

cin>>d;

{

// если нашли

if (ptree->fd_nd (d)==true)

cout << «tThe word < „<<�“ > is in tree! n»;

else

cout << «t Word < „<<�“ > not found… n»;

}

break;

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

std:cout << «tGOOD LUCK!» <

break;

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

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

break;

}

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

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

if (ptree)

{

delete ptree;

}

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

return 0;

}