Algorytm drzewa sufiksów Ukkonena w prostym języku angielskim

W tym momencie czuję się trochę gruby. Spędziłem dni próbując całkowicie owinąć głowę nad konstrukcją drzewa sufiksów, ale ponieważ nie mam matematycznego zaplecza, wiele wyjaśnień wymyka mi się, gdy zaczynają nadmiernie używać symboliki matematycznej. Najbliższe dobre wyjaśnienie, które znalazłem, to szybkie wyszukiwanie ciągów za pomocą drzewek sufiksów , ale przegląda różne punkty, a niektóre aspekty algorytmu pozostają niejasne.

Jestem pewien, że wyjaśnienie tego algorytmu krok po kroku na temat przepełnienia stosu byłoby nieocenione dla wielu innych osób.

Dla odniesienia, oto artykuł Ukkonena na temat algorytmu: http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf

Moje dotychczasowe zrozumienie:

• Muszę iterować przez każdy prefiks P danego ciągu T
• Muszę iterować przez każdy przyrostek S w prefiksie P i dodać go do drzewa
• Aby dodać przyrostek S do drzewa, muszę iterować każdą postać w S, przy czym iteracje polegają na chodzeniu po istniejącej gałęzi, która zaczyna się od tego samego zestawu znaków C w S i potencjalnie dzieleniu krawędzi na potomne węzły, gdy I osiągnij inną postać w sufiksie LUB, jeśli nie było żadnej pasującej krawędzi do zejścia. Jeśli nie znaleziono pasującej krawędzi, która mogłaby zejść dla C, tworzona jest nowa krawędź skrzydła dla C.

Podstawowym algorytmem wydaje się być O (n ² ), jak wskazano w większości wyjaśnień, ponieważ musimy przejść przez wszystkie przedrostki, a następnie musimy przejść przez każdy z przyrostków dla każdego przedrostka. Algorytm Ukkonena jest najwyraźniej unikalny ze względu na technikę stosowaną przez przyrostek, chociaż myślę, że właśnie z tego powodu mam problem ze zrozumieniem.

Mam również problemy ze zrozumieniem:

• kiedy i jak „aktywny punkt” jest przypisywany, wykorzystywany i zmieniany
• co się dzieje z aspektem kanonizacji algorytmu
• Dlaczego implementacje, które widziałem, muszą „naprawić” zmienne graniczne, których używają

Oto gotowy kod źródłowy C # . Działa nie tylko poprawnie, ale obsługuje automatyczną kanonizację i renderuje ładniejszy wygląd tekstu wyjściowego. Kod źródłowy i przykładowe dane wyjściowe znajdują się w:

https://gist.github.com/2373868

Aktualizacja 2017-11-04

Po wielu latach znalazłem nowe zastosowanie do drzewek sufiksów i zaimplementowałem algorytm w JavaScript . Gist jest poniżej. Powinien być wolny od błędów. Zrzuć go do pliku js npm install chalkz tej samej lokalizacji, a następnie uruchom z node.js, aby zobaczyć kolorowe wyjście. W tej samej Gist istnieje wersja uproszczona, bez żadnego kodu debugującego.

https://gist.github.com/axefrog/c347bf0f5e0723cbd09b1aaed6ec6fc6

Poniżej znajduje się próba opisania algorytmu Ukkonen poprzez pokazanie, co robi, gdy łańcuch jest prosty (tj. Nie zawiera żadnych powtarzających się znaków), a następnie rozszerzenie go na pełny algorytm.

Najpierw kilka wstępnych stwierdzeń.

1. To, co budujemy, to w zasadzie trie wyszukiwania. Więc jest węzeł główny, krawędzie wychodzą z niego, prowadząc do nowych węzłów, i dalsze krawędzie wychodzą z nich, i tak dalej

2. Ale : W przeciwieństwie do trie wyszukiwania, etykiety krawędzi nie są pojedynczymi znakami. Zamiast tego każda krawędź jest oznaczona za pomocą pary liczb całkowitych [from,to]. Są to wskaźniki do tekstu. W tym sensie każda krawędź ma etykietę o dowolnej długości, ale zajmuje tylko spację O (1) (dwa wskaźniki).

Podstawowa zasada

Chciałbym najpierw zademonstrować, jak utworzyć drzewo sufiksów szczególnie prostego łańcucha, łańcucha bez powtarzających się znaków:

abc

Algorytm działa w krokach, od lewej do prawej . Jest jeden krok dla każdego znaku ciągu . Każdy krok może obejmować więcej niż jedną pojedynczą operację, ale zobaczymy (patrz końcowe obserwacje na końcu), że całkowita liczba operacji wynosi O (n).

