Power pruning



next up previous
Next: Dependency and categorial Up: Speeding it up Previous: The fast-match data

Power pruning

Power pruning is a refinement of pruning that takes advantage of the ordering requirement of the connectors of a disjunct, the exclusion rule, and other properties of any valid linkage. It also interacts with the fast-match data structure in a beautiful way. Unfortunately, these details are beyond the scope of this paper gif. Table gif shows outcome of pruning and power pruning on a typical sentence.

Each of the refinements described in this section significantly reduced the time required to do search for a linkage. The operations of pruning, power pruning, and searching for a linkage all take roughly the same amount of time.




Thu Oct 12 13:01:13 EDT 1995