Да, я прочитал это: Алгоритм дерева суффиксов Укконена на простом английском?
Это отличное объяснение алгоритма, но меня убивает не столько сам алгоритм, сколько структура данных, используемая для его реализации.
Мне нужно, чтобы структура данных была минимальной и максимально быстрой, и я видел много реализаций, использующих только узлы, некоторые с только ребрами, некоторые с ребрами и узлами и т. Д. Затем есть варианты, и сайт, который я читал, утверждал, что узел не должен иметь указатель на своего родителя, а другие места не учитывают, как управляются дочерние узлы.
Моя идея состоит в том, чтобы иметь структуру Node с int start и int * end (указывает на текущий конец или фазу i). Каждый узел будет иметь указатель суффикса-ссылки, указатель на своего родителя и указатель на вектор, содержащий его дочерние узлы.
У меня вопрос: достаточно ли и необходимо ли это для реализации дерева суффиксов? Могу ли я свести это к минимуму? Я еще не видел реализацию с детьми в векторах, поэтому я скептически отношусь к своему собственному мышлению. Может ли кто-нибудь объяснить, что нужно для реализации дерева суффиксов таким образом, используя только узлы?
Когда я должен реализовать этот алгоритм, лучше объяснил документ Укконен бумага и есть один новее с изображениями.
Да, в этих документах есть все для реализации алгоритма дерева суффиксов Укконена.
Следующее может быть полезно:
Ukkonen’s Suffix Tree Construction
Здесь мы имеем
1. начало, конец для обозначения метки ребра
2. суффиксная ссылка
3. массив для детей