\section{Zrýchlenia dynamického programovania na výpočet editačnej 
vzdialenosti}

\subsection{Ukkonenon algoritmus: Zrýchlenie pre veľmi podobné reťazce}

Ukážeme Ukkonenov algoritmus z roku 1985, ktorý pracuje v čase $O(nD)$, kde
$D=d_E(S,T)$. Uvažujeme základnú definíciu editačnej vzdialenosti, v
ktorej má každá operácia cenu 1. V grafovej reprezentácii dynamického
programovania má každá zvislá a vodorovná hrana cenu 1 a uhlopriečne
hrany majú cenu 1 alebo 0 podľa toho, či sa príslušné znaky $S$ a $T$
zhodujú. Hľadáme najkratšiu cestu z $(0,0,)$ do $(m,n)$. Ak
$d_E(S,T)=D$, môžeme použiť najviac $D$ vodorovných alebo zvislých
hrán.

Očísľujme uhlopriečky v matici dynamického programovania (resp. v
grafe) tak, že uhlopriečka $k$ obsahuje políčka $A[i,j]$ pre $k=j-i$.
Optimálne zarovnanie začína na uhlopriečke 0. Každá uhlopriečna hrana
necháva číslo uhlopriečky rovnaké, každá zvislá a vodorovná ho mení o
jedna. Nakoľko najkratšia cesta obsahuje najviac $D$ vodorovných a
zvislých hrán, bude sa celá vyskytovať v páse uhlopriečok $-D,\dots,D$. 

\paragraph{Rozhodovací problém.}
Najskôr vyriešime rozhodovací problém, v ktorom máme dané reťazce $S$
a $T$ a hodnotu $k$ a chceme vedieť, či $d_E(S,T)\le k$. Uvažujme
všetky cesty z $(0,0)$ do $(m,n)$, ktoré nevybočia z pruhu uhlopriečok
$-k,\dots,k$. Z týchto ciest vieme nájsť najkratšiu jednoduchou
modifikáciou dynamického programovania, kde pre každý vrchol budeme v
rekurencii uvažovať len tých z troch predchodcov, ktorí sú vo vnútri
pruhu. V každom stĺpci matice počítame najviac $2k+1$ hodnôt, celková
zložitosť je teda $O(kn)$.

Ak nakoniec dostaneme hodnotu $A[m,n]\le k$, odpoveď na problém je
áno, lebo sme našli aspoň jedno zarovnanie s cenou menšou ako $k$.
Toto zarovnanie musí byť aj optimálne, lebo zarovnania, ktoré sme
neuvažovali (tie, ktoré vybočia z nášho pruhu), majú cenu väčšiu ako
$k$. Teda vieme, že $d_E(S,T) = A[m,n]$.

Ak naopak dostaneme hodnotu $A[m,n]>k$, odpoveď je nie, lebo všetky
zarovnania (v pruhu aj mimo pruhu) majú cenu väčšiu ako $k$. Súčasne
však nepoznáme cenu optimálneho zarovnania, vieme iba, že
$k<d_E(S,T)\le A[m,n]$, lebo optimálne zarovanie môže vyjsť mimo pruh.

\paragraph{Hľadanie hodnoty $D$.}
Ak vopred nepoznáme hodnotu $k$, ktorú by sme mohli použiť pri
rozhodovacom probléme, môžeme ju nájsť postupom podobným na binárne
vyhľadávanie. Začneme s hodnotou $k=1$ a vždy keď odpoveď na
rozhodovací problém je nie, hodnotu $k$ zdvojnásobíme. Keď narazíme na
prvé $k^*$, pre ktoré dostaneme odpoveď áno, môžeme skončiť, lebo
zároveň sme spočítali aj $D=d_E(S,T)$ a optimálne zarovnanie.  Vieme,
že $k^*/2<D\le k^*$ a teda $k^*< 2D$. Ak čas potrebný na rozhodovací
problém je najviac $ckn$ pre nejakú konštantu $c$, čas pre hľadanie
$D$ bude
$$\sum_{i=0}^{\log_2 k^*} c2^in < 2k^*cn <  4Dcn = O(Dn).$$

Hodnota $D$ je najviac $\max(m,n)$ a teda čas tohto algoritmu nebude
nikdy asymptotický horší ako čas základného dynamického programovania.
Môže však byť oveľa lepší pre veľmi podobné reťazce.

\subsection{Technika ``štyroch Rusov''}

