## 4 Choice of Occurrences  
### Global Optimization of Occurrences Replacement  
Once an IRR algorithm has chosen a repeated word \(\omega\), it replaces all non-overlapping occurrences of that word in the current grammar by a new non-terminal \(N\) and then adds \(N\rightarrow\omega\) to the set of production rules. In this section, we propose to perform a global optimization of the replacement of occurrences, considering not only the last non-terminal but also all the previously introduced non-terminals. The idea is to allow occurrences of words to be kept (instead of being replaced by non-terminals) if replacing other occurrences of words overlapping them results in a better compression. We propose to separate the choice of which terminal strings will be final constituents of the final grammar from the choice of which of the occurrences of these constituents will be replaced by non-terminals. First, let us assume that a set of constituents \(\{s\}\cup Q\) is given and we want to find a smallest grammar whose constituent set is \(\{s\}\cup Q\). If we denote this set by \(\{s=\omega_{0},\omega_{1},\ldots,\omega_{m}\}\), we need to be able to generate these constituents and for each constituent \(\omega_{i}\) the grammar must thus have a non-terminal \(N_{i}\) such that \(\omega_{i}=cons(N_{i})\). In the smallest grammar problem, no unnecessary rule should be introduced since the grammar has to generate only one sequence. More precisely such a grammar must have exactly \(m+1\) non-terminals and associate production rules. For this, we define a new problem, called _Minimal Grammar Parsing_ (MGP) Problem. An instance of this problem is a set of strings \(\{s\}\cup Q\), such that all strings of \(Q\) are substrings of \(s\). A Minimal Grammar Parsing of \(\{s\}\cup Q\) is a context-free grammar \(G=\langle\Sigma,\mathcal{N},\mathcal{P},S\rangle\) such that:  
1. all symbols of \(s\) are in \(\Sigma\). 2. \(S\) derives only \(s\). 3. for each string \(\omega_{\ell}\left\{s\right\}\cup Q\) there is a non-terminal \(N_{\ell}\) that derives only \(\omega_{\ell}\) and \(\mathcal{N}=\{N_{0}\ldots N_{m}\}\). 4. for each non-terminal \(N\) there is a string \(s^{\prime}\) of \(\{s\}\cup Q\) such that \(N\) derives \(s^{\prime}\). 5. \(|G|\) is of minimal size for all possible grammars that satisfy conditions 1-4. Note that this is similar to the Smallest Grammar Problem, except that all constituents for the non-terminals of the grammar are also given. The MGP problem is related to the problem of static dictionary parsing [22] with the difference that the dictionary also has to be parsed. This recursive approach is partly what makes grammars interesting to both compression and structure discovery. As an example consider the sequence \(s=ababbabababaabbabaa\) and suppose the constituents are \(\{s,abbaba,bab\}\). This defines the set of non-terminals \(\{N_{0},N_{1},N_{2}\}\), such that \(\text{cons}(N_{0})=s\), \(\text{cons}(N_{1})=abbaba\) and \(\text{cons}(N_{2})=bab\). A minimal parsing is \(N_{0}\to aN_{2}N_{2}N_{1}N_{1}a\), and \(N_{1}\to abN_{2}a,N_{2}\to bab\). This problem can be solved in a classical way in polynomial time by searching for a shortest path in \(|Q|+1\) graphs as follows. Given the set of constituents, \(s=\{\omega_{0},\omega_{1},\ldots,\omega_{m}\}\). 1. Let \(\{N_{0},N_{1},\ldots,N_{m}\}\) be the set of non-terminals. Each \(N_{\ell}\) will be the non-terminal whose constituent is \(\omega_{\ell}\). 2. Define \(m+1\) directed acyclic graphs \(\Gamma_{0}\ldots\Gamma_{m}\), where \(\Gamma_{\ell}=\langle M_{\ell},E_{\ell}\rangle\). If \(|\omega_{\ell}|=k\) then the graph \(\Gamma_{\ell}\) will have \(k+1\) nodes: \(M_{\ell}=\{1\ldots|\omega_{\ell}|+1\}\). The edges \(E_{l}\) are of two types: 1. for every node \(i\) there is an edge to node \(i+1\) labeled with \(\omega_{\ell}[i]\). 2. there will be an edge from node \(i\) to \(j+1\) labeled by \(N_{m}\) if there exists a non-terminal \(N_{m}\) different from \(N_{\ell}\) such that \(\omega_{\ell}[i:j]=\omega_{m}\). 3.