Jak czas działania algorytmu Ukkonen zależy od wielkości alfabetu?

Niepokoi mnie kwestia asymptotycznego czasu działania algorytmu Ukkonena , być może najpopularniejszego algorytmu do konstruowania drzewek sufiksów w czasie liniowym (?).

Oto cytat z książki „Algorytmy na strunach, drzewach i sekwencjach” Dana Gusfielda (sekcja 6.5.1):

„... wszystkie algorytmy Aho-Corasick, Weiner, Ukkonen i McCreight wymagają albo przestrzeni , albo ograniczenie czasowe O (m) należy zastąpić minimum O (m \ log m ) i O (m \ log | \ Sigma |) ".O ( m ) O ( m log m ) O ( m log | Σ |$\Theta(m|\Sigma|)$$O(m)$$O(m \log m)$$O(m \log|\Sigma|)$

[ $m$ to długość łańcucha, a $\Sigma$ to rozmiar alfabetu]

Nie rozumiem, dlaczego to prawda.

• Space: cóż, w przypadku, gdy reprezentujemy gałęzie poza węzłami za pomocą tablic o rozmiarze $\Theta(|\Sigma|)$ , wówczas faktycznie kończy się użycie miejsca $\Theta(m|\Sigma|)$ . Jednak, o ile widzę, możliwe jest również przechowywanie gałęzi za pomocą tabel skrótów (powiedzmy słowników w Pythonie). Wówczas mielibyśmy tylko wskaźniki $\Theta(m)$ zapisane we wszystkich tabelach skrótów (ponieważ w drzewie znajdują się krawędzie $\Theta(m)$ ), a jednocześnie nadal jesteśmy w stanie uzyskać dostęp do węzłów potomnych w czasie $O(1)$ , tak szybko jak przy użyciu tablic.
• Czas : jak wspomniano powyżej, użycie tabel skrótów pozwala nam uzyskać dostęp do wychodzących gałęzi dowolnego węzła w czasie . Ponieważ algorytm Ukkonena wymaga operacji (w tym dostępu do węzłów potomnych), całkowity czas działania wyniósłby wówczas również .O ( m ) O ( m $O(1)$$O(m)$$O(m)$

Byłbym bardzo wdzięczny za wszelkie wskazówki, dlaczego mylę się we wnioskach i dlaczego Gusfield ma rację co do zależności algorytmu Ukkonen od alfabetu.

Jak wspomina @jogojapan w komentarzach, hasing zasadniczo jest tylko zamortyzowanym , więc otrzymasz tylko zamortyzowane granice algorytmu. Myślę jednak, że nawet ich nie otrzymujesz: aby uzyskać zamortyzowany hasz , tabele skrótów muszą mieć rozmiar , więc nadal masz przestrzeń ( i ten sam wymóg czasu inicjalizacji).O ( 1 ) Ω ( Σ ) Θ ( m Σ $O(1)$$O(1)$$\Omega(\Sigma)$$\Theta(m\Sigma)$

Co więcej, w praktyce czas na ustawienie wszystkich tych tabel skrótów będzie znacznie dłuższy niż czas na ustawienie tablic.

Możesz lepiej sobie radzić przy użyciu globalnej tabeli skrótów, która jest indeksowana parami (węzeł, znak), ale przynajmniej pozostanie argument „tylko zamortyzowany”.