\section{Výpočet editačnej vzdialenosti}

Hľadanie približných výskytov vzoriek v texte je dôležité z viacerých pohľadov. Za všetky spomenieme napríklad biológiu, kde môže vzniknúť napr. mutácia v DNA, chyby v texte alebo odhaľovanie plagiatorstva.
Videli sme už vyhľadávanie s Hammingovou vzdialenosťou $d_H$ a algoritmus pre takéto vyhľadávanie s časovou zložitosťou $\mathcal{O}(nk)$.

\subsection{Editačná vzdialenosť}
\begin{defin}
  Editačná alebo Levenshteinova vzdialenosť $d_E$ je vzdialenosť, ktorá dovoľuje robiť tri operácie na reťazcoch: (Zápis $u \to v$ znamená, že operácia zmení reťazec $u$ na~reťazec $v$.)
  \begin{description}
  \item[substitúcia] $uav \to ubv$, kde $u,v \in \Sigma^*$ a $a,b \in \Sigma$,
  \item[inzercia] $uv \to uav$, kde $u,v \in \Sigma^*$ a $a \in \Sigma$, 
  \item[delécia] $uav \to uv$, kde $u,v \in \Sigma^*$ a $a \in \Sigma$.
  \end{description}
  Vzdialebnosť je definovaná
  $$
  d_E(S,T) = \textrm{najmenší počet operácií, ktoré transformujú $S$ na $T$.}
  $$
\end{defin}

\begin{priklad}\label{priklad:zmena}
  Majme reťazec $S = strom$. Vykonáme nasledovné operácie: zmaž štvrý znak (dostávame $strm$), vlož $a$ na tretie miesto (dostávame $starm$), zmeň piaty znak na $\textit{ý}$ (dostávame $star\textit{ý}$). Môžeme si tiež všimnúť, že slovo $strom$ na slovo $star\textrm{ý}$ nevieme prerobiť na menej ako tri operácie. Preto  $d_E(strom,star\textrm{ý}) = 3$.
\end{priklad}

Zamyslíme sa, aká môže byť najväčšia editačná vzdialenosť medzi dvoma reťazcami. Môžu sa líšiť v každom písmene, napríklad pre $a^n$ a $b^m$ to bude maximum ich dĺžok. (Musíme substituovať všetky písmená kratšieho slova na písmena dlhšieho a doplniť písmenká na koniec.) Naopak najmenšia editačná vzdialenosť reťazcov s dĺžkami $n$ a $m$ bude absolútna hodnota rozdielu $|n-m|$, pretože v najlepšom prípade je kratší reťazec podreťazcom dlhšieho, preto stačí dopísať chýbajúce písmenká.

\begin{defin}
Zarovnanie alebo alignment je dvojriadková tabuľka (matica) pozostávajúca z písmen reťazcov alebo pomlčiek. V prvom riadku je prvé slovo, v druhom druhé. (Pričom v oboch riadkoch môžu byť nejaké pomlčky.) Je zostavená tak, že pod seba napíšeme písmenká ktoré sa nezmenili alebo sa zmenili substitúciou. Tie písmená čo boli zmazané alebo vložené chceme mať v samostatných stĺpcoch, doplnené pomlčkami.
\end{defin}

\begin{table}[h]
  \begin{center}
  \begin{tabular}{c|c|c|c|c|c}
    s&t&{\bf -}&r&{\bf o}&{\bf m}\\
    \hline
    s&t&{\bf a}&r&{\bf -}&{\bf ý}
  \end{tabular}
\end{center}
  \caption{Zarovnanie pre operácie uvedené v príklade \ref{priklad:zmena}}\label{tab:zarovnanie}
\end{table}

Zodpovedajúce zarovnanie k príkladu \ref{priklad:zmena} je zobrazené v tabuľke \ref{tab:zarovnanie}. Zo zarovnania sa ľahko vypíše postupnosť krokov, ako zmeniť prvé slovo na druhé. Tiež vieme ľahko zrátať počet operácií -- tam kde sa naše dva riadky líšia. (V tabuľke \ref{tab:zarovnanie} vyznačené hrubo.) 

\begin{table}[h]
  \begin{center}
  \begin{tabular}{c|c|c|c|c}
    s&t&{\bf r}&{\bf o}&{\bf m}\\
    \hline
    s&t&{\bf a}&{\bf r}&{\bf ý}
  \end{tabular}
\end{center}
  \caption{Iné zarovnanie reťazcov z príkladu \ref{priklad:zmena}}\label{tab:zarovnanie2}
\end{table}

Na editačnú vzdialenosť sa môžeme pozerať aj ako na cenu najlpšieho zarovnania. iné zarovnanie tých slov je napríklad to zobrazené v tabuľke \ref{tab:zarovnanie2}.