Zaczynamy od lewej i najpierw wstawiamy tylko pojedynczy znak a, tworząc krawędź od węzła głównego (po lewej) do liścia i oznaczając go jako [0,#], co oznacza, że ​​krawędź reprezentuje podłańcuch zaczynający się w pozycji 0 i kończący się na obecnym końcu . Używam tego symbolu, #aby oznaczać bieżący koniec , który jest na pozycji 1 (zaraz po a).

Mamy więc wstępne drzewo, które wygląda następująco:

A to oznacza:

Teraz przechodzimy do pozycji 2 (zaraz po b). Naszym celem na każdym kroku jest wstawienie wszystkich sufiksów do aktualnej pozycji . Robimy to przez

• rozszerzenie istniejącego a-edge doab
• wstawianie jednej nowej krawędzi dla b

W naszej reprezentacji wygląda to tak

A to oznacza:

Obserwujemy dwie rzeczy:

• Odwzorowanie na krawędzi abjest samo jak dawniej w początkowym drzewa: [0,#]. Jego znaczenie zmieniło się automatycznie, ponieważ zaktualizowaliśmy bieżącą pozycję #z 1 na 2.
• Każda krawędź zajmuje miejsce O (1), ponieważ składa się tylko z dwóch wskaźników w tekście, niezależnie od liczby znaków, które reprezentuje.

Następnie zwiększamy pozycję ponownie i aktualizujemy drzewo, cdodając a do każdej istniejącej krawędzi i wstawiając jedną nową krawędź dla nowego sufiksu c.

W naszej reprezentacji wygląda to tak

A to oznacza:

Obserwujemy:

• Drzewo to poprawne drzewo przyrostków do bieżącej pozycji po każdym kroku
• W tekście jest tyle kroków, ile znaków
• Ilość pracy na każdym kroku wynosi O (1), ponieważ wszystkie istniejące krawędzie są aktualizowane automatycznie poprzez inkrementację #, a wstawienie jednej nowej krawędzi dla końcowego znaku można wykonać w czasie O (1). Dlatego dla ciągu o długości n wymagany jest tylko czas O (n).

Pierwsze rozszerzenie: proste powtórzenia

Oczywiście działa to tak ładnie tylko dlatego, że nasz ciąg nie zawiera żadnych powtórzeń. Teraz patrzymy na bardziej realistyczny ciąg:

abcabxabcd

Zaczyna się abctak, jak w poprzednim przykładzie, następnie abjest powtarzane i następuje x, a następnie abcjest powtarzane, a następnie d.

Kroki od 1 do 3: Po pierwszych 3 krokach mamy drzewo z poprzedniego przykładu:

Krok 4: Przechodzimy #do pozycji 4. To domyślnie aktualizuje wszystkie istniejące krawędzie do tego:

i musimy wstawić ostatni przyrostek bieżącego kroku a, w katalogu głównym.

Zanim to zrobimy, wprowadzamy jeszcze dwie zmienne (oprócz #), które oczywiście były tam przez cały czas, ale jak dotąd ich nie używaliśmy:

• Punkt aktywny , który jest potrójny (active_node,active_edge,active_length)
• The remainder, która jest liczbą całkowitą wskazującą, ile nowych sufiksów należy wstawić

Dokładne znaczenie tych dwóch wkrótce stanie się jasne, ale na razie powiedzmy:

• W prostym abcprzykładzie punktem aktywnym był zawsze (root,'\0x',0), tj. active_nodeWęzeł główny, active_edgebył określony jako znak zerowy '\0x'i active_lengthwynosił zero. Efektem tego było to, że jedna nowa krawędź, którą wstawiliśmy na każdym kroku, została wstawiona w węźle głównym jako świeżo utworzona krawędź. Wkrótce przekonamy się, dlaczego potrójny jest potrzebny do przedstawienia tych informacji.
• remainderBył zawsze ustawiony na 1 na początku każdego kroku. Oznaczało to, że liczba przyrostków, które musieliśmy aktywnie wstawiać na końcu każdego kroku, wynosiła 1 (zawsze tylko ostatni znak).

Teraz to się zmieni. Kiedy wstawić bieżącą ostateczną postać au nasady, zauważamy, że nie ma już wychodzących krawędzi zaczynając a, a konkretnie: abca. Oto, co robimy w takim przypadku:

• My nie wstawić nową przewagę [4,#]w węźle głównym. Zamiast tego po prostu zauważamy, że przyrostek ajest już w naszym drzewie. Kończy się na środku dłuższej krawędzi, ale nie przeszkadza nam to. Po prostu zostawiamy rzeczy takimi, jakie są.
• Możemy ustawić aktywnego punktu do (root,'a',1). Oznacza to, że punkt aktywny znajduje się teraz gdzieś pośrodku krawędzi wychodzącej węzła głównego, która zaczyna się aod pozycji 1 na tej krawędzi. Zauważamy, że krawędź jest określona po prostu przez jej pierwszy znak a. To wystarczy, ponieważ może istnieć tylko jedna krawędź zaczynająca się od dowolnego określonego znaku (potwierdź, że jest to prawda po przeczytaniu całego opisu).
• Zwiększamy również remainder, więc na początku następnego kroku będzie to 2.

Obserwacja: kiedy okaże się, że ostatni sufiks, który musimy wstawić , już istnieje w drzewie , samo drzewo w ogóle się nie zmienia (aktualizujemy tylko punkt aktywny i remainder). Drzewo nie jest zatem dokładną reprezentacją drzewa sufiksów aż do bieżącej pozycji , ale zawiera wszystkie sufiksy (ponieważ końcowy sufiks ajest zawarty niejawnie ). Dlatego oprócz aktualizacji zmiennych (wszystkie o stałej długości, więc jest to O (1)), w tym kroku nie wykonano żadnej pracy .

Krok 5: Aktualizujemy bieżącą pozycję #do 5. To automatycznie aktualizuje drzewo do tego:

A ponieważ remainderjest to 2 , musimy wstawić dwa końcowe sufiksy bieżącej pozycji: abi b. Wynika to głównie z tego, że:

• aPrzyrostek z poprzedniego etapu nigdy nie został prawidłowo włożony. Tak to pozostało , a ponieważ postępują krok, obecnie uprawiana od acelu ab.
• I musimy wstawić nową końcową krawędź b.

W praktyce oznacza to, że przechodzimy do aktywnego punktu (który wskazuje za tym, aco jest teraz abcabkrawędzią) i wstawiamy aktualny końcowy znak b. Ale: Ponownie okazuje się, że bjest już obecny na tej samej krawędzi.

Zatem znowu nie zmieniamy drzewa. Po prostu:

• Zaktualizuj punkt aktywny do (root,'a',2)(ten sam węzeł i krawędź jak poprzednio, ale teraz wskazujemy za b)
• Zwiększ wartość remainderdo 3, ponieważ nadal nie wstawiliśmy poprawnie końcowej krawędzi z poprzedniego kroku i nie wstawiamy również bieżącej krawędzi końcowej.

Żeby było jasne: musieliśmy wstawić abi bw bieżącym kroku, ale ponieważ abjuż został znaleziony, zaktualizowaliśmy punkt aktywny i nawet nie próbowaliśmy wstawić b. Dlaczego? Ponieważ jeśli abjest w drzewie, każdy jego przyrostek (w tym b) musi również znajdować się w drzewie. Być może tylko pośrednio , ale musi tam być, ponieważ dotychczas zbudowaliśmy drzewo.

Przechodzimy do kroku 6 , zwiększając #. Drzewo jest automatycznie aktualizowane do:

Ponieważ remainderjest 3 , musimy wstawić abx, bxi x. Aktywny punkt mówi nam, gdzie się abkończy, więc musimy tylko wskoczyć tam i wstawić x. Rzeczywiście, xjeszcze go nie ma, więc podzieliliśmy abcabxkrawędź i wstawiliśmy wewnętrzny węzeł:

Reprezentacje krawędzi są nadal wskaźnikami w tekście, więc dzielenie i wstawianie węzła wewnętrznego można wykonać w czasie O (1).

Mamy więc do czynienia z abxi ubytek remainderna 2. Teraz musimy wstawić następny pozostały sufiks, bx. Ale zanim to zrobimy, musimy zaktualizować punkt aktywny. Reguła tego, po podzieleniu i wstawieniu krawędzi, będzie nazywała się Regułą 1 poniżej i ma zastosowanie zawsze, gdy active_nodejest zrootowana (zasady 3 poznamy w dalszych przypadkach poniżej). Oto reguła 1:

Po wstawieniu z katalogu głównego

• active_node pozostaje rootem
• active_edge jest ustawiony na pierwszy znak nowego sufiksu, który musimy wstawić, tj b
• active_length zmniejsza się o 1

Stąd nowy potrójny punkt aktywny (root,'b',1)wskazuje, że następna wstawka musi być wykonana na bcabxkrawędzi, za 1 znakiem, tj b. Za . Możemy zidentyfikować punkt wstawienia w czasie O (1) i sprawdzić, czy xjest już obecny, czy nie. Gdyby był obecny, zakończylibyśmy obecny krok i pozostawili wszystko tak, jak jest. Ale x nie jest obecny, więc wstawiamy go, dzieląc krawędź:

Ponownie zajęło to czas O (1) i aktualizujemy remainderdo 1, a punkt aktywny do stanu (root,'x',0)reguły 1.

Ale jest jeszcze jedna rzecz, którą musimy zrobić. Nazwiemy to regułą 2:

Jeśli podzielimy krawędź i wstawimy nowy węzeł, a jeśli nie jest to pierwszy węzeł utworzony podczas bieżącego kroku, łączymy poprzednio wstawiony węzeł i nowy węzeł za pomocą specjalnego wskaźnika, łącza przyrostka . Później zobaczymy, dlaczego jest to przydatne. Oto, co otrzymujemy, link do sufiksu jest reprezentowany jako kropkowana krawędź:

Nadal trzeba wstawić ostateczny przyrostek aktualnego kroku x. Ponieważ active_lengthskładnik aktywnego węzła spadł do 0, ostateczna wstawka jest wykonywana bezpośrednio w katalogu głównym. Ponieważ w węźle głównym nie ma krawędzi wychodzącej x, zaczynamy od nowej, wstawiamy nową krawędź:

Jak widać, w bieżącym kroku wykonano wszystkie pozostałe wkładki.

Przechodzimy do kroku 7 , ustawiając wartość #= 7, która ajak zawsze automatycznie dołącza następny znak do wszystkich krawędzi liści. Następnie próbujemy wstawić nowy końcowy znak do aktywnego punktu (root) i stwierdzimy, że już tam jest. Tak więc kończymy bieżący krok bez wstawiania czegokolwiek i aktualizujemy punkt aktywny do (root,'a',1).

W punkcie 8 , #= 8, możemy dołączyć b, i jak dotąd, to tylko oznacza, że aktualizować aktywny wskaż (root,'a',2)i przyrost remaindernie robiąc nic innego, bo bjest już obecny. Zauważamy jednak (w czasie O (1)), że punkt aktywny znajduje się teraz na końcu krawędzi. Odzwierciedlamy to, ustawiając ponownie na (node1,'\0x',0). Tutaj używam node1w odniesieniu do wewnętrznego węzła, na którym abkończy się krawędź.

Następnie w kroku #= 9 musimy wstawić „c”, co pomoże nam zrozumieć ostatnią sztuczkę:

Drugie rozszerzenie: Korzystanie z łączy sufiksów

Jak zawsze #aktualizacja cautomatycznie dołącza się do krawędzi liścia i przechodzimy do aktywnego punktu, aby sprawdzić, czy możemy wstawić „c”. Okazuje się, że „c” istnieje już na tej krawędzi, więc ustawiamy punkt aktywny na (node1,'c',1), zwiększamy remainderi nic więcej nie robimy.

Teraz w etapie #= 10 , remainderjest 4, a więc najpierw umieścić abcd(która pozostaje z 3 stopni temu), umieszczając dw aktywnym miejscu.

Próba wstawienia dw punkcie aktywnym powoduje podział krawędzi w czasie O (1):

Symbol active_node, od którego rozpoczął się podział, jest zaznaczony na czerwono powyżej. Oto ostatnia zasada, reguła 3:

Po podzieleniu krawędzi od active_nodewęzła, który nie jest węzłem głównym, podążamy za łączem sufiksu wychodzącym z tego węzła, jeśli taki istnieje, i resetujemy active_nodewęzeł, na który wskazuje. Jeśli nie ma linku do sufiksu, ustawiamy active_nodekatalog główny. active_edge i active_lengthpozostają niezmienione.

Aktywny punkt jest teraz (node2,'c',1)i node2jest zaznaczony na czerwono poniżej:

Ponieważ wstawienie abcdjest zakończone, możemy zmniejszyć remainderdo 3 i rozważyć następny pozostały sufiks bieżącego kroku bcd. Reguła 3 ustawiła punkt aktywny tylko na właściwy węzeł i krawędź, więc wstawianie bcdmożna wykonać, po prostu wstawiając jego końcowy znak dw punkcie aktywnym.

Spowoduje to kolejny podział krawędzi i z powodu reguły 2 musimy utworzyć link do sufiksu z wcześniej wstawionego węzła do nowego:

Obserwujemy: Łącza sufiksów pozwalają nam zresetować punkt aktywny, abyśmy mogli wykonać następny pozostały wkład przy wysiłku O (1). Spójrz na powyższy wykres, aby potwierdzić, że rzeczywiście węzeł w etykiecie abjest połączony z węzłem w b(jego sufiksem), a węzeł w abcjest połączony z bc.

Aktualny krok jeszcze się nie zakończył. remainderjest teraz 2 i musimy postępować zgodnie z regułą 3, aby ponownie zresetować punkt aktywny. Ponieważ bieżący active_node(czerwony powyżej) nie ma linku do sufiksu, resetujemy do rootowania. Punkt aktywny jest teraz (root,'c',1).

Stąd obok wkładki występuje na jednej krawędzi wychodzącej z węzła głównego, którego etykieta rozpoczyna się c: cabxabcd, za pierwszego znaku, czyli z tyłu c. Powoduje to kolejny podział:

A ponieważ wiąże się to z utworzeniem nowego węzła wewnętrznego, postępujemy zgodnie z regułą 2 i ustawiamy nowy link do sufiksu z wcześniej utworzonego węzła wewnętrznego:

(Używam Graphviz Dot do tych małych wykresów. Nowy link do sufiksu spowodował, że kropka ponownie ułożyła istniejące krawędzie, więc dokładnie sprawdź, czy jedyną rzeczą, która została wstawiona powyżej, jest nowy link do sufiksu.)

Dzięki temu remaindermożna ustawić wartość 1, a ponieważ active_nodejest to root, do aktualizacji punktu aktywnego używamy reguły 1 (root,'d',0). Oznacza to, że ostatnią wstawką w bieżącym kroku jest wstawienie jednego d w katalogu głównym:

To był ostatni krok i jesteśmy skończeni. Istnieje jednak kilka uwag końcowych :

• Na każdym kroku poruszamy #się o 1 pozycję do przodu. To automatycznie aktualizuje wszystkie węzły liści w czasie O (1).

• Nie dotyczy to jednak: a) żadnych sufiksów pozostałych po poprzednich krokach, oraz b) z jednym ostatnim znakiem bieżącego kroku.

• remaindermówi nam, ile dodatkowych wkładek musimy wykonać. Te wstawki odpowiadają jeden-do-jednego końcowym sufiksom łańcucha, który kończy się w bieżącej pozycji #. Rozważamy jeden po drugim i wykonujemy wkładkę. Ważne: Każda wstawka jest wykonywana w czasie O (1), ponieważ punkt aktywny mówi nam dokładnie, gdzie iść, i musimy dodać tylko jeden znak w punkcie aktywnym. Dlaczego? Ponieważ pozostałe znaki są zawarte niejawnie (w przeciwnym razie punkt aktywny nie byłby tam, gdzie jest).

• Po każdej takiej wstawce zmniejszamy remainderi podążamy za przyrostkiem, jeśli taki istnieje. Jeśli nie, przejdziemy do rootowania (reguła 3). Jeśli już jesteśmy w katalogu głównym, modyfikujemy punkt aktywny za pomocą reguły 1. W każdym razie zajmuje to tylko czas O (1).

• Jeśli podczas jednej z tych wstawek okaże się, że znak, który chcemy wstawić, już tam jest, nic nie robimy i kończymy bieżący krok, nawet jeśli remainder> 0. Powodem jest to, że wszelkie wstawki będą sufiksami tego, który właśnie próbowaliśmy zrobić. Dlatego wszystkie są ukryte w bieżącym drzewie. Fakt, że remainder> 0 gwarantuje, że zajmiemy się pozostałymi przyrostkami później.

• Co jeśli na końcu algorytmu remainder> 0? Dzieje się tak za każdym razem, gdy koniec tekstu jest podciągiem, który pojawił się gdzieś wcześniej. W takim przypadku musimy dodać jeden dodatkowy znak na końcu ciągu, który nie występował wcześniej. W literaturze zwykle $jest to symbol dolara . Dlaczego to ma znaczenie? -> Jeśli później użyjemy wypełnionego drzewa sufiksów do wyszukiwania sufiksów, musimy zaakceptować dopasowania tylko wtedy, gdy kończą się liściem . W przeciwnym razie otrzymalibyśmy wiele fałszywych dopasowań, ponieważ w drzewie pośrednio zawartych jest wiele łańcuchów , które nie są rzeczywistymi przyrostkami łańcucha głównego. Zmuszanieremainderbycie 0 na końcu jest zasadniczo sposobem na zapewnienie, że wszystkie przyrostki kończą się na węźle liścia. Jeśli jednak chcemy użyć drzewa do wyszukiwania ogólnych podciągów , a nie tylko sufiksów łańcucha głównego, ten ostatni krok rzeczywiście nie jest wymagany, jak sugeruje komentarz OP poniżej.

• Jaka jest złożoność całego algorytmu? Jeśli tekst ma długość n znaków, oczywiście jest n kroków (lub n + 1, jeśli dodamy znak dolara). Na każdym etapie albo nic nie robimy (oprócz aktualizacji zmiennych), albo wykonujemy remainderwstawki, z których każdy zajmuje czas O (1). Ponieważ remainderwskazuje, ile razy nic nie zrobiliśmy w poprzednich krokach i jest zmniejszana dla każdej wstawionej teraz wkładki, łączna liczba wykonywanych czynności wynosi dokładnie n (lub n + 1). Zatem całkowita złożoność wynosi O (n).

• Jest jednak jedna drobna rzecz, której nie wyjaśniłem poprawnie: może się zdarzyć, że podążymy za sufiksem, zaktualizujemy punkt aktywny, a następnie okaże się, że jego active_lengthkomponent nie działa dobrze z nowym active_node. Rozważmy na przykład taką sytuację:

(Linie przerywane wskazują resztę drzewa. Linia kropkowana jest łącznikiem z przyrostkiem.)

Teraz niech będzie aktywny punkt (red,'d',3), więc zwraca się do miejsca tył fna defgkrawędzi. Załóżmy teraz, że dokonaliśmy niezbędnych aktualizacji, a następnie podążamy za sufiksem, aby zaktualizować punkt aktywny zgodnie z regułą 3. Nowy punkt aktywny to (green,'d',3). Jednak dkrawędź wychodząca z zielonego węzła jest de, więc ma tylko 2 znaki. Aby znaleźć właściwy punkt aktywny, oczywiście musimy podążać tą krawędzią do niebieskiego węzła i zresetować do (blue,'f',1).

W szczególnie złym przypadku wartość active_lengthmoże być tak duża remainder, jak n może być tak duża jak n. I może się zdarzyć, że aby znaleźć właściwy punkt aktywny, potrzebujemy nie tylko przeskoczyć przez jeden wewnętrzny węzeł, ale być może wielu, w najgorszym przypadku do n. Czy to oznacza, że ​​algorytm ma ukrytą złożoność O (n ² ), ponieważ na każdym etapie remainderjest generalnie O (n), a korekty po aktywacji węzła po połączeniu z sufiksem również mogą być O (n)?

Nie. Powodem jest to, że jeśli rzeczywiście musimy dostosować punkt aktywny (np. Z zielonego na niebieski, jak powyżej), to przenosi nas do nowego węzła, który ma własne łącze do sufiksu i active_lengthzostanie zmniejszony. Gdy podążamy za łańcuchem łączy sufiksowych, robimy pozostałe wstawki, active_lengthmożemy tylko zmniejszyć, a liczba korekt punktów aktywnych, które możemy wprowadzić po drodze, nie może być większa niż active_lengthw danym momencie. Ponieważ active_lengthnigdy nie może być większy niż remainderi remainder wynosi O (n) nie tylko na każdym etapie, ale całkowita suma przyrostów kiedykolwiek dokonanych remainderw trakcie całego procesu wynosi również O (n), liczba korekt punktów aktywnych wynosi również ograniczone przez O (n).

Próbowałem zaimplementować Drzewo sufiksów zgodnie z podejściem podanym w odpowiedzi jogojapan, ale w niektórych przypadkach nie działało z powodu sformułowania użytego w regułach. Ponadto wspomniałem, że nikt nie zdołał zaimplementować absolutnie poprawnego drzewa sufiksów przy użyciu tego podejścia. Poniżej napiszę „przegląd” odpowiedzi jogojapana z pewnymi modyfikacjami zasad. Opiszę również przypadek, gdy zapomnimy utworzyć ważne linki do sufiksów.

Zastosowano dodatkowe zmienne

1. punkt aktywny - potrójny (active_node; active_edge; active_length), wskazujący skąd musimy zacząć wstawiać nowy przyrostek.
2. reszta - pokazuje liczbę przyrostków, które musimy jawnie dodać . Na przykład, jeśli nasze słowo to „abcaabca”, a reszta = 3, oznacza to, że musimy przetworzyć 3 ostatnie sufiksy: bca , ca i a .

Użyjmy pojęcia węzła wewnętrznego - wszystkie węzły, z wyjątkiem korzenia i liści, są węzłami wewnętrznymi .

Obserwacja 1

Kiedy okaże się, że ostatni sufiks, który musimy wstawić, już istnieje w drzewie, samo drzewo w ogóle się nie zmienia (aktualizujemy tylko active pointi remainder).

Obserwacja 2

Jeśli w którymś momencie active_lengthjest większa lub równa długości aktualnego zbocza ( edge_length), przesuwamy nasz active pointdół, aż edge_lengthbędzie ściśle większy niż active_length.

Teraz ponownie zdefiniujmy zasady:

Zasada nr 1

Jeśli po wstawieniu z aktywnego węzła = root , aktywna długość jest większa niż 0, wówczas:

1. aktywny węzeł nie jest zmieniany
2. długość aktywna jest zmniejszana
3. aktywna krawędź jest przesunięta w prawo (do pierwszego znaku następnego sufiksu musimy wstawić)

Reguła 2

Jeśli utworzymy nowy węzeł wewnętrzny LUB zrobimy moduł wstawiający z węzła wewnętrznego , a nie jest to pierwszy TAKI węzeł wewnętrzny na obecnym etapie, wówczas łączymy poprzedni TAKI węzeł z TENEM przez łącze sufiksu .

Ta definicja Rule 2różni się od jogojapan, ponieważ tutaj bierzemy pod uwagę nie tylko nowo utworzone węzły wewnętrzne, ale także węzły wewnętrzne, z których wykonujemy wstawianie.

Zasada 3

Po wstawieniu z aktywnego węzła, który nie jest węzłem głównym , musimy podążać za przyrostkiem i ustawić aktywny węzeł na węzeł, na który wskazuje. Jeśli nie ma łącza do sufiksu, ustaw aktywny węzeł na węzeł główny . Tak czy inaczej, aktywna krawędź i aktywna długość pozostają niezmienione.

W tej definicji Rule 3rozważamy również wstawki węzłów liści (nie tylko węzłów dzielonych).

I wreszcie obserwacja 3:

Kiedy symbol, który chcemy dodać do drzewa, jest już na krawędzi, my, zgodnie z Observation 1aktualizacją, active pointi remainderpozostawiając drzewo bez zmian. ALE jeśli istnieje wewnętrzny węzeł oznaczony jako wymagający łącza sufiksowego , musimy połączyć ten węzeł z naszym prądem active nodepoprzez łącze sufiksowe.

Spójrzmy na przykład drzewa sufiksów dla cdddcdc, jeśli w takim przypadku dodamy link do sufiksu, a jeśli nie:

1. Jeśli NIE połączymy węzłów poprzez link sufiksu:

   • przed dodaniem ostatniej litery c :

   

   • po dodaniu ostatniej litery c :

   

2. Gdybyśmy DO połączyć węzły za pośrednictwem łącza przyrostkiem:

   • przed dodaniem ostatniej litery c :

   

   • po dodaniu ostatniej litery c :

   

Wygląda na to, że nie ma znaczącej różnicy: w drugim przypadku są jeszcze dwa linki przyrostków. Ale te linki sufiksów są poprawne , a jedno z nich - od niebieskiego do czerwonego - jest bardzo ważne dla naszego podejścia z punktem aktywnym . Problem polega na tym, że jeśli nie dodamy tutaj linku do sufiksu, później, gdy dodamy kilka nowych liter do drzewa, możemy pominąć dodawanie niektórych węzłów do drzewa z powodu Rule 3, ponieważ zgodnie z nim, jeśli nie ma link sufiks, to musimy umieścić active_noderoot w katalogu głównym.

Kiedy dodawaliśmy ostatnią literę do drzewa, czerwony węzeł już istniał, zanim zrobiliśmy wstawkę z niebieskiego węzła (krawędź oznaczona „c” ). Ponieważ z niebieskiego węzła pojawiła się wstawka, oznaczamy ją jako wymagającą łącza do sufiksu . Następnie, bazując na podejściu do punktu aktywnego , active nodeustawiono czerwony węzeł. Ale nie robimy wstawki z czerwonego węzła, ponieważ litera „c” jest już na krawędzi. Czy to oznacza, że ​​niebieski węzeł musi zostać pozostawiony bez linku do sufiksu? Nie, musimy połączyć niebieski węzeł z czerwonym poprzez link sufiksu. Dlaczego to jest poprawne? Ponieważ punkt aktywnypodejście gwarantuje, że dotrzemy do właściwego miejsca, tj. do następnego miejsca, w którym musimy przetworzyć wstawkę o krótszym sufiksie.

Wreszcie, oto moje implementacje drzewa sufiksów:

1. Jawa
2. C ++

Mam nadzieję, że ten „przegląd” w połączeniu ze szczegółową odpowiedzią jogojapana pomoże komuś wdrożyć jego własne drzewo sufiksów.

Dzięki za dobrze wyjaśniony samouczek @jogojapan , zaimplementowałem algorytm w Pythonie.

Kilka drobnych problemów wspomnianych przez @jogojapan okazuje się bardziej wyrafinowanych niż się spodziewałem i należy je traktować bardzo ostrożnie. Zapewnienie wystarczającej niezawodności implementacji kosztowało mnie kilka dni ( tak sądzę). Problemy i rozwiązania są wymienione poniżej:

1. Koniec zRemainder > 0 Okazuje się, że taka sytuacja może się zdarzyć podczas kroku rozwijania , a nie tylko na końcu całego algorytmu. Kiedy tak się stanie, możemy pozostawić pozostałą część, actnode, actedge i actlength bez zmian , zakończyć bieżący krok rozwijania i rozpocząć kolejny krok albo dalej składać lub rozkładać, w zależności od tego, czy następny znak w oryginalnym ciągu znajduje się na bieżącej ścieżce lub nie.

2. Przeskocz nad węzłami: Kiedy podążamy za sufiksem, zaktualizuj punkt aktywny, a następnie stwierdzimy, że jego składnik active_length nie działa dobrze z nowym węzłem active_node. Musimy przejść do właściwego miejsca, aby podzielić lub wstawić liść. Proces ten może nie być taki prosty, ponieważ podczas przesuwania długości i kąta działania ciągle się zmieniają, kiedy trzeba wrócić do węzła głównego , skok i długość działania mogą być nieprawidłowe z powodu tych ruchów. Potrzebujemy dodatkowych zmiennych, aby zachować te informacje.

   

Pozostałe dwa problemy zostały w jakiś sposób wskazane przez @managonov

3. Podział może się zdegenerować Podczas próby podziału krawędzi, czasami okaże się, że operacja podziału jest odpowiednia dla węzła. W takim przypadku musimy tylko dodać nowy liść do tego węzła, weź go jako standardową operację podziału krawędzi, co oznacza, że ​​linki przyrostków, jeśli takie istnieją, powinny być odpowiednio obsługiwane.

4. Ukryte linki sufiksowe Istnieje inny szczególny przypadek, który powstaje w wyniku problemu 1 i problemu 2 . Czasami musimy przeskoczyć przez kilka węzłów do odpowiedniego punktu do podziału, możemy przekroczyć właściwy punkt, jeśli poruszymy się, porównując pozostały ciąg i etykiety ścieżek. W takim przypadku link do sufiksu zostanie przypadkowo pominięty, jeśli taki będzie. Można tego uniknąć, zapamiętując właściwy punkt podczas ruchu do przodu. Link do sufiksu powinien zostać zachowany, jeśli węzeł podzielony już istnieje, lub nawet problem 1 występuje podczas etapu rozwijania.

Wreszcie moja implementacja w Pythonie wygląda następująco:

• Pyton

Wskazówki: Zawiera on naiwną funkcję drukowania drzewa w powyższym kodzie, co jest bardzo ważne podczas debugowania . Zaoszczędziło mi to dużo czasu i jest wygodne do lokalizowania specjalnych przypadków.

Przepraszam, jeśli moja odpowiedź wydaje się zbędna, ale niedawno zaimplementowałem algorytm Ukkonena i przez kilka dni miałem z nim problemy; Musiałem przeczytać wiele artykułów na ten temat, aby zrozumieć, dlaczego i jak niektóre podstawowe aspekty algorytmu.

Uznałem, że podejście oparte na „regułach” poprzednich odpowiedzi było nieprzydatne dla zrozumienia podstawowych przyczyn , dlatego napisałem wszystko poniżej, koncentrując się wyłącznie na pragmatyce. Jeśli masz problem z przestrzeganiem innych wyjaśnień, tak jak ja, być może moje dodatkowe wyjaśnienie sprawi, że klikniesz.

Tutaj opublikowałem moją implementację C #: https://github.com/baratgabor/SuffixTree

Pamiętaj, że nie jestem ekspertem w tym temacie, więc poniższe sekcje mogą zawierać nieścisłości (lub gorzej). Jeśli napotkasz jakieś, możesz je edytować.

Wymagania wstępne

Punktem początkowym poniższego wyjaśnienia jest założenie, że znasz treść i użycie drzewek sufiksów, a także cechy algorytmu Ukkonen, np. Sposób rozszerzania znaku drzewa sufiksów po znaku od początku do końca. Zasadniczo zakładam, że przeczytałeś już niektóre inne wyjaśnienia.

(Musiałem jednak dodać podstawową narrację dotyczącą przepływu, więc początek może się wydawać zbędny).

Najciekawsze jest wyjaśnienie różnicy między używaniem łączy sufiksowych a ponownym skanowaniem z katalogu głównego . To sprawiło mi wiele błędów i problemów podczas wdrażania.

Otwarte węzły liści i ich ograniczenia

Jestem pewien, że już wiesz, że najbardziej podstawową „sztuczką” jest uświadomienie sobie, że możemy po prostu zostawić koniec sufiksów „otwarty”, tj. Odwołując się do bieżącej długości łańcucha zamiast ustawiać koniec na wartość statyczną. W ten sposób, gdy dodamy dodatkowe znaki, znaki te zostaną domyślnie dodane do wszystkich etykiet sufiksów, bez konieczności odwiedzania i aktualizowania wszystkich.

Ale to otwarte zakończenie sufiksów - z oczywistych powodów - działa tylko w przypadku węzłów, które reprezentują koniec łańcucha, tj. Węzłów liści w strukturze drzewa. Operacje rozgałęziania, które wykonujemy na drzewie (dodanie nowych węzłów gałęzi i węzłów liści) nie będą propagowane automatycznie wszędzie tam, gdzie będą potrzebne.

Jest to prawdopodobnie elementarne i nie wymagałoby wzmianki, że powtarzające się podciągi nie pojawiają się jawnie w drzewie, ponieważ drzewo już je zawiera, ponieważ są to powtórzenia; jednak gdy powtarzające się podciągi kończą się napotkaniem nie powtarzającego się znaku, musimy utworzyć rozgałęzienie w tym punkcie, aby reprezentować rozbieżność od tego momentu.

Na przykład w przypadku ciągu „ABCXABCY” (patrz poniżej) rozgałęzienie do X i Y należy dodać do trzech różnych sufiksów, ABC , BC i C ; w przeciwnym razie nie byłoby prawidłowym drzewem sufiksów i nie moglibyśmy znaleźć wszystkich podciągów łańcucha, dopasowując znaki od katalogu głównego w dół.

Jeszcze raz, aby podkreślić - każda operacja, którą wykonujemy na sufiksie w drzewie, musi być odzwierciedlona również przez kolejne sufiksy (np. ABC> BC> C), w przeciwnym razie po prostu przestaną być poprawnymi sufiksami.

Ale nawet jeśli akceptujemy konieczność ręcznych aktualizacji, skąd wiemy, ile sufiksów należy zaktualizować? Ponieważ kiedy dodajemy powtarzający się znak A (i resztę powtarzających się znaków kolejno), nie mamy jeszcze pojęcia, kiedy / gdzie musimy podzielić sufiks na dwie gałęzie. Potrzeba podzielenia zostaje stwierdzona tylko wtedy, gdy napotkamy pierwszy nie powtarzający się znak, w tym przypadku Y (zamiast X, który już istnieje w drzewie).

Możemy dopasować najdłuższy powtarzający się ciąg znaków i policzyć, ile jego sufiksów potrzebujemy zaktualizować później. To właśnie oznacza „reszta” .

Pojęcie „reszty” i „ponownego skanowania”

Zmienna remaindermówi nam, ile powtórzonych znaków dodaliśmy domyślnie, bez rozgałęziania; tzn. ile sufiksów musimy odwiedzić, aby powtórzyć operację rozgałęziania, gdy znajdziemy pierwszy znak, którego nie możemy dopasować. Zasadniczo jest to równe liczbie „głębokich” postaci znajdujących się w drzewie od jego korzenia.

Tak więc, pozostając przy poprzednim przykładzie ciągu ABCXABCY , dopasowujemy powtarzaną część ABC „niejawnie”, zwiększając za remainderkażdym razem, co skutkuje pozostałą liczbą 3. Następnie napotykamy nie powtarzający się znak „Y” . Tutaj dzielimy wcześniej dodanej ABCX w ABC -> X i ABC -> Y . Następnie zmniejszamy remainderz 3 do 2, ponieważ już zadbaliśmy o rozgałęzienie ABC . Teraz powtarzamy operację, dopasowując ostatnie 2 znaki - BC - od rdzenia do punktu, w którym musimy się podzielić, i dzielimy BCX również na BC-> X i BC -> Y . Ponownie zmniejszamy remainderdo 1 i powtarzamy operację; aż do remainder0. Na koniec musimy również dodać bieżący znak ( Y ) do korzenia.

Ta operacja, po kolejnych sufiksach z katalogu głównego, aby dotrzeć do punktu, w którym musimy wykonać operację, w algorytmie Ukkonena nazywa się „ponownym skanowaniem” , i zazwyczaj jest to najdroższa część algorytmu. Wyobraź sobie dłuższy ciąg, w którym musisz „przeskanować” długie podciągi w wielu dziesiątkach węzłów (omówimy to później), potencjalnie tysiące razy.

Jako rozwiązanie wprowadzamy tak zwane „linki przyrostków” .

Pojęcie „linków przyrostkowych”

Łącza sufiksów w zasadzie wskazują na pozycje, w których normalnie musielibyśmy „ponownie skanować” , więc zamiast kosztownej operacji ponownego skanowania możemy po prostu przeskoczyć do połączonej pozycji, wykonać naszą pracę, przejść do następnej połączonej pozycji i powtarzać - aż do tego miejsca nie ma już pozycji do aktualizacji.

Oczywiście jednym wielkim pytaniem jest, jak dodać te linki. Istniejąca odpowiedź jest taka, że ​​możemy dodawać łącza podczas wstawiania nowych węzłów gałęzi, wykorzystując fakt, że w każdym rozszerzeniu drzewa węzły gałęzi są naturalnie tworzone jeden po drugim w dokładnie takiej kolejności, w jakiej musielibyśmy je połączyć . Chociaż musimy połączyć z ostatnio utworzonym węzłem gałęzi (najdłuższy sufiks) do poprzednio utworzonego, więc musimy buforować ostatnio tworzone, połączyć to z następnym, który tworzymy, i buforować nowo utworzony.

Jedną z konsekwencji jest to, że w rzeczywistości często nie mamy linków do przyrostków, ponieważ właśnie utworzono dany węzeł odgałęzienia. W takich przypadkach musimy jeszcze wrócić do wspomnianego „ponownego skanowania” z poziomu root. Dlatego po wstawieniu instruujesz się, aby albo użyć sufiksu, albo przejść do rootowania.

(Lub alternatywnie, jeśli przechowujesz wskaźniki nadrzędne w węzłach, możesz spróbować podążać za rodzicami, sprawdzić, czy mają link i użyć go. Stwierdziłem, że jest to bardzo rzadko wspominane, ale użycie linku w sufiksie nie jest osadzone w kamieniach. Istnieje wiele możliwych podejść, a jeśli zrozumiesz podstawowy mechanizm, możesz wdrożyć taki, który najlepiej odpowiada Twoim potrzebom.)

Pojęcie „punktu aktywnego”

Do tej pory omawialiśmy wiele wydajnych narzędzi do budowania drzewa i niejasno mówiliśmy o przechodzeniu przez wiele krawędzi i węzłów, ale nie zbadaliśmy jeszcze odpowiednich konsekwencji i złożoności.

Wyjaśniona wcześniej koncepcja „reszty” jest przydatna do śledzenia, gdzie jesteśmy w drzewie, ale musimy zdać sobie sprawę, że nie przechowuje wystarczającej ilości informacji.

Po pierwsze, zawsze rezydujemy na określonej krawędzi węzła, dlatego musimy przechowywać informacje o krawędzi. Nazwiemy to „aktywną przewagą” .

Po drugie, nawet po dodaniu informacji o krawędzi, nadal nie mamy możliwości zidentyfikowania pozycji, która jest bardziej niżej w drzewie i nie jest bezpośrednio połączona z węzłem głównym . Więc musimy również zapisać węzeł. Nazwijmy to „aktywnym węzłem” .

Wreszcie możemy zauważyć, że „reszta” jest nieodpowiednia do zidentyfikowania pozycji na krawędzi, która nie jest bezpośrednio połączona z korzeniem, ponieważ „reszta” jest długością całej trasy; i prawdopodobnie nie chcemy zawracać sobie głowy zapamiętywaniem i odejmowaniem długości poprzednich krawędzi. Potrzebujemy więc reprezentacji, która jest zasadniczo pozostałą częścią bieżącej krawędzi . Nazywamy to „aktywną długością” .

Prowadzi to do czegoś, co nazywamy „punktem aktywnym” - pakiet trzech zmiennych, które zawierają wszystkie informacje, które musimy zachować na temat naszej pozycji w drzewie:

Active Point = (Active Node, Active Edge, Active Length)

Na poniższym obrazku można zobaczyć, w jaki sposób dopasowana trasa ABCABD składa się z 2 znaków na krawędzi AB (z katalogu głównego ) oraz 4 znaków na krawędzi CABDABCABD (z węzła 4) - w wyniku czego „reszta” wynosi 6 znaków. Tak więc naszą obecną pozycję można określić jako Active Node 4, Active Edge C, Active Length 4 .

Inną ważną rolą „punktu aktywnego” jest to, że zapewnia on warstwę abstrakcji dla naszego algorytmu, co oznacza, że ​​części naszego algorytmu mogą wykonywać swoją pracę na „punkcie aktywnym” , niezależnie od tego, czy ten punkt aktywny znajduje się w katalogu głównym, czy gdziekolwiek indziej . Ułatwia to implementację użycia linków sufiksowych w naszym algorytmie w przejrzysty i prosty sposób.

Różnice w ponownym skanowaniu w porównaniu z użyciem łączy sufiksowych

Teraz trudną częścią, która - z mojego doświadczenia - może powodować wiele błędów i bólów głowy i jest słabo wyjaśniona w większości źródeł, jest różnica w przetwarzaniu przypadków linków do sufiksów w porównaniu do przypadków ponownego skanowania.

Rozważ następujący przykład ciągu „AAAABAAAABAAC” :

Powyżej można zaobserwować, w jaki sposób „reszta” 7 odpowiada całkowitej sumie znaków z katalogu głównego, a „długość aktywna” 4 odpowiada sumie dopasowanych znaków z aktywnej krawędzi aktywnego węzła.

Teraz, po wykonaniu operacji rozgałęzienia w punkcie aktywnym, nasz aktywny węzeł może zawierać link sufiksowy lub nie.

Jeśli istnieje link do sufiksu: Musimy przetworzyć tylko część „aktywnej długości” . „Reszta” nie ma znaczenia, ponieważ węzeł, gdzie skakać przez link do przyrostkiem już koduje prawidłowy „resztę” bez zastrzeżeń , po prostu z racji bycia w drzewie, gdzie jest.

Jeśli link do sufiksu NIE jest obecny: Musimy ponownie przeskanować od zera / roota, co oznacza przetworzenie całego sufiksu od początku. W tym celu musimy wykorzystać całą „pozostałą część” jako podstawę do ponownego skanowania.

Przykładowe porównanie przetwarzania z łączem sufiksu i bez niego

Zastanów się, co stanie się w następnym kroku powyższego przykładu. Porównajmy, jak osiągnąć ten sam wynik - tj. Przejście do następnego sufiksu do przetworzenia - z łączem sufiksu i bez niego.

Korzystanie z „sufiksu linku”

Zauważ, że jeśli użyjemy linku do sufiksu, jesteśmy automatycznie „we właściwym miejscu”. Co często nie jest do końca prawdą ze względu na fakt, że „długość aktywna” może być „niezgodna” z nową pozycją.

W powyższym przypadku, ponieważ „długość aktywna” wynosi 4, pracujemy z sufiksem „ ABAA” , zaczynając od połączonego węzła 4. Ale po znalezieniu krawędzi odpowiadającej pierwszemu znakowi sufiksu ( „A” ), zauważamy, że nasza „długość aktywna” przepełnia tę krawędź o 3 znaki. Przeskakujemy więc przez całą krawędź do następnego węzła i zmniejszamy „długość aktywną” przez postacie, które pochłonęliśmy przez skok.

Następnie, gdy znaleźliśmy następną krawędź „B” , odpowiadającą zmniejszonemu przyrostkowi „BAA ”, w końcu zauważamy, że długość krawędzi jest większa niż pozostała „aktywna długość” 3, co oznacza, że ​​znaleźliśmy właściwe miejsce.

Należy pamiętać, że wydaje się, że ta operacja zwykle nie jest określana jako „ponowne skanowanie”, chociaż wydaje mi się, że jest to bezpośredni odpowiednik ponownego skanowania, tylko ze skróconą długością i punktem początkowym innym niż root.

Używanie „ponownego skanowania”

Zauważ, że jeśli zastosujemy tradycyjną operację „ponownego skanowania” (tutaj udając, że nie mamy linku do sufiksu), zaczynamy od szczytu drzewa, w katalogu głównym, i musimy znów iść w dół do właściwego miejsca, wzdłuż całej długości bieżącego sufiksu.

Długość tego sufiksu to „reszta” , o której mówiliśmy wcześniej. Musimy skonsumować całość tej reszty, aż osiągnie zero. Może to (i często obejmuje) przeskakiwanie przez wiele węzłów, przy każdym skoku zmniejszanie reszty o długość krawędzi, przez którą przeskoczyliśmy. W końcu dochodzimy do krawędzi, która jest dłuższa niż nasza pozostała „reszta” ; tutaj ustawiamy aktywną krawędź na daną krawędź, ustawiamy „aktywną długość” na pozostającą „resztę ” i gotowe.

Należy jednak pamiętać, że rzeczywista zmienna „pozostała” musi zostać zachowana i zmniejszana tylko po każdym wstawieniu węzła. Więc to, co opisałem powyżej, zakładało użycie oddzielnej zmiennej zainicjowanej na „resztę” .

Uwagi na temat łączy sufiksowych i ponownego skanowania

1) Zauważ, że obie metody prowadzą do tego samego wyniku. Skakanie do sufiksu jest jednak w większości przypadków znacznie szybsze; to całe uzasadnienie linków sufiksowych.

2) Rzeczywiste implementacje algorytmiczne nie muszą się różnić. Jak wspomniałem powyżej, nawet w przypadku użycia linku do sufiksu „długość aktywna” często nie jest kompatybilna z połączoną pozycją, ponieważ ta gałąź drzewa może zawierać dodatkowe rozgałęzienia. Zasadniczo musisz więc użyć „długości aktywnej” zamiast „reszty” i wykonać tę samą logikę ponownego skanowania, aż znajdziesz krawędź krótszą niż pozostała długość sufiksu.

