постройка дерева суффиксов - PullRequest
2 голосов
/ 14 марта 2012

я собираюсь реализовать дерево суффиксов для данной строки, я думаю, что это должно делаться на две строки вот так

struct suffix
{

char  letter;
suffix * left,*right; 

};
suffix *insert(suffix *node,char *s){

}

// здесь я собираюсь построить дерево со всеми вхождениями подстрок и символов, но не знаю какиспользовать левую и правую части, отсортировано ли это дерево и упорядочено ли по строгому порядку символов, таких как дерево двоичного поиска? или? пожалуйста, помогите мне, я не хочу использовать некоторый код в Интернете, мне нужно реализовать его myselft, поэтому, пожалуйста, дайте мне немногоподсказки, немного кода

Ответы [ 2 ]

4 голосов
/ 19 июня 2012

Википедия - это начало.

Однако на самом деле мы понимаем алгоритм построения дерева суффиксов, алгоритм Вейнера или Укконена.

Алгоритм Укконена проще: http://europa.zbh.uni -hamburg.de / Пабы / PDF / GieKur1997.pdf

Также эта ссылка менее академична и более практична: http://www.cise.ufl.edu/~sahni/dsaaj/enrich/c16/suffix.htm

Попробуйте начать понимать алгоритм.

После удачи это одна из самых сложных структур данных. Единственное, что хуже всего - это сжатые и оптимизированные версии дерева суффиксов.

Но все великие программисты любят большие проблемы.

4 голосов
/ 14 марта 2012

Взгляните на описание Википедии :

Suffix tree

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

Далее, недостаточно хранить один символ на узел / ветку; Ветвь суффиксного дерева представляет подстроку , которая может быть длиннее одного символа. Также обычно хранятся только начальный и конечный индексы подстроки в строке, а не сама строка; в противном случае дерево суффиксов будет занимать много ненужной памяти.

Наконец, не используйте указатели здесь. Они ничего вам не покупают и только доставляют неприятности. Вместо этого используйте что-то вроде boost::container::vector<suffix> (я бы предложил std::vector<suffix>, но, к сожалению, стандартные библиотечные контейнеры не могут работать с неполными типами ).

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