Я просто хочу знать, когда дерево суффиксов превосходит расширенный массив суффиксов.
После прочтения Замена suf fi x с расширенными массивами suf fi x я больше не вижу причины использовать суффиксные деревья. Некоторые методы могут усложниться, но вы можете делать все с помощью массива суффикса, что вы можете сделать с деревом суффиксов, и вам нужна такая же сложность времени, но меньше памяти.
A опрос даже показал, что массивы суффиксов быстрее, потому что они более дружелюбны к кешу и не дают столько промахов в кеше, затем суффиксные деревья (так что кеш может лучше предсказать использование массива, а затем в рекурсивной древовидной структуре).
Итак, кто-нибудь знает причину выбора дерева суффиксов над массивом суффиксов?
изменить Хорошо, если вы знаете больше, скажите мне, до сих пор его:
- Суффиксары не позволяют строить on-line
- Некоторые алгоритмы сопоставления шаблонов работают быстрее на Suffixtrees
- (добавлено) из-за он-лайн построения, вы можете сохранить его на hd a и увеличить существующий суффикс. Если вы используете SSD, он также должен быть тихим.