# siEDM: An Efficient String Index and Search Algorithm for Edit Distance with Moves
## 6 Search Algorithm
### Improvement  
The siEDM approximately solves Problem 1 with the same guarantees presented in Theorem 1. Let \(X_{i}\in V(S)\) such that \(|val(X_{i})|>|Q|\). There are \(|Q|\)-grams formed by the string \(\textit{suf}(val(X_{i(i)}),\)\(|Q|-k)\textit{pre}(val(X_{r(i)}),k)\) with \(k=1,2,\ldots,(|Q|-1)\). Then, the variable \(X_{i}\) is said to _stab_ the \(|Q|\)-grams. The set of the \(|Q|\)-grams stabbed by \(X_{i}\) is denoted by \(\textit{itv}(X_{i})\). Let \(\textit{itv}(S)\) be the set of \(\textit{itv}(X_{i})\) for all \(X_{i}\) appearing in \(T(S)\). An important fact is that \(itv(S)\) includes any \(|Q|\)-gram in \(S\). Using this characteristic, we can reduce the search space.  
If a \(|Q|\)-gram \(R\) is in \(itv(X_{i})\), there exists a maximal subtree decomposition \(X_{i_{1}},X_{i_{2}},\ldots,X_{i_{m}}\). Then, the \(L_{1}\)-distance of \(F(Q)\) and \(\sum_{j=1}^{m}F(X_{i_{j}})\) guarantees the same upper bounds in the original ESP as follows.  
Theorem 2: Let \(R\in itv(X_{i})\) be a \(|Q|\)-gram on \(S\) and \(X_{i_{1}},X_{i_{2}},\ldots,X_{i_{m}}\) be its maximal subtree decomposition in the tree \(T(X_{i})\). Then, it holds that  
\[\|F(Q)-\sum_{j=1}^{m}F(X_{i_{j}})\|_{1}=O(\lg|Q|\lg^{*}|S|)d(Q,R)\]  
Proof: By Theorem 1, \(\|F(Q)-F(R)\|_{1}=O(\lg|Q|\lg^{*}|S|)d(Q,R)\). On the other hand, for an occurrence of \(R\) in \(S\), let \(T(X_{i})\) be the smallest subtree in \(T(S)\) containing the occurrence of \(R\), _i.e._, \(R\in itv(X_{i})\). For \(T(R)\) and \(T(X_{i})\), let \(s(R)\) and \(s(X_{i})\) be the sequences of the level 2 symbols in \(T(R)\) and \(T(X_{i})\), respectively. By the definition of the ESP, it holds that \(s(R)=\alpha\beta\gamma\) and \(s(X_{i})=\alpha^{\prime}\beta^{\prime}\) for some strings satisfying \(|\alpha a^{\prime}\gamma\gamma^{\prime}|=O(\lg^{*}|S|)|\), and this is true for the remaining string \(\beta\) iteratively. Thus, \(\|F(R)-F(X_{i})\|_{1}=O(\lg|R|\lg^{*}|S|)\) since the trees are balanced. Hence, by the equation  
\[\|F(Q)-\sum_{j=1}^{m}F(X_{i_{j}})\|_{1} =O(\lg|Q|\lg^{*}|S|)d(Q,R)+O(\lg|Q|\lg^{*}|S|)\] \[=O(\lg|Q|\lg^{*}|S|)d(Q,R)\]  
we obtain the approximation ratio.  
To further enhance the search efficiency, we present a lower bound of the \(L_{1}\)-distance between characteristic vectors, which can be used for reducing the search space.  
Theorem 3 (A lower bound \(\mu\)): _For any \(X_{i}\in V(S)\cup V(Q)\), the inequality \(\|F(S)-F(Q)\|_{1}\geq\mu(X_{i})\) holds where_  
\[\mu(X_{i})=\sum_{e\in V(S)\bigoplus V(Q)}F(X_{i})(e)\]  
Proof: The \(L_{1}\) distance between \(F(S)\) and \(F(Q)\) is divided into four classes of terms: (i) both members in \(F(S)\) and \(F(Q)\) are non-zero, (ii) both members in \(F(S)\) and \(F(Q)\) are zero, (iii) the members in \(F(S)\) and \(F(Q)\) are zero and non-zero, (iv) the members in \(F(S)\) and \(F(Q)\) are non-zero and zero, respectively. Terms consisting of class (iii) and (iv) can be written as \(\sum_{e\in V(S)\bigoplus V(Q)}F(S)(e)\), which is a lower bound of the \(L_{1}\)-distance. Thus, \(\|F(S)-F(Q)\|_{1}\geq\sum_{e\in V(S)\bigoplus V(Q)}F(S)(e)\).  
Theorem 4 (Monotonicity of \(\mu\)): _If a variable \(X_{i}\) derives \(X_{k}\), the inequality \(\mu(X_{i})\geq\mu(X_{k})\) holds._  
Proof: Every entry in \(F(X_{k})\) is less than or equal to the corresponding entry in \(F(X_{i})\). Thus, the inequality holds.