Send us a comment.
Every active edge represents a hypothesis that needs to be explored. If it succeeds, even partially, then it is likely to generate further hypotheses (active and inactive edges), due to the operation of the fundamental rule and the rule invocation strategy that we adopt. With a serial machine, we have to make choices about the order in which to pursue these hypotheses. The basis on which we make these choices is our search strategy. In chart parsing, it is convenient to have a data structure, an agenda, for storing hypotheses to be explored or edges to be added to the chart, so that we can avoid investigating identical hypotheses and make a reasoned decision about what to investigate when.
One possibility is to regard the agenda as a stack: as new edges are produced, we push them on to the stack. Then, when we have to select an edge to work on, we take the one on the top of the stack.
This will produce behaviour rather like depth-first search, as the following example indicates.
Imagine, for instance, that we have the following stack of edges to add to the chart, where e1 is at the top):
e1: e2: e3
Popping e1 off the stack, we might find that the addition of this edge leads to three more edges - e11, e12 and e13 - being proposed. If we push these on to the stack, the result is:
e11: e12: e13: e2: e3
Popping e11 off the stack, we might find that this results in three new edges - e111, e112 and e113. So, the next state of the stack is:
e111: e112: e113: e12: e13: e2: e3
Now, if the multiple edges produced at each stage represent alternatives, such as alternative categories for a word or alternative ways that a particular phrase type might be realized, then what we are doing at each point is taking one of the possibilities and pursuing it as far as possible before trying an alternative. For instance, because new edges are pushed on to the top of the stack, the edge e2 will never be considered until all the edges e111, e112, e113, e12 and e13, and all edges arising from them, have been added. Similarly, e3 will never be considered until all these edges, and also all edges arising from e2, have been added.
Another strategy is to regard the agenda as a queue, which is like a stack except that new items are added to the opposite end from which items are removed. In such a scheme, as new edges are produced, we push them on the end of the queue. When we have to select an edge to work on, we take the one at the front of the queue, whatever it is. This will produce something more like breadth-first search. For instance, in the foregoing example, the sequence would be:
e1: e2: e3 select e1 e2: e3: e11: e12: e13 select e2 e3: e11: e12: e13: e21: e22: e23 select e3 e11: e12: e13: e21: e22: e23: e31: e32: e33 select e11 ...
and so on, where e21, e22 and e23 are the new edges arising from the addition of e2, and similarly for e3. This time, if the different edges at each point represent alternatives, the system spends only a small amount of time on each possibility before switching its attention to the next.
Lots of other strategies are imaginable, of course, by manipulating the agenda in various ways. For example, we could position active edges according to how near completion they are - for example, empty edges to the end, those with only one category to find to the front, or conversely; or according to their categories - noun phrases to the front, other categories to the end, or whatever; or according to information gleaned from another component - the semantics, say. We can favour edges that result from particular grammar rules over edges that result from others, attempting to exploit statistical results about language use or human parsing preferences. If we want our parse to produce all possible parses, then the chart will eventually go through exactly the same work and produce exactly the same results whatever search strategy we impose. So, if we do not care what order the parses are produced in, then the choice of search strategy is essentially arbitrary. But, if we only want one parse, or we only want parses that meet certain additional constraints which may not be inherent in the rules alone), or if we have some other process running in parallel like semantic interpretation of constituents, then the choice of search strategy becomes a matter of concern and has efficiency implications (see later).
Send us a comment.