W praktyce często szukamy wzorców w sposób aproksymacyjny. Pierwszą miarą aproksymacji tekstów jest tzw. odległość edycyjna, oznaczona przez \(edit(x,\, y)\). Odległość ta jest równa minimalnej liczbie operacji usunięcia, wstawienia lub zamiany pojedyńczego symbolu, które należy wykonać na podanych słowach, by doprowadzić je do jednakowej postaci. Funkcja \(edit\) ma następujące własności:
Tekst \(x = abab\) można zamienić na \(y = baabc\) za pomocą dwóch operacji zamiany i jednej operacji wstawienia symbolu. Tak więc \(edit(abab,\, baabc) = 3\).
Ustalmy teksty \(x\) (\(\vert x \vert = m\)) i \(y\) (\(\vert y \vert = n\)). Definiujemy następującą tablicę dwuwymiarową:
$$ED[i,\, j] = edit(x[1 \ldots i],\, y[1 \ldots j])$$
dla \(0 < i \leq m\), \(0 < j \leq n\). Wartości brzegowe tablicy ustalamy następująco:
$$\left( \forall\; 0 \leq i \leq m,\, 0 \leq j \leq n \right) \quad ED[i,\, 0] = i,\; ED[0,\, j] = j.$$
Pozostałe elementy tablicy liczymy korzystając z programowania dynamicznego:
$$ED[i,\, j] = \min \lbrace ED[i-1,\, j] + 1,\; ED[i,\, j-1] + 1,\; ED[i-1,\, j-1] + \partial (x[i],\, y[j]),$$
gdzie \(\partial (\alpha,\, \beta) = 0\) gdy \(\alpha = \beta\), oraz \(\partial(\alpha,\, \beta) = 1\) w przeciwnym przypadku.
Kolejne wiersze tablicy \(ED\) możemy liczyć pamiętając jedynie ostatni wiersz, ponieważ musimy policzyć jedynie element \(ED[m,\, n]\). Zatem nie musimy trzymać w pamięci całej tablicy. Odległość edycyjną dwóch tekstów o długościach \(n\) i \(m\) może być obliczona w czasie \(O(mn)\) korzystając z dodatkowej pamięci rozmiaru \(O(\min \lbrace m,\, n \rbrace)\).
Jeśli chcemy policzyć najkrótszą sekwencję operacji zamieniających jeden tekst w drugi, to potrzebna nam jest cała tablica \(ED\). Sekwencję taką liczymy cofając się od elementu \(ED[m,\, n]\).
Problem string-matchingu z błędami różni się tylko nieznacznie od liczenia odległości edycyjnej. Problem polega na policzeniu wartości \(\min (edit(x,\, y) : y \in Subwords(y))\). Jednocześnie chcielibyśmy policzyć podsłowo w \(y\) jak najbliższe danemu wzorcowi \(x\).
Definiujemy tablicę:
$$SMED[i,\,j] = \min ( edit(x[1 \ldots i],\, y) : y \in Subwords(y[1 \ldots j]) ).$$
Twierdzenie: problem string-matchingu z błędami można rozwiązać w czasie \(O(mn)\).
Dowód
Zasadniczą róźnicą między obliczaniem \(ED\) i \(SMED\) jest inicjalizacja, gdyż pusty prefiks wzorca "pasuje" do pustego podsłowa tekstu \(y\):
$$\left( \forall\; 0 \leq i \leq m,\, 0 \leq j \leq n \right) \quad SMED[i,\, 0] = i,\; SMED[0,\, j] = 0.$$
Wzory rekurencyjne liczenia "wewnętrznych" elementów tablicy \(SMED\) są takie same jak dla tablicy \(ED\).
Załóżmy, że pewne pozycje wzorca są nieistotne - będziemy mówić, że zawierają one symbol \(\diamondsuit\) będący dziurą lub tzw. symbolem uniwersalnym (ang. don't care symbol). Symbol \(\diamondsuit\) pasuje do każdego innego symbolu, włącznie ze sobą. Piszemy \(\alpha \approx \beta\) gdy symbole \(\alpha\) i \(\beta\) są równe lub co najmniej jeden jest dziurą.
Słowa \(u\), \(v\) (tej samej długości \(n\)) są prawie równe, gdy \(u[i] \approx v[i]\) dla każdej pozycji \(i\); piszemy wtedy \(u \approx v\). Wyszukiwanie wzorca z dziurami polega na znalezieniu pozycji w tekście \(y\) takich, że \(y[i..i+m-1] \approx x\), gdzie \(x\) jest wzorcem z dziurami długości \(m\).
Twierdzenie
Jeśli jedyną informacją z danych wejściowych jest porównanie dwóch symboli za pomocą operacji \(\approx\), to dla pewnych tekstów wejściowych potrzeba \(\Omega(n^{2})\) porównań \(\approx\) do rozwiązania problemu string-matchingu z dziurami.
Dowód
Rozważmy \(x = \diamondsuit^m\), \(y = \diamondsuit^{2m}\). W tym przypadku wzorzec występuje (zaczyna się) na wszystkich pozycjach w przedziale \([1..m]\). Jeśli nie wykonamy jakiegoś porównania między symbolami na pozycjach \(i,\, j\) to zmieniając zawartość tych pozycji na dwa różne symbole zmienimy wyjście nie zmieniając informacji, z której korzystamy na wejściu. Prowadzi to do sprzeczności z poprawnością algorytmu.
Załóżmy, że pozycje słów \(x,\, y\) są teraz ponumerowane od zera. Zdefiniujmy operację \(\odot\) w następujący sposób. Niech \(z = x \odot y\) będzie słowem długości \(m+n-1\), w którym wartością na \(k\)-tej pozycji, dla \(k = 0,\, 1, \ldots,\, m+n-2\), jest wartość:
$$z[k] = \bigwedge_{i+j = k}\; x[i] \approx y[j]$$
Operacja \(\bigwedge\) oznacza tutaj koniunkcję logiczną wielu czynników. Symbolicznie zapisujemy:
$$\odot =(\approx ,\textrm{ and})$$
Jak zwykle \(x^R\) oznacza odwrócenie słowa \(x\). Rozważmy "iloczyn" \(z = x^R \odot y\). Zachodzi
$$z[k] = 1 \ \Leftrightarrow\ x^R[m-1] \approx y[k-m+1] \wedge x^R[m-2] \approx y[k-m+2] \wedge \ldots \wedge x^R[0] \approx y[k] $$
Zatem każda sytuacja \(z[k] = 1\) odpowiada wystąpieniu wzorca \(x\), które kończy się na pozycji \(k\) w \(y\). Tak więc string-matching z dziurami sprowadza się do obliczania iloczynu \(\odot\).
Zamiast bezpośrednio liczyć operację \(\odot\) zdefiniujemy obliczeniowo łatwiejsze operacje. Dla wektorów logicznych \(x,\, y\) definiujemy operację \(z = x \otimes y\) jako:
$$z[k] = \bigvee_{i+j = k} \; x[i] \wedge y[j]$$
Operacja \(\bigvee\) oznacza tutaj alternatywę wielu składników logicznych. Dla słowa \(x\) i symbolu \(\alpha\), oznaczamy przez \(\mathit{logical}(\alpha,\, x)\) wektor logiczny, którego \(i\)-ta współrzędna jest \(true\) wtedy i tylko wtedy, gdy \(x[i] = \alpha\). Zdefiniujmy również
$$\mathit{LOGICAL}_{\alpha,\, \beta}(x,\, y) = \mathit{logical}(\alpha,\, x) \otimes logical(\beta,\, y).$$
Zachodzi teraz następujący oczywisty fakt:
$$x \odot y = \textrm{not}\;\left(\; \bigvee_{\alpha \neq \beta,\; \alpha,\, \beta \in \Sigma} \mathit{LOGICAL}_{\alpha,\, \beta}(x,\, y)\;\right)$$
Zatem dla ustalonego alfabetu złożoność operacji \(\odot\) jest tego samego rzędu, co operacji \(\otimes\). W poniższym twierdzeniu pokażemy jaki to ma związek ze złożonością mnożenia liczb naturalnych zapisanych w systemie binarnym.
Twierdzenie
Problem string-matchingu z dziurami można rozwiązać w czasie \(O(n\log^3 n)\) dla alfabetu o rozmiarze \(O(1)\).
Dowód
Niech \(x,\, y\) będą dwoma logicznymi (binarnymi) ciągami długości \(n\) oraz niech \(k = \lceil \log n \rceil\)). Zastępujemy w \(x,\, y\) wartości logiczne \(true\), \(false\) przez (odpowiednio) jedynki i zera. Wstawmy blok \(k\) zer pomiędzy każde dwa elementy ciągów \(x,\, y\). W ten sposób otrzymujemy binarne reprezentacje dwóch liczb \(x'\) i \(y'\).
Ciąg \(z = x \otimes y\) możemy odtworzyć z ciągu binarnego odpowiadającego standardowemu mnożeniu \(x \times y\) w następujący sposób. Bierzemy kolejne bloki długości \(k+1\) w \(x \times y\). Jeśli taki blok odpowiada liczbie niezerowej, to kolejnym elementem \(x \odot y\) będzie 1, w przeciwnym wypadku zero. W ten sposób zredukowaliśmy problem liczenia operacji \(\odot\) do mnożenia liczb binarnych długości \(O(n\log n)\). Mnożenie liczb binarnych długości \(k\) można wykonać w czasie \(O(k \log^2 k)\) za pomocą algorytmu Schönhage-Strassena, zatem koszt operacji \(\otimes\) to \(O(n \log^2 n )\). Stąd i z redukcji operacji \(\odot\) do \(\otimes\) wynika teza twierdzenia.
Dygresja: mnożenie liczb można wykonać trochę szybciej niż \(O(k \log^2 k)\) używając niezmiernie skomplikowanych algorytmów algebraicznych.