## 4 Choice of Occurrences
### Widening the Explored Space
#### 4.3.2 The Algorithm  
In contrast with classical methods, we can now define algorithms discarding also constituents. To perform a wider exploration of the search space, we propose a new algorithm performing a succession of greedy search in ascending and descending directions in the lattice until a local minimum is found. This algorithm explores the lattice in a zigzag path. Therefore we denote it ZZ. It explores the lattice by an alternation of two different phases: _bottom-up_ and _top-down_. The bottom-up can be started at any node, it moves upwards in the lattice and at each step it looks among its ascendants for the one with the lowest score. In order to determine which is the one with the lowest score, it inspects them all. It stops when no ascendant has a better score than the current one. As in bottom-up, top-down starts at any given node but it moves downwards looking for the node with the smallest score among its descendants. Going up or going down from the current node is equivalent to adding or removing a substring to or from the set of substrings in the current node respectively. ZZ starts at the bottom node, that is, the node that corresponds to the grammar \(S\to s\) and it finishes when no improvements are made in the score between two bottom-up-top-down iterations. A pseudo-code is given in Algorithm 3. ZZ(\(s\))
```
1:\(s\) is a sequence
2:\(\mathcal{L}\leftarrow\langle\mathcal{R}(s),\subseteq\rangle\)
3:\(\eta\leftarrow\emptyset\)
4:repeat
5:while\(\exists\eta^{\prime}\in\mathcal{L}\ :\ \big{(}\eta^{\prime}\gets argmin_{\eta^{ \prime}\in\text{\sc ancestors}(\eta)}\text{score}(\eta^{\prime}))\wedge\text{ score}(\eta^{\prime})\leq\text{score}(\eta)\big{)}\)do
6:\(\eta\leftarrow\eta^{\prime}\)
7:endwhile
8:\(\eta\leftarrow\eta^{\prime}\)
9:endwhile
10:until\(\text{score}(\eta)\) doesn't decrease
11:return\(G\left(\text{mgp}(\eta)\right)\)
```  
**Algorithm 3** Zigzag algorithm. For example, suppose that there are \(5\) substrings that occur more than once in \(s\) and that they all have length greater than two. Let these strings be numbered from \(0\) to \(4\). We start the ZZ algorithm at the bottom node. It inspects nodes {\(0\)}, {1}, {2}, {3}, and {4}. Suppose that {1} produces the best grammar, then ZZ moves to that node and starts over exploring the nodes above it. Figure 2 shows a part of the lattice being explored. Dotted arrows point to nodes that are explored while full arrows point to nodes having the lowest score. Suppose that the algorithm then continues up until it reaches node \(\{1,2,3\}\) where no ancestor has lower score. Then ZZ starts the top-down phase, going down to node \(\{2,3\}\) where no descendant has lower score. At this point a bottom-up-top-down iteration is done and the algorithm starts over again. It goes up, suppose that it reaches node \(\{2,3,4\}\) where it stops. Bold circled nodes correspond to nodes were the algorithm switches phases, grey nodes correspond to nodes with the best score among its siblings. Computational ComplexityIn the previous section we showed that the computational complexity of computing the score function for each node is \(\mathcal{O}(n\times m^{2})\), where \(n\) is the length of the target string and \(m\) is the number of substrings in the node. Every time ZZ looks for a substring to add or remove it has to inspect all possible candidates with the aim of finding the one that minimizes the score. Depending on the number of substrings that are already in the node, there might be at most \(\mathcal{O}(n^{2})\) candidate strings. As a consequence, each step upwards or downwards is made in \(\mathcal{O}(n^{2}\times n\times m^{2})\). Next, we need to give an upper bound for the length of the path that is potentially traversed by the algorithm. In order to define it, we first note two important properties: the score of the bottom node is equal to \(n\) and the score of any node containing more than \(n/2\) substrings is at least \(n\).