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 należy zastąpić minimum i ". $\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(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.

— Michaił Dubow
źródło

Nie sądzę, aby istniał jakikolwiek dowód na to, że niezależne od czasu / przestrzeni ograniczenie wielkości alfabetu jest niemożliwe. Uważam, że Gusfield wydał oświadczenie, ponieważ nie ma znanej metody całkowitego pozbycia się czasu. Aby je ustanowić, musisz bardziej szczegółowo omówić swoje funkcje haszujące. Prawdziwy najgorszy przypadek O (1) związany z wyszukiwaniem skrótu wymaga idealnego skrótu. Nie jest dla mnie jasne, jak to zrobić podczas algorytmu (ponieważ wpisy hash nie są w tym momencie statyczne).

— jogojapan,

(kont.) Możesz to zrobić po skompletowaniu drzewa, ale wtedy czas dla samego algorytmu pozostałby niezmieniony. (+1 dla pytania.)

— jogojapan,

Przydatny kontekst: wyjaśniono algorytm Ukkonena

— FrankW

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)$ $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”.

— FrankW
źródło