Этот вопрос основан на этом ответе jogojapan.
В этом ответе он отмечает, что для некоторых алгоритмов суффиксного дерева / массива суффиксов, просто имеющих уникальный символ стража $ достаточно, в то время как другие требуют $ либо для лексикографического сравнения наименьшего / наибольшего.
читая статью Replacing suffix trees with enhanced suffix arrays Абуэльоды и др., они делают выбор, что $ должен быть больше, чем любой другой символ , Благодаря этому выбору они могут создавать эффективные алгоритмы, которые могут имитировать обход дерева суффиксов как снизу вверх, так и сверху вниз, а также различные потенциальные приложения на основе этих схем обхода.
С другой стороны, алгоритмы для эффективного построения массива суффиксов или массива LCP с использованием принудительной сортировки сделайте противоположный выбор: $ должно быть лексикографически наименьшим. (см .: Linear Suffix Array Construction by Almost Pure Induced-Sorting от Nong et al. и Inducing the LCP-Array от Johannes Fischer).
Для меня не сразу очевидно, необходимы ли эти выборы для того, какие свойства $ необходимы или были только что сделаны для удобство. Мне было бы крайне неприятно, если бы самые быстрые алгоритмы построения SA / LCP-Array не могли использоваться со многими эффективными алгоритмами, которые используют суффиксные массивы.
- Строго ли требуют методы построения индуцированной сортировки
$ быть лексикографически наименьшим или они одинаково хорошо работают (или с небольшими изменениями), если я выбрал $ как лексикографически наибольший? - Если ответ на 1 - нет, представляют ли алгоритмы Abouelhoda для эмуляции Применяется ли обход дерева сверху вниз / снизу вверх, если
$ является лексикографически наименьшим, и если нет, то могут ли они быть слегка изменены, чтобы их можно было использовать? - Если нет 1 и 2, существуют ли совершенно разные алгоритмы, которые можно использовать для выполнения аналогичных задач, когда я делаю выбор
$ является лексикографически наименьшим? Кто они, если они существуют?