## 5 Edit Distance with Block Deletions
### Block Deletions with or without Character Insertions
Otherwise, if\(o_{k}\) is a character insertion of a character different than \(t_{m}\), then \(O\) is an optimal sequence of block deletions and character insertions which converts \(s_{1}\cdots s_{n-1}\) into \(t_{1}\cdots t_{m-1}\). * If \(o_{k}\) is a block deletion that ends with the character \(s_{n}\), then \(O^{\prime}=\left\{o_{1,\ldots}o_{k}\right\}\) is an optimal sequence of character insertions and block deletions which converts \(s_{1}\cdots s_{n-1}\) into \(T\). Otherwise, \(O\) is an optimal sequence of character insertions and block deletions which converts \(s_{1}\cdots s_{n-1}\) into \(t_{1}\cdots t_{m-1}\). **Proof:**  
1. If \(o_{k}\) is a block deletion, the proof is constructed the same as the proof of Lemma 1, only that the set of operations \(\left\{o_{1,\ldots}o_{k-1}\right\}\) is an optimal sequence of block deletions and character insertions. 2. If \(o_{k}\) is a character insertion: * If \(o_{k}\) is a character insertion of \(t_{m}\) then \(O^{\prime}=\left\{o_{1,\ldots}o_{k-1}\right\}\) is an optimal sequence of character insertions and block deletions which converts \(S\) into \(t_{1}\cdots t_{m-1}\). Otherwise, if \(O^{\prime}\) is not optimal, let \(\left\{\tilde{o}_{1,\ldots}\tilde{o}_{\ell}\right\}\) be an optimal sequence of block deletions and character insertions converting \(s_{1}\cdots s_{n-1}\) into \(T\) with cost less than \(O^{\prime}\).= Define \(\tilde{O}=\left\{\tilde{o}_{1,\ldots}\tilde{o}_{\ell},o_{k}\right\}\). The sequence \(\tilde{O}\) of block deletions and character insertions is a sequence which converts \(S\) into \(T\) with cost less than \(O\), which contradicts the optimality of \(O\). * If \(o_{k}\) is a character insertion of a character different than \(t_{m}\), and using the fact that there is no block deletion that involves \(s_{n}\) (otherwise it was treated in case 1), then \(s_{n}\) is equal to \(t_{m}\) and \(O\) is an optimal sequence of block deletions and character insertions 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,\ldots}\tilde{o}_{\ell}\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 and character insertions, \(<\)c,b,-\(>\)\[ed\left\langle c,b,-\right\rangle\left(s_{1}\cdots s_{i},t_{1}\cdots t_{j}\right)= \begin{bmatrix}1&\text{if}&j=0\\ j&\text{if}&i=0\\ \min\left[ed\left\langle c,b,-\right\rangle\left(s_{1}\cdots s_{i-1},t_{1} \cdots t_{j-1}\right),\right.\\ \left.ed\left\langle c,b,-\right\rangle\left(s_{1}\cdots s_{i-1},t_{1}\cdots t _{j}\right)+BD,\\ \left.ed\left\langle c,b,-\right\rangle\left(s_{1}\cdots s_{i},t_{1}\cdots t_{j -1}\right)+1\right]&\text{if}&s_{i}=t_{j}\\ \min\left[ed\left\langle c,b,-\right\rangle\left(s_{1}\cdots s_{i-1},t_{1} \cdots t_{j}\right)+BD,\\ \left.ed\left\langle c,b,-\right\rangle\left(s_{1}\cdots s_{i},t_{1}\cdots t_{j -1}\right)+1\right]&\text{if}&s_{i}\
eq t_{j}\end{bmatrix} \]  
where BD is a block deletion cost and is applied only for the character that opens the block. ```
functionDelete_Insert(\(S\),\(T\)) { A[0,0] \(\gets 0\) for\(1\leq i\leq n\)do\(A[i,0]\gets 1\) for\(1\leq j\leq m\)do\(A[0,j]\gets j\) for\(i=1\)to\(n\)do if\(s_{i}=t_{j}\)then\(\{\) if\(\text{during\_deletion}(i-1,j)\)then\(A[i/j]\leftarrow\min(A[i-1j-1],\)\(A[i-1,j],\)\(A[ij-1]+1)\) else\(A[i,j]\leftarrow\min(A[i-1,j-1],\)\(A[i-1,j]+1,\)\(A[ij-1]+1)\) } else\(\{\) if\(\text{(during\_deletion}(i-1,j))\) then\(A[ij]\leftarrow\min(A[i-1,j],\)\(A[ij-1]+1)\) else\(A[i,j]\leftarrow\min(A[i-1,j]+1,\)\(A[i,j-1]+1)\) } return\(A[n,m]\) }
```  
**Algorithm 3**Edit Distance with Block Deletions and Character Insertion.