General Indexing Strategy

The purpose of indexing is to reduce the time spent on failed attempts when searching for an edge in the chart. Each edge (edge's category or description) in the chart has an associated index key which uniquely identifies sets of categories that can potentially match that edge's category. When completing a rule, the chart parsing algorithm looks up edges matching a specific daughter in the chart. Instead of visiting all edges in the chart, the daughter's index key selects a restricted number of edges for traversal, thus reducing the number of unification attempts.

The passive edges added to the chart represent specializations of rules' mothers. Each time a rule is completed, its mother $\mathcal{M}$ is added to the chart according to $\mathcal{M}$'s indexing scheme, i.e., the set of index keys of daughters that are possible candidates for a successful unification with $\mathcal{M}$. The indexing scheme needs to be re-built only when the grammar rules or the signature change.

From an implementation point of view, the index is represented as a hash, where the hash function applied to a daughter yields the daughter's index key. Each entry in the chart has a hash associated with it. When passive edges are added to the chart, they are inserted into one or more hash entries. For an edge representing $\mathcal{M}$, the list of hash entries where it will be added is given by $\mathcal{M}$'s indexing scheme.