## 5 Edit Distance with Block Deletions
### Block Deletions with or without Character Insertions
If the characters \(s_{i}\) and \(t_{j}\) are identical, the cost of converting \(s_{1}\cdots s_{i}\) into \(t_{1}\cdots t_{j}\) is equal to converting \(s_{1}\cdots s_{i-1}\) into \(t_{1}\cdots t_{j-1}\), unless it is cheaper to apply a block deletion to the character \(s_{i}\). The character \(s_{i}\) can be deleted among other characters, and the cost of a block deletion is constant, no matter how many characters are deleted. ```
functionDelete(\(S\),\(T\)) {  A[0,0] \(\leftarrow\) 0 for\(1\leq i\leq n\)do\(A[i,0]\gets 1\) for\(1\leq j\leq m\)do\(A[0,j]\leftarrow\infty\) for\(i=1\)to\(n\)do if\(s_{i}=t_{j}\)then\(\{\) ifduring_deletion(\(i-1\),\(j\)) then\(A[i,j]\leftarrow\min(A[i-1\),\(A[i-1\),\(j\)]) else\(A[i,j]\leftarrow\min(A[i-1\),\(j-1],\(A[i-1\),\(j]+1)\) } else\(\{\) if(during_deletion(\(i-1\),\(j\))) then\(A[i,j]\gets A[i-1\),\(j\)] else\(A[i,j]\gets A[i-1\),\(j]+1\) } return\(A[n\),\(m]\) }
```  
**Algorithm 2**Edit distance with block deletion. Two cases are distinguished, the case for which its previous character was deleted, and the case its previous character was not deleted. In the former case there is no new charge for deleting \(s_{i}\) since the block deletion is charged by the first character of the block. In this case \(A[ij]\) has the same cost as \(A[i-1j]\). Otherwise, it is worthwhile starting a block deletion with \(s_{i}\), charging the first character of the block. In this case \(A[ij]\) is equal to \(A[i-1j]+1\) (we assume that \(\infty+1=\infty\)). If the characters \(s_{i}\) and \(t_{j}\) are not identical, \(s_{i}\) should be deleted. In order to determine the cost, it has to be checked if \(s_{i}\) shall be the first character of a block deletion or not, as done previously. Since the _during_deletion_ function runs in linear time in the size of \(S\), the total running time of the edit distance with block deletion algorithm is \(O(n^{2}\ m)\). Running Algorithm 2 on the above example, \(S=b\mathit{cxyabczfdlmeffj}\) and \(T=abcdef\), produces Figure 1a. The optimal path from the bottom right cell (corresponding to \(S\) and \(T\)) to the upper left cell (corresponding to \(S=\varepsilon\) and \(T=\varepsilon\)) is illustrated by gray colored cells. The number of block deletions is 4, and the deleted blocks are \(\{b\mathit{cxy},\mathit{zf},\mathit{lm},\mathit{ij}\}\). The block deletion problem is now extended to include character insertions, and requires small modifications to the algorithm presented in Algorithm 2. An optimal solution to the edit distance problem of character insertions and block deletions will not insert a character \(c\) into \(S\) followed by a block deletion that includes \(c\), since the insertion of \(c\) is unnecessary. Thus, block deletions and character insertions can be ordered so that all insertions follow block deletions. The following lemma refers to the case of character insertions and block deletions, but does not separate them, and considers both operations in every step, so that the two dimension table is traversed only once. The lemma is followed by a recurrence formula which is the basis of the polynomial time dynamic programming algorithm presented in Algorithm 3. Figure 1: Edit distance Example: (**a**) with block deletion for \(S=b\mathit{cxyabczfdlmeffj}\) and \(T=abcdef\), (**b**) with character insertions and block deletion for \(S=b\mathit{cxyabczfdlmeffj}\) and \(T=abcdef\). **Lemma 2:**  
Let \(S=s_{1}\cdots s_{n}\) and \(T=t_{1}\cdots t_{m}\) be two strings of lengths \(n\) and \(m\), respectively, and let \(O=\left\{o_{1,\ldots}o_{k}\right\}\) be an optimal sequence of block deletions and character insertions which converts \(S\) into \(T\). * If \(o_{k}\) is a character insertion: then if it is an insert of the character \(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}\).