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
  1. $$x_1\approx x_2 \Leftrightarrow \hat{x}_1\approx \hat{x}_2$$
  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)\).