Na dynamické programovanie sa môžeme pozerať aj ako na hľadanie najkratšej cesty
v acyklickom grafe (viď obr. \ref{l14_edit_distance_graph},
\ref{l14_shortest_to_ij}).

%pic1
\begin{figure}[h]
	\caption{Reprezentácia editačnej vzdialenosti grafom}
	\centering\includegraphics{figures/l14.1}
	\label{l14_edit_distance_graph}
\end{figure}

\begin{figure}[h]
	\centering\includegraphics{figures/l14.2}
	\caption{Najkratšia cesta z $(0,0)$ do $(i,j)$}
	\label{l14_shortest_to_ij}
\end{figure}

Najkratšie hrany v grafe sa dajú počítať napr. Dijkstrovým algoritmom. Čo ale
skutočne hľadáme, je najkratšia cesta v orientovanom \emph{acyklickom} grafe --
Dijkstru nutne nepotrebujeme, stačí nám dynamické programovanie:
\begin{enumerate}
\item topologicky si zoradíme hrany
\item pre vrcholy $i$ a $j$ bude $A[i,j]$ dĺžka najkratšej cesty z $(0,0)$ do
$(i,j)$. Toto vieme spočítať dynamickým programovaním -- pozeráme sa na predkov
aktuálneho vrcholu, a hodnotu získame ako $$A[i,j] = \min \{A[i',j'] +
w((i',j'),(i,j)) \mid (i',j'), (i,j) \in E\}$$. 

\end{enumerate}
\par Máme sľúbené dynamické programovanie, ktoré funguje v čase $O(mn)$ a pamäti
$O(mn)$. Navyše, pokiaľ chceme len $d_E(S,T)$, stačí nám pamäť len $O(n+m)$
(pamätáme si iba 2 riadky $A$). Ak chceme vypísať zarovnanie (postupnosť
operácií), potrebujeme tabuľku $B$ o rozmeroch pôvodnej tabuľky $A$.

\subsection{Hirschbergov algoritmus (1975)}

%novy text
Tento algoritmus sa od klasického výpočtu editačnej vzdialenosti líši tým,
že potrebuje pamäť iba $O(n+m)$ namiesti $O(nm)$. 
%stary text
Rozdiely oproti predchádzajúcemu algoritmu
raz prejdem celú maticu a spočítam všetky $A$. Zapamätám si, kde moja cesta
prejde cez stredný riadok matice 
-- pričom ju počítam tak, že si pamätám iba dva
riadky. 


Stredný riadok matice označme $k$-ty. Zavedieme si zovšeobecnené pole $B_k[i,j]$
-- najväčší index v riadku $k$, cez ktorý prechádza najkratšia cesta z $(0,0)$
do $(i,j)$. 
%novy text
Hodnoty $B_k[i,j]$ počítame podobne ako hodnoty $B$. Konkrétne pre $i>k$ máme
\begin{enumerate}
\item ak $A[i,j] = A[i-1,j-1]+w(S[i],T[j])$, potom $B_k[i,j]=B_k[i-1,j-1]$.
\item ak $A[i,j]=A[i-1,j]+1$, potom $B_k[i,j]=B_k[i-1,j]$.
\item ak $A[i,j]=A[i,j-1]+1$, potom $B_k[i,j]=B_k[i,j-1]$ 
\end{enumerate}
Pre $i=k$ nastavíme $B_k[i,j]=j$. 

%stary text
Ak už poznáme $A[i-1,*]$ a $B_k[i-1,*]$, vieme spočítať $A[i,*]$ aj $B_k[i,*]$.

Nech $k'=B_k[m,n]$. Potom v optimálnom zarovnaní sa 
$S[1..k]$ zarovná s $T[1..k']$ a $S[k+1..m]$  s $T[k'+1..n]$.
Toto použijeme na rekurzívny algoritmus na výpočet zarovnania:

\begin{lstlisting}
optA(l1, r1, l2, r2) { 
    // zarovnaj S[l1..r1] a T[l2..r2]
    if(r1-l1 <= 1 ||  r2-l2 <=1) 
        vyries pomocou dynamickeho programovania
    else {
        k=(r-l+1)/2;
        for (i=0; i<=k; i++) 
           pocitaj A[i,*] z A[i-1,*]
        for (i=k+1; i<=r-l+1; i++) 
           pocitaj A[i,*], B_k[i,*] z A[i-1,*], B_k[i-1,*]
        k2=B_k[r1-l1-1,r2-l2-1];
        optA(l1, l1+k-1, l2, l2+k2-1); 
        optA(l1+k, r2, l2+k2, r2); 
    }
}
\end{lstlisting}

