# siEDM: An Efficient String Index and Search Algorithm for Edit Distance with Moves
## 5 Index Structure for ESP-Trees  
### Efficient Encoding Scheme  
siEDM encodes an ESP-tree built from a string for fast query searches. This encoding scheme sorts the production rules in an ESP-tree such that the left symbols on the right hand side of the production rules are in monotonically increasing order, which enables encoding of these production rules efficiently and supporting fast operations for ESP-trees. The encoding scheme is performed from the first and second levels to the top level (_i.e._, root) in an ESP-tree.  
First, the set of production rules at the first and second levels in the ESP-tree is sorted in increasing order of the left symbols on the right hand of the production rules, _i.e._, \(X_{I(i)}\) in the form of \(X_{i}\to X_{I(i)}X_{r(i)}\), which results in a sorted sequence of these production rules. The variables in the left hand side in the sorted production rules are renamed in the sorted order, generating a set of new production rules that is assigned to the corresponding nodes in the ESP-tree. The same scheme is applied to the next level of the ESP-tree, which iterates until it reaches the root node.  
Figure 3 shows an example of the encoding scheme for the ESP-tree built from an input string \(S=babababaaba\). At the first and second levels in the ESP-tree, the set of production rules, \(\{X_{1}\to ab,X_{2}\to bX_{1},X_{3}\to aa,X_{4}\to ba\}\), is sorted in the lexicographic order of the left symbols on right hand sides of production rules, which results in the sequence of production rules, \((X_{1}\to ab,X_{3}\to aa,X_{2}\to bX_{1},X_{4}\to ba)\). The variables on the right hand side of the production rules are renamed in the sorted order, resulting in the new sequence \((X_{1}\to ab,X_{2}\to aa,X_{3}\to bX_{1},X_{4}\to ba)\), whose production rules are assigned to the corresponding nodes in the ESP-tree. This scheme is repeated until it reaches level 4.  
Figure 2: Illustration of edit sensitive parsing (ESP)-tree and characteristic vector.  
Using the above encoding scheme, we obtain a monotonically increasing sequence of left symbols on the right hand side of the production rules, _i.e._, \(X_{l(i)}\) in the form of \(X_{i}\to X_{l(i)}X_{r(i)}\). Let \(A_{l}\) be the increasing sequence; \(A_{l}\) can be efficiently encoded into a bit string by using the gap-encoding and the unary coding. For example, the gap-encoding represents the sequence \((1,1,3,5,8)\) by \((1,0,2,2,3)\), and it is further transformed to the bit string \(0^{1}0^{0}10^{2}10^{2}10^{3}1=01100100010\) by unary coding. Generally, for a sequence \((x_{1},x_{2},\ldots,x_{n})\), its unary code \(U\) represents \(x_{i}\) by \(rank_{0}(U,select_{1}(U,i))\). Because the number of 0s and the number of 1s is \(n+\sigma\) and \(n\), respectively, the size of \(U\) is \(2n+\sigma\) bits. The bit string is indexed by the rank/select dictionary.  
Let \(A_{r}\) be the sequence consisting of the right symbols on the right hand side of the production rules, _i.e._, \(X_{r}(i)\) in the form of \(X_{i}\to X_{l(i)}X_{r(i)}\). \(A_{r}\) is represented using \((n+\sigma)\lg(n+\sigma)\) bits. \(A_{r}\) is indexed by GMR [21].  
The space for storing \(A_{l}\) and \(A_{r}\) is \((n+\sigma)\lg(n+\sigma)+2n+\sigma+o((n+\sigma)\lg(n+\sigma))\) bits in total. \(A_{l}\) and \(A_{r}\) enable us to simulate fast queries on encoded ESP-trees, which is presented in the next subsection.