Evaluation using the constrained MERGE

Figure 7.4: Parsing times for EFD, EFD with positional indexing, and EFD with path indexing applied to the constrained MERGE grammar. Sentences were numbered according to the ascending order of parsing times for path indexing.

For the constrained version (Figure 7.4), positional indexing outperformed the non-indexed parser with an average of 5% (the best improvement being 60%). Path indexing brought no improvements relative to positional indexing (showing the same average improvements as positional indexing, while the best improvement being slightly better, 62%). Similarly with the unconstrained MERGE, both indexing methods exhibited a rather uniform improvement as the parsing times increased.

As can be seen in the examples^7.2 presented in Table 7.2, although the indexing methods avoid a significant number of failed unifications, the total number of unifications is roughly 10 times smaller than for the unconstrained version. This causes not only faster parsing times, but the indexed parser to pay a significantly higher price for managing the index.

Table 7.2: The number of successful and failed unifications for the non-indexed and indexed parsers over the constrained MERGE grammar, for selected sentences where significant improvements (at least 3%) in parsing times were recorded both between positional indexing and EFD and between path indexing and positional indexing. The sentence numbers are the same as those used in Figure 7.4.

Sentence	Successful	Failed unifications
number	unifications	EFD	EFD with	EFD with
			positional index	path index
414	18	169	143	103
681	28	127	120	103
1056	63	561	479	351