## 5 Edit Distance with Block Deletions
### Block Deletions with or without Character Insertions
Define \(\tilde{o}_{i}\) to be a block deletion of the continues substring starting with characters deleted by \(\tilde{o}_{i}\) concatenated to the characters deleted by \(o_{k}\), and let \(\tilde{O}=\left\{\tilde{o}_{{}_{1\cdots\tilde{o}_{i-1}}},\tilde{o}_{i}\right\}\). The sequence \(\tilde{O}\) of block deletions includes \(i\leq\ell<k\) block deletions, which converts \(S\) into \(T\), contradicting the optimality of \(O\). * Assume that \(o_{k}\) does not end with the character \(s_{n}\):
* In this case \(s_{n}\) is equal to \(t_{m}\), and \(O\) is also an optimal sequence of block deletions which converts \(s_{1}\cdots s_{n-1}\) into \(t_{1}\cdots t_{m-1}\). Otherwise, if \(O\) is not optimal, let \(\tilde{O}=\left\{\tilde{o}_{{}_{1\cdots\tilde{o}_{t}}}\right\}\) be an optimal sequence of block deletions which converts \(s_{1}\cdots s_{n-1}\) into \(t_{1}\cdots t_{m-1}\) with cost less than \(O\). Then \(\tilde{O}\) is a sequence of block deletions which converts \(S\) into \(T\) with cost less than \(O\), which contradicts the optimality of \(O\). The last lemma implies the following recurrence formula for the edit distance problem with block deletions \(<\),b,\(>\),  
\[ed\left\langle-,b,-\right\rangle\left(s_{1}\cdots s_{i},t_{1}\cdots t_{j} \right)=\left[ \begin{array}{ccc}1&\text{if}&j=0\\ \infty&\text{if}&i=0\\ \min\left(\begin{array}{ccc}ed\left\langle-,b,-\right\rangle\left(s_{1} \cdots s_{i-1},t_{1}\cdots t_{j-1}\right),\\ ed\left\langle-,b,-\right\rangle\left(s_{1}\cdots s_{i-1},t_{1}\cdots t_{j} \right)+BD\end{array}\right)&\text{if}&s_{i}=t_{j}\\ ed\left\langle-,b,-\right\rangle\left(s_{1}\cdots s_{i-1},t_{1}\cdots t_{j} \right)+BD&\text{if}&s_{i}\
eq t_{j}\end{array} \right.\]  
where BD is a block deletion cost which is 1 for the character that opens the block and 0 otherwise. The dynamic programming algorithm is given in Algorithm 2. It uses a table \(A[ij]\), where rows correspond to \(S\) and columns correspond to \(T\). An assistant function, _During_Deletion_, is given in Algorithm 1. It receives the current cell in the dynamic programming table, \(A\), indexed by \((ij)\) and returns whether the cheapest sequence of operations converting \(s_{1}\cdots s_{i}\) into \(t_{1}\cdots t_{j}\) ends with a block deletion, _i.e._, whether \(A[ij]=A[i-1j]+1\) (\(s_{i}\) starts a block deletion) or \(A[ij]=A[i-1j]\) (\(s_{i}\) is an internal character of a block deletion). In the later case it should be verified that there exists an index \(0<i_{0}<i\) such that \(s_{i_{\epsilon}}\) starts a block deletion, _i.e._, such that \(A[i_{0}j]=A[i-1j]+1\). If \(s_{i+1}\) follows a block deletion, there is no need in recharging a cost of a block deletion if \(s_{i+1}\) should be deleted too, it could be deleted \"for free\" with the cost applied to the first character, \(s_{i_{\epsilon}}\), of the block deletion. The _Delete_ function presented in Algorithm 2 is given two strings \(S\) and \(T\) of lengths \(n\) and \(m\), respectively, and returns the minimum number of block deletions applied to \(S\) in order to convert it into \(T\). If both strings are empty there is no cost to convert \(S\) into \(T\). If only \(S\) is empty, the cost is infinity, since block deletions are applied to \(S\). If T is empty, the cost is 1 since a single block deletion of the entire string \(S\) converts it into \(T\). ```
functionDuring_Deletion(\(i\)) {  while (\(i>1\)) and (A[\(i\)] == A[\(i-1\),\(j\)]) \(i\)-;  return ((\(i\
eq 0\)) and (A[\(i\)] == A[\(i-1\),\(j\)] + 1)) }
```  
**Algorithm 1**During_Deletion function--returns whether cell (\(i\),\(j\)) is involved in a block deletion operation. After the dynamic programming table is initialized, the cost of converting \(s_{1}\cdots s_{i}\) into \(t_{1}\cdots t_{j}\) is calculated and stored in cell \(A[i\),\(j\)] of the dynamic programming table.