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.