Koncepcyjnie proste konstrukcje drzewne z sufiksem czasu liniowego

W 1973 r. Weiner przedstawił pierwszą konstrukcję drzewek z przyrostkami. Algorytm został uproszczony w 1976 r. Przez McCreighta, aw 1995 r. Przez Ukkonen. Niemniej jednak uważam, że algorytm Ukkonen jest stosunkowo zaangażowany koncepcyjnie.

Czy istnieją uproszczenia algorytmu Ukkonen od 1995 roku?

Nie jestem pewien, czy były jakieś nowe wyniki bezpośrednio upraszczające budowę drzewek sufiksów. Jednak co najmniej jeden wynik dał bardzo prosty algorytm do konstruowania tablic sufiksów w czasie liniowym.

Zauważ, że między tymi dwiema strukturami danych istnieje więcej niż koncepcyjna równoważność, ponieważ możesz użyć tablicy sufiksów (z czasem do zapytania o najdłuższy wspólny prefiks), aby zbudować równoważne drzewo sufiksów. To powinno być stosunkowo proste ćwiczenie, ale w razie potrzeby mogę podać więcej szczegółów.$\cal{O}(1)$

Ponadto ze względów praktycznych jeszcze łatwiej jest budować tablice sufiksów w czasie , ale myślę, że przechodzę tutaj nieco poza tematem.$\cal{O}(n \lg n)$

Oprócz tego, o czym wspomniano ( Kärkkäinen i Sanders, 2003 ), myślę, że doceniłbyś „nowszą” wersję autorstwa Kärkkäinen, Sanders i Burkhard, 2006 . Algorytm zasadniczo podąża za strukturą algorytmu Faracha. Jest to prawdopodobnie łatwiejsze koncepcyjnie, ale prawdziwą zaletą jest to, że zapewniają one czytelnikowi implementację algorytmu. To tylko około 50 linii C ++, więc w rzeczywistości nie ma żadnych ukrytych szczegółów.