Rozdział 6: Równoważność kwadratowa

Dwa słowa są kwadratowo równoważne gdy możemy zamienić jedno w drugie wykonując ciąg (być może pusty) operacji zamiany podsłowa typu $zz$ przez $z$ lub podsłowa $z$ przez $zz$. Inaczej mówiąc definiujemy $z \approx zz$ oraz $x \approx y$ gdy można otrzymać $x$ z $y$ przez wielokrotne stosowanie $z \to zz$ dla podsłów $x$ lub $y$. Na przykład słowa abac, aabaabaac i ababaabaabbabbaacc są kwadratowo równoważne.

Niech $\Sigma(x)$ będzie zbiorem liter słowa $x$. Zauważmy, że
$$x\approx y\ \Rightarrow \ \Sigma(x)=\Sigma(y)$$

Oznaczamy
$$\hat{x} = p \alpha \beta q, \quad p,\, q \in \Sigma(x)^*, \ \alpha,\, \beta \in \Sigma(x)$$
gdzie $p\alpha$ to najkrótszy prefiks taki, że $\Sigma(p\alpha)=\Sigma(x)$ oraz $\beta q$ najkrótszy sufiks o tej samej własności. Zauważmy, że
$$\Sigma(p) = \Sigma(x) - \lbrace \alpha \rbrace$$

Teoretyczna charakteryzacja równoważności kwadratowej.

Następujący fakt (a dokładniej punkt 2) daje algorytm sprawdzania równoważności kwadratowej.

Twierdzenie o równoważności kwadratowej

$$x_1\approx x_2 \Leftrightarrow \hat{x}_1\approx \hat{x}_2$$
Niech $\hat{x}_1 = p_1 \alpha_1 \beta_1 q_1$ i $\hat{x}_2 = p_2 \alpha_2 \beta_2 q_2$. Wtedy
$$\hat{x}_1 \approx \hat{x} _2 \Leftrightarrow (p_1 \approx p_2 \wedge q_1 \approx q_2 \wedge \alpha_1 = \alpha_2 \wedge \beta_1 = \beta_2)$$

Fakt 1.

$$\Sigma(y)\subseteq \Sigma(x) \Rightarrow (\exists u) \; x\approx xyu$$

Dowód

Dowód przez indukcję ze względu na długość $y$. Dla $|y|=0$ oczywiste. Niech $y=y'\alpha$. Wtedy z założenia indukcyjnego $(\exists u') \; x \approx xy'u'$. Rozłóżmy $x = z \alpha z'$ - istnieje taki rozkład, bo mamy założenie o $\Sigma(y) \subseteq \Sigma(x)$. Twierdzimy zatem, że istnieje $u$, że $x \approx xyu = z \alpha z' y' \alpha u$. Wystarczy wziąć $u=z'y'u'$, bo wtedy otrzymujemy
$$xyu = z \alpha z' y' \alpha z'y'u' = z(\alpha z' y')^2u' \approx z \alpha z' y' u' = x y' u' \stackrel{\text{ind.}}{\approx} x$$

Analogicznie można dowieść
$$\Sigma(y)\subseteq \Sigma(x) \Rightarrow (\exists u) \; x\approx uyx$$

Fakt 2.

$$(\exists w,\, t)\; x\approx t \hat{x} \wedge \hat{x}\approx xw$$

Dowód

Niech $x = p \alpha y$. Zachodzi $\Sigma(y) \subseteq \Sigma(p \alpha)$, więc można skorzystać z faktu 1.: $ (\exists u) \; p\alpha \approx p \alpha y u$ i dodatkowo ustalmy $w = u \beta q$, co daje
$$\hat{x} = p \alpha \beta q \stackrel{\text{fakt 1.}}{\approx} p \alpha y u \beta q = x u \beta q = xw$$

Analogicznie ustalmy $x = z \beta q$, mamy $\Sigma(p \alpha) = \Sigma(\beta q)$, więc $(\exists v) \; \beta q \approx v p \alpha
\beta q$ i niech $t = z v$, zatem
$$x = z \beta q \stackrel{\text{fakt 1.}} \approx z v p \alpha \beta q = z v \hat{x} = t \hat{x}$$

