Как время выполнения алгоритма Укконена зависит от размера алфавита?

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

Вот цитата из книги «Алгоритмы на строках, деревьях и последовательностях» Дэна Гасфилда (раздел 6.5.1):

»... в Ахо-Corasick, Weiner, Ukkonen алгоритмы и McCreight все либо требуют пространство, или$\Theta(m|\Sigma|)$ временные рамки следует заменить минимум O ( м логов м ) и O ( m log | Σ | ) ".$O(m)$$O(m \log m)$$O(m \log|\Sigma|)$

[ - длина строки и Σ - размер алфавита]$m$$\Sigma$

Я не понимаю, почему это правда.

• Пространство: хорошо, если мы представляем ветви из узлов, используя массивы размера , то, действительно, мы получим использование пространства Θ ( m | Σ | ) . Однако, насколько я вижу, ветки также можно хранить с использованием хеш-таблиц (например, словарей в Python). Тогда у нас было бы только Θ ( m ) указателей, сохраненных во всех хеш-таблицах (так как в дереве есть Θ ( m ) ребер), при этом мы могли бы получить доступ к дочерним узлам в O ( 1 $\Theta(|\Sigma|)$$\Theta(m|\Sigma|)$$\Theta(m)$$\Theta(m)$$O(1)$ время, так же быстро, как при использовании массивов.
• Время : как упоминалось выше, использование хеш-таблиц позволяет нам получить доступ к исходящим ветвям любого узла за время. Поскольку алгоритм Укконена требует O ( m ) операций (включая доступ к дочерним узлам), общее время работы также будет O ( m ) .$O(1)$$O(m)$$O(m)$

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

$O(1)$$O(1)$$\Omega(\Sigma)$$\Theta(m\Sigma)$

Более того, на практике время для установки всех этих хеш-таблиц будет намного больше, чем время для настройки массивов.

Вы могли бы лучше использовать глобальную хеш-таблицу, которая индексируется парами (узел, символ), но, по крайней мере, аргумент «только амортизированный» останется.