Массив суффикса nlogn

Я изучал создание массивов суффиксов, и я понимаю, что мы сначала сортируем все суффиксы в соответствии с первым символом, затем согласно первым двум символам, затем первые 4 символа и т.д., в то время как число символов, подлежащих рассмотрению, меньше, чем 2n.

Но я сомневаюсь, почему мы не выбираем первые 3 символа, затем 9... и так далее. Почему учитываются только 2 символа, поскольку строки являются частью одних и тех же строк, а не разных случайных строк?

Ответы

Ответ 1

Я не полностью проанализировал алгоритм построения массива суффикса, но все равно хотел бы поделиться своими мыслями.

По моему скромному мнению, ваш вопрос похож на следующие:

  • Почему компьютеры используют двоичное кодирование информации вместо тройного?

  • Почему двоичный поиск делит пополам диапазон вместо того, чтобы trisecting его?

  • Почему существуют два пола, а не три?

Причина в том, что номер 2 является особенным - это наименьшее число множественных чисел. Разница между 1 и 2 является качественной, тогда как разница между 2 и 3 (а также любое другое положительное целое число) является количественной и, следовательно, не столь резкой.

В результате двоичная формулировка многих алгоритмов и структур данных оказывается самой простой, хотя некоторые из них могут быть обобщены с различной степенью сложности для произвольной базы.

Ответ 2

Ответ предоставляется из сообщения . И как ответил @Leon, алгоритм работает, потому что использует дихотомический подход для решения проблемы сортировки. если вы правильно прочитали ответ, основная цель - разделить слово на небольшие фрагменты с 2 символами. Так что 4 символа могут быть легко отсортированы по расположению двух пар символов, 6 символов с 4-2 или 2-4 или 2-2-2 и так далее. Таким образом, слово из 3 букв в таблице не имеет смысла, так как может отображаться слово из 3 символов, имеет 2 символа + позицию в алфавите последнего символа.

Ответ 3

Я думаю, что вы рассматриваете только скорость 2^x по сравнению с 3^x, где вы, очевидно, предпочтете последнее. Но вы должны учитывать усилия, необходимые для каждого шага. Поскольку 3^x требуется примерно на 1,58 меньше шагов, чем 2^x, вам нужно будет вычислить один шаг для роста 3^x менее чем в 1,58 раза, что вам нужно для одного шага роста 2^x для выполнения лучше. Как правило, проблемы будут намного сложнее, если вам придется обрабатывать три элемента на каждом шаге, а не два. Кроме того, если вы могли бы расширить его до 3^x, вы могли бы также сделать это для большего n^x, а затем с большим n ваш алгоритм внезапно не экспоненциальный, а эффективно линейный.