3) Jedną ważną uwagą dotyczącą wydajności jest to, że nie ma potrzeby sprawdzania każdej postaci podczas ponownego skanowania. Ze względu na sposób budowania prawidłowego drzewa sufiksów możemy bezpiecznie założyć, że znaki są zgodne. Więc najczęściej liczysz długości, a jedyna potrzeba sprawdzenia równoważności znaków pojawia się, gdy przeskakujemy do nowej krawędzi, ponieważ krawędzie są identyfikowane przez ich pierwszy znak (który jest zawsze unikalny w kontekście danego węzła). Oznacza to, że logika „ponownego skanowania” różni się od logiki pełnego dopasowania łańcucha (tj. Wyszukiwanie podłańcucha w drzewie).

4) Opisane tutaj oryginalne połączenie przyrostków jest tylko jednym z możliwych podejść . Na przykład NJ Larsson i in. nazywa to podejście Node-Oriented Top-Down i porównuje je do Node-Oriented Bottom-Up i dwóch odmian zorientowanych na krawędzie . Różne podejścia mają różne typowe i najgorsze wyniki, wymagania, ograniczenia itp., Ale ogólnie wydaje się, że podejścia zorientowane na krawędź są ogólną poprawą do oryginału.

@ jojojapan przyniosłeś niesamowite wyjaśnienie i wizualizację. Ale jak wspomniał @makagonov, brakuje niektórych zasad dotyczących ustawiania linków do sufiksów. Jest to dobrze widoczne, gdy krok po kroku przechodzisz na http://brenden.github.io/ukkonen-animation/ poprzez słowo „aabaaabb”. Kiedy przechodzisz od kroku 10 do kroku 11, nie ma łącza przyrostka od węzła 5 do węzła 2, ale punkt aktywny nagle się tam przenosi.