Pomocniczy lemat

$$x\approx \hat{x}$$

Dowód

$$x \stackrel{\text{fakt 2.}}{\approx} t \hat{x} \approx t \hat{x} \hat{x} \stackrel{\text{fakt 2.}}{\approx} x\hat{x} \stackrel{\text{fakt 2.}}{\approx} xxw \approx xw \stackrel{\text{fakt 2.}}{\approx} \hat{x}$$

Przy pomocy lematu udowodnijmy twierdzenie główne.

Dowód twierdzenia

Punkt 1. Zauważmy, że relacja $\approx$ jest relacją równoważności (działa zwrotność, przechodniość i symetria), na mocy czego jeśli $x_1 \approx x_2$ i $\hat{x}_1 \approx \hat{x}_2$, to wszystkie cztery słowa leżą w jednej klasie abstrakcji. Podobnie jeśli $x_1 \not\approx x_2$, to $\hat{x}_1$ i $\hat{x}_2$ znajdują się w dwóch różnych klasach abstrakcji.

Punkt 2. $(\Rightarrow)$

Załóżmy, że $\hat{x}_1 \approx \hat{x}_2$ oraz nie zachodzi prawa strona twierdzenia (dowód nie wprost). Rozpatrzmy przypadki:

$p_1 \not\approx p_2$. Jeśli $\Sigma(p_1) \neq \Sigma(p_2)$ (wtedy $\alpha_1 \neq \alpha_2$), to za pomocą operacji podwojenia dowolnego podsłowa (lub odwrotnej) nie możemy doprowadzić do ,,wymienienia'' $\alpha_1$ na jakiś inny znak, a co za tym idzie zmiany zbioru $\Sigma(p_1)$. Nie można zatem uzgodnić prefiksów słów $\hat{x}_1$ i $\hat{x}_2$, więc sprzeczność z założeniem.
Załóżmy zatem, że $\Sigma(p_1) = \Sigma(p_2)$ (wtedy także $\alpha_1 = \alpha_2$). Jeśli $\vert \Sigma(p_1) \vert = 1$, to wtedy $p_1 \approx p_2$ i mamy sprzeczność. W przeciwnym przypadku rozbijmy $p_1$ i $p_2$ na czwórki $(p_{p_1},\, \alpha_{p_1},\, \beta_{p_1},\, q_{p_1})$ i $(p_{p_2},\, \alpha_{p_2},\, \beta_{p_2},\, q_{p_2})$ i rekurencyjnie dla krótszych słów o mniejszym alfabecie sprawdzamy przypadki tego twierdzenia. Na którymś poziomie tej rekurencji musiałoby okazać się (dla pewnych słów $w_1$ i $w_2$), że
- $\Sigma(w_1) = \Sigma(w_2)$ i $\vert \Sigma(w_1) \vert = 1$ i sprzeczność, albo
- $\alpha_{w_1} \neq \alpha_{w_2}$ lub $\beta_{w_1} \neq \beta_{w_2}$, co doprowadzi do sprzeczności z założeniem o $\hat{x}_1 \approx \hat{x}_2$, bo nie będzie się dało uzgodnić prefiksów.
$q_1 \not\approx q_2$. Analogicznie jak powyżej.
$\alpha_1 \neq \alpha_2$. Wtedy $\Sigma(p_1) \neq \Sigma(p_2)$ i można skorzystać z dowodu pierwszego podpunktu.
$\beta_1 \neq \beta_2$. Analogicznie jak powyżej.

Punkt 2. $(\Leftarrow)$

Niech $\hat{x}_1 = p_1 \alpha \beta q_1$ i $\hat{x}_2 = p_2 \alpha \beta q_2$. Z założenia $p_1 \approx p_2$ i $q_1 \approx q_2$, więc możemy prefiksy i sufiksy obu słów uzgodnić ze sobą niezależnie i będzie dobrze.

Konstrukcja efektywnego algorytmu

