Я просто хочу знать, когда дерево суффиксов превосходит расширенный массив суффиксов.
После прочтения Замена суффиксных деревьев расширенными суффиксными массивами я не вижу причин использовать суффиксные деревья больше. Некоторые методы могут быть сложными, но вы можете делать все с массивом суффиксов, что вы можете делать с деревом суффиксов, и вам нужна такая же временная сложность, но меньше памяти.
опрос даже показал, что суффиксные массивы быстрее, потому что они более удобны для кеша и не производят столько промахов в кеше, чем суффиксные деревья (поэтому кеш может намного лучше предсказывать использование массива, чем в рекурсивной древовидной структуре).
Итак, кто-нибудь знает причину выбора дерева суффиксов вместо массива суффиксов?
редактировать Хорошо, если вы знаете больше, расскажите мне, пока это:
- Массивы суффиксов не допускают онлайн-конструкции
- Некоторые алгоритмы сопоставления с образцом работают быстрее на деревьях суффиксов.
- (добавлено) из-за онлайновой конструкции вы можете сохранить его на HD и увеличить существующее дерево суффиксов. Если вы используете SSD, он также должен быть тихим и быстрым.