@makagonov, ponieważ mieszkam w świecie Java, również próbowałem śledzić twoją implementację, aby zrozumieć przepływ pracy w budowaniu ST, ale było to dla mnie trudne z powodu:

• łączenie krawędzi z węzłami
• używając wskaźników zamiast odniesień
• łamie wypowiedzi;
• kontynuuj wyciągi;

Skończyło się na takiej implementacji w Javie, która - mam nadzieję - odzwierciedla wszystkie kroki w jaśniejszy sposób i skróci czas nauki dla innych ludzi Java:

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class ST {

  public class Node {
    private final int id;
    private final Map<Character, Edge> edges;
    private Node slink;

    public Node(final int id) {
        this.id = id;
        this.edges = new HashMap<>();
    }

    public void setSlink(final Node slink) {
        this.slink = slink;
    }

    public Map<Character, Edge> getEdges() {
        return this.edges;
    }

    public Node getSlink() {
        return this.slink;
    }

    public String toString(final String word) {
        return new StringBuilder()
                .append("{")
                .append("\"id\"")
                .append(":")
                .append(this.id)
                .append(",")
                .append("\"slink\"")
                .append(":")
                .append(this.slink != null ? this.slink.id : null)
                .append(",")
                .append("\"edges\"")
                .append(":")
                .append(edgesToString(word))
                .append("}")
                .toString();
    }

    private StringBuilder edgesToString(final String word) {
        final StringBuilder edgesStringBuilder = new StringBuilder();
        edgesStringBuilder.append("{");
        for(final Map.Entry<Character, Edge> entry : this.edges.entrySet()) {
            edgesStringBuilder.append("\"")
                    .append(entry.getKey())
                    .append("\"")
                    .append(":")
                    .append(entry.getValue().toString(word))
                    .append(",");
        }
        if(!this.edges.isEmpty()) {
            edgesStringBuilder.deleteCharAt(edgesStringBuilder.length() - 1);
        }
        edgesStringBuilder.append("}");
        return edgesStringBuilder;
    }

    public boolean contains(final String word, final String suffix) {
        return !suffix.isEmpty()
                && this.edges.containsKey(suffix.charAt(0))
                && this.edges.get(suffix.charAt(0)).contains(word, suffix);
    }
  }

  public class Edge {
    private final int from;
    private final int to;
    private final Node next;

    public Edge(final int from, final int to, final Node next) {
        this.from = from;
        this.to = to;
        this.next = next;
    }

    public int getFrom() {
        return this.from;
    }

    public int getTo() {
        return this.to;
    }

    public Node getNext() {
        return this.next;
    }

    public int getLength() {
        return this.to - this.from;
    }

    public String toString(final String word) {
        return new StringBuilder()
                .append("{")
                .append("\"content\"")
                .append(":")
                .append("\"")
                .append(word.substring(this.from, this.to))
                .append("\"")
                .append(",")
                .append("\"next\"")
                .append(":")
                .append(this.next != null ? this.next.toString(word) : null)
                .append("}")
                .toString();
    }

    public boolean contains(final String word, final String suffix) {
        if(this.next == null) {
            return word.substring(this.from, this.to).equals(suffix);
        }
        return suffix.startsWith(word.substring(this.from,
                this.to)) && this.next.contains(word, suffix.substring(this.to - this.from));
    }
  }

  public class ActivePoint {
    private final Node activeNode;
    private final Character activeEdgeFirstCharacter;
    private final int activeLength;

    public ActivePoint(final Node activeNode,
                       final Character activeEdgeFirstCharacter,
                       final int activeLength) {
        this.activeNode = activeNode;
        this.activeEdgeFirstCharacter = activeEdgeFirstCharacter;
        this.activeLength = activeLength;
    }

    private Edge getActiveEdge() {
        return this.activeNode.getEdges().get(this.activeEdgeFirstCharacter);
    }

    public boolean pointsToActiveNode() {
        return this.activeLength == 0;
    }

    public boolean activeNodeIs(final Node node) {
        return this.activeNode == node;
    }

    public boolean activeNodeHasEdgeStartingWith(final char character) {
        return this.activeNode.getEdges().containsKey(character);
    }

    public boolean activeNodeHasSlink() {
        return this.activeNode.getSlink() != null;
    }

    public boolean pointsToOnActiveEdge(final String word, final char character) {
        return word.charAt(this.getActiveEdge().getFrom() + this.activeLength) == character;
    }

    public boolean pointsToTheEndOfActiveEdge() {
        return this.getActiveEdge().getLength() == this.activeLength;
    }

    public boolean pointsAfterTheEndOfActiveEdge() {
        return this.getActiveEdge().getLength() < this.activeLength;
    }

    public ActivePoint moveToEdgeStartingWithAndByOne(final char character) {
        return new ActivePoint(this.activeNode, character, 1);
    }

    public ActivePoint moveToNextNodeOfActiveEdge() {
        return new ActivePoint(this.getActiveEdge().getNext(), null, 0);
    }

    public ActivePoint moveToSlink() {
        return new ActivePoint(this.activeNode.getSlink(),
                this.activeEdgeFirstCharacter,
                this.activeLength);
    }

    public ActivePoint moveTo(final Node node) {
        return new ActivePoint(node, this.activeEdgeFirstCharacter, this.activeLength);
    }

    public ActivePoint moveByOneCharacter() {
        return new ActivePoint(this.activeNode,
                this.activeEdgeFirstCharacter,
                this.activeLength + 1);
    }

    public ActivePoint moveToEdgeStartingWithAndByActiveLengthMinusOne(final Node node,
                                                                       final char character) {
        return new ActivePoint(node, character, this.activeLength - 1);
    }

    public ActivePoint moveToNextNodeOfActiveEdge(final String word, final int index) {
        return new ActivePoint(this.getActiveEdge().getNext(),
                word.charAt(index - this.activeLength + this.getActiveEdge().getLength()),
                this.activeLength - this.getActiveEdge().getLength());
    }

    public void addEdgeToActiveNode(final char character, final Edge edge) {
        this.activeNode.getEdges().put(character, edge);
    }

    public void splitActiveEdge(final String word,
                                final Node nodeToAdd,
                                final int index,
                                final char character) {
        final Edge activeEdgeToSplit = this.getActiveEdge();
        final Edge splittedEdge = new Edge(activeEdgeToSplit.getFrom(),
                activeEdgeToSplit.getFrom() + this.activeLength,
                nodeToAdd);
        nodeToAdd.getEdges().put(word.charAt(activeEdgeToSplit.getFrom() + this.activeLength),
                new Edge(activeEdgeToSplit.getFrom() + this.activeLength,
                        activeEdgeToSplit.getTo(),
                        activeEdgeToSplit.getNext()));
        nodeToAdd.getEdges().put(character, new Edge(index, word.length(), null));
        this.activeNode.getEdges().put(this.activeEdgeFirstCharacter, splittedEdge);
    }

    public Node setSlinkTo(final Node previouslyAddedNodeOrAddedEdgeNode,
                           final Node node) {
        if(previouslyAddedNodeOrAddedEdgeNode != null) {
            previouslyAddedNodeOrAddedEdgeNode.setSlink(node);
        }
        return node;
    }

    public Node setSlinkToActiveNode(final Node previouslyAddedNodeOrAddedEdgeNode) {
        return setSlinkTo(previouslyAddedNodeOrAddedEdgeNode, this.activeNode);
    }
  }

  private static int idGenerator;

  private final String word;
  private final Node root;
  private ActivePoint activePoint;
  private int remainder;

  public ST(final String word) {
    this.word = word;
    this.root = new Node(idGenerator++);
    this.activePoint = new ActivePoint(this.root, null, 0);
    this.remainder = 0;
    build();
  }

  private void build() {
    for(int i = 0; i < this.word.length(); i++) {
        add(i, this.word.charAt(i));
    }
  }

  private void add(final int index, final char character) {
    this.remainder++;
    boolean characterFoundInTheTree = false;
    Node previouslyAddedNodeOrAddedEdgeNode = null;
    while(!characterFoundInTheTree && this.remainder > 0) {
        if(this.activePoint.pointsToActiveNode()) {
            if(this.activePoint.activeNodeHasEdgeStartingWith(character)) {
                activeNodeHasEdgeStartingWithCharacter(character, previouslyAddedNodeOrAddedEdgeNode);
                characterFoundInTheTree = true;
            }
            else {
                if(this.activePoint.activeNodeIs(this.root)) {
                    rootNodeHasNotEdgeStartingWithCharacter(index, character);
                }
                else {
                    previouslyAddedNodeOrAddedEdgeNode = internalNodeHasNotEdgeStartingWithCharacter(index,
                            character, previouslyAddedNodeOrAddedEdgeNode);
                }
            }
        }
        else {
            if(this.activePoint.pointsToOnActiveEdge(this.word, character)) {
                activeEdgeHasCharacter();
                characterFoundInTheTree = true;
            }
            else {
                if(this.activePoint.activeNodeIs(this.root)) {
                    previouslyAddedNodeOrAddedEdgeNode = edgeFromRootNodeHasNotCharacter(index,
                            character,
                            previouslyAddedNodeOrAddedEdgeNode);
                }
                else {
                    previouslyAddedNodeOrAddedEdgeNode = edgeFromInternalNodeHasNotCharacter(index,
                            character,
                            previouslyAddedNodeOrAddedEdgeNode);
                }
            }
        }
    }
  }

  private void activeNodeHasEdgeStartingWithCharacter(final char character,
                                                    final Node previouslyAddedNodeOrAddedEdgeNode) {
    this.activePoint.setSlinkToActiveNode(previouslyAddedNodeOrAddedEdgeNode);
    this.activePoint = this.activePoint.moveToEdgeStartingWithAndByOne(character);
    if(this.activePoint.pointsToTheEndOfActiveEdge()) {
        this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge();
    }
  }

  private void rootNodeHasNotEdgeStartingWithCharacter(final int index, final char character) {
    this.activePoint.addEdgeToActiveNode(character, new Edge(index, this.word.length(), null));
    this.activePoint = this.activePoint.moveTo(this.root);
    this.remainder--;
    assert this.remainder == 0;
  }

  private Node internalNodeHasNotEdgeStartingWithCharacter(final int index,
                                                         final char character,
                                                         Node previouslyAddedNodeOrAddedEdgeNode) {
    this.activePoint.addEdgeToActiveNode(character, new Edge(index, this.word.length(), null));
    previouslyAddedNodeOrAddedEdgeNode = this.activePoint.setSlinkToActiveNode(previouslyAddedNodeOrAddedEdgeNode);
    if(this.activePoint.activeNodeHasSlink()) {
        this.activePoint = this.activePoint.moveToSlink();
    }
    else {
        this.activePoint = this.activePoint.moveTo(this.root);
    }
    this.remainder--;
    return previouslyAddedNodeOrAddedEdgeNode;
  }

  private void activeEdgeHasCharacter() {
    this.activePoint = this.activePoint.moveByOneCharacter();
    if(this.activePoint.pointsToTheEndOfActiveEdge()) {
        this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge();
    }
  }

  private Node edgeFromRootNodeHasNotCharacter(final int index,
                                             final char character,
                                             Node previouslyAddedNodeOrAddedEdgeNode) {
    final Node newNode = new Node(idGenerator++);
    this.activePoint.splitActiveEdge(this.word, newNode, index, character);
    previouslyAddedNodeOrAddedEdgeNode = this.activePoint.setSlinkTo(previouslyAddedNodeOrAddedEdgeNode, newNode);
    this.activePoint = this.activePoint.moveToEdgeStartingWithAndByActiveLengthMinusOne(this.root,
            this.word.charAt(index - this.remainder + 2));
    this.activePoint = walkDown(index);
    this.remainder--;
    return previouslyAddedNodeOrAddedEdgeNode;
  }

  private Node edgeFromInternalNodeHasNotCharacter(final int index,
                                                 final char character,
                                                 Node previouslyAddedNodeOrAddedEdgeNode) {
    final Node newNode = new Node(idGenerator++);
    this.activePoint.splitActiveEdge(this.word, newNode, index, character);
    previouslyAddedNodeOrAddedEdgeNode = this.activePoint.setSlinkTo(previouslyAddedNodeOrAddedEdgeNode, newNode);
    if(this.activePoint.activeNodeHasSlink()) {
        this.activePoint = this.activePoint.moveToSlink();
    }
    else {
        this.activePoint = this.activePoint.moveTo(this.root);
    }
    this.activePoint = walkDown(index);
    this.remainder--;
    return previouslyAddedNodeOrAddedEdgeNode;
  }

  private ActivePoint walkDown(final int index) {
    while(!this.activePoint.pointsToActiveNode()
            && (this.activePoint.pointsToTheEndOfActiveEdge() || this.activePoint.pointsAfterTheEndOfActiveEdge())) {
        if(this.activePoint.pointsAfterTheEndOfActiveEdge()) {
            this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge(this.word, index);
        }
        else {
            this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge();
        }
    }
    return this.activePoint;
  }

  public String toString(final String word) {
    return this.root.toString(word);
  }

  public boolean contains(final String suffix) {
    return this.root.contains(this.word, suffix);
  }

  public static void main(final String[] args) {
    final String[] words = {
            "abcabcabc$",
            "abc$",
            "abcabxabcd$",
            "abcabxabda$",
            "abcabxad$",
            "aabaaabb$",
            "aababcabcd$",
            "ababcabcd$",
            "abccba$",
            "mississipi$",
            "abacabadabacabae$",
            "abcabcd$",
            "00132220$"
    };
    Arrays.stream(words).forEach(word -> {
        System.out.println("Building suffix tree for word: " + word);
        final ST suffixTree = new ST(word);
        System.out.println("Suffix tree: " + suffixTree.toString(word));
        for(int i = 0; i < word.length() - 1; i++) {
            assert suffixTree.contains(word.substring(i)) : word.substring(i);
        }
    });
  }
}

