Создание суффиксного массива nlogn
Я изучал создание массивов суффиксов, и я понимаю, что сначала мы сортируем все суффиксы по первому символу, затем по первым 2 символам, затем по первым 4 символам и т. Д., В то время как количество символов, которые нужно рассмотреть, меньше, чем 2n.
Но я сомневаюсь, почему бы нам не выбрать первые 3 символа, затем 9... и так далее. Почему учитываются только 2 символа, поскольку строки являются частью одинаковых строк, а не разных случайных строк?
3 ответа
Я не проанализировал алгоритм построения массива суффиксов полностью, но все же хотел бы поделиться своими мыслями.
По моему скромному мнению, ваш вопрос похож на следующие:
Почему компьютеры используют двоичное кодирование информации вместо троичного?
Почему бинарный поиск делит диапазон на части, а не разделяет его?
Почему существует два пола, а не три?
Причина в том, что число 2 особенное - это наименьшее число во множественном числе. Разница между 1 и 2 является качественной, тогда как разница между 2 и 3 (как и любое другое положительное целое число) является количественной и, следовательно, не такой существенной.
В результате двоичная формулировка многих алгоритмов и структур данных оказывается самой простой, хотя некоторые из них могут быть обобщены с различной степенью сложности для произвольной базы.
Я думаю, что вы рассматриваете только скорость 2^x против 3^x где вы, очевидно, предпочли бы последнее. Но вы должны учитывать усилие, необходимое для каждого шага. поскольку 3^x нужно примерно на 1,58 меньше шагов, чем 2^x Вы должны быть в состоянии рассчитать один шаг для 3^x рост менее чем в 1,58 раза, что вам нужно для одного шага в 2^x рост, чтобы работать лучше. Как правило, проблемы станут намного сложнее, когда вам придется обрабатывать три элемента на каждом шаге вместо двух. Также, если бы вы могли расширить его до 3^x Вы также можете сделать это для большего n^x а потом с большой n ваш алгоритм вдруг не экспоненциальный, а эффективно линейный.
Ответ дается с поста, который вы связали. И как @Leon ответил, алгоритм работает, потому что он использует дихотомический подход для решения проблемы сортировки. если вы правильно прочитали ответ, основная цель - разделить слово на маленькие 2-х символьные фрагменты. Таким образом, 4 символа могут быть легко отсортированы в зависимости от расположения 2 пар символов, 6 символов с 4-2 или 2-4 или 2-2-2 и так далее. Таким образом, иметь слово из 3 букв в таблице не имеет смысла, так как слово из 3 символов можно увидеть имеет 2 символа + позиция в алфавите последнего символа.