link-grammar-5.8.0/link-grammar/parse/prune.c
/**
 * Delete disjuncts whose links would cross those implied by the mlink table.
 * Since links are not allowed to cross, such disjuncts would create null
 * links. So this optimization can only be done when parsing a sentence
 * with null_count==0 (in which null links are not allowed).
 * Possible FIXME:
 * Part of such kind of deletions are also be done in
 * possible_connection(), so there is some overlapping. However,
 * eliminating this overlap (if possible) would not cause a significant
 * speedup because these functions are lightweight.
 */
Delete disjuncts whose links would cross those implied by the mlink table.
Since links are not allowed to cross, such disjuncts would create null
links. So this optimization can only be done when parsing a sentence
with null_count==0 (in which null links are not allowed).
Possible FIXME:
Part of such kind of deletions are also be done in
possible_connection(), so there is some overlapping. However,
eliminating this overlap (if possible) would not cause a significant
speedup because these functions are lightweight.
Delete disjuncts whose links would cross those implied by the mlink table . Since links are not allowed to cross such disjuncts would create null links . So this optimization can only be done when parsing a sentence with null_count == 0 ( in which null links are not allowed ) . Possible FIXME : Part of such kind of deletions are also be done in possible_connection () so there is some overlapping . However eliminating this overlap ( if possible ) would not cause a significant speedup because these functions are lightweight .
static unsigned int cross_mlink_prune(Sentence sent, mlink_table *ml)
{
	int N_deleted[2] = {0}; 
	static Connector bad_connector = { .nearest_word = BAD_WORD };
	for (unsigned int w = 0; w < sent->length; w++)
	{
		if (sent->word[w].optional) continue;
		if (sent->word[w].d == NULL) continue;
		WordIdx_m nw0 = ml[w].nw[0];
		WordIdx_m nw1 = ml[w].nw[1];
		WordIdx_m fw0 = ml[w].fw[0];
		WordIdx_m fw1 = ml[w].fw[1];
		if ((w > 0) && (nw1 != w))
		{
			for (Disjunct *d = sent->word[nw1].d; d != NULL; d = d->next)
			{
				Connector *shallow_c = d->left;
				if (shallow_c == NULL)
				{
					if ((nw1 == fw1) || ((d->right->nearest_word > fw1) && PR(1)))
					{
						d->left = &bad_connector;
						N_deleted[0]++;
					}
					continue;
				}
				if (shallow_c->nearest_word == BAD_WORD)
				{
					N_deleted[1]++;
					continue;
				}
				Connector *c = connector_deepest(shallow_c);
				if (c->nearest_word < w)
				{
					shallow_c->nearest_word = BAD_WORD;
					N_deleted[0]++;
					continue;
				}
				if (!c->multi)
					c->farthest_word = MAX(w, c->farthest_word);
			}
		}
		if ((w < sent->length-1) && (nw0 != w))
		{
			for (Disjunct *d = sent->word[nw0].d; d != NULL; d = d->next)
			{
				Connector *shallow_c = d->right;
				if (shallow_c == NULL)
				{
					if ((nw0 == fw0) || ((d->left->nearest_word < fw0) && PR(0)))
					{
						d->right = &bad_connector;
						N_deleted[0]++;
						PR(0);
					}
					continue;
				}
				if (shallow_c->nearest_word == BAD_WORD)
				{
					N_deleted[1]++;
					continue;
				}
				Connector *c = connector_deepest(shallow_c);
				if (c->nearest_word > w)
				{
					shallow_c->nearest_word = BAD_WORD;
					N_deleted[0]++;
					continue;
				}
				if (!c->multi)
					c->farthest_word = MIN(w, c->farthest_word);
			}
		}
		for (unsigned int rw = w+1; rw < nw1; rw++)
		{
			for (Disjunct *d = sent->word[rw].d; d != NULL; d = d->next)
			{
				Connector *shallow_c = d->left;
				if (shallow_c == NULL) continue;
				if (shallow_c->nearest_word == BAD_WORD)
				{
					N_deleted[1]++;
					continue;
				}
				if (shallow_c->nearest_word < w)
				{
					shallow_c->nearest_word = BAD_WORD;
					N_deleted[0]++;
					continue;
				}
				shallow_c->farthest_word = MAX(w, shallow_c->farthest_word);
				if (d->right != NULL)
					d->right->farthest_word = MIN(fw1, d->right->farthest_word);
			}
		}
		for (unsigned int lw = nw0+1; lw < w; lw++)
		{
			for (Disjunct *d = sent->word[lw].d; d != NULL; d = d->next)
			{
				Connector *shallow_c = d->right;
				if (shallow_c == NULL) continue;
				if (shallow_c->nearest_word == BAD_WORD)
				{
					N_deleted[1]++;
					continue;
				}
				if (shallow_c->nearest_word > w)
				{
					shallow_c->nearest_word = BAD_WORD;
					N_deleted[0]++;
					continue;
				}
				shallow_c->farthest_word = MIN(w, shallow_c->farthest_word);
				if (d->left != NULL)
					d->left->farthest_word = MAX(fw0, d->left->farthest_word);
			}
		}
	}
	lgdebug(+D_PRUNE, "Debug: [nw] detected %d (%d+%d)\n",
	        N_deleted[0] + N_deleted[1], N_deleted[0], N_deleted[1]);
	return N_deleted[0] + N_deleted[1];
}
static unsigned int cross_mlink_prune ( Sentence sent , mlink_table * ml ) { int N_deleted [ 2 ] = { 0 } ; static Connector bad_connector = { . nearest_word = BAD_WORD } ; for ( unsigned int w = 0 ; w < sent -> length ; w ++ ) { if ( sent -> word [ w ] . optional ) continue ; if ( sent -> word [ w ] . d == NULL ) continue ; WordIdx_m nw0 = ml [ w ] . nw [ 0 ] ; WordIdx_m nw1 = ml [ w ] . nw [ 1 ] ; WordIdx_m fw0 = ml [ w ] . fw [ 0 ] ; WordIdx_m fw1 = ml [ w ] . fw [ 1 ] ; if ( ( w > 0 ) && ( nw1 != w ) ) { for ( Disjunct * d = sent -> word [ nw1 ] . d ; d != NULL ; d = d -> next ) { Connector * shallow_c = d -> left ; if ( shallow_c == NULL ) { if ( ( nw1 == fw1 ) || ( ( d -> right -> nearest_word > fw1 ) && PR ( 1 ) ) ) { d -> left = & bad_connector ; N_deleted [ 0 ] ++ ; } continue ; } if ( shallow_c -> nearest_word == BAD_WORD ) { N_deleted [ 1 ] ++ ; continue ; } Connector * c = connector_deepest ( shallow_c ) ; if ( c -> nearest_word < w ) { shallow_c -> nearest_word = BAD_WORD ; N_deleted [ 0 ] ++ ; continue ; } if ( ! c -> multi ) c -> farthest_word = MAX ( w , c -> farthest_word ) ; } } if ( ( w < sent -> length - 1 ) && ( nw0 != w ) ) { for ( Disjunct * d = sent -> word [ nw0 ] . d ; d != NULL ; d = d -> next ) { Connector * shallow_c = d -> right ; if ( shallow_c == NULL ) { if ( ( nw0 == fw0 ) || ( ( d -> left -> nearest_word < fw0 ) && PR ( 0 ) ) ) { d -> right = & bad_connector ; N_deleted [ 0 ] ++ ; PR ( 0 ) ; } continue ; } if ( shallow_c -> nearest_word == BAD_WORD ) { N_deleted [ 1 ] ++ ; continue ; } Connector * c = connector_deepest ( shallow_c ) ; if ( c -> nearest_word > w ) { shallow_c -> nearest_word = BAD_WORD ; N_deleted [ 0 ] ++ ; continue ; } if ( ! c -> multi ) c -> farthest_word = MIN ( w , c -> farthest_word ) ; } } for ( unsigned int rw = w + 1 ; rw < nw1 ; rw ++ ) { for ( Disjunct * d = sent -> word [ rw ] . d ; d != NULL ; d = d -> next ) { Connector * shallow_c = d -> left ; if ( shallow_c == NULL ) continue ; if ( shallow_c -> nearest_word == BAD_WORD ) { N_deleted [ 1 ] ++ ; continue ; } if ( shallow_c -> nearest_word < w ) { shallow_c -> nearest_word = BAD_WORD ; N_deleted [ 0 ] ++ ; continue ; } shallow_c -> farthest_word = MAX ( w , shallow_c -> farthest_word ) ; if ( d -> right != NULL ) d -> right -> farthest_word = MIN ( fw1 , d -> right -> farthest_word ) ; } } for ( unsigned int lw = nw0 + 1 ; lw < w ; lw ++ ) { for ( Disjunct * d = sent -> word [ lw ] . d ; d != NULL ; d = d -> next ) { Connector * shallow_c = d -> right ; if ( shallow_c == NULL ) continue ; if ( shallow_c -> nearest_word == BAD_WORD ) { N_deleted [ 1 ] ++ ; continue ; } if ( shallow_c -> nearest_word > w ) { shallow_c -> nearest_word = BAD_WORD ; N_deleted [ 0 ] ++ ; continue ; } shallow_c -> farthest_word = MIN ( w , shallow_c -> farthest_word ) ; if ( d -> left != NULL ) d -> left -> farthest_word = MAX ( fw0 , d -> left -> farthest_word ) ; } } } lgdebug ( + D_PRUNE , " \n " , N_deleted [ 0 ] + N_deleted [ 1 ] , N_deleted [ 0 ] , N_deleted [ 1 ] ) ; return N_deleted [ 0 ] + N_deleted [ 1 ] ; }
Delete disjuncts whose links would cross those implied by the mlink table.
Delete disjuncts whose links would cross those implied by the mlink table .
/* Counts deletions: 0: initial 1: by mem. sharing */ /* If (nw1 == fw1) then word w must have a link to word
						 * nw1, and disjuncts of word nw1 which don't have an
						 * LHS jet can be deleted.
						 * Else, since word w cannot connect to this disjunct
						 * then if it is used then word w must connect to a word
						 * after it in the range [nw1+1, fw1]. As a result,
						 * disjuncts of nw1 with an RHS shallow connector having
						 * nearest_word > fw1 can be deleted.
						 *
						 * Naturally there are no connectors to assign BAD_WORD
						 * to. So use a dummy one. The same is done for the
						 * other direction. */ /* Deepest connector constraint l->r. */ /* See the comments in the handling of the other direction. */ /* Deepest connector constraint r->l. */ /* Remove disjuncts that are blocked by mandatory l->r links. */ /* Remove disjuncts that are blocked by mandatory r->l links. */