Moja intuicja jest następująca:

Po zakończeniu iteracji głównej pętli zbudowałeś drzewo sufiksów, które zawiera wszystkie sufiksy pełnego łańcucha rozpoczynającego się na pierwsze k znaków.

Na początku oznacza to, że drzewo sufiksów zawiera pojedynczy węzeł główny, który reprezentuje cały ciąg znaków (jest to jedyny sufiks zaczynający się od 0).

Po iteracjach len (string) masz drzewo sufiksów, które zawiera wszystkie sufiksy.

Podczas pętli klucz jest punktem aktywnym. Domyślam się, że reprezentuje to najgłębszy punkt w drzewie przyrostków, który odpowiada poprawnemu przyrostkowi pierwszych k znaków ciągu. (Myślę, że właściwe oznacza, że ​​przyrostek nie może być całym ciągiem.)

Załóżmy na przykład, że widziałeś znaki „abcabc”. Punkt aktywny reprezentowałby punkt w drzewie odpowiadający przyrostkowi „abc”.

Punkt aktywny jest reprezentowany przez (początek, pierwszy, ostatni). Oznacza to, że aktualnie znajdujesz się w punkcie drzewa, do którego dochodzisz, zaczynając od początku węzła, a następnie wprowadzając znaki w ciągu [pierwszy: ostatni]

