Rozważamy problem Najkrótszego Wspólnego Nadsłowa (NWN). Na wejściu mamy zbiór słów \(S\) o sumarycznym rozmiarze \(n\) i chcemy znaleźć najkrótsze słowo (nadsłowo albo z angielskiego superstring), zawierające każde słowo ze zbioru \(S\) jako podsłowo. Problem ten jest \(NP\)-trudny. Rozważymy jeden z prostszych algorytmów aproksymacyjnych dla tego problemu - algorytm \(GREEDY\) (zachłanny). Do końca tego rozdziału zakładamy, że \(S\) jest bezinfiksowy, tzn. żadne słowo z \(S\) nie jest podsłowem innego słowa z \(S\).

Dla słów \(x\) i \(y\) oznaczmy przez \(ov(x,\, y)\) najdłuższy sufiks \(x\), będący prefiksem \(y\), zatem jeśli \(ov(x,\, y) = z\), to \(x = x'z\) i \(y = z y'\). Oznaczmy \(x \oplus y = x'y'\). Słowo \(z\) nazywamy nakładką (ang. overlap) słów \(x\) i \(y\).

Zdefiniujmy graf nakładkowy \(G = (V,\, E)\), gdzie \(V = S\) oraz \(dist(u,\, v) = ov(u,\, v)\). Każde nadsłowo odpowiada pewnej ścieżce Hamiltona w tym grafie, długością tej ścieżki jest suma wielkości kolejnych nakładek. Algorytm \(GREEDY\) działa w ten sposób, że wybiera kolejno krawędzie o maksymalnej długości.

Zdefiniujmy przez \(greedy(S)\) sumaryczną wartość długości nakładek realizowanych przez algorytm \(GREEDY\), podobnie niech \(opt(S)\) oznacza sumaryczną długość nakładek dla optymalnego algorytmu \(OPT\), który znajduje najcięższą ścieżkę Hamiltona w naszym grafie \(G\). Możemy to zapisać następująco:
$$greedy(S) = \vert S \vert - \vert GREEDY(S) \vert,\ opt(S) = \vert S \vert - \vert OPT(S) \vert$$

Obliczenie \(OPT(S)\) jest \(NP\)-zupełne, dlatego też musimy się zadowolić algorytmem aproksymacyjnym. \(GREEDY\) jest najlepszym znanym takim algorytmem w sensie sumy nakładek. Udowodnimy następujący fakt.

Twierdzenie (o jakości algorytmu \(GREEDY\))

• Algorytm \(GREEDY\) \(\frac{1}{2}\)-aproksymuje algorytm optymalny w sensie sumy nakładek, tzn. \(greedy(S) \geq \frac{1}{2} opt(S)\).
• W pesymistycznym przypadku \( \frac{1}{2} \) to najlepszy współczynnik dla algorytmu \(GREEDY\).