Teraz predstavíme ďalšie zrýchlenie dynamického programovania na
výpočet editačnej vzdialenosti. Základná myšlienka je rozdeliť problém
na malé podproblémy, predpočítať riešenie každého možného podproblému
a potom použiť tieto predpočítané riešenia na zrýchlenie
algoritmu. Túto techniku vymysleli Arlazarov, Dinic, Kronrod and
Faradzev v roku 1970, na editačnú vzdialenosť ju adaptovali Masek a
Paterson v roku 1980. Bille and Farach-Colton (2008) tento prístup
rozšírili pre veľké abecedy.

%pouzitie na editacnu vzdialenost 
% Masek, Paterson A faster algorithm for computing string edit distances
%vseobecna abeceda Fast and compact regular expression matching Bille,Farach-Colton

Predpokladajme, že vstupné reťazce sú rovnako dlhé
$|S|=|T|=n$ a veľkosť abecedy je 2. Maticu $A$ dynamického
programovania rozdelíme na štvorce (bloky) veľkosti $t\times t$, tak aby sa
susedné bloky prekrývali jedným stĺpcom a jedným riadkom.  Každý
blok bude tvoriť jeden podproblém. Uvažujme blok s ľavým horným
rohom v políčku $(i,j)$. Vstupom pre podproblém bude prvý riadok a
prvý stĺpec bloku ako aj príslušné časti reťazcov $S$ a $T$, t.j.
dvojica vektorov $x_1=(A[i,j..j+t-1],A[i+1..i+t-1,j])$ a
$x_2=(S[i+1..i+t-1],T[j+1..j+t-1])$. Výstupom je vektor
$y=(A[i+t-1,j+1..j+t-1],A[i+1..i+t-2,j+t-1])$ obsahujúci posledný
riadok a stĺpec bloku. Uvedomme si, že vstup jednoznačne určuje
výstup, lebo pri výpočte vnútra bloku potrebujeme len hodnoty z
hranice bloku a podreťazce vstupných reťazcov v $x_2$. 

Všetkých možných podproblémov je $(n+1)^{2t-1}2^{2t-2}$, lebo vektor
$x_1$ má dĺžku $2t-1$ a každý jeho prvok je editačná vzdialenosť medzi
nejakými prefixami $S$ a $T$, čiže celé číslo od 0 do $n$. Podobne
vektor $x_2$ obsahuje $2t-2$ znakov zo vstupnej binárnej abecedy.
Tento počet je príliš velký a už pre $t=2$ by predpočítanie trvalo
dlhšie ako bežné dynamické programovanie. Potrebujeme zredukovať
veľkosť vstupu $x_1$. 

\begin{lema}
Susedné políčka v stĺpci alebo riadku matice $A$ sa
líšia najviac o 1.
\end{lema}

\paragraph{Dôkaz.} Uvažujme dve susedné políčka v riadku. Z definície 
$A[i,j]\le A[i,j-1]+1$, lebo existuje hrana dĺžky 1 z vrcholu
$(i,j-1)$ do $(i,j)$ a teda zo zarovnania $S[1..i]$ s $T[1..j-1]$
vieme vytvoriť zarovnanie $S[1..i]$ s $T[1..j]$. Podobne zo zarovnania
$S[1..i]$ s $T[1..j]$ chceme vytvoriť zarovnanie pre $S[1..i]$ s
$T[1..j-1]$. Odlíšime tri prípady podľa posledného stĺpca optimálneho
zarovnania $S[1..i]$ s $T[1..j]$:
\begin{itemize}
\item Ak posledný stĺpec obsahuje $T[j]$ zarovnaný s medzerou. Tento
  stĺpec môžeme vynechať a dostaneme tak zarovnanie s cenou o jedna
  nižšou. Teda máme $A[i,j-1]\le A[i,j]-1$. 
\item Ak posledný stĺpec obsahuje $S[i]$ a $T[j]$, vynecháme zo stĺpca $T[j]$. 
  Tým cena vzrastie o 1 alebo ostane taká istá, podľa toho, či 
  $S[i]=T[j]$ alebo nie. Teda máme $A[i,j-1]\le A[i,j]+1$.
\item Ak posledný stĺpec obsahuje $S[i]$ zarovnané s medzerou, nájdeme
  stĺpec obsahujúci $T[j]$ a z neho $T[j]$ zmažeme. Ak stĺpec ostane
  prázdny, zmažeme aj celý tento stĺpec. Táto zmena zase môže skóre buď nechať 
  rovnaké, znížiť alebo zvýšiť o 1.
\end{itemize}
V každom prípade teda platí, že $A[i,j]\ge A[i,j-1]-1$. Podobne môžeme 
tvrdenie dokázať pre stĺpec.