Po dodaniu nowej postaci sprawdzisz, czy punkt aktywny nadal znajduje się w istniejącym drzewie. Jeśli tak, to koniec. W przeciwnym razie musisz dodać nowy węzeł do drzewa sufiksów w punkcie aktywnym, wrócić do następnego najkrótszego dopasowania i sprawdzić ponownie.

Uwaga 1: Wskaźniki sufiksów dają link do następnego najkrótszego dopasowania dla każdego węzła.

Uwaga 2: Gdy dodajesz nowy węzeł i zastępujesz go, dodajesz nowy wskaźnik sufiksu dla nowego węzła. Miejscem docelowym tego wskaźnika sufiksu będzie węzeł w skróconym punkcie aktywnym. Ten węzeł będzie już istniał lub zostanie utworzony podczas następnej iteracji tej pętli rezerwowej.

Uwaga 3: Część kanonizacyjna po prostu oszczędza czas w sprawdzaniu aktywnego punktu. Załóżmy na przykład, że zawsze używałeś origin = 0, a tylko zmieniałeś pierwszy i ostatni. Aby sprawdzić punkt aktywny, należy za każdym razem podążać za drzewem sufiksu wzdłuż wszystkich węzłów pośrednich. Sens buforowania wyniku podążania tą ścieżką ma sens, rejestrując tylko odległość od ostatniego węzła.

