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

19

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

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

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

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

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

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

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

Михаил Дубов
источник
3
Я не думаю, что есть какие-либо доказательства того, что независимая от времени / пространства независимая граница размера алфавита невозможна. Я полагаю, что Гасфилд сделал заявление, потому что нет никакого известного способа полностью избавиться от времени. Чтобы создать его, вам нужно более подробно остановиться на ваших хэш-функциях. Истинный O (1) наихудший случай для поиска хеша требует идеального хеша. Мне не понятно, как это сделать во время алгоритма (потому что хеш-записи не являются статичными в этот момент).
jogojapan
(продолжение) Вы можете сделать это, как только дерево будет завершено, но тогда временные рамки для самого алгоритма все равно останутся неизменными. (+1 к вопросу, хотя.)
jogojapan
1
Полезный контекст: объяснил алгоритм Укконена
FrankW

Ответы:

2

О(1)О(1)Ω(Σ)Θ(мΣ)

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

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

FrankW
источник