Czy drzewa sufiksów mogą być użyte do znalezienia wszystkich popularnych podciągów?

Próbuję użyć drzewa sufiksów do porównania sekwencji ciągów. Znalazłem implementacje / teorię najdłuższego wspólnego problemu podciągów przy użyciu drzewek sufiksów. Jednak to, czego szukam, to omówienie powiązanego problemu - „wszystkich typowych podciągów”. W szczególności mam problem, w którym muszę najpierw znaleźć najdłuższy wspólny podciąg, a następnie znaleźć następny najdłuższy wspólny podciąg, który nie zawiera już znalezionych indeksów lcs, i tak dalej, aż do minimalnej długości. Czy ten problem można rozwiązać, budując uogólnione drzewo sufiksów (GST) tylko raz dla dwóch sekwencji. Wiem, że można to rozwiązać poprzez wielokrotne konstruowanie GST po każdej iteracji znalezienia i usunięcia LCS. Zastanawiam się jednak, czy brakuje mi zgrabnej sztuczki, w której GST jest budowany tylko raz.

Tak, drzewa sufiksów mogą być użyte do znalezienia wszystkich popularnych podciągów. Powiedziałbym, aby zamiast tego użyć tablicy sufiksów, ale jeśli masz już drzewo sufiksów, zbudowanie tablicy sufiksów z drzewa sufiksów zajmuje DFS liniowy czas. Reszta mojej odpowiedzi zakłada, że ​​pracujemy z tablicą przyrostków.

Biorąc pod uwagę tekst , tablica sufiksów dla to tablica liczb całkowitych z zakresu od do określająca porządek leksykograficzny sufiksów ciągu $ S 0 n n + 1 $S = s_1 , ..., s_n$$S$$0$$n$$n+1$$S$

Chcemy połączyć tablicę sufiksów z , najdłuższymi powszechnymi prefiksami. Możemy skonstruować tablicę w czasie liniowym, jak wspomniano w pracy Kasai i in . Tablice sufiksów i ich tablice lcp ustawiają się razem w taki sposób, że biorąc pod uwagę indeks w tablicy lcp, powiedz gdzie jest numerem indeksu, wtedy będzie początkiem jednej instancji wspólnego podłańcucha, a będzie początkowym indeksem drugiej instancji. Długość jest oczywiście wartością w tablicy lcp.L C P s l c p [ k ] k s a [ k ] s a [ k - 1 $LCPs$$LCPs$$lcp[k]$$k$$sa[k]$$sa[k-1]$

Mam pomysł, który może zadziałać. Zaczynamy uogólnionej drzewa przyrostkiem dla sekwencji i . Każdy wewnętrzny węzeł z sufiksami zarówno jak i w swoim poddrzewie odpowiada niektórym wspólnym podciągom sekwencji. Nazwijmy te węzły niebanalnymi. Wspólny podciąg jest maksymalny, jeśli odpowiedni węzeł nie ma nietrywialnych potomków. Jeśli węzeł nie jest trywialny, to zapisujemy największą głębokość ciągu nietrywialnego węzła w jego poddrzewie jako . Jeśli jest korzeń, a ma długość najdłuższego wspólnego podciągu i .T S T v l c s ( v ) r l c s ( r ) S $S$$T$$S$$T$$v$$lcs(v)$$r$$lcs(r)$$S$$T$

Aktualizacja drzewa po usunięciu podciągu z jednej z sekwencji nie powinna być zbyt trudna. Najpierw usuwamy liście odpowiadające usuniętym przyrostkom, w razie potrzeby aktualizując ich przodków. Następnie zaczynamy przetwarzać sufiksy poprzedzające usunięty podciąg. Niech będzie najniższym nietrywialnym przodkiem bieżącego liścia. Jeśli długość sufiksu wynosi (jesteśmy kroków od usunięcia) i , musimy przenieść sufiks do jego właściwej pozycji w drzewie, aktualizując w razie potrzeby przodków. Jeśli , to skończymy, ponieważ nie interesują nas poddrzewa z trywialnymi korzeniami.k k k < l c s ( v ) k ≥ l c s ( v $v$$k$$k$$k < lcs(v)$$k \ge lcs(v)$

Ogólny algorytm wielokrotnie wyszukuje najdłuższy wspólny podciąg i i usuwa jedno z jego wystąpień z obu sekwencji, o ile długość LCS jest wystarczająco duża.$S$$T$

Istnieje kilka szczegółów technicznych, ale ogólny pomysł powinien zadziałać.

Zacznij od połączonego tekstu S $ T , gdzie występuje nigdzie w $ * lub T . Skonstruuj drzewo / tablicę sufiksów z tego tekstu. Łatwo jest teraz przejść przez tę strukturę danych sufiksu, aby zebrać wszystkie właściwe maksymalne powtórzenia. Badając lewy kontekst, odfiltruj lewe maksymalne powtórzenia. To lewe filtrowanie może zostać zaimplementowane przy użyciu tabeli Burrows-Wheeler, jak w Abouelhoda i in., Chociaż nie uważam, że jest to konieczne. Powtarza się tylko w S lub tylko w Tw tym momencie powinien zostać wyeliminowany. Powtórzenia, które nie zostały wyeliminowane, są następnie umieszczane w kolejce priorytetowej z priorytetem określonym przez długość. Po przejściu, ponieważ nagrane powtórzenia są usuwane z priorytetu, można przeprowadzić ostateczne filtrowanie (w celu powstrzymania podciągów). Biorąc pod uwagę użycie maksymalnych fraz, podejrzewam jednak, że bardzo mało tego filtrowania byłoby konieczne.

Ten algorytm jest moim własnym wynalazkiem. Nie sklasyfikowałbym tego jako bardzo sprytnego, ale powinien zadziałać.

$S$$s$$T$$t$$s$$t$$S$$T$