Czy możesz podać kodowy przykład tego, co rozumiesz przez „naprawienie” zmiennych granicznych?

Ostrzeżenie zdrowotne: Uważam również, że ten algorytm jest szczególnie trudny do zrozumienia, więc pamiętaj, że ta intuicja może być niepoprawna we wszystkich ważnych szczegółach ...

Cześć, próbowałem wdrożyć powyższą implementację w Ruby, sprawdź to. wydaje się, że działa dobrze.

jedyną różnicą w implementacji jest to, że próbowałem użyć obiektu krawędzi zamiast tylko symboli.

jest również obecny na https://gist.github.com/suchitpuri/9304856

    require 'pry'


class Edge
    attr_accessor :data , :edges , :suffix_link
    def initialize data
        @data = data
        @edges = []
        @suffix_link = nil
    end

    def find_edge element
        self.edges.each do |edge|
            return edge if edge.data.start_with? element
        end
        return nil
    end
end

class SuffixTrees
    attr_accessor :root , :active_point , :remainder , :pending_prefixes , :last_split_edge , :remainder

    def initialize
        @root = Edge.new nil
        @active_point = { active_node: @root , active_edge: nil , active_length: 0}
        @remainder = 0
        @pending_prefixes = []
        @last_split_edge = nil
        @remainder = 1
    end

    def build string
        string.split("").each_with_index do |element , index|


            add_to_edges @root , element        

            update_pending_prefix element                           
            add_pending_elements_to_tree element
            active_length = @active_point[:active_length]

            # if(@active_point[:active_edge] && @active_point[:active_edge].data && @active_point[:active_edge].data[0..active_length-1] ==  @active_point[:active_edge].data[active_length..@active_point[:active_edge].data.length-1])
            #   @active_point[:active_edge].data = @active_point[:active_edge].data[0..active_length-1]
            #   @active_point[:active_edge].edges << Edge.new(@active_point[:active_edge].data)
            # end

            if(@active_point[:active_edge] && @active_point[:active_edge].data && @active_point[:active_edge].data.length == @active_point[:active_length]  )
                @active_point[:active_node] =  @active_point[:active_edge]
                @active_point[:active_edge] = @active_point[:active_node].find_edge(element[0])
                @active_point[:active_length] = 0
            end
        end
    end

    def add_pending_elements_to_tree element

        to_be_deleted = []
        update_active_length = false
        # binding.pry
        if( @active_point[:active_node].find_edge(element[0]) != nil)
            @active_point[:active_length] = @active_point[:active_length] + 1               
            @active_point[:active_edge] = @active_point[:active_node].find_edge(element[0]) if @active_point[:active_edge] == nil
            @remainder = @remainder + 1
            return
        end



        @pending_prefixes.each_with_index do |pending_prefix , index|

            # binding.pry           

            if @active_point[:active_edge] == nil and @active_point[:active_node].find_edge(element[0]) == nil

                @active_point[:active_node].edges << Edge.new(element)

            else

                @active_point[:active_edge] = node.find_edge(element[0]) if @active_point[:active_edge]  == nil

                data = @active_point[:active_edge].data
                data = data.split("")               

                location = @active_point[:active_length]


                # binding.pry
                if(data[0..location].join == pending_prefix or @active_point[:active_node].find_edge(element) != nil )                  


                else #tree split    
                    split_edge data , index , element
                end

            end
        end 
    end



    def update_pending_prefix element
        if @active_point[:active_edge] == nil
            @pending_prefixes = [element]
            return

        end

        @pending_prefixes = []

        length = @active_point[:active_edge].data.length
        data = @active_point[:active_edge].data
        @remainder.times do |ctr|
                @pending_prefixes << data[-(ctr+1)..data.length-1]
        end

        @pending_prefixes.reverse!

    end

    def split_edge data , index , element
        location = @active_point[:active_length]
        old_edges = []
        internal_node = (@active_point[:active_edge].edges != nil)

        if (internal_node)
            old_edges = @active_point[:active_edge].edges 
            @active_point[:active_edge].edges = []
        end

        @active_point[:active_edge].data = data[0..location-1].join                 
        @active_point[:active_edge].edges << Edge.new(data[location..data.size].join)


        if internal_node
            @active_point[:active_edge].edges << Edge.new(element)
        else
            @active_point[:active_edge].edges << Edge.new(data.last)        
        end

        if internal_node
            @active_point[:active_edge].edges[0].edges = old_edges
        end


        #setup the suffix link
        if @last_split_edge != nil and @last_split_edge.data.end_with?@active_point[:active_edge].data 

            @last_split_edge.suffix_link = @active_point[:active_edge] 
        end

        @last_split_edge = @active_point[:active_edge]

        update_active_point index

    end


    def update_active_point index
        if(@active_point[:active_node] == @root)
            @active_point[:active_length] = @active_point[:active_length] - 1
            @remainder = @remainder - 1
            @active_point[:active_edge] = @active_point[:active_node].find_edge(@pending_prefixes.first[index+1])
        else
            if @active_point[:active_node].suffix_link != nil
                @active_point[:active_node] = @active_point[:active_node].suffix_link               
            else
                @active_point[:active_node] = @root
            end 
            @active_point[:active_edge] = @active_point[:active_node].find_edge(@active_point[:active_edge].data[0])
            @remainder = @remainder - 1     
        end
    end

    def add_to_edges root , element     
        return if root == nil
        root.data = root.data + element if(root.data and root.edges.size == 0)
        root.edges.each do |edge|
            add_to_edges edge , element
        end
    end
end

suffix_tree = SuffixTrees.new
suffix_tree.build("abcabxabcd")
binding.pry