Dowód
Niech \(opt'(S)\) będzie długością ścieżki optymalnej w \(G\) przy dodatkowym warunku, że mamy krawędź \(u \rightarrow v\), gdzie \(overlap = ov(u,\, v)\) jest maksymalne. Pokażemy najpierw, że wartość ta niewiele różni się od \(opt(S)\). Zachodzi
$$(*) \quad opt'(S) \geq opt(S) - overlap$$

Niech \(\pi\) będzie ścieżką wygenerowaną przez \(OPT\). Rozważamy przypadki:

1. \(u\) jest przed \(v\) na \(\pi\).

   Wtedy ścieżka ma postać:
   $$\pi = w_1 \stackrel{*}{\longrightarrow} w_2 \rightarrow u \rightarrow w_3 \stackrel{*}{\longrightarrow} w_4 \rightarrow v \rightarrow w_5 \stackrel{*}{\longrightarrow} w_6$$
   Możemy ją zamienić na ścieżkę dla \(opt'\) tracąc jedynie w sumie \(overlap\), ponieważ "tracimy" dwie nakładki, a zyskujemy \(ov(u,\, v)\), maksymalną nakładkę.
   $$\pi' = w_3 \stackrel{*}{\longrightarrow} w_4 \rightarrow w_1\stackrel{*}{\longrightarrow} w_2 \rightarrow u \rightarrow v \rightarrow w_5 \stackrel{*}{\longrightarrow} w_6$$
   Tracimy wagi (nakładki) krawędzi \(u \rightarrow w_3\) i \(w_4 \rightarrow v\) natomiast zyskujemy (maksymalną) wagę utworzonej krawędzi \(u \rightarrow v\).

2. \(v\) jest przed \(u\) na \(\pi\).

   Wtedy ścieżka ma postać:
   $$\pi = w_1 \stackrel{*}{\longrightarrow} w_2 \rightarrow v \rightarrow w_3 \stackrel{*}{\longrightarrow} w_4 \rightarrow u \rightarrow w_5 \stackrel{*}{\longrightarrow} w_6$$
   Podobnie jak poprzednio możemy ją zamienić na następującą ścieżkę dla \(opt'\):
   $$\pi' = w_1 \stackrel{*}{\longrightarrow} w_2 \rightarrow w_5 \stackrel{*}{\longrightarrow} w_6 \rightarrow w_3 \stackrel{*}{\longrightarrow} w_4 \rightarrow u \rightarrow v $$
   W ten sposób tracimy jedynie w sumie co najwyżej \(overlap\), ponieważ "tracimy" trzy nakładki, z których dwie to \(ov(w_2,v),\; ov(u,w_5)\), a zyskujemy \(ov(u,\, v)+ov(w_2,w_5)\).

   Zauważmy, że
   $$ov(w_2,v)+ov(u,w_5) \; \le ov(u,\, v)+ov(w_2,w_5).$$
   Wynika to stąd że z maksymalności nakładki \(ov(u,v)\), dla prefiksu \(v'\) słowa v długości \(ov(u,v)\) wynikają równości:
   $$ov(w_2,v)=ov(w_2,v'),\ \ ov(u,w_5)=ov(v',w_5).$$
   Zatem $$ov(w_2,w_5)\;\ge \; ov(w_2,v')+ov(v',w_5)-|v'|$$

   Ostatecznie mamy: $$ ov(w_2,w_5)\;\ge \; ov(w_2,v)+ov(u,w_5)-ov(u,v).$$

Kończy to dowód nierówności \((*)\).

Przejdźmy teraz do głównego dowodu, który przeprowadzimy indukcyjnie. Załóżmy, że nierówność \(greedy(S') \geq \frac{1}{2} opt(S')\) jest spełniona dla \(S'\) mających mniej elementów niż \(S\). Z własności \((*)\) wynika, że dla \(S' = S - \lbrace u,\, v \rbrace \cup \lbrace u \oplus v \rbrace\) zachodzi
$$opt(S') + 2\, overlap \geq opt(S)$$

Jednocześnie \(greedy(S) = greedy(S') + overlap\), oraz z założenia indukcyjnego \(greedy(S') \geq \frac{1}{2} opt(S')\). Zbierając te nierówności mamy:
$$greedy(S) = greedy(S') + overlap \geq \frac{1}{2} (opt(S') + 2\, overlap) \geq \frac{1}{2} opt(S).$$

Kończy to dowód pierwszej części twierdzenia. Część druga wynika z przykładu bezpośrednio poprzedzającego twierdzenie.

Liniowa implementacja algorytmu \(GREEDY\): prefikso-sufiksy na drzewie

Początkowy zbiór słów będziemy dalej oznaczać przez \(S = \lbrace s_1,\, s_2,\ldots,\, s_n \rbrace\), a jego elementy będziemy nazywali słowami bazowymi. Niech \(x\) i \(y\) będą słowami, które w pewnym momencie znajdują się w zbiorze słów rozważanych przez algorytm \(GREEDY\). Powstały one przez operację \(\oplus\) wykonaną na pewnych słowach bazowych. Niech więc \(x = x_1 \oplus x_2 \oplus \ldots \oplus x_k\), \(y = y_1 \oplus y_2 \oplus \ldots \oplus y_l\), gdzie \(x_i,\, y_i \in S\) (w zapisie pomijamy nawiasowanie). Pozwala to traktować takie słowa \(x,\, y\) jak ciągi słów bazowych. Na mocy poniższej obserwacji wiemy, że \(ov(x,\, y) = ov(x_k,\, y_1)\).

Obserwacja
Niech \(S\) będzie zbiorem słów oraz \(Ov(S)=\max \lbrace \vert ov(x,\, y)\vert : x \neq y \in S \rbrace\). Jeśli \(\vert ov(u,\, v) \vert = Ov(S)\), to dla dowolnego \(x \in S \setminus \lbrace u,\, v \rbrace\) zachodzi \(ov(u \oplus v,\, x) = ov(v,\, x)\) oraz \(ov(x,\, u \oplus v) = ov(x,\, u)\).

Dowód
Gdyby \(u \oplus v\) i \(x\) miały zakładkę dłuższą niż \(\vert v \vert\), to łatwo zauważyć, że \(u\) i \(x\) miałyby zakładkę dłuższą niż \(\vert ov(u,\, v)\vert\), co nie jest możliwe. Zatem zakładką słów \(u \oplus v\) i \(x\) musi być sufiks \(v\), a więc zakładka \(v\) i \(x\). Analogicznie \(ov(x,\, u \oplus v) = ov(x,\, u)\). Koniec dowodu.

Algorytm będzie tworzył z elementów zbioru \(S\) (rozłączne) ciągi. Na początku są to ciągu jednoelementowe - po jednym na każde słowo bazowe. \(F\) to zbiór początków tych ciągów, a \(L\) - końców. Funkcja \(word(s)\) zwraca ciąg, w którym słowo bazowe \(s\) się znajduje. Przez \(first\) oznaczmy funkcję zwracającą pierwszy wyraz ciągu, a przez \(last\) ostatni. Zauważmy tu, że \(last \circ word\) jest bijekcją z \(F\) na \(L\).

Algorytm znajduje takie \(f \in F\) i \(\ell \in L\), że \(word(f) \neq word(\ell)\), a przy tym \(ov(\ell,\, f)\) jest maksymalne. Następnie łączy ciągi \(word(\ell)\) i \(word(f)\). Powtarza te czynności dopóki wszystkie słowa bazowe nie są w jednym ciągu.

Powiemy jeszcze, że sufiks słowa \(\ell \in S\) jest zakładką, jeśli \(\ell \in L\) oraz dla pewnego \(f \in F\) (takiego, że \(word(\ell) \neq word(f)\)) jest zakładką \(\ell\) i \(f\). W każdym kroku szukamy więc najdłuższej zakładki. Łatwo można zauważyć, że jeśli jakiś sufiks w danym momencie nie jest zakładką, to nigdy już nią nie będzie. Tym samym możemy przejść wszystkie sufiksy słów z \(S\) w kolejności malejącej długości. Jeśli natrafimy na zakładkę, to ją "realizujemy", czyli łączymy odpowiednie ciągi, a jeśli nie, po prostu przechodzimy do następnego sufiksu.

Struktury danych i preprocessing

Zbudujemy tablicę sufiksową \(SA\) słowa \(s_1 \$ s_2 \$ \ldots \$ s_n \$ \) wraz z wartościami \(rank\) i tablicą \(LCP\) (por. rozdział 8). De facto tablica ta odpowiada posortowanej tablicy wszystkich sufiksów słów bazowych. W szczególności znajdują się w niej całe słowa bazowe (posortowane). Dzięki temu możemy łatwo zbudować drzewo trie dla tych słów. Co więcej dla każdej pozycji \(j\) w słowie \(s_i\) będziemy trzymać wskaźnik do węzła w drzewie odpowiadającego \(j\)-temu prefiksowi słowa \(w_i\) (aby móc uzyskać dostęp do tej pozycji w czasie stałym).

Ponadto przechodząc jednokrotnie (od tyłu) tablicę \(SA\) będziemy na podstawie \(LCP\) mogli dla każdego sufiksu \(suf\) znaleźć długość najdłuższego wspólnego prefiksu z (leksykograficznie) najmniejszym i nie mniejszym niż \(suf\) słowem bazowym. Po prostu na pozycjach odpowiadających słowom bazowym wpisujemy ich długość, a na pozostałych - minimum z \(LCP\) i wyniku dla kolejnego w tablicy \(SA\) sufiksu. Dzięki tej wartości dla każdego sufiksu będziemy w stanie szybko wskazać odpowiadający mu pewien węzeł z trie lub stwierdzić, że takiego nie ma.

Zbiory \(L\) będziemy przechowywać jako funkcję charakterystyczną. Ponadto w każdym węźle drzewa trie stworzymy listę \(fLst\) słów z \(F\), którym odpowiadają liście znajdujące się w poddrzewie danego węzła. Funkcję \(word\) zaimplementujemy jako tablicę, przy czym jej wartości będą poprawne tylko dla argumentów z \(L \cup F\), gdyż tylko z nich będziemy korzystać.

Główny krok

Przedstawimy teraz implementację przetwarzania sufiksu \(\ell\) słowa \(s\). Po pierwsze sprawdzamy czy \(\ell \in L\). Jeśli tak, to szukamy odpowiadającego mu węzła w drzewie trie. Jeżeli jest taki węzeł (czyli jest to prefiks jakiegokolwiek słowa z \(S\)), to patrzymy na listę \(fLst\) w tym węźle. Jeśli jest ona pusta lub jej jedynym elementem jest takie \(f'\), że \(word(f') = word(\ell)\), to \(\ell\) nie jest zakładką. W przeciwnym razie na tej liście (na pierwszej lub drugiej pozycji) znajduje się takie \(f\), że zachodzi \(word(f) \neq word(\ell)\).

Słowa \(word(\ell)\) i \(word(f)\) są już dobrymi kandydatami do złączenia. Łączymy więc odpowiednie ciągi (przy okazji zapamiętujemy \(\vert s \vert = ov(\ell,\, f)\) - ta informacja stanie się potrzebna, gdy będziemy chcieli faktycznie dokonać operacji \(\oplus\)), aktualizujemy funkcję \(word\) dla początku i końca otrzymanego ciągu oraz zbiory \(L\) i \(F\). Musimy usunąć \(f\) ze wszystkich list \(fLst\). Aby uczynić to szybko, pamiętamy dla każdego słowa wskaźniki do odpowiednich miejsc we wszystkich listach \(fLst\). Alternatywnie możemy pamiętać zbiór \(F\) jako funkcję charakterystyczną i usuwać zbędne wartości z \(fLst\) dopiero gdy na takie natrafimy przeglądając te listy.

Usuwanie podsłów

Zakładaliśmy, że żadne słowo w zbiorze \(S\) nie jest podsłowem innego. Należałoby więc na samym początku usunąć takie słowa. Mając tablicę sufiksową i \(LCP\) możemy to uczynić w prosty sposób. Wystarczy bowiem sprawdzić, czy \(LCP\) tego słowa i następnego lub poprzednego (sufiksu) w tablicy jest mniejsze niż długość słowa. Jeśli nie, to należy słowo usunąć. Należy przy tym uważać na słowa, które na wejściu pojawiają się wielokrotnie - chcemy usunąć ich wszystkie wystąpienia poza jednym. Następnie możemy po prostu usunąć odpowiednie sufiksy z tablicy \(SA\) i odpowiednio zaktualizować \(LCP\).

Oszacowanie złożoności

Niech \(N\) będzie sumą długości słów w \(S\). Pokażemy, że poza konstrukcją tablicy sufiksowej cały algorytm działa w czasie \(O(N)\) niezależnie od rodzaju alfabetu. Tworzenie tablicy \(LCP\) i naszych dodatkowych opartych na niej wskaźników działa w takiej złożoności. Drzewo trie dla posortowanego ciągu słów konstruuje się również w \(O(N)\). Dane słowo bazowe jest na co najwyżej tylu listach \(fLst\), ile wynosi jego długość, a uzupełniamy je przechodząc od liścia do korzenia w trie, więc sumarycznie jest to \(O(N)\). Posortowanie sufiksów (a właściwie słów z \(S\)) po długości możemy wykonać w czasie proporcjonalnym do sumarycznej ich liczby i długości najdłuższego, co także jest \(O(N)\). Przetwarzanie danego sufiksu odbywa się w czasie stałym, o ile pominie się aktualizację list \(fLst\). Odpowiedni element takiej listy usuwamy w \(O(1)\), więc ten koszt jest amortyzowany przez tworzenie tych list. Cała główna faza działa więc w \(O(N)\), gdyż tyle jest sufiksów. Wreszcie stworzenie wynikowego nadsłowa, czyli dokonanie operacji \(\oplus\) na kolejnych elementach otrzymanego ciągu ma także łączny koszt \(O(N)\), ponieważ zapamiętywaliśmy wartości \(\vert ov \vert\) między kolejnymi słowami.

Ostatecznie algorytm działa w czasie \(O(N+S)\), gdzie \(S\) jest czasem potrzebnym do zbudowania tablicy sufiksowej. W zależności od typu i rozmiaru alfabetu mamy zatem złożoność \(O(N)\) albo \(O(N\log \vert \Sigma \vert)\).

Przypadek słów długości 2

Jeśli wszystkie słowa są dwuznakowe, to istnieje algorytm liniowy znalezienia najkrótszego nadsłowa. Skojarzmy z każdym symbolem \(\alpha \in \Sigma\) wierzchołek grafu \(G\). Dla każdego dwuznakowego słowa \(\alpha_1 \alpha_2\) dodajemy krawędź \(\alpha_1 \to \alpha_2\). W tak powstałym grafie skierowanym szukamy pokrycia ścieżkowego o najkrótszej sumie długości ścieżek. Wtedy każda taka ścieżka jest pewnym podsłowem całego nadsłowa, pokrywającego wszystkie zadane pary znaków.

W ogólnym przypadku minimalne pokrycie ścieżkowe oblicza się znajdując cykl Eulera w odpowiednio zmodyfikowanym grafie \(G\). Modyfikacja polega na dodaniu krawędzi w taki sposób, aby powstał graf eulerowski \(G'\). W \(G'\) znajdujemy cykl Eulera, a następnie usuwamy z niego dodane wcześniej krawędzie. W ten sposób cykl rozpada się na zbiór ścieżek, które pokrywają graf \(G\).

Uwaga: jeśli w \(G\) znajdują się spójne składowe eulerowskie, to wyłączamy je z konstrukcji cyklu Eulera przebiegającego całą resztę grafu. Robimy tak, ponieważ taka spójna składowa wygeneruje odpowiedni fragment (podsłowo) całego nadsłowa niezależnie od reszty grafu i nie ma sensu włączać jej do pełnego cyklu pokrywającego cały graf.