\paragraph{Ako spočítať editačnú vzdialenosť} Použijeme dynamické programovanie. (Zrátame to pre podproblémy -- podreťazce -- a z toho pre celý reťazec, vypočítané hodnoty si budeme pamätať v tabuľke $A$.)

Podproblém $A[i,j] = d_E(S[1..i],T[1..j])$. Chceme zistiť $A[m,n]$, kde budeme mať uloženú editačnú vzdialenosť reťazcov $S$ a $T$.  

Začneme vypĺňať tabuľku od triviálnych prípadov. Platí $A[0,j]=j$, pretože do prvého reťazca musíme vložiť $j$ znakov. Rovnako platí $A[i,0] = i$, z toho istého dôvodu. Všeobecný prípad, hodnotu na políčku $A[i,j]$, môžeme vyrátať formulou
$$A[i,j] = \left\{ 
\begin{array}{ll}
  \min\left(A[i-1,j]+1,A[i,j-1]+1,A[i-1,j-1]\right) & \textrm{ak } S[i]=T[j],\\
  \min\left(A[i-1,j]+1,A[i,j-1]+1,A[i-1,j-1]+1\right)& \textrm{ak } S[i]\not=T[j].
\end{array}
\right.$$

Túto formulu môžeme odvôvodniť nasledovne. Uvažujme najlacnejšie zarovnanie. Ak sú poslednom znaku dve písmená, tak je to tretia zložka predchádzajúcej formuly, (použijeme substitúciu alebo nič,) ak je tam pomlčka, tak jedna z prvých dvoch zložiek. (Buď delécia alebo inzercia.)

\begin{verbatim}
for(i=0;i<=n;i++){
  for(j=0;j<=n;j++){
    vypocitaj A[i,j] podla rekurencie;
  }
}
\end{verbatim}

Výsledok je $d_E(S,T) = A[m,n]$.

\paragraph{Časová zložitosť} Je zjavne $\mathcal{O}(mn)$.

V niektorých aplikáciách chceme nielen zistiť editačnú vzdialenosť, ale aj ako premeníme jeden reťazec na druhý. (tj. chceme nájsť minimálne zarovnanie.) Preto si pri $A[i,j]$ môžeme pamatať, ako sme to dostali. (Je to v prvom prípade inzercia, v druhom delécia, v treťom substitúcia.) Budeme to robiť napríklad v poli $B[i,j]$, potom postupnosť krokov získame ``odzadu''. Graficky môžeme pole $B$ znázorniť ako šípky, pozri tabuľku \ref{obr:dynprog}.

\begin{table}[h]
\begin{minipage}[b]{0.5\linewidth}
\centering
\begin{center}
\begin{tabular}{c|c|c|c|c|c}
  & - & a & b & a & a \\
\hline
- & 0 & 1 & 2 & 3 & 4 \\
\hline
b & 1 & 1 & 1 & 2 & 3 \\
\hline
a & 2 & 1 & 2 & 1 & 2 \\
\hline
a & 3 & 2 & 2 & 2 & 1 \\
\hline
b & 4 & 3 & 2 & 3 & 2 \\
\end{tabular}
\end{center}
\caption{Pole $A$ k príkladu \ref{priklad:alg}.}\label{tab:dynprog}
\end{minipage}
\hspace{0.5cm}
\begin{minipage}[b]{0.5\linewidth}
\centering
  \centerline{\includegraphics{figures/l13-sipky.1}}
  \caption{Pole $B$ k príkladu \ref{priklad:alg}.}\label{obr:dynprog}
\end{minipage}
\end{table}

\begin{priklad}\label{priklad:alg}
  Majme reťazce $S = baab$, $T=abaa$. V tabuľke \ref{tab:dynprog} a v tabuľke \ref{obr:dynprog} vidíme hodnoty polí $A$ a $B$. Minimálne zarovnanie dostaneme, ak pôjdeme po šípkach v poli $B$ tak, že začneme na políčku $B[m,n]$. Pritom vodorovná šípka značí inzerciu, zvislá deléciu a diagonálna substitúciu alebo žiadnu operáciu. Preto reťazec $T$ dostaneme z reťazca $S$ vykonaním operácií: vlož $a$ na pozíciu 1, zmaž $b$ z poslednej pozície.
\end{priklad}



Vadí nám, že tento algoritmus používa kvadratickú pamäť. Výhodou je, že ak nás zaujíma iba hodnota editačnej vzdialenosti a nie zarovnanie, potrebujeme si pamätať len predchádzajúce hodnoty, takže nám stačí $\mathcal{O}(n)$ pamäť. Nabudúce bude algoritmus, ktorý bude asymptoticky rovnako rýchly, ale s lineárnou pamäťou aj pre výpis zarovnania.
