# siEDM: An Efficient String Index and Search Algorithm for Edit Distance with Moves
## 4 Edit Sensitive Parsing (ESP) for Building SLPs  
### ESP Revisit  
We review the edit sensitive parsing algorithm for building SLPs [10]. This algorithm, referred to as ESP-comp, computes an SLP from an input string \(S\). The tasks of ESP-comp are to (i) partition \(S\) into \(s_{1}s_{2}\cdots s_{\ell}\) such that \(2\leq|s_{i}|\leq 3\) for each \(1\leq i\leq\ell\), (ii) if \(|s_{i}|=2\), generate the production rule \(X\to s_{i}\) and replace \(s_{i}\) by \(X\) (this subtree is referred to as a 2-tree), and if \(|s_{i}|=3\), generate the production rule \(Y\to AX\) and \(X\to BC\) for \(s_{i}=ABC\), and replace \(s_{i}\) by \(Y\) (referred to as a 2-2-tree), (iii) iterate this process until \(S\) becomes a symbol. Finally, the ESP-comp builds an SLP representing the string \(S\). We focus on how to determine the partition \(S=s_{1}s_{2}\cdots s_{\ell}\). A string of the form \(a^{\prime}\) with \(a\in\Sigma\cup V\) and \(r\geq 2\) is called a repetition. First, \(S\) is uniquely partitioned into the form \(w_{1}x_{1}w_{2}x_{2}\cdots w_{k}x_{k}w_{k+1}\) by its maximal repetitions, where each \(x_{i}\) is a maximal repetition of a symbol in \(\Sigma\cup V\), and each \(w_{i}\in(\Sigma\cup V)^{*}\) contains no repetition. Then, each \(x_{i}\) is called type1, each \(w_{i}\) of length at least \(2\lg^{*}|S|\) is type2, and any remaining \(w_{i}\) is type3. If \(|w_{i}|=1\), this symbol is attached to \(x_{i-1}\) or \(x_{i}\) with preference \(x_{i-1}\) when both cases are possible. Thus, if \(|S|>2\), each \(x_{i}\) and \(w_{i}\) is longer than or equal to two. One of the substrings is referred to as \(S_{i}\). Next, ESP-comp parses each \(S_{i}\) depending on the type. For type1 and type3 substrings, the algorithm performs the _left aligned parsing_ as follows. If \(|S_{i}|\) is even, the algorithm builds 2-tree from \(S_{i}[2j-1,2j]\) for each \(j\in\{1,2,\ldots,|S_{i}|/2\}\); otherwise, the algorithm builds a 2-tree from \(S_{i}[2j-1,2j]\) for each \(j\in\{1,2,\ldots,\lfloor(|S_{i}|-3)/2\rfloor\}\) and builds a 2-2-tree from the last trigram \(S_{i}[|S_{i}|-2,|S_{i}|]\). For type2 \(S_{i}\), the algorithm further partitions it into short substrings of length two or three by _alphabet reduction_[8]. **Alphabet reduction:** Given a type2 string \(S\), consider \(S[i]\) and \(S[i-1]\) as binary integers. Let \(p\) be the position of the least significant bit, in which \(S[i]\
eq S[i-1]\), and let \(bit(p,S[i])\) be the bit of \(S[i]\) at the \(p\)-th position. Then, \(L[i]=2p+bit(p,S[i])\) is defined for any \(i\geq 2\). Because \(S\) is repetition-free (_i.e._, type2), the label string \(L(S)=L[2]L[3]\cdots L[|S|]\) is also type2. If the number of different symbols in \(S\) is \(n\) (denoted by \([S]\)), then \([L(S)]=O(\lg n)\). For the \(L(S)\), the next label string is iteratively computed until the final \(L^{*}(S)\) satisfying \([L^{*}(S)]\leq\lg^{*}|S|\) is obtained. \(S[i]\) is called the _landmark_ if \(L[i]>\max\{L[i-1],L[i+1]\}\). The alphabet reduction transforms \(S\) into \(L^{*}(S)\) such that any substring of \(L^{*}(S)\) of length at least \(2\lg^{*}|S|\) contains at least one landmark because \(L^{*}(S)\) is also type2. Using this characteristic, the algorithm ESP-comp determines the bigrams \(S[i,i+1]\) to be replaced for any landmark \(S[i]\), where any two landmarks are not adjacent, and then the replacement is deterministic. After replacing all landmarks, any remaining maximal substring \(s\) is replaced by the left aligned parsing, where if \(|s|=1\), it is attached to its left or right block. We give an example of the edit sensitive parsing of an input string in Figure 1-(i) and (ii). The input string \(S\) is divided into three maximal substrings depending on the types. The label string \(L\) is computed for the type2 string. Originally, \(L\) is iteratively computed until \([L]\leq\lg^{*}|S|\). This case shows that a single iteration satisfies this condition. After the alphabet reduction, three landmarks \(S[i]\) are found, and then each \(S[i,i+1]\) is parsed.