В чем преимущество обобщенного дерева суффиксов перед деревом префиксов?

Question

В чем преимущество обобщенного дерева суффиксов перед деревом префиксов?

Будет очень полезно, если кто-то объяснит причину в мельчайших подробностях и в каком сценарии один более выгоден, чем другой. Заранее спасибо!!

1

data-structures trie suffix-tree prefix-tree

Источник

user3203158 21 мар '14 в 05:36

1 ответ

Решение

Другие вопросы по тегам data-structures trie suffix-tree prefix-tree

user501557 21 мар '14 в 05:43 2014-03-21 05:43 · Accepted Answer · 2014-03-21 05:43

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

Надеюсь это поможет!