Táto lema nám dáva návod ako úspornejšie zakódovať vektor $x_1$:
pomocou hodnoty $A[i,j]\in \{0,1,\dots,n\}$ a vektoru $x'_1$ hodnôt
rozdielov medzi susednými hodnotami v prvom riadku resp. stĺpci
$A[i,j+k]-A[i,j+k-1]$ a $A[i+k,j]-A[i+k-1,j]\in \{0,1,-1\}$. Teda
možných vektorov $x_1$ je najviac $(n+1)3^{2t-2}$. Podobne zadefinujme
vektor $y'$ rozdielov na výstupe $A[i+t-1,j+k]-A[i+t-1,j+k-1]$,
$A[i+k,j+t-1]-A[i+k-1,j+t-1]$.

Teraz zmeníme definíciu podproblému tak, že nebudeme z $(x_1,x_2)$ počítať
$y$, ale z $(x'_1,x_2)$ budeme počítať $y'$ nasledovným postupom:
\begin{itemize}
\item Do ľavého horného políčka bloku dáme hodnotu 0 (namiesto
  $A[i,j]$, ktoré nepoznáme).
\item Z vektora rozdielov $x'_1$ spočítame prvý riadok a prvý stĺpec.
\item Pomocou dynamického programovania vyplníme zvyšok bloku. Políčko 
$(i+p,j+q)$ bude obsahovať hodnotu $A[i+p,j+q]-A[i,j]$.
\item Z posledného riadku a stĺpca spočítame vektor rozdielov $y'$, v 
ktorých člen $A[i,j]$ vypadne. 
\end{itemize}
Tento algoritmus trvá $O(t^2)$ pre každý blok daný vstupom $(x'_1,x_2)$ a 
máme $3^{2t-2}2^{2t-2}$ možných blokov. Teda celkový čas predspracovania je 
$O(t^2 6^{2t})$. Výsledky pre jednotlivé bloky uložíme do poľa indexovaného
vstupom prepočítaným na celé číslo. Pre daný vstup vieme v čase $O(t)$
spočítať index podproblému a nájsť riešenie v poli. 


Po predspracovaní algoritmus funguje nasledovne:
\begin{itemize}
\item Vyplň nultý riadok a stĺpec matice, spočítaj rozdiely medzi
  susednými políčkami.
\item Pre jednotlivé bloky matice nájdi vstupné rozdiely 
$x'_1$ spočítané v predchádzajúcich blokoch a v poli nájdi spočítané 
výstupné rozdiely.
\item Na konci spočítaj z rozdielov hodnoty v poslednom stĺci matice a 
vypíš $A[m,n]$.
\end{itemize}

Počet blokov je $n^2/t^2$, na každý blok potrebujeme čas $O(t)$. Teda
celkový čas je $O(n^2/t+t^26^{2t})$, čo pre $t=\log_6(n)/2$ je
$O(n^2/\log n)$. 

\paragraph{Poznámky.} Ak vieme vstup pre jeden blok uložiť do registra, 
nájdenie indexu riešenia sa dá spraviť v čase $O(1)$ a celková
zložitosť bude $O(n^2/\log^2 n)$. Algoritmus sa dá použiť aj pre
abecedy veľkosti väčšej ako 2, ale dostávame zložitosť
$O(n^2/\log_\sigma n)$. Naopak, algoritmus sa bez zmeny nedá použiť, ak
operáciam v definícii editačnej vzdialenosti priradíme všeobecné
váhy.


\subsection{Prehľad algoritmov na výpočet editačnej vzdialenosti}

\begin{center}
\begin{tabular}{llll}
\hline
Algoritmus          & Problém   & Čas              & Poznámka\\
\hline
Základné dyn. prog. & ľub. váhy & $O(mn)$          & \\
Hirschbergov alg.   & ľub. váhy & $O(mn)$          & $O(n)$ pamäť\\
Hunt-Szymanski      & lcs       & $O((n+r)\log n)$ & $0\le r \le mn$ \\
Ukkonenov alg.      & $d_E$/lcs & $O(nD)$          & $0\le D \le \max(m,n)$ \\
Four Russians       & $d_E$/lcs & $O(mn/\log n)$   & $\sigma=O(1)$\\
\hline
\end{tabular}
\end{center}

Algoritmy Hunt-Szymanski a Ukkonenov sú adaptívne, lebo sa
adaptujú na vlastnosti vstupu: hoci v najhoršom prípade ich čas je
rovnaký alebo ešte horší ako čas základného algoritmu, pre niektoré
triedy vstupov bežia oveľa rýchlejšie.