Korzystając wprost z twierdzenia można skontruować wykładniczy algorytm sprawdzania równoważności kwadratowej dwóch słów $x_1$ i $x_2$. Jeśli alfabet $ \Sigma $ jest stosunkowo niewielki, to można nieco inaczej podejść do problemu. Będziemy identyfikowali podsłowa słów $x_1$ i $x_2$ z pewnymi klasami abstrakcji relacji równoważności kwadratowej. Dzięki temu, znając identyfikatory podsłów $p_1$, $p_2$, $s_1$ i $s_2$ oraz symbole $\alpha_1$, $\alpha_2$, $\beta_1$ i $\beta_2$ będziemy mogli w czasie stałym odpowiedzieć na pytanie o równoważność kwadratową całych słów.

Dla ustalenia uwagi przyjmijmy, że działamy tylko na jednym słowie $w = x_1 \$ x_2$ o długości $n$. Dzięki temu gdy określimy klasę abstrakcji prefiksu $x_1$ i sufiksu $x_2$, będziemy mogli od razu odpowiedzieć na pytanie o równoważność kwadratową. Zauważmy bowiem, że słowo $w$ ma rozkład $ (p,\, \alpha,\, \beta,\, s) = (x_1,\, \$,\, \$,\, x_2) $. Jednakże aby znaleźć identyfikator klasy abstrakcji słów $x_1$ oraz $x_2$, musimy dla nich wykonać odpowiedni rozkład, dla tych rozkładów wykonać kolejne itd. Każdy "poziom" rozkładu powoduje zmniejszenie rozmiaru alfabetu o 1. Skonstruujemy zatem algorytm bottom-up, który w kolejnych fazach $k = 1,\, 2,\ldots,\, \vert \Sigma \vert $ będzie obliczał klasy abstrakcji podsłów, składających się z alfabetu rozmiaru $k$.

Aby nie tracić czasu na częste odszukiwanie rozkładu $p$ i $s$ oraz odpowiadających im identyfikatorów klas abstrakcji, potrzebne nam będą dwie tablice. Niech $PREF_k[i]$ zawiera identyfikator klasy abstrakcji podsłowa $w[i..j]$, gdzie $j$ jest takie, że podsłowo $w[i..j]$ składa się z dokładnie $k$ różnych znaków, ale podsłowo $w[i..j+1]$ składa się już z $k + 1$ różnych znaków. Zauważmy, że wtedy dla pewnego podsłowa $v = w[i..t]$, gdzie $t > j$ podsłowo $w[i..j]$ jest $p$ z twierdzenia, a symbol $w[j+1]$ jest $\alpha$ (przy założeniu lokalnego ograniczenia alfabetu do $k + 1$ znaków). Niech także $SUF_k[i]$ zawiera identyfikator klasy abstrakcji podsłowa $w[j..i]$, gdzie $j$ definiujemy analogicznie.

Dla $k = 1$ ustalamy $PREF_k[i] := SUF_k[i] := \mathcal{I}(w[i])$ dla $i = 1,\, 2, \ldots,\, n$, gdzie $\mathcal{I}$ jest operatorem nadania unikalnego identyfikatora symbolom z alfabetu $\Sigma$. Dla $k > 1$ obliczamy $PREF_k$ następująco:

Dla każdego $i = 1,\, 2 \ldots$ szukamy wartości $j$ (z definicji $PREF$).
Obliczamy $PREF_k[i]$ jako identyfikator klasy abstrakcji słowa reprezentowanego przez trójkę $ (PREF_{k-1}[i],\, \mathcal{I}(w[j + 1]),\, SUF_{k-1}[j]) $.

Analogicznie obliczamy $SUF_k$. Dla ustalonego $k$ algorytm działa w czasie liniowym: wartości $j$ przy obliczaniu $PREF$ (odpowiednio $SUF$) tylko rosną (odpowiednio maleją), więc ich wyznaczanie można wykonać w czasie liniowym. Drugą część również można wykonać liniowo; generujemy trójki zgodnie z algorytmem, a następnie sortujemy je pozycyjnie i bloki takich samych trójek numerujemy unikalnym identyfikatorem.

Podsumowując, powyższy algorytm dowodzi następującego faktu.

Twierdzenie

Równoważność kwadratową dwu tekstów o sumarycznym rozmiarze $n$ nad alfabetem $k$-elementowym można sprawdzić w czasie $O(n\cdot k)$.

Informatyka MIMUW