## 6 Non-Uniqueness of Smallest Grammar and Structure Discovery
### An Empirical Analysis
#### 6.2.4 Conserved Parsing among Minimal Grammar Parsings  
In the previous section we analyzed how different the grammars are considering different sizes of brackets. Here, we consider the differences between the grammars on single positions. The objective of this experiment is to measure the amount of different ways in which a single position of the original  
\begin{table}
\begin{tabular}{|l|c c c|} \hline
**Sequence** & **humdyst.chr.seq** & **asyoulik.txt** & **alice29.txt** \\ \hline \(UF_{1}\) mean & 66.02\% & 81.48\% & 77.81\% \\ \(UF_{1}\) standard deviation & 1.19\% & 1.32\% & 1.52\% \\ Smallest \(UF_{1}\) & 62.26\% & 77.94\% & 73.44\% \\ Largest \(UF_{1}\) & 70.64\% & 85.64\% & 83.44\% \\ \hline \end{tabular}
\end{table}
Table 4: Different figures for a sample of 1000 grammars uniformly taken from \(\mathcal{G}_{Q}\).  
\begin{table}
\begin{tabular}{|l|c c|c c|c c|} \hline
**k** & **asyoulik.txt.ij** & **alice29.txt.ij** & **humdyst.chr.seq.ij** \\ \hline  & \(UF_{1,k}\) & Brackets & \(UF_{1,k}\) & Brackets & \(UF_{1,k}\) & Brackets \\
1 & 81.50\% & 100.00\% & 77.97\% & 100.00\% & 67.32\% & 100.00\% \\
2 & 88.26\% & 50.86\% & 83.70\% & 53.14\% & 71.11\% & 45.99\% \\
3 & 92.49\% & 29.57\% & 87.94\% & 32.42\% & 75.93\% & 37.54\% \\
4 & 95.21\% & 19.85\% & 89.60\% & 22.01\% & 82.17\% & 15.69\% \\
5 & 96.35\% & 11.78\% & 88.88\% & 14.36\% & 88.51\% & 3.96\% \\
6 & 97.18\% & 8.23\% & 89.45\% & 9.66\% & 95.46\% & 1.24\% \\
7 & 97.84\% & 5.72\% & 91.50\% & 6.44\% & 98.38\% & 0.44\% \\
8 & 97.82\% & 3.83\% & 92.78\% & 4.30\% & 99.87\% & 0.19\% \\
9 & 98.12\% & 2.76\% & 92.37\% & 2.95\% & 100.00\% & 0.06\% \\
10 & 98.35\% & 1.88\% & 91.87\% & 2.10\% & 100.00\% & 0.04\% \\ \hline \end{tabular}
\end{table}
Table 5: \(UF_{1,k}\) for different values of \(k\) each from a sample of 100 grammars uniformly taken from \(\mathcal{G}_{Q}\).  
sequence \(s\) can be parsed by a minimal grammar. For this we will consider the partial parse tree where only the first level is retained. Doing this for each minimal grammar, we compute for each position the number of different subtrees it belongs to. This is equivalent to the number of edges that cover that position on the _MGP-graph_ of \(s\). If the number for one position is one for instance, this means that in all minimal grammars the same occurrence of the same non-terminal expands on this position.  
On alice29.txt, \(89\%\) of the positions are parsed exactly the same way. A histogram for all values of different parses can be seen in Figure 3. Note that the y-axis is in logarithmic scale and that the number of positions reduce drastically if the number of parses is increased: only \(10\%\) of positions are parsed in two different ways, \(1\%\) in three and all others in less than \(0.2\%\).  
There were two regions that presented peaks on the number of different symbols. Both correspond to parts in the text with long runs of the same character (white spaces): at the beginning, and in the middle during a poetry.  
While this experiment is only restricted to the first level of the parse tree, it seems to indicate that the huge number of different minimal parses is due to a small number of positions where different parses have the same size. Most of the positions however are always parsed the same way.