Я просто хочу знать, когда дерево суффиксов превосходит расширенный массив суффиксов.
После прочтения Замена suf fi x с расширенными массивами suf fi x я больше не вижу причины использовать суффиксные деревья. Некоторые методы могут усложниться, но вы можете делать все с помощью массива суффикса, что вы можете сделать с деревом суффиксов, и вам нужна такая же сложность времени, но меньше памяти.
A опрос даже показал, что массивы суффиксов быстрее, потому что они более дружелюбны к кешу и не дают столько промахов в кеше, затем суффиксные деревья (так что кеш может лучше предсказать использование массива, а затем в рекурсивной древовидной структуре).
Итак, кто-нибудь знает причину выбора дерева суффиксов над массивом суффиксов?
изменить Хорошо, если вы знаете больше, скажите мне, до сих пор его:
В SO есть несколько интересных мыслей. Вы также можете найти больше технических материалов в режиме онлайн. Существует другая статья, которая может помочь вам в решении ваших проблем, утверждая, что это еще один эффективный способ реализации этих структур.
Я не эксперт в этой проблеме, но мне кажется, что массивы суффиксов могут быть несколько медленнее, хотя они более эффективны в пространстве. Тем не менее, мне не хватает практического опыта, чтобы быть более подробным о них обоих.
Другой пример, показывающий, что дерево суффиксов превосходит:
Вы можете легко построить массив суффикса, если у вас уже есть дерево суффиксов.
Но гораздо сложнее построить дерево суффиксов из массива суффиксов.