The fast-match data structure



next up previous
Next: Power pruning Up: Speeding it up Previous: Pruning

The fast-match data structure

The inner loop in the algorithm described in section 4 searches for a word and a disjunct of this word whose first left connector matches , or whose first right connector matches . If there were a fast way to find all such disjuncts, significant savings might be achieved. The fast-match data structure, which is based on hashing, does precisely this. The speed-up afforded by this technique is roughly the number of different connector types, which is roughly 30 in our current dictionary.




Thu Oct 12 13:01:13 EDT 1995