Označme si $N=nm$ (súčin dĺžky dvoch daných reťazcov). Na hornej
úrovni rekurzie spúšťame dynamické programovanie pre celú maticu -- čas bude
teda $\leq c\cdot N$. Teraz vzniknú dva podproblémy -- označme ich $N_1$ a
$N_2$ (obr. \ref{l14_subproblems}):
$$N_1 = (k-l+1)(k'-l'+1)$$
$$N_2 = (r-k)(r'-k')$$
$$T(N)\leq T(N_1)+T(N_2)+c\cdot N$$.

%pic4.
\begin{figure}[h]
	\centering\includegraphics{figures/l14.5}
	\caption{Vzniknuté podproblémy pri výpočte hodnôt matice}
	\label{l14_subproblems}
\end{figure}

Platí, že $N_1 + N_2 = \frac{1}{2}N$.
Na hlavnej úrovni rekurzie máme problém veľkosti $N$, ktorý sa rozpadne na na
menšie problémy (obr. \ref{l14_rec_tree}).

%pic 5

\begin{figure}[h]
	\centering\includegraphics{figures/l14.6}
	\caption{Strom rekurzie pre výpočet matice}
	\label{l14_rec_tree}
\end{figure}

Výška vzniknutého stromu bude $\log_2 m$. 

$$T(n)=c\cdot N + \frac{1}{2}c\cdot N+ \frac{1}{4}c\cdot N + \ldots \leq c\cdot N
\sum_{i=0}^{\infty}\left(\frac{1}{2}\right)^i$$
$$ = \underbrace{2\cdot N}_{norm. dyn. prog}$$

V priemere každé políčko vyplním dvakrát, teda čas $O(mn)$ je zhruba
dvojnásobný. Pamäťová zložitosť -- potrebujeme $2$ riadky z oboch matíc $A$,
$B_k$ ($O(n))$, zásobník $O(\log m)$, vstup $O(n+m)$, výstup $O(n+m)$.
Celková pamäť je $O(n+m)$.

\subsection{Zovšeobecnené editačné vzdialenosti}
\paragraph{Definícia} \emph{Zovšeobecnená editačná vzdialenosť}, označujeme
$d'_E$, je editačná vzdialenosť, ktorá má ku každej operácii priradenú cenu:

\begin{itemize}
	\item $w_s(a,b)$ -- substitúcia $a$ za $b$
	\item $w_d(a)$ -- zmazanie $a$
	\item $w_i(a)$ -- vloženie $a$
\end{itemize}

\par Ak máme dvojpísmenkové reťazce $ab$ a $ba$, kde ceny budú
$w_d(a)=w_i(a)=1$, $w_d(b)=w_i(b)=w_s(a,b)=w_s(b,a)=2$ (obr.
\ref{l14_two_letter_string_graph}).
%pic6


\begin{figure}[h]
	\centering\includegraphics{figures/l14.7}
	\caption{Graf pre dvojpísmenkové reťazce $ab$ a $ba$}
	\label{l14_two_letter_string_graph}
\end{figure}


$$
A[i,j] = \min
\left\{\begin{array}{l}
	A[i-1,j-1]+w_s(S[i],T[j]) \\
	A[i-1,j]+w_d(S[i]) \\
	A[i,j-1]+w_i(T[i]) \\
\end{array}
\right.
$$

$d_E(S,T)$ je metrika:
\begin{itemize}
	\item $d_E(S,T) \geq 0$
	\item $d_E(S,T) = 0 \iff S = T$
	\item $d_E(S,T) = d_E(T,S)$ 
	\item $d_E(S,T) \leq d_E(S,U) + d_E(U,T)$
\end{itemize}

\paragraph{Príklad} 
\begin{enumerate}
\item $w_d(a)=1$, $w_i(a)=2$, $d'_E(\varepsilon,a) \neq
d'E(a,\varepsilon)$

\item $w_s(a,b)=1, w_s(b,c)=1, w_s(a,c)=3$. $a \rightarrow b \rightarrow c = 2$
\end{enumerate}

\paragraph{Voľba váhovacej funkcie na hľadanie optimálneho zarovnania.}
Pri váhovanej editačnej vzdialenosti sme hľadali zarovnanie s minimálnou cenou, pričom ceny stĺpcov boli nasledujúce:

\begin{table}[h]
	\centering
	\begin{tabular}{|l|l|l|l|}

\hline

 & a & a & a-\\%
 & a & b & -a\\%
 skóre:& 0 & $> 0$ & $> 0$ \\%
\hline
	\end{tabular}
\end{table}

Môžeme však namiesto vzdialenosti hľadať podobnosť a potom budeme hľadať zarovnanie s maximálnou cenou, kde ceny stĺpcov sú takéto:

\begin{table}[h]
	\centering
	\begin{tabular}{|l|l|l|l|}

\hline

 & a & a & a-\\%
 & a & b & -a\\%
 skóre:& 0 & $> 0$ & $> 0$ \\%
\hline
	\end{tabular}
\caption{príklad typického ohodnotenia}
\end{table}

Uvažujme reťazec "acba" a "abca" a váhovaciu funkciu $w$ spĺňajúcu podmienky:
\begin{itemize}
    \item $w(x,x)=0$
    \item $w(x,y)=w(y,x)$
    \item $w(x,y) \geq 0$
\end{itemize}

Optimálne zarovnania môžu vyzerať napríklad nasledovne:

\begin{equation}
    \begin{array}{llll}
    a&c&b&a\\
    a&c&b&a\\
    \end{array}
    \left \}
        2w(b,c)
    \right.
