## 5 Edit Distance with Block Deletions
### Block Deletions with Character Moves  
We now consider the minimum number of block deletions, character insertions and character moves applied to \(S\) in order to attain \(T\). We use the dynamic programming algorithm introduced in the previous section taking into account character _moves_. A character move is an insert and a delete of the same character. Therefore, when performing dynamic programming, we try to reduce the cost by exchanging insertions and deletions with moves. We first consider the case of character deletions, character insertions, and character moves for general costs. Replacing the character deletion with block deletions is considered for uniform costs and is solved using dynamic programming. [PERSON] and [PERSON] [4]_showed_ that in the case of uniform costs of character insertions, character deletions and character moves, the minimal edit distance occurs in any optimal path transforming \(S\) to \(T\) of the traditional edit distance. We now generalize this to all cases. We use the following notations: \(P\) and \(P^{r}\) denote paths in a constructed dynamic table, starting at the left most upper cell and ending at the right lower cell (the final cell). \(I_{\sigma}^{P}/D_{\sigma}^{P}\) denote the number of character insertions and character deletions of \(\sigma\in\Sigma\), when converting \(S\) into \(T\) in path \(P\), and \(c(x)\) denotes the cost of operation \(x\), where \(x\) is either an insert character or a delete character or a move character. The traditional edit distance, including only character insertions and character deletions, is denoted by \(ed\), and the edit distance of \(S\) and \(T\), including character moves is denoted by \(edm\). Thus, \(ed^{P}\) and \(edm^{P}\) refer to paths in the traditional and move edit distance, respectively, _i.e._, if path \(P\) in the model of edit distance with moves includes both an insertion and a deletion of some character \(\sigma\), the cost is calculated as the cost of a move, subtracting the cost of a delete and an insert. **Fact:** For any two paths \(P\) and \(P^{r}\) and every \(\sigma\in\Sigma\),  
\[|\,I_{\sigma}^{P}-D_{\sigma}^{P}\models|\,I_{\sigma}^{P^{r}}-D_{\sigma}^{P^{ r}}\,| \tag{1}\]  
The proof appears in Shapira and Storer [4], and is included here for completeness. **Proof:** Denote by \(n_{\sigma}^{S}\) and \(n_{\sigma}^{T}\) the number of appearances of a character \(\sigma\) in the strings \(S\) and \(T\) respectively. For any path \(P\) which converts \(S\) into \(T\), \(|\,I_{\sigma}^{P}-D_{\sigma}^{P}\models|\,n_{\sigma}^{S}-n_{\sigma}^{T}\,|\). The following lemma only considers the edit distance problem with character insertions, character deletions and character moves. Character moves are irrelevant unless the cost of a move is cheaper than the cost of a character insert and the cost of a character delete. Then block deletion is added to the set of operations, and a dynamic programming algorithm is presented, which is optimal under the assumption of unit costs. **Lemma 3**. : For any positive costs of character insertion, character deletion, and character move, denoted \(c(insert)\), \(c(delete)\) and \(c(move)\) respectively, such that \(c(move)<c(insert)+c(delete)\), the minimal edit distance including character moves can be reconstructed from **every** optimal path of the traditional edit-distance. **Proof:** A character move is deleting the character from its source location and inserting it again at its destination.