# siEDM: An Efficient String Index and Search Algorithm for Edit Distance with Moves
## 6 Search Algorithm
### Candidate Finding  
By Theorems 2, 3 and 4, the task of the algorithm is reduced to finding a maximal subtree decomposition \((X_{i_{1}},X_{i_{2}},\ldots,X_{i_{m}})\) within \(X_{i}\). Given a threshold \(\tau\geq 0\), for each \(|Q|\)-gram in \(itv(S)\), the algorithm finds the _candidate_: the maximal subtree decomposition \((X_{i_{1}},X_{i_{2}},\ldots,X_{i_{m}})\) satisfying \(\mu(X_{i_{1}})+\mu(X_{i_{2}})+\cdots+\mu(X_{i_{m}})\leq\tau\).  
Figure 4: Illustration of candidate finding and \(L_{1}\)-distance computation.  
For an \(X_{i}\) and an occurrence of some \(|Q|\)-gram in \(\mathit{itv}(X_{i})\), the \(|Q|\)-gram is formed by the expression \(\mathit{suf}(val(X_{l(i)}),|Q|-k)\mathit{pre}(val(X_{r(i)}),k)\) for a \(k\) (\(1\leq k\leq|Q|-1\)). The algorithm computes the maximal subtree decompositions \((x_{1},x_{2},\ldots,x_{p})\) covering \(\mathit{suf}(val(X_{l(i)}),|Q|-k)\) and \((y_{1},y_{2},\ldots,y_{q})\) covering \(\mathit{pre}(val(X_{r(i)}),k)\), and outputs \((x_{1},\ldots,x_{p},y_{1},\ldots,y_{q})\) covering the \(|Q|\)-gram when \(\sum_{1\leq i\leq p}\mu(x_{i})+\sum_{1\leq i\leq q}\mu(y_{i})\leq\tau\). We illustrate the computation of candidates satisfying \(\mu(X_{i_{1}})+\mu(X_{i_{2}})+\cdots+\mu(X_{i_{n}})\leq\tau\) in Figure 4 and show the pseudo-code in Algorithm 1.  
Applying all variables to Algorithm 1 enables us to find the candidates covering all solutions. There are no possibilities for missing any \(|Q|\)-grams in \(\mathit{itv}(S)\) such that the \(L_{1}\)-distances between their characteristic vectors and \(F(Q)\) are at most \(\tau\), _i.e._, false negatives. The set may include a false positive, _i.e._, the solution set encodes a \(|Q|\)-gram such that the \(L_{1}\)-distance between its characteristic vector and \(F(Q)\) is more than \(\tau\). However, false positives are efficiently removed by computing the \(L_{1}\)-distance \(\|F(Q)-\sum_{j=1}^{m}F(X_{i_{j}})\|_{1}\) as a post-processing.  
The computation time of FindCandidates is \(O(n|Q|\lg\lg(n+\sigma)(\lg|S|+\lg|Q|))\).  
Proof.: Because the height of the ESP-tree is \(O(\lg|S|)\), for each variable \(X\), the number of visited nodes is \(O(\lg|Q|+\lg|S|)\). The computation time of \(\mathit{LeftChild}(X)\) and \(\mathit{RightChild}(X)\) is \(O(\lg\lg(n+\sigma))\), and the time of FindLeft and FindRight is \(O(|Q|\lg\lg(n+\sigma)(\lg|S|+\lg|Q|))\). Thus, for \(n\) iterations of the functions, the total computation time is \(O(n|Q|\lg\lg(n+\sigma)(\lg|S|+\lg|Q|))\).  
```
1:functionFindCandidates(X,Q,\(\tau\))
2:for\(j=1,2,\ldots,|Q|\)do
3:\(k\leftarrow\emptyset\)\(q_{i}\leftarrow\textsc{FindLeftChild}(X),|Q|-j,0,R)\)\(\triangleright\) Initialize solution set
4:\(q_{i}\leftarrow\textsc{FindLeftChild}(X),|Q|-j,0,R)\)\(\triangleright\) for left child
5:\(q_{2}\leftarrow\textsc{FindRightChild}(X),j,0,R)\)\(\triangleright\) for right child
6:if\(q_{1}=0\) and \(q_{2}=0\)then
7: Output \(R\)
8:functionFindLeft(X,\(q,d,R\))
9:if\(d\succ\) time
10:return \(\infty\)
11:elseif\(q=0\)then
12:return \(\infty\)
13:elseif\(X\subseteq\textbf{then}\)
14:\(d\gets d+1\) if\(X\
ot\in V(Q)\)
15:\(R\gets R\cup(X)\)
16:return \(q-1\)
17:elseif\(|val(X)|<q\)then
18:\(d\gets d+\mu X\)
19:\(R\gets R\cup(X)\)
20:return \(q-1\)
21:\(q^{\prime}\leftarrow\textsc{FindLeftChild}(X),q,d,R)\)
22:if\(q^{\prime}\
eq 0\)then
23:returnFindLeft(LeftChild\((X,q^{\prime},d,R)\)
24:functionFindRight(X,\(q,d,R\))
25:if\(d>\textbf{then}\)
26:return \(\infty\)
27:elseif\(q=0\)then
28:return \(0\)
29:elseif\(X\in\textbf{then}\)
30:\(d\gets d+1\) if\(X\
ot\in V(Q)\)
31:\(R\gets R\cup(X)\)
32:return \(q-1\)
33:elseif\(|val(X)|<q\)then
34:\(d\gets d+|u|X\)
35:\(R\gets R\cup(X)\)
36:return \(q-|val(X)|\)
37:\(q^{\prime}\leftarrow\textsc{FindLeftChild}(X),q,d,R)\)
38:if\(q^{\prime}\
eq 0\)then
39:returnFindRight(RightChild\((X),q^{\prime},d,R\))
```  
**Algorithm 1** to output the candidate \(R\subseteq V(S)\) for \(X\in V(S)\), a query pattern \(Q\) and a distance threshold \(\tau\).