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.