\end{equation}

\begin{equation}
    \begin{array}{lllll}
    a&c&b&-&a\\
    a&-&c&b&a\\
    \end{array}
    \left \}
        2w(c,-)
    \right.
\end{equation}

\begin{equation}
    \begin{array}{lllll}
    a&c&b&a&-\\
    -&a&b&c&a\\
    \end{array}
    \left \}
        2w(a,-) + 2w(a,c)
    \right.
\end{equation}
Na uvedených príkladoch si môžeme všimnúť, že podľa nastavenia váh môžu byť rôzne zarovnania optimálne.


\subsection{Podobnosť reťazcov}
Ak sú reťazce tie isté, majú vysokú podobnosť.

\paragraph{Definícia} $s(a,b)$ -- podobnosť znakov, kde $a, b \in \Sigma \cup
\{-\}$ (tab. \ref{l14_string_similarity_ex}).


\begin{table}[h]
\centering\begin{tabular}{|l|l|l|}
\hline
a & -- & a \\
\hline
-- & a & b \\
\hline
s(a,--) & s(--,a) & s(a,b) \\
\hline
%pic7
\end{tabular}
\caption{Príklad podobnosti reťazcov}
\label{l14_string_similarity_ex}
\end{table}

\paragraph{Definícia} \emph{Cena zarovnania} je súčet podobností znakov v stĺpcoch.
$s(S,T)$ je maximálna cena ich zarovnania.

\paragraph{Príklad}  %pic8
Hľadáme najdlhšiu cestu v grafe z $(0,0)$ do $(i,j)$ -- v normálnom grafe je to
ťažké, ale keďže náš graf je acyklický, môžeme použiť dynamické programovanie
(obr. \ref{l14_string_similarity_graph}).

\begin{figure}[h]
	\centering\includegraphics{figures/l14.8}
	\caption{Príklad grafu pri hľadaní podobnosti reťazcov}
	\label{l14_string_similarity_graph}
\end{figure}

\par Keďže chceme podobnosť, podobnosť medzi rovnakými znakmi je zvyčajne $0$,
medzi rôznymi nižšia:

$$
\begin{array}{lll}
s(a,a) &>& 0	\\
s(a,b) &<& 0, a \neq b	\\
\end{array}
$$

\paragraph{Príklad}
$$
\begin{array}{lll}
s(a,a) &=& 1, a \in \Sigma	\\
s(a,b) &=& -1, a \neq b, a,b \in \Sigma \cup \{-\}	\\
\end{array}
$$
(tab. \ref{l14_alignment1})%pic9 

\begin{table}[h]
	\centering\begin{tabular}{ccccc}
		--&b&a&a&b \\
		a&b&a&a&-- \\
		\hline
		$-1$ & 1 & 1 & 1 & $-1$ \\
	\end{tabular}
	\caption{Príklad zarovnania}
	\label{l14_alignment1}
\end{table}
\paragraph{Príklad}
$$
\begin{array}{lll}
s(a,a) &=& 0\\
s(a,b) &=& -1\\
s(S,T) &=& -d(S,T)\\
\end{array}
$$

\paragraph{Príklad}
$$
\begin{array}{lll}
s(a,a) &=& 1	\\
s(a,b) &=& 0	\\
\end{array}
$$

Pri tejto definícii dostávame 
$s(S,T)=$ dĺžka najdlhšej spoločnej podpostupnosti $S$